Practical summary / reference to properties of containers / adapters C ++ 11?

Question

I am looking for a detailed summary / links to important properties of various standard C ++ 11 containers and container adapters (optionally also including boost / Qt), but indexed by these properties , rather than regular container documentation (more on this below).

The properties that I have in mind include starting from the top of the head:

• Insertion options (front / rear / optional).
• Removal options (front / back / arbitrary).
• Access options (front / reverse / unified / bi-directional bypass / random access).
• The complexity of the above operations and the iterator cancellation rules.
• Uniqueness? Ordered? Associative? Continuous storage? Booking ahead of time?

^{Perhaps I forgot some, and in this case do not hesitate to comment / edit.}

The goal is to use this document as an aid in choosing the right container / adapter to work properly without having to repeat each individual documentation every time (I have a terrible memory).

Ideally, it should be indexed both by property and by type of container (for example, in the form of a table) to ensure decision making, as well as for quick reference to the main restrictions. But indeed, for property indices, they are most important to me, as it is most painful to search the documentation.

I would be very surprised if no one created such a document, but my Search-fu couldn’t get me there.

NOTE: I do not ask you to summarize all this information (I will do it myself if I really need, in which case I will publish the result here), but only if you know an existing document that meets these requirements. Something like this is a good start, but as you can see, there is still a lot of information that I would like to have, as it is limited to member functions.

Thank you for attention.

Answer 1

I don’t know a single document that provides everything you need, but most of it has been cataloged somewhere.

• This help site contains a large table with all member functions of all containers
• This question fooobar.com/questions/4286 / ... contains a large table of guarantees of complexity .
• This question fooobar.com/questions/4286 / ... gives you a decision tree for choosing between containers.

The complexity requirements for container member functions are not too difficult to remember, since there are only 4 categories: (amortized) O(1) , O(log N) , O(N) and O(N log N) ( std::list::sort() member function std::list::sort() , which really traverses the domain of the algorithms of the standard library), so if you want, you can make a 4-color version of the cpp link container table.

Choosing the right container can be as simple as ever with std::vector , unless your profiler points to a bottleneck. After you reach this point, you must make tough compromises between the complexity of space / time, the locality of the data , the simplicity of the search and the ease of insertion / modification, vs additional invariants (sorting, uniqueness, rules for canceling an iterator ).

The hardest part is that you have to balance your containers (space requirements) against the algorithms you use (time requirements). Containers can support invariants (for example, std::map sorted by their keys) that other containers can only simulate algorithms (for example, std::vector with std::sort , but without the same complexity of insertion). So after you finish the container table, make sure you do something similar for the algorithms!

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