std :: queue <T, list<T>> :: size() jest wolny w O (n)?

Question

Doświadczyłem nieoczekiwanego zachowania wydajności mojego kodu, który używa kolejki. Zdałem sobie sprawę, że wydajność uległa pogorszeniu, gdy w kolejce było więcej elementów. Okazało się, że powodem było użycie metody size(). Oto kod, który pokazuje problem:

#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; 


} 

Gdzie CStopwatch to klasa, która wykorzystuje clock_gettime(CLOCK_REALTIME, ..). Wynikiem jest:

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 

Wydaje się to sprzeczne http://www.cplusplus.com/reference/stl/queue/size/:

Złożoność: Stała.

Problem jest gorszy, jeśli struktura jest większa. Używam GCC 4.3.2.

Czy możesz to wyjaśnić? Czy istnieje sposób rozwiązania tego problemu za pomocą listy?

(. Proszę pamiętać, że muszę korzystać z listy jako bazowego pojemnika kolejki, bo wymaga stałej wstawiania czasu złożoności)

Answer 1

queue jest kontenerem adapter, więc trzeba zrozumieć, że opisy złożoność może odnosić się tylko do pracy adapter robi się (co jest rzeczywiście stały, czyli po prostu przechodząc przez wezwanie do bazowego pojemnika). Na przykład see this reference: size() dzwoni do podstawowej funkcji kontenera: W przypadku list ma to złożoność O (n) w C++ 98/03 i O (1) w C++ 11.

Answer 2

Jesteś Twój queue użyć list pojemnik, zamiast domyślnego deque:

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

nie należy się dziwić, że wielkość zajmuje o (n), ponieważ jest to całkowicie poprawny realizacja pojemnika list pre C++ 11. Poprzednia wersja standardu nie gwarantowała złożoności funkcji składowej size dla list.

W przypadku zmiany kodu do:

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

widać zachowanie chcesz (O (1) złożoność rozmiar).

Answer 3

Dodawanie do odpowiedzi Michaela: używasz std::list jako kontenera kolejki, więc metoda size() zależy od twojej implementacji rozmiaru std :: list. Jeśli spojrzysz na tę samą stronę, znajdziesz http://www.cplusplus.com/reference/stl/list/size/, a złożoność jest stała w niektórych implementacjach i liniowa na innych. Jeśli potrzebujesz stałej wstawiania i rozmiaru, potrzebujesz innej struktury danych lub lepszej implementacji std::list.