std::deque or std::list [closed]

Question

I am using push_front() and push_back() only. Thus, I do not incur any other cost of using insert() or remove().

I know both containers offer O(1) complexity for each of these functions, deques having amortized constant time compared to lists having constant time.

But I want to know which time is less than the other, if there is, at all.

Answer 1

Not sure how to answer your question. You seem to want us to write a benchmark program that you could easily write yourself. So instead of doing that, I'll just state this:

• With a list, every item you push will incur a memory allocation.
• With a deque, large blocks are allocated at once.

Given that memory allocation is normally slow, I would expect the deque to out-perform list.

If you push or pop many items at once, this will be especially true, as cache locality comes into play.

Of course, you could write an allocator on the list to use a memory pool. Then you might get better performance.

So with these hypotheses in mind, go away and measure it, and if you want to discuss the results, that would be the time to ask a question.

Answer 2

Whenever it comes to performance, it's a bad idea to "guess" (or ask on the internet, which is slightly better than guessing, but only somewhat), and always best to measure the two options - in this case, just do a loop, and push_back or push_front enough things to make it realistic [you may want to make it more realistic and run most of what your code does, and do that in a loop enough times to make it last enough to measure the time - it's often more realistict than adding a bazillion values to a list/deque and then finding that "when you have to swap out, it gets very slow!"].