4

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.

Piotr Chojnacki
  • 6,837
  • 5
  • 34
  • 65
  • Can you give more information? Deleting an item and adding in front of a vector is not that of a big deal. Unless you try to do it 1000 times a second, and each object is a big object. Have you tried it and does it impact your application? – RvdK Dec 05 '12 at 10:54
  • http://linuxsoftware.co.nz/cppcontainers.html – RvdK Dec 05 '12 at 10:56
  • 2
    How much data will be stored in your container? Below 1MB, choose the simple `vector`. There won't be big performance differences. – Didier Trosset Dec 05 '12 at 10:57
  • 1
    From [this `std::deque` reference](http://en.cppreference.com/w/cpp/container/deque): "Insertion or removal of elements - linear O(n)". – Some programmer dude Dec 05 '12 at 10:57
  • @RvdK Yes, those objects are quite big and they need to be drawn every frame by OpenGL so vector is a bit slow in case of more objects in a scene. – Piotr Chojnacki Dec 05 '12 at 10:57
  • 3
    If the objects are big then the first attempt to optimize could be to use a vector/deque of (smart) pointers to them. Your `erase` is still `O(n)`, but the size of data to move is smaller. – Steve Jessop Dec 05 '12 at 10:58
  • 2
    If you would be using `vector` then push it to the back and use reverse iterators. Pushing it to the front is silly. – Pubby Dec 05 '12 at 10:59
  • 4
    Do you need to `push` it on the top of the list, or `swap` this element with the one on the top? The latter is much more efficient –  Dec 05 '12 at 11:04
  • @aleguna In fact I need to swap it! I didn't think it's more efficient. – Piotr Chojnacki Dec 05 '12 at 11:08
  • 2
    @Mosquito, well then just use vector (better of pointers) –  Dec 05 '12 at 11:10
  • 1
    If your collection is small (fits in cache) vector is almost always better. [See](http://www.baptiste-wicht.com/2012/11/cpp-benchmark-vector-vs-list/) – TeaOverflow Dec 05 '12 at 11:12

2 Answers2

7

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.

Konrad Rudolph
  • 530,221
  • 131
  • 937
  • 1,214
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.

Community
  • 1
  • 1
user1284631
  • 4,446
  • 36
  • 61
  • Even in the second case a `std::vector` will be faster for many scenarios due to cache locality. – Konrad Rudolph Dec 05 '12 at 12:53
  • @KonradRudolph: You are right, as it also depends on the size of the data structure. What is really wrong with the vector it is bad behavior when the element IS MOVED (that is, erased from its current position) and that will trigger a vector shuffle. If the OP can circumvent that operation, than the vector is the preferred chocie. OTOH, for small data structures, it simply could use TWO vectors: one with the values of interests, and another one with a permutation indicating the CURRENT order of those values. The "remove-and-insert" procedure would simply be a value changing for the second vec. – user1284631 Dec 05 '12 at 15:59