1

I would like some advice on which STL container best meets the following needs:

  1. The collection is relatively short-lived.
  2. The collection contains pointers.
  3. Elements are added only at the end. The order of elements must be maintained.
  4. The number of elements is unknown and may vary from hundreds to millions. The number is known only after the final element is added.
  5. I may iterate over the elements several times.
  6. After all elements are added, I need to sort the collection, based on the objects the pointers refer to.
  7. After sorting, I may iterate over the elements several more times.
  8. After that, the collection will be destroyed.

Thread safety is not required.

Here are my thoughts:
list: Requires a separate allocation for each element. More expensive traversal.
vector: Need to be reallocated as the collection grows. Best sort and traversal performance.
deque: Fewer allocations than list and fewer reallocations than vector. I don't know about behavior with respect to sort.

I am currently using list. The flowchart at In which scenario do I use a particular STL container? leads me to deque.

My knowledge of STL is old; I don't know about container types that have been added since 2003, so maybe there's something well-suited that I've never heard of.

prl
  • 11,716
  • 2
  • 13
  • 31
  • 7
    Almost always `vector`. Anyway, if you really care about performance, measure it. If you don't measure, you don't really care. – Igor Tandetnik Sep 23 '17 at 04:02
  • Following the flow chart, I would use vector - which is almost always a sensible default choice, anyway, unless you have evidence otherwise. "Size varying widely" refers to needing to increase and decrease size regularly, not that the size may steadily grow large. – Peter Sep 23 '17 at 04:20
  • Aah, @Peter, thanks, I misinterpreted that. – prl Sep 23 '17 at 04:26
  • Yes, @Igor, of course I plan to measure it, but I want to make sure I'm starting with the right choices. – prl Sep 23 '17 at 04:29

1 Answers1

3

std::vector<T*> will be the winner based on the points discussed.

Don't be afraid of the resizing that will need to occur--just reserve() a reasonable amount (say 500 if many of your collections will be around there).

Sorting performance with vector<T*> will also be very good.

Allocation and deallocation of each T will be important. Pay attention to this. For example you may want to allocate thousands of Ts at a time, to reduce the memory allocation overhead (and make it faster to deallocate everything at the end). This is known as an "arena" or "pool". You can probably store 32-bit relative pointers into the arena, saving half the pointer storage space.

And of course, if T is small you might consider storing it by value instead of by pointer.

John Zwinck
  • 239,568
  • 38
  • 324
  • 436