CODEWITHSUNDEEP
c++performancestlqueue
Philipp
Philipp

Reputation: 11813

std::queue<T, list<T> >::size() is slow in O(n)?

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;


}

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

This seems to contradict http://www.cplusplus.com/reference/stl/queue/size/:

Complexity: Constant.

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.)

Upvotes: 7

Views: 3886

Answers (3)

Michael Goldshteyn
Michael Goldshteyn

Reputation: 74360

You're your queue to use a list container, instead of the deque default:

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

You shouldn't be surprised that size takes O(n), since that's a perfectly valid implementation of the list container pre C++11. The previous version of the standard did not guarantee the complexity of the size member function for lists.

If you change your code to:

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

You will see the behavior you want (O(1) size complexity).

Upvotes: 5

Kerrek SB
Kerrek SB

Reputation: 477020

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).

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.

Upvotes: 8

Corey D
Corey D

Reputation: 4689

Adding to Michael's answer: You're using std::list as your queue container, so the size() method depends on your std::list implementation of size. If you look up on the same website, you find http://www.cplusplus.com/reference/stl/list/size/ and the complexity is constant on some implementations and linear on others. If you need constant insertion and size, then you need a different data structure or a better std::list implementation.

Upvotes: 1

Related Questions