4

I'm looking for a comprehensive summary/reference of important properties of the various C++11 standard containers and container adapters (optionally also including boost/Qt), but indexed by those properties rather than the usual per container documentation (more on that below).

The properties I have in mind include, from the top of my head:

  • Insertion capabilities (front / back / arbitrary).
  • Removal capabilities (front / back / arbitrary).
  • Access capabilities (front / back / uni/bi-directional traversal / random access).
  • Complexity of the aforementioned operations, and iterator invalidation rules.
  • Uniqueness? Ordered? Associative? Contiguous storage? Reservation ahead of time?

I may have forgotten some in which case don't hesitate to comment/edit.

The goal is to use that document as an aid to choose the right container/adapter for the right job, without having to wade through the various individual documentations over and over every time (I have a terrible memory).

Ideally it should be indexed both by property and by container type (eg. table-like) to allow for decision-making as well as for quick reference of the basic constraints. But really the per property indexes are the most important for me since this is the most painful to search in the documentation.

I'd be very surprised if nobody had already produced such a document, but my Search-fu is failing me on this one.

NOTE: I'm not asking for you to summarize all these informations (I'll do that myself if I really have to, in which case I'll post the result here) but only if you happen to know an existing document that fits those requirements. Something like this is a good start but as you can see it still lacks many of the information I'd like to have since it's restricted to member functions.

Thanks for your attention.

syam
  • 14,701
  • 3
  • 41
  • 65
  • Doubtful there is such a reference. Maybe you can create one for cppreference.com? – Some programmer dude May 03 '13 at 18:35
  • @JoachimPileborg: Yes this is probably what I'll end up doing if I don't get a satisfactory answer here. I just figured I'd ask first in case I missed something during my research (wouldn't be the first time). ;) – syam May 03 '13 at 18:40

1 Answers1

3

I am not aware of a single document that provides everything you need, but most of it has been catalogued somewhere.

  • This reference site has a large table with all the member functions of all the containers
  • This SO question has a large table of the complexity guarantees.
  • This SO question gives you a decision tree to choose between containers.

The complexity requirements for container member functions are not too hard to memorize since there are only 4 categories: (amortized) O(1), O(log N), O(N), and O(N log N) (member function std::list::sort() which really crosses into the algorithms domain of the Standard Library) so if you want you could make a 4-color-coded version of the cpp reference container table.

Choosing the right container can be as simple as always using std::vector unless your profiler indicates a bottleneck. After you reach that point, you have to make hard tradeoffs between space / time complexity, data locality, ease of lookup vs ease of insertion / modification, vs extra invariants (sortedness, uniqueness, iterator invalidation rules).

The hardest part is that you have to balance your containers (space requirements) against the algorithms that you are using (time requirements). Containers can maintain invariants (e.g. std::map is sorted on its keys) that other containers can only mimic using algorithms (e.g. std::vector with std::sort, but without the same insertion complexity). So after you finish the container table, make sure to do something similar for the algorithms!

Finally, no container summary would be complete without mentioning Boost.MultiIndex: because sometimes you don't have to choose!

Community
  • 1
  • 1
TemplateRex
  • 69,038
  • 19
  • 164
  • 304
  • Thanks for the links to SO (I already found the cppreference.com one), I somehow missed those and they are very helpful, especially the decision tree! All of this would definitely be good source material to build the document I have in mind. – syam May 03 '13 at 18:52
  • WRT to "*After you reach that point, you have to make hard tradeoffs...*" => yes this is exactly why I asked this question: I have such a terrible memory and I waste too much time (IMO) searching the documentation to remember all those constraints for each container. Hence the "summary / at a glance" request. ;) – syam May 03 '13 at 19:02
  • @syam After a while they become very familiar :) There are broad categories such as Sequence containers (vector, array, deque, list), Associative containers (map, set, with/without unique_, with/without unordered_) that have many of the member functions in common. – TemplateRex May 03 '13 at 19:16
  • Define "*after a while*"... I've been using C++ since 1995 and my memory still isn't any better for the small details, I always have to look them up tediously. Maybe in another 20 years, who knows... (but I somehow doubt it) ;) – syam May 03 '13 at 19:28
  • @syam I meant "after a while of intensive use". With that I mean not using C-style arrays, manual memory allocation or node pointer manipulation of hand-written lists. Just use STL containers wherever it makes sense :-) – TemplateRex May 03 '13 at 19:35