0

Which will be the std container to use if I only want to insert a lot (10.000-100.000) of small (int,floats and doubles) items and then iterate over all of them (order is not important)? (Note: the number of items is unknown at the start)

I have noticed that unsorted_set, list and forward_list have O(1) for insertion and O(n) for iteration. Is there any other which also has that complexity? Which one of those is the fastest? (if there is significant differences in memory use i will also be interested in knowing about them.

(I'm only interested in std containers, not Boost or other libraries ones)

Lightness Races in Orbit
  • 378,754
  • 76
  • 643
  • 1,055
José D.
  • 4,175
  • 7
  • 28
  • 47
  • Have a look at: http://stackoverflow.com/questions/4010097/general-use-cases-for-c-containers –  Aug 14 '13 at 13:19
  • Define 'a lot', also how big are they? The answer is likely to be `vector`. – CB Bailey Aug 14 '13 at 13:21
  • It depends heavily on the number of elements you want to hold, their type, and the patterns of access. You should profile it in a realistic running scenario. `std::vector` is a likely candidate for the best fit. – juanchopanza Aug 14 '13 at 13:22
  • Question has been edited to reflect size and number of items – José D. Aug 14 '13 at 13:24
  • 2
    Post-edit, answer is almost definitely `std::vector` on a 'normal' machine. You could happily `.reserve(200000)` on a `vector` and reduce the number of allocations to one without stressing a modern (in the loosest possible sense) machine. – CB Bailey Aug 14 '13 at 13:28
  • If you know the maximum size then vector will do the trick. – andre Aug 14 '13 at 13:37

4 Answers4

2

My bet is std::vector with a call to std::vector::reserve().

Lightness Races in Orbit
  • 378,754
  • 76
  • 643
  • 1,055
0

vector might be a good choice. It is same as array in memory consumption. O(1) insertion(If you are inserting at the end) and O(n) iteration. It's simplest of containers and is a good choice if deletion or random insertion is not on your list.

mshriv
  • 332
  • 1
  • 2
  • std::vector would have a lot of reallocs that wouldn't be neccesary in a forward_list for example. Also it is not the same as array in memory consumption – José D. Aug 14 '13 at 13:21
  • 1
    @Trollkemada A vector is much closer to an array's memory consumption than any kind of linked list. In fact, it's virtually identical (about two pointers larger *in total*) when the vector is sized correctly. Also, with 100k elements and even assuming you don't pre-size the vector, there would only be about 17 re-allocs, most of which only copy a few dozen or hundred items. –  Aug 14 '13 at 13:27
  • After looking at all the others comments in all the answers, seems like vector is the best – José D. Aug 14 '13 at 13:32
0

All of the classes in your question have optimal complexity for what you want, but std::vector may be faster, in particular if you know how many elements you want to insert approximately, i.e. you have an upper bound available.

I suppose that performance may differ depending on your compiler, compiler version and the number of elements you want to insert. Sorry for not providing more specific help.

Markus Mayr
  • 4,038
  • 1
  • 20
  • 42
  • `std::vector` may be faster even if you don't have an upper bound on the number of elements. You just have to measure this stuff. – juanchopanza Aug 14 '13 at 13:24
  • std::vector would have to do a lot of reallocs if we do not know the number of items, right? – José D. Aug 14 '13 at 13:25
  • @Trollkemada Correct, but the number of reallocs may not be that bad either. For example if you increase (reserved) container size exponentially there are only a couple of reallocs. If you iterate a lot over the container, this may pay off. – Markus Mayr Aug 14 '13 at 13:28
  • I think std::vector is the best bet if you are able to do a std::vector.reserve to prevent reallocation –  Aug 14 '13 at 13:28
  • @Trollkemada it will have to do some, but it might be blindingly quick to do so compared to, say, traversing a list to find a point of insertion. The speed of iteration will be considerably faster, and it will have better cache behaviour. – juanchopanza Aug 14 '13 at 13:28
  • @Trollkemada Again, only about `log_a n` where `a` is the resizing factor (commonly between 1.5 and 4). And the cache friendliness will most likely outweigh that. –  Aug 14 '13 at 13:29
0

Well according to me it depends on what you want to do with the elements in the container.

  • If you want to insert elements at some positions, then list is the fastest because arrays and vectors have to move all the items after the insert position, one step forward.
  • On the other hand, if you want to access an item at a position, then arrays and vectors are faster.

Moreover, other than these there are container adapters as well like queue, stack, priority_queue etc.

So again, it all depends on your implementation and what you want from the container of elements.

Abhishek Bansal
  • 12,589
  • 4
  • 31
  • 46
  • As I said in the question, order is not important so I am not interested in inserting at any position, just insert (in any position) and then iterate over all the elements (in whatever order) so i am not interested in access an item in a given position – José D. Aug 14 '13 at 13:28
  • std::vector seems the best fit in that case – Abhishek Bansal Aug 14 '13 at 13:32