C++ STL queue memory usage compared to vector?

Question

I was wondering just exactly how much more memory the queue uses in comparison to the vector. I was having an issue the other day where I had an array of int queues that used around 60MB and when the same data was put in a vector of vectors it used around 4MB. Is this an error on my part in coding the program or do stl queues generally use more memory than vectors?

Answer 1

The std::queue is a container adaptor, not a container itself. So let's compare the overhead of some actual containers:

• std::vector is very memory-efficient, it uses almost zero overhead. A std::vector<int> uses about 4 bytes per item, on most platforms.

• std::list is very inefficient with memory, it will likely use two pointers of overhead per item. A std::list<int> uses about 24 bytes per item, on 64-bit platforms, and 12 bytes on 32-bit platforms.

• std::deque is between the two, and it is the default container for std::queue. According to "what the heck is going on with the memory overhead of std::deque", the MSVC deque is a list of blocks each containing around 16 bytes, which is quite a bit of overhead if your queues contain one or two int each and you have a lot of queues.

Another factor that affects overhead is the efficiency of the allocator on your platform, which will color your results unless you can account for it. A 15x difference between two implementations is so large it's downright suspicious — it makes me wonder how you got those numbers.

In general, if your queues are very short, there is a lot of room for improvement over the other implementations. If you're okay with writing your own container, you could write a circular buffer container or use Boost's circular_buffer. A circular buffer combines the memory efficiency of std::vector with the CPU efficiency of std::deque for deque type operations. Kind of makes me wish it were in the STL to begin with. Oh well.

Footnote

The actual amounts of overhead will vary with the implementation.