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を使用しています。

これを説明できますか？リストを使ってこれを解決する方法はありますか？

（Iは一定時間挿入の複雑さを必要とするので、私はキューの根底にあるコンテナとしてリストを使用する必要がありますのでご注意ください。）

Answer 1

queueは、コンテナアダプタあるので、あなたは（つまり、単に基本的なコンテナに至るまでの呼び出しを渡し、実際に一定である）複雑さの記述は唯一のアダプタが自分自身を行う作業を参照してもよいことを理解する必要があります。

たとえば、see this reference：size()は、基になるコンテナのsize()関数を呼び出します。 listの場合、これはC++ 98/03では複雑さO（n）、C++ 11ではO（1）を持ちます。

Answer 2

あなたが代わりにdequeデフォルトで、listコンテナを使用するようにqueueます：

​​

あなたはそれがlistコンテナ事前C++ 11の完全に有効な実装なのでサイズは、O（n）をとることに驚いてはいけません。以前のバージョンの標準では、リストのメンバ関数sizeの複雑さは保証されていませんでした。

あなたがあなたのコードを変更した場合：

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

あなたは（O（1）サイズの複雑さを）したい行動が表示されます。

Answer 3

マイケルの回答に追加：std::listをキューコンテナとして使用しているため、size()メソッドは、サイズのstd :: list実装に依存します。同じWebサイトを参照すると、http://www.cplusplus.com/reference/stl/list/size/が見つかり、複雑さは一定の実装では一定で、他の実装では直線的です。一定の挿入とサイズが必要な場合は、異なるデータ構造またはより良いstd::listの実装が必要です。