std::deque or std::list

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.

Read this: http://stackoverflow.com/questions/1436020/c-stl-containers-whats-the-difference-between-deque-and-list — Rapptz, Jan 29 '13 at 02:49
How do you access the elements? Do you do random access or sequential access? — Karthik T, Jan 29 '13 at 02:51
I was more after reasoning behind it, not benchmarking code. — Intern87, Jan 29 '13 at 03:00
See this concise post too: http://stackoverflow.com/a/1436418/341744 — ninMonkey, Jan 29 '13 at 03:19
I had seen that @monkey thank you, it just said both were fast though and no more. — Intern87, Jan 29 '13 at 03:26

score 11 · Accepted Answer · answered Jan 29 '13 at 02:50

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.

this is it, thank you. Lists allocate memory on the fly. Deques allocate a block. Thank you — Intern87, Jan 29 '13 at 03:21

score 2 · Answer 2 · answered Jan 29 '13 at 03:04

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!"].

std::deque or std::list

2 Answers2