Which STL container should I use? C++

Question

I have a 'list' of objects, from which I want to take object at random position and push it on front of this list. Only this kind of operation will be performed. So I don't need a fast access to end of the list, only to it's front and average access to any other place.

Which container would be the best for this? I was thinking about std::vector, but I've read that insert operation is not efficient. Then I came up with std::deque because of it's fast access to front, but what about efficiency of it's erase at specific position method?

Thanks in advance for help.

Answer 1

We can give you guidelines, but no definitive answer – you need to benchmark that yourself because it crucially depends on your collection and object size:

• For small objects and/or a relatively small collection, std::vector will be faster because even though you need to copy more data, the better random access time (O(1) vs O(n) for std::list) and the cache locality will dominate.
• For large objects and/or a large collection, std::list will be faster because although you need O(n) to pick a random object, insertion will be much faster since the copying of many large objects is very slow.

But where exactly the cut-off between these two scenarios lies I cannot say.

Furthermore, if you can get away with swapping the elements instead of insertion, this is a no-brainer: always use a std::vector.

Answer 2

Based on this answer: https://stackoverflow.com/a/471481/1284631 (and also, on this: https://stackoverflow.com/a/471461/1284631), I would go for a list. It is cheap to append, iterate, insert and remove.

PS: This depends if the random position is index-based or not (that is, if you know numerically what position, or the object to move to front results through an iteration over the list and testing its properties).

So: if the position is known without iterating the list, then go for a vector. if the position requires iterating over the collection, then go for a list.