станд :: очереди:: размер () медленно в 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().Для list это имеет сложность O (n) в C ++ 98/03 и O (1) в C ++ 11.

Answer 2

Вы queue используете контейнер list вместо deque по умолчанию:

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

Вы не должны удивляться, что размер занимает O (n), так какэто совершенно правильная реализация контейнера list до C ++ 11.Предыдущая версия стандарта не гарантировала сложности функции size для списков.

Если вы измените свой код на:

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

Вы увидите желаемое поведение(O (1) размер сложности).

Answer 3

Добавление к ответу Майкла: вы используете std::list в качестве контейнера очереди, поэтому метод size() зависит от вашей реализации размера std :: list.Если вы посмотрите на тот же веб-сайт, вы найдете http://www.cplusplus.com/reference/stl/list/size/, и сложность постоянна в некоторых реализациях и линейна в других.Если вам нужна постоянная вставка и размер, тогда вам нужна другая структура данных или лучшая реализация std::list.