std :: queue <T, list<T> :: size()가 O (n)에서 느립니다?

Question

큐를 사용하는 코드의 예상치 못한 성능 문제가 발생했습니다. 큐에 더 많은 요소가있을 때 성능이 저하된다는 것을 알게되었습니다. size() 방법의 사용이 이유였습니다. 여기에 문제를 보여 일부 코드는 다음과 같습니다 CStopwatch는 clock_gettime(CLOCK_REALTIME, ..)를 사용하는 클래스가

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


} 

. 결과는 다음과 같습니다

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 

이 http://www.cplusplus.com/reference/stl/queue/size/ 모순 보인다

복잡성 : 정수입니다.

구조체가 더 커지면 문제가 더 심해집니다. 나는 GCC 4.3.2를 사용하고있다.

설명 할 수 있습니까? 목록을 사용하여이를 해결할 수있는 방법이 있습니까?

(. 내가 일정 시간 삽입 복잡성을 필요로하기 때문에 큐의 기본 컨테이너로 목록을 사용할 필요가 있습니다)

Answer 1

queue는 컨테이너 어댑터입니다.

예를 들어 see this reference : size()은 기본 컨테이너의 size() 함수를 호출합니다. list의 경우 C++ 98/03에서는 복잡성 O (n)이고 C++ 11에서는 O (1)입니다.

Answer 2

당신이있어 당신의 queue 대신 deque 기본으로하는 list 컨테이너를 사용합니다 : 즉, list 용기의 완벽 유효 구현 C++ (11)을 사전은 이후

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

당신은 놀라지 않을해야 그 크기는 O (N)를합니다. 이전 버전의 표준은 목록에 대한 구성원 함수 size의 복잡성을 보장하지 않았습니다. 당신은 당신이 원하는 행동 (O (1) 크기의 복잡성을) 볼 수

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

:

당신이 코드를 변경하는 경우

. 당신은 복잡한 설명은 (즉, 단지 기본 컨테이너를 통해 전화를 통과, 참 상수이다) 어댑터가 자신을 수행하는 작업 만 참조 할 수 있음을 이해 할 수 있도록

Answer 3

마이클의 대답에 추가 : std::list을 큐 컨테이너로 사용하므로 size() 메서드는 std :: list 크기 구현에 따라 다릅니다. 같은 웹 사이트를 살펴보면 http://www.cplusplus.com/reference/stl/list/size/이고 복잡성은 일부 구현에서는 일정하고 다른 구현에서는 선형입니다. 상수 삽입 및 크기가 필요한 경우 다른 데이터 구조 또는 더 나은 std::list 구현이 필요합니다.