Quickest Queue Container (C++)

Question

I'm using queue's and priority queues, through which I plan on pumping a lot of data quite quickly.

Therefore, I want my q's and pq's to be responsive to additions and subtractions.

What are the relative merits of using a vector, list, or deque as the underlying container?

Update: At the time of writing, both Mike Seymour and Steve Townsend's answers below are worth reading. Thanks both!

Answer 1

vector would implement a stack as your fast insertion is at the end and fast removal is also at the end. If you want a FIFO queue, vector would be the wrong implementation to use.

deque or list both provide constant time insertion at either end. list is good for LRU caches where you want to move elements out of the middle fast and where you want your iterators to remain valid no matter how much you move them about. deque is generally used when insertions and deletions are at the end.

The main thing I need to ask about your collection is whether they are accessed by multiple threads. I sort-of assume they are, in which case one of your primary aims is to reduce locking. This is best done if you at least have a multi_push and multi_get feature so that you can put more than one element on at a time without any locking.

There are also lock-free containers or semi-lock-free containers.

You will probably find that your locking strategy is more important than any performance in the collection itself as long as your operations are all constant-time.