std :: queue <T, list<T>> :: size() es lento en O (n)?

Question

Experimenté un comportamiento de rendimiento inesperado de mi código que utiliza una cola. Me di cuenta de que el rendimiento se degradaba cuando había más elementos en la cola. Resultó que el uso del método size() fue el motivo. Aquí hay un código que muestra el problema:

#include <queue> 
#include <list> 
#include <iostream> 

#include "Stopwatch.h" 

using namespace std; 

struct BigStruct 
{ 
    int x[100]; 
}; 
int main() 
{ 
    CStopwatch queueTestSw; 

    typedef BigStruct QueueElementType; 
    typedef std::queue<QueueElementType, std::list<QueueElementType> > QueueType; 
    //typedef std::queue<QueueElementType > QueueType; //no surprise, this queue is fast and constant 
    QueueType m_queue; 

    for (int i=0;i<22000;i++) 
     m_queue.push(QueueElementType()); 
    CStopwatch sw; 
    sw.Start(); 
    int dummy; 
    while (!m_queue.empty()) 
    { 
     //remove 1000 elements: 
     for (int i=0;i<1000;i++) 
     { 
      m_queue.pop(); 
     } 
     //call size() 1000 times and see how long it takes 
     sw = CStopwatch(); 
     sw.Start(); 
     for (int i=0;i<1000;i++) 
     { 
      if (m_queue.size() == 123456) 
      { 
       dummy++; 
      } 
     } 
     std::cout << m_queue.size() << " items left. time: " << sw.GetElapsedTimeInSeconds() << std::endl; 
    } 
    return dummy; 


} 

Dónde CStopwatch es una clase que utiliza clock_gettime(CLOCK_REALTIME, ..). El resultado es:

21000 items left. time: 1.08725 
20000 items left. time: 0.968897 
19000 items left. time: 0.818259 
18000 items left. time: 0.71495 
17000 items left. time: 0.583725 
16000 items left. time: 0.497451 
15000 items left. time: 0.422712 
14000 items left. time: 0.352949 
13000 items left. time: 0.30133 
12000 items left. time: 0.227588 
11000 items left. time: 0.178617 
10000 items left. time: 0.124512 
9000 items left. time: 0.0893425 
8000 items left. time: 0.0639174 
7000 items left. time: 0.0476441 
6000 items left. time: 0.033177 
5000 items left. time: 0.0276136 
4000 items left. time: 0.022112 
3000 items left. time: 0.0163013 
2000 items left. time: 0.0101932 
1000 items left. time: 0.00506138 

Esto parece contradecir http://www.cplusplus.com/reference/stl/queue/size/:

Complejidad: Constante.

El problema es peor si la estructura es más grande. Estoy usando GCC 4.3.2.

¿Puede explicar esto? ¿Hay alguna manera de resolver esto usando la lista?

(. Tenga en cuenta que necesito utilizar la lista como contenedor subyacente de la cola porque necesito la complejidad de inserción constante de tiempo)

Answer 1

queue es un contenedor adaptador, por lo que tiene que entender que las descripciones pueden complejidad se refieren únicamente a la obra el adaptador hace en sí (que es de hecho constante, es decir, de paso a través de la llamada al contenedor subyacente).

Por ejemplo, see this reference: size() llama a la función size() del contenedor subyacente. Para un list, esto tiene complejidad O (n) en C++ 98/03, y O (1) en C++ 11.

Answer 2

Eres su queue utilizar un contenedor list, en lugar del predeterminado deque:

typedef std::queue<QueueElementType, std::list<QueueElementType> > QueueType; 

Usted no debe sorprenderse de que el tamaño toma O (n), ya que es una aplicación perfectamente válida del contenedor list pre C++ 11. La versión anterior del estándar no garantizaba la complejidad de la función de miembro size para las listas.

Si cambia el código para:

typedef std::queue<QueueElementType, std::deque<QueueElementType> > QueueType; 

Usted verá el comportamiento que desea (O (1) Tamaño de la complejidad).

Answer 3

Agregando a la respuesta de Michael: Está utilizando std::list como su contenedor de cola, por lo que el método size() depende de la implementación de tamaño estándar de su lista. Si busca en el mismo sitio web, encuentra http://www.cplusplus.com/reference/stl/list/size/ y la complejidad es constante en algunas implementaciones y lineal en otras. Si necesita una inserción y tamaño constantes, entonces necesita una estructura de datos diferente o una mejor implementación de std::list.