General Use Cases for C++ Containers

General use cases for C++ containers

A picture is worth a thousand words.

It's available from nolyc, the informative bot of ##C++ on Freenode, using the command "container choice" or "containerchoice". The link to this picture you receive in response is hosted at adrinael.net, which suggests we should thank Adrinael, member of Freenode's ##C++ community.

Data structures equivalents of STL containers

Concering the C++ standard library containers, the standard itself tries not to say too much about implementation. However, the very specific constraints on complexity of insertion, removal, look-up, range insertion and so on, mean that most implementations use the same types of data structures for the containers. Concerning some of your examples:

• std::list : doubly linked list
• std::set, std::multiset, std::map, std::multimap: self-balancing
  binary trees, typically red-blacktrees.
• hash_*: C++11 provides unordered_set, unordered_map and multi
  siblings. These are hash tables.
• bitset: fixed-size array

I believe the STL follows these implementations.

Appropiate std container for (only) insertion and iteration

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

Container Class / Library for C

I just came across SGLIB while looking for a C implementation of a map/dictionary container. Unfortunately, no map but it seems to include the containers you asked about. I have no idea how good it is.

http://sglib.sourceforge.net.

Range based for in C++17 for custom container or general classes with different begin/end types

The main problem with your solution is that you try to so things in a non standard way which has many limitations and might make it hard to use by expert who have a good understanding how iterators works in STL.

I will try to answer most questions in a less technical way that should help understand how it works in practice.

1) Sharing the type will lead to some problem as some algorithms might need more than one active iterator. Also, it does not respect the SRP (single responsibility principle) and thus is not a good design practice.

2) It only need to return something that essentially behave like an iterator.

3) Or it could be a pointer if the data is contiguous in memory.

4) Usually the begin function returns an iterator by value.

5) Usually the end function returns an iterator to the end. It could also returns a sentinel object if the end is not really a position (for ex. input stream or if the last value of the container is a sentry).

6) You could put your own typedef/aliases inside the class and use them as appropriate.

7) The return value type of operator * will almost always be different than the one of the iterator type.

Then some remarks/suggestions

• In you case LinkedList would be the iterator type (or you would use a wrapper around that).
• Often you want you container to be more than an iterator if you want to be able to know the size for example without having to iterate the whole list. Also the container might provide some optimized member function like sort in std::list.
• STL source code might be a good source if you want to know how expert do it.
• Your code does not respect constness and thus would not work if you replace Example example; with const Example example;.
• Most of your operators does not follows usual convention in their declaration.
• Your begin function has side effect.
• With your code, you won't be able to store an iterator to a position in your list. This mean that algorithm like sorting or erasing matching items will probably fails.
• Putting void inside empty parameter list is essentially an obsolete way to write code that should not be used anymore in C++. It only has useful purpose in C.
• Operator++ should usually return a reference to this.
• If you want to use a sentry for the end value, it is better to use your own type (an enum value could do). Otherwise, it would allows unexpected comparison to compile like example != 25 (and in that case, one might thing that the loop would end when the value of k is 25) so it make the code harder to understand.
• Why not use std::forward_list instead of reinventing the wheel.
• If you really need to use your LinkedList then STL one could be a valuable source of information on how to properly define iterators.

In which scenario do I use a particular STL container?

This cheat sheet provides a pretty good summary of the different containers.

See the flowchart at the bottom as a guide on which to use in different usage scenarios:

_{Created by David Moore and licensed CC BY-SA 3.0}

---

Related Topics