std :: queue <T,list <T >>> :: size()在O(n)中是否很慢？

Question

我遇到了使用队列的代码的意外性能行为.我意识到当队列中有更多元素时,性能会下降.事实证明,使用该size()方法是原因.以下是一些显示问题的代码:

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


}

哪个CStopwatch类使用clock_gettime(CLOCK_REALTIME, ..).结果是:

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是一个容器适配器,所以你必须要理解复杂性描述可能只涉及适配器本身的工作(这确实是不变的,即只是将调用传递给底层容器).

例如,请参阅此参考:size()调用基础容器的size()函数.对于a list,这在C++ 98/03中具有复杂度O(n),在C++ 11中具有O(1).

Answer 2

您是queue使用list容器而不是deque默认容器:

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

你不应该对大小需要O(n)感到惊讶,因为这是listC++ 11前容器的完全有效的实现.该标准的先前版本不保证size列表的成员函数的复杂性.

如果您将代码更改为:

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

您将看到所需的行为(O(1)大小复杂度).