std :: queue< T，list< T> > :: size（）在O（n）中慢？ [英] std::queue<T, list<T> >::size() is slow in O(n)?

问题描述

我遇到了使用队列的代码的意外性能行为。我意识到，当更多的元素在队列中时，性能下降。原来，使用 size（）方法是原因。下面是一些显示问题的代码：

I experienced unexpected performance behavior of my code which uses a queue. I realized that performance degraded when more elements were in the queue. It turned out that usage of the size() method was the reason. Here is some code that shows the 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;


}

其中 CStopwatch 是使用 clock_gettime（CLOCK_REALTIME，..）的类。其结果是：

Where CStopwatch is a class which uses clock_gettime(CLOCK_REALTIME, ..). The result is:

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/ ：

复杂性：常数。

Complexity: Constant.

如果结构体更大，问题会更严重。我使用GCC 4.3.2。

The problem is worse if the struct is bigger. I am using GCC 4.3.2.

你能解释一下吗？有没有办法解决这个使用列表？

Can you explain this? Is there a way to solve this using the list?

（请注意，我需要使用列表作为队列的底层容器，因为我需要不断的时间插入复杂性。 ）

(Please note that I need to use the list as underlying container of the queue because I need constant time insertion complexity.)

推荐答案

队列是容器适配器，所以你必须明白，复杂性描述可能仅指适配器本身的工作（这是确定不变的，即只是将调用传递到底层容器）。

queue is a container adaptor, so you have to understand that the complexity descriptions may refer only to the work the adaptor does itself (which is indeed constant, namely just passing the call through to the underlying container).

例如，请参阅此参考： size（）调用底层容器的 size（）函数。对于列表，在C ++ 98/03中有复杂度O（n），C ++ 11中有O（1）。

For example, see this reference: size() calls the underlying container's size() function. For a list, this has complexity O(n) in C++98/03, and O(1) in C++11.

这篇关于std :: queue< T，list< T> > :: size（）在O（n）中慢？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！