Std :: deque or std :: list

Question

I use only push_front() and push_back() . Thus, I do not incur any other costs for using insert() or remove() .

I know that both containers offer O(1) complexity for each of these functions, deque with amortized constant time compared to list with constant time.

But I want to know what time is shorter than another, if at all.

Answer 1

Not sure how to answer your question. You seem to want us to write a test program that you could easily write yourself. So instead, I just point this out:

• When using list each item you click will take up memory allocation.
• With deque , large blocks are immediately highlighted.

Given that memory allocation is usually slow, I expect deque exit the list.

If you click or click multiple items at once, this will be especially true since the cache is included in the game.

Of course, you can write a allocator in the list to use the memory pool. Then you can get better performance.

So, given these hypotheses, go away and measure it, and if you want to discuss the results, it's time to ask a question.

Answer 2

Whenever it comes to performance, it’s a bad idea to “guess” (or ask on the Internet what is a little better than guessing, but only a few), and it’s always best to measure two options - in this case, just loop and push_back or push_front has enough things to make it realistic [you can make it more realistic and do most of what your code does, and loop it enough time to make it last enough to measure time - this is often more realistic than adding bazillion values in the list / deque , and then to discover that "when you need to change the place, it becomes very slow!" ].