The C++ standard library comes with a wide range of standard containers. A container always contains a collection of data or objects. The cool thing is that containers can be used with practically any kind of object, so we just need to pick the right containers for our specific application. The STL gives us stacks, automatically growing vectors, maps, and so on. This way we can concentrate on our app and don't need to reinvent the wheel. Knowing all containers well is therefore crucial for every C++ programmer.

All containers the STL provides can be categorized as follows, which is explained in detail in the subsequent subsection:

A lot of novice C++ programmers learn about std::vector, that it basically works like an automatically growing array, and stop right there. Later, they only lookup its documentation in order to see how to do very specific things, for example, removing items. Using STL containers like this will only scratch the surface of how much they help writing clean, maintainable, and fast code.

This section is all about removing items from in-between a vector instance. When an item disappears from a vector, and sits somewhere in the middle between other items, then all items right from it must move one slot to the left (which gives this task a runtime cost within O(n)). Many novice programmers will do that using a loop, since it is also not really a hard thing to do. Unfortunately, they will potentially ignore a lot of optimization potential while doing that. And in the end, a hand crafted loop is neither faster, nor prettier to read than the STL way, which...

Deleting items from somewhere in the middle of an std::vector takes O(n) time. This is because the resulting gap from removing an item must be filled by moving all the items which come after the gap one slot to the left.

While moving items around like this, which might be expensive if they are complex and/or very large and include many items, we preserve their order. If preserving the order is not important, we can optimize this, as this section shows.

      #include <iostream>
      #include <vector>
      #include <algorithm>

      int main()
      {
          std::vector<int> v {123, 456, 789,...

The std::vector is probably the most widely used container in the STL, because it holds data just like an array, and adds a lot of comfort around that representation. However, wrong access to a vector can still be dangerous. If a vector contains 100 elements, and by accident our code tries to access an element at index 123, this is obviously bad. Such a program could just crash, which might be the best case, because that behavior would make it very obvious that there is a bug! If it does not crash, we might observe that the program just behaves strangely from time to time, which could lead to even more headaches than a crashing program. The experienced programmer might add some checks before any directly indexed vector access. Such checks do not increase the readability of the code, and many people do not know that std::vector already has built-in bound checks!

Arrays and vectors do not sort their payload objects themselves. But if we need that, this does not mean that we always have to switch to data structures, which were designed to do that automatically. If an std::vector is perfect for our use case, it is still very simple and practical to add items to it in a sorting manner.

      #include <iostream>
      #include <vector>
      #include <string>
      #include <algorithm>
      #include <iterator> 
      #include <cassert>

      using namespace std;

      int main()
      {
       ...

Sometimes we want to fill a map with key-value pairs and while filling the map up, we might run into two different cases:

We could just naively use the insert or emplace methods of map and see if they succeed. If it doesn't, we have case 2 and modify the existing item. In both cases, insert and emplace create the item which we try to insert, and in case 2 the freshly created item is dropped. We get a useless constructor call in both cases.

Since C++17, there is the try_emplace function, which enables us to create items only conditionally upon insertion. Let's implement a program that takes a list of billionaires and constructs a map that tells us the number of billionaires per country. In addition to that, it stores the wealthiest person in every country. Our example will not contain expensive to create items...

Looking up items in an std::map takes O(log(n)) time. This is the same for inserting new items, because the position where to insert them must be looked up. Naive insertion of M new items would thus take O(M * log(n)) time.

In order to make this more efficient, std::map insertion functions accept an optional insertion hint parameter. The insertion hint is basically an iterator, which points near the future position of the item that is to be inserted. If the hint is correct, then we get amortizedO(1) insertion time.

      #include <iostream>
      #include <map>
      #include <string>

Since the std::map data structure maps from keys to values in a way that the keys are always unique and sorted, it is of crucial value that users cannot modify the keys of map nodes that are already inserted. In order to prevent the user from modifying the key items of perfectly sorted map nodes, the const qualifier is added to the key type.

This kind of restriction is perfectly sane because it makes it harder for the user to use std::map the wrong way. But what shall we do if we really need to change the keys of some map items?

Prior to C++17, we had to remove the items of which we need to change the key value from the tree, in order to reinsert them. The downside of this approach is that this always needlessly reallocates some memory, which sounds bad in terms of performance.

Since C++17, we can remove and reinsert map nodes without any reallocation of memory. We will see how that works in this recipe.