3

STL Containers

In this chapter, we will focus on the container classes in the STL. In short, a container is an object that contains a collection of other objects, or elements . The STL provides a complete suite of container types that form the foundation of the STL itself.

In this chapter we will cover the following recipes:

• Use uniform erasure functions to delete elements from a container
• Delete items from an unsorted vector
• Access vector elements safely
• Keep vector elements sorted
• Efficiently insert elements into a map
• Efficiently modify keys in a map
• Use unordered_map with custom keys
• Sort and filter user input with set
• Create a simple RPN calculator with deque
• Count word frequency with map
• Find long sentences with a vector of vectors
• Create an efficient ToDo list using a multimap

The heart of the STL is in its container classes. The STL leverages the power of Templates (the T in STL) to provide containers that work transparently with a broad spectrum of classes and types.

A quick overview of the STL container types

The STL provides a comprehensive set of container types, including sequential containers , associative containers , and container adapters . Here's a brief overview.

Sequential containers

Sequential containers provide an interface where the elements are arranged in sequence. While you may use the elements sequentially, some of these containers use contiguous storage and others do not. The STL includes these sequential containers:

• The array is a fixed-size sequence that holds a specific number of elements in contiguous storage. Once allocated, it cannot change size. This is the simplest and fastest contiguous storage container.
• The vector is like an array, but a vector can shrink and grow. Its elements are stored contiguously, so changing its size may involve the expense of allocating memory and moving data. A vector may keep extra space in reserve to mitigate that cost. Inserting and deleting elements from anywhere other than the back of a vector will trigger realignment of the elements to maintain contiguous storage.
• The list is a doubly-linked list structure that allows elements to be inserted and deleted in constant O(1) time. Traversing the list happens in linear O(n) time. A single-linked variant is available as forward_list , which iterates forward only. A forward_list uses less space and is somewhat more efficient than a doubly-linked list , but iterates only in one direction.
• The deque (commonly pronounced, deck ) is a d ouble- e nded que ue. It's a sequential container that can be expanded or contracted on both ends. A deque allows random access to its elements, much like a vector , but does not guarantee contiguous storage.

Associative containers

An associative container associates a key with each element. Elements are referenced by their key, rather than their position in the container. STL associative containers include these classes:

• The set is an associative container where each element is also its own key. Elements are ordered, usually by some sort of binary tree. Elements in a set are immutable and cannot be modified, but they can be inserted and removed. Elements in a set must be unique ; duplicates are not allowed. A set iterates in order according to its sorting operators.
• The multiset is like a set with non-unique keys, where duplicates are allowed.
• The unordered_set is like a set that does not iterate in order. Elements are not sorted in any specific order but are organized according to their hash values for fast access.
• The unordered_multiset is like an unordered_set with non-unique keys, where duplicates are allowed.
• The map is an associative container for key-value pairs, where each key is mapped to a specific value (or payload ). The types of the key and value may be different. Keys are unique but values are not. A map iterates in the order of its keys according to its sorting operators.
• The multimap is like a map with non-unique keys, where duplicate keys are allowed.
• The unordered_map is like a map that does not iterate in order.
• The unordered_multimap is like an unordered_map with non-unique keys, where duplicates are allowed.

Container adapters

A container adapter is a class which encapsulates an underlying container. The container class provides a specific set of member functions to access the underlying container elements. The STL provides these container adapters:

The stack provides a LIFO (last-in, first-out) interface where elements may be added and extracted from only one end of the container. The underlying container may be one of vector , deque , or list . If no underlying container is specified, the default is deque .

The queue provides a FIFO (first-in, first-out) interface where elements may be added at one end of the container and extracted from the other end. The underlying container may be one of deque or list . If no underlying container is specified, the default is deque .

The priority_queue keeps the greatest value element at the top, according to a strict weak ordering . It provides a constant time lookup of the greatest value element, at the expense of logarithmic time insertion and extraction. The underlying container may be one of vector or deque . If no underlying container is specified, the default is vector .

Use uniform erase functions to delete elements from a container

Before C++20, the erase-remove idiom was commonly used to efficiently delete elements from an STL container. This was a little cumbersome, but not a great burden. It was common to use a function like this for the task:

template<typename Tc, typename Tv> void remove_value(Tc & c, const Tv v) {     auto remove_it = std::remove(c.begin(), c.end(), v);     c.erase(remove_it, c.end()); }

The std::remove() function is from the < algorithm > header. std::remove() searches for the specified value and removes it by shifting elements forward from the end of the container. It does not change the size of the container. It returns an iterator past the end of the shifted range. We then call the container's erase() function to delete the remaining elements.

This two-step process is now reduced to one step with the new uniform erasure function:

std::erase(c, 5);   // same as remove_value() function

This one function call does the same thing as the remove_value() function we wrote above.

There ' s also a version that uses a predicate function. For example, to remove all even-numbered values from a numeric container:

std::erase_if(c, [](auto x) { return x % 2 == 0; });

Let's look at the uniform erasure functions in a bit more detail.

How to do it

• There are two forms of the uniform erasure functions. The first form, called erase() , takes two parameters: a container and a value:

  erase(container, value);

  The container may be any of the sequential containers ( vector , list , forward_list , deque ), except array , which cannot change size.

• The second form, called erase_if() , takes a container and a predicate function:

  erase_if(container, predicate);

  This form works with any of the containers that work with erase() , plus the associative containers, set , map , and their multi-key and unordered variants.

The functions erase() and erase_if() are defined, as non-member functions, in the header for the corresponding container. There is no need to include another header.

Let's look at some examples:

• First, let's define a simple function to print the size and elements of a sequential container:

  void printc(const auto& r) {     print("size: {}: ", r.size());     for( auto& e : r ) print("{} ", e);     print("\n"); }

  The printc() function uses the C++23 print() function to print the size and values of an STL container.

• Here's a vector with 10 integer elements, printed with our printc() function:

  vector v {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; printc(v);

  Output:

  size: 10: 0 1 2 3 4 5 6 7 8 9

  We see that the vector has 10 elements. Now we can use erase() to remove all elements with the value 5 :

  erase(v, 5); printc(v);

  Output:

  size: 9: 0 1 2 3 4 6 7 8 9

• The vector version of the std::erase() function is defined in the <vector> header. After the erase() call, the element with the value 5 has been removed and the vector has 9 elements.

  This gives us the exact same results with a list container:

  list l{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; printc(l); erase(l, 5); printc(l);

  Output:

  size: 10: 0 1 2 3 4 5 6 7 8 9 size: 9: 0 1 2 3 4 6 7 8 9

• The list version of the std::erase() function is defined in the <list> header. After the erase() call, the element with the value 5 has been removed and the list has 9 elements.

  We can use erase_if() to remove all the even-numbered elements with a simple predicate function:

  vector v{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; printc(v); erase_if(v, [](auto x) { return x % 2 == 0; }); printc(v);

  Output:

  size: 10: 0 1 2 3 4 5 6 7 8 9 size: 5: 1 3 5 7 9

  The erase_if() function also works with associative containers, like map :

  void print_assoc(const auto& r) {     print("size: {}: ", r.size());     for (auto& [k, v] : r) print("{}:{} ", k, v);     print("\n"); }  int main() {     map<int, string> m{ {1, "uno"}, {2, "dos"},         {3, "tres"}, {4, "quatro"}, {5, "cinco"} };     print_assoc(m);     erase_if(m,         [](auto&p){auto&[k,v]=p;         return k % 2 == 0; }     );     print_assoc(m); }

  Output:

  size: 5: 1:uno 2:dos 3:tres 4:quatro 5:cinco size: 3: 1:uno 3:tres 5:cinco

Because each element of a map is returned as a pair , we need a different function to print them. The print_assoc() function unpacks the pair elements with a structured binding in the for loop. We also use a structured binding in the predicate function of erase_if() to isolate the key for filtering the even numbered elements.

How it works

The erase() and erase_if() functions are simply wrappers that perform the erase-remove idiom in one step. They perform the same operations as a function like this:

template<typename Tc, typename Tv> void remove_value(Tc & c, const Tv v) {     auto remove_it = std::remove(c.begin(), c.end(), v);     c.erase(remove_it, c.end()); }

If we consider a simple vector of int , called vec , with the following values:

vector vec {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

We can visualize vec as a one-row table of int values:

Figure 3.1: begin() and end() iterators

The begin() iterator points at the first element, and the end() iterator points past the last element. This configuration is standard for all STL sequential containers.

When we call remove(c.begin(), c.end(), 5) , the algorithm searches for matching elements, starting at the begin() iterator. For each matching element that it finds, it shifts the next element into its place. It continues searching and shifting until it reaches the end() iterator. The result is a container where all the remaining elements are at the beginning, without the deleted elements, and in their original order. The end() iterator is unchanged, and the remaining elements are undefined . We can visualize the remove() operation like this:

Figure 3.2: Removing an element

The remove() function returns an iterator ( remove_it ) that points to the first element past the elements that were shifted. The end() iterator remains as it was before the remove() operation. To further illustrate, if we were to remove all even-numbered elements using remove_if() , our result would look like this:

Figure 3.3: After removing even-numbered elements

In this case, all that remains are the five odd-numbered elements followed by five elements of undefined value.

The container's erase() function is then called to erase the remaining elements:

c.erase(remove_it, c.end());

The container's erase() function is called with the remove_it and end() iterators to delete all the undefined elements.

The erase() and erase_if() functions call both the remove() function and the container's erase() function, in order to perform the erase-remove idiom in one step.

Delete items from an unsorted vector

Using the uniform erasure functions (or the erase-remove idiom ) to delete items from the middle of a vector takes linear O(n) time. This is because elements must be shifted from the end of the vector to close the gap of the deleted items. If the order of items in the vector is not important, we can optimize this process to take constant O(1) time. Here's how.

How to do it

This recipe takes advantage of the fact that removing an element from the end of a vector is quick and easy.

• Let's start by defining a function to print out a vector:

  void printc(const auto& r) {     print("size({}) ", r.size());     for( auto& e : r ) print("{} ", e);     print("\n"); }

• In our main() function we define a vector of int and print it using printc() :

  int main() {     vector v {12, 196, 47, 38, 19};     printc(v); }

  Output:

  size(10) 0 1 2 3 4 5 6 7 8 9

• Now we'll write a function that will delete an element from the vector :

  template<typename T> void quick_delete(T& v, size_t idx) {     if (idx < v.size()) {         if (idx != v.size() - 1) {             v[idx] = std::move(v.back());         }         v.pop_back();     } }

  The quick_delete() function takes two arguments, a vector v and an index idx . We first check to make sure our index is within boundaries. Then we call the std::move() function from the <algorithms> header to move the last element of the vector to the position of our index. Finally, the v.pop_back() function is called to shorten the vector from the back.

• Let's also create a version of quick_delete() for use with an iterator instead of an index:

  template<typename T> void quick_delete(T& v, typename T::iterator it) {     if (it < v.end()) {         if (it != std::prev(v.end())) {             *it = std::move(v.back());         }         v.pop_back();     } }

  This version of quick_delete() operates from an iterator instead of an index. Otherwise, it works the same as the indexed version.

• Now we can call it from our main() function:

  int main() {     vector v{ 12, 196, 47, 38, 19 };     printc(v);     auto it = std::ranges::find(v, 47);     quick_delete(v, it);     printc(v);     quick_delete(v, 1);     printc(v); }

  And the output will look like this:

  size(5) 12 196 47 38 19 size(4) 12 196 19 38 size(3) 12 38 19

The first call to quick_delete() uses an iterator from the std::ranges::find() algorithm. This deletes the value 47 from the vector . Notice the value from the back of the vector ( 19 ) takes its place. The second call to quick_delete() uses an index ( 1 ) to delete the second element from the vector ( 196 ). Again, the value from the back of the vector takes its place.

How it works

The quick_delete() function uses a simple trick to delete elements from a vector quickly and efficiently. The element at the back of the vector is moved ( not copied ) into the position of the element to be deleted. The deleted element is discarded in the process. Then, the pop_back() function shortens the vector by one element from the end.

This takes advantage of the fact that deleting the element at the back of the vector is especially cheap. The pop_back() function operates at constant complexity, as it only needs to change the end() iterator.

This diagram shows the state of the vector before and after the quick_delete() operation:

Figure 3.4: Before and after quick_delete()

The quick_remove() operation simply moves the element from the back of the vector into the position of the iterator ( it ), then shortens the vector by one element. It's important to use std::move() instead of an assignment to move the element. The move operation is much faster than a copy-assignment, especially for large objects.

If you don't require ordered elements, this is an extremely efficient technique. It happens in constant O(1) time and without touching any other elements.

Access vector elements safely

The vector is one of the most widely used containers in the STL, and for good reason. It's just as convenient as an array but far more powerful and flexible. It's common practice to use the [] operator to access elements in a vector like this:

vector v {19, 71, 47, 192, 4004}; auto& i = v[2];

The vector class also provides a member function for the same purpose:

auto& i = v.at(2);

The result is the same but there is an important difference. The at() function does bounds checking and the [] operator does not. This is intentional, as it allows the [] operator to maintain compatibility with the original C-array. Conversely, the bounds checking of the at() method requires a tiny bit of extra compute time, which may or may not be important in a given application. Let's examine this in somewhat more detail.

How to do it

There are two ways to access an element with an index in a vector . The at() member function does bounds checking, and the [] operator does not.

• Here's a simple main() function that initializes a vector and accesses an element:

  int main() {     vector v {19, 71, 47, 192, 4004};     auto& i = v[2];     println("element is {}", i); }

  Output:

  element is 47

  Here, we used the [] operator to directly access the third element in the vector . As with most sequential objects in C++, the index starts at 0 so the third element is number 2 .

• The vector has five elements, numbered 0 through 4 . If I were to try to access element number 5 that would be beyond the boundary of the vector:

  vector v {19, 71, 47, 192, 4004}; auto& i = v[5]; println("element is {}", i);

  Output:

  element is 0

  This result is extremely deceiving. It's a common error, since humans tend to count from 1, not 0. But there is no guarantee that an element past the end of the vector has any particular value.

• Even worse, the [] operator will silently allow you to write to a position beyond the end of the vector:

  vector v {19, 71, 47, 192, 4004}; v[5] = 2001; auto& i = v[5]; println("element is {}", i);

  Output:

  element is 2001

  We have now written to memory that is not under our control and the compiler has silently allowed it, with no error messages or crashes. But do not be fooled—this is extremely dangerous code, and it will cause problems at some point in the future. Out-of-bounds memory access is one of the primary causes of security breaches.

• The solution is to use the at() member function wherever possible, instead of the [] operator:

  vector v {19, 71, 47, 192, 4004}; auto& i = v.at(5); println("element is {}", i);

  Now we get a runtime exception:

  terminate called after throwing an instance of 'std::out_of_range'   what():  vector::_M_range_check: __n (which is 5) >= this->size() (which is 5) Aborted

The code compiles without error, but the at() function checks the boundaries of the container and throws a run-time exception when you try to access memory outside of those boundaries. This is the exception message from code compiled with the GCC compiler. The message will be different in different environments.

How it works

The [] operator and the at() member function do the same job: they provide direct access to container elements based on their indexed position. The [] operator does it without any bounds checking, so it may be a tiny bit faster in some intensely iterative applications.

That said, the at() function should be your default choice . While the bounds checking may take a few CPU cycles, it's cheap insurance. For most applications the benefit is well worth the cost.

There's more…

In some applications you may not want your application to just crash when an out-of-bounds condition is encountered. In this case, you can catch the exception, like this:

int main() {     vector v {19, 71, 47, 192, 4004};     try {         v.at(5) = 2001;     } catch (const std::out_of_range & e) {         println("Ouch!\n{}", e.what());     }     println("end element is {}", v.back()); }

Output:

Ouch! vector end element is 4004

The try block catches the exception specified in the catch clause; in this case, the exception is std::out_of_range . The e.what() function returns a C-string with the error message from the STL library. Each implementation will have different messages.

Keep in mind that all of this applies to array and deque containers as well.

Keep vector elements sorted

The vector is a sequential container that keeps elements in the order in which they were inserted. It does not sort elements, nor change their order in any way. Other containers, such as set and map , keep elements sorted, but those containers are not random-access and may not have the features you need. You can, however, keep your vector sorted. It just requires a little bit of management.

How to do it

The idea with this recipe is to create a simple function, insert_sorted() , that inserts an element into the correct position in a vector to keep the vector sorted.

• For convenience, we'll start with type alias es for a vector of string and a vector of int :

  using Vstr = std::vector<std::string>; using Vint = std::vector<int>;

  I like the type aliases here because the exact details of the vector are not so important as its application.

• Then we can define a couple of support functions:

  // print a vector void printv(const auto& v) {     for(const auto& e : v) {         print("{} ", e);     }     print("\n"); } // is it sorted? void psorted(const auto& v) {     if(ranges::is_sorted(v)) print("sorted: ");     else print("unsorted: ");     printv(v); }

  The printv() function is simple enough; it prints the elements of the vector on one line.

  The psorted() function uses the ranges version of the is_sorted() algorithm to tell us if the vector is sorted. Then it calls printv() to print the vector .

• Now we can initialize a Vstr vector in our main() function:

  int main() {     Vstr v{         "Miles",         "Hendrix",         "Beatles",         "Zappa",         "Shostakovich"     };     psorted(v); }

  Output:

  unsorted: Miles Hendrix Beatles Zappa Shostakovich

  At this point we have a Vstr vector with the names of some interesting musicians, in no particular order.

• We can sort our vector using the ranges version of the sort() algorithm

  ranges::sort(v); psorted(v);

  Output:

  sorted: Beatles Hendrix Miles Shostakovich Zappa

• We want to be able to insert items into the vector so that they're already in sorted order. The insert_sorted() function does this for us:

  void insert_sorted(Vstr& v, const string& s) {     const auto pos {std::ranges::lower_bound(v, s)};     v.insert(pos, s); }

  The insert_sorted() function uses the ranges version of the lower_bound() algorithm to get an iterator for the insert() function that keeps the vector sorted.

• Now we can use the insert_sorted() function to insert more musicians into the vector :

  insert_sorted(v, "Ella"); insert_sorted(v, "Stones");

  Output:

  sorted: Beatles Ella Hendrix Miles Shostakovich Stones Zappa

How it works

The insert_sorted() function is used to insert elements into a sorted vector while maintaining its order:

void insert_sorted(Vstr& v, const string& s) {     const auto pos {std::ranges::lower_bound(v, s)};     v.insert(pos, s); }

The lower_bound() algorithm finds the first element not less than the argument. We then use the iterator returned by lower_bound() to insert an element at the correct position.

In this case we're using the ranges version of lower_bound() , but either version will work.

There's more…

The insert_sorted() function can be made more generic by using a template. This version will work with other container types, such as set , deque , and list .

template<typename C, typename E> void insert_sorted(C& c, const E& e) {     const auto pos {std::ranges::lower_bound(c, e)};     c.insert(pos, e); }

Efficiently insert elements into a map

The map class is an associative container that holds key-value pairs , where keys must be unique within the container.

There are a number of ways to populate a map container. Consider a map defined like this:

map<string, string> m;

We can add an element with the [] operator:

m["Miles"] = "Trumpet"

We can use the insert() member function:

m.insert({"Hendrix", "Guitar"});

Here we use template argument deduction to pass a std::pair of values to the m.insert() function.

Or, we can use the emplace() member function:

m.emplace("Krupa", "Drums");

I tend to gravitate toward the emplace() function. Introduced with C++11, emplace() uses perfect forwarding to create the new element in place by forwarding parameters directly to the container's constructor. This is quick, efficient, and easy to code.

Though it's certainly an improvement over the other options, the problem with emplace() is that it constructs an object even when it's not needed. This involves calling the constructors, allocating memory, moving data around, and then discarding that temporary object.

To solve this problem, C++17 provided the new try_emplace() function which only constructs the value object if it's needed. This is especially important with large objects or many emplacements.

How to do it

Each element of a std::map is a key-value pair. Within the pair structure, the elements are named first and second , but their purpose in the map is key and value . I tend to think of the value object as the payload , as this is usually the point of the map .

To search for an existing key, the C++17 try_emplace() function must construct the key object; this cannot be avoided. But it need not construct the value object unless and until it's needed for insertion into the map . This creates valuable efficiency in the case of key collisions, especially with large payloads. Let's take a look:

• First, we create a payload class. For demonstration purposes, this class has a simple std::string payload and displays a message when constructed:

  struct BigThing {     string value;     BigThing(const char * v) : value(v) {         println("BigThing constructed {}", value);     } }; using Mymap = map<string, BigThing>;

  This BigThing class has only one member function, a constructor that displays a message when the object is constructed. We'll use this to keep track of how often a BigThing object is constructed. In practice, of course, this class would be larger and use more resources.

  Each map element will consist of a pair of objects, a std::string for the key and a BigThing object for the payload. Mymap is just a convenience alias. This allows us to focus on function rather than form.

• We'll also create a printm() function to print the contents of the map :

  void printm(const Mymap& m) {     for(auto& [k, v] : m) {         print("[{}:{}] ", k, v.value);     }     print("\n"); }

  This uses the C++23 print() function to print out the map , so we can keep track of the elements as we insert them.

• In our main() function we create the map object and insert some elements:

  int main() {     Mymap m;     m.emplace("Miles", "Trumpet");     m.emplace("Hendrix", "Guitar");     m.emplace("Krupa", "Drums");     m.emplace("Zappa", "Guitar");     m.emplace("Liszt", "Piano");     printm(m); }

  Output:

  BigThing constructed Trumpet BigThing constructed Guitar BigThing constructed Drums BigThing constructed Guitar BigThing constructed Piano [Hendrix:Guitar] [Krupa:Drums] [Liszt:Piano] [Miles:Trumpet] [Zappa:Guitar]

  Our output shows the construction of each of the payload objects, and then the output from the printm() function call.

• I used the emplace() method to add the elements to the map , and each payload element was constructed just once. We can use the try_emplace() method and the result will be the same:

  Mymap m; m.try_emplace("Miles", "Trumpet"); m.try_emplace("Hendrix", "Guitar"); m.try_emplace("Krupa", "Drums"); m.try_emplace("Zappa", "Guitar"); m.try_emplace("Liszt", "Piano"); printm(m);

  Output:

  BigThing constructed Trumpet BigThing constructed Guitar BigThing constructed Drums BigThing constructed Guitar BigThing constructed Piano [Hendrix:Guitar] [Krupa:Drums] [Liszt:Piano] [Miles:Trumpet] [Zappa:Guitar]

• The difference between emplace() and try_emplace() shows up when we try to insert new elements with duplicate keys:

  println("emplace(Hendrix)"); m.emplace("Hendrix", "Singer"); println("try_emplace(Zappa)"); m.try_emplace("Zappa", "Composer"); printm(m);

  Output:

  emplace(Hendrix) BigThing constructed Singer try_emplace(Zappa) [Hendrix:Guitar] [Krupa:Drums] [Liszt:Piano] [Miles:Trumpet] [Zappa:Guitar]

  The emplace() function tried to add an element with a duplicate key ( "Hendrix" ). It failed but still constructed the payload object ( "Singer" ). The try_emplace() function also tried to add an element with a duplicate key ( "Zappa" ). It failed and did not construct the payload object.

This recipe demonstrates the distinctions between emplace() and try_emplace() in a map object. The efficiency of try_emplace() may be significant with larger payloads.

How it works

The try_emplace() function signature is similar to that of emplace() , so it should be easy to retrofit legacy code. Here's the try_emplace() function signature:

pair<iterator, bool> try_emplace( const Key& k, Args&&... args );

At first glance, this looks different from the emplace() signature:

pair<iterator,bool> emplace( Args&&... args );

The distinction is that try_emplace() uses a separate parameter for the key argument, which allows it to be isolated for construction. Functionally, because of template argument deduction , try_emplace() can be a drop-in replacement:

m.emplace("Miles", "Trumpet"); m.try_emplace("Miles", "Trumpet");

The return value of try_emplace() is the same as that of emplace() , a pair representing an iterator and a bool :

    const auto key = "Zappa";     const auto payload = "Composer";     if(auto [it, success] = m.try_emplace(key, payload);             !success) {         println("update");         it->second = payload;     }     printm(m);

Output:

update BigThing constructed Composer [Hendrix:Guitar] [Krupa:Drums] [Liszt:Piano] [Miles:Trumpet] [Zappa:Composer]

Here we used structured binding ( auto [it, success] = ) with an if initializer statement to test the return value and conditionally update the payload. Notice that it still just constructs the payload object once.

It's worth noting that the try_emplace() function also works with unordered_map . We change our alias and everything works the same except unordered:

using Mymap = unordered_map<string, BigThing>;

The advantage of try_emplace() is that it only constructs the payload object if and when it's ready to store it in the map . In practice, this should save significant resources at run-time. We should always favor try_emplace() over emplace() .

Efficiently modify keys in a map

A map is an associative container that stores key-value pairs . The container is ordered by the keys. The keys must be unique and they are const -qualified, so they cannot be changed.

For example, if I populate a map and attempt to change the key, I'll get an error at compilation time:

map<int, string> mymap {     {1, "foo"}, {2, "bar"}, {3, "baz"} }; auto it = mymap.begin(); it->first = 47;

Output from gcc ; your error may differ:

error: assignment of read-only member ...     5 |     it->first = 47;       |

If you need to re-order a map container, you may do so by swapping keys using the extract() method.

Beginning with C++17, the extract() member function allows elements of a map to be extracted from the sequence without touching the payload. Once extracted, the key is no longer const -qualified and may be modified.

Let's look at an example.

How to do it

In this example we'll define a map that represents contestants in a race. At some point during the race, the order changes, and we need to modify the keys of the map .

• We start by defining an alias for the map type:

  using Racermap = map<unsigned int, string>;

  This allows us to use the type consistently throughout our code.

• We write a function for printing out the map:

  void printm(const Racermap &m) {     println("Rank:");     for (const auto& [rank, racer] : m) {         println("{}:{}", rank, racer);     } }

  We can pass the map to this function at any time to print out the current rankings of our contestants.

• In our main() function we define a map with the initial state of our racers:

  int main() {     Racermap racers {         {1, "Mario"}, {2, "Luigi"}, {3, "Bowser"},         {4, "Peach"}, {5, "Donkey Kong Jr"}     };     printm(racers);     node_swap(racers, 3, 5);     printm(racers); }

  The key is an int indicating the rank of the racer. The value is a string with the name of the racer. We call printm() to print the current rank.

  At some point, one of the racers falls behind and another racer takes the opportunity to move up in the rankings. The node_swap() function will swap the ranking of two racers:

  template<typename M, typename K> bool node_swap(M& m, K k1, K k2) {     if (k1 == k2) return true;     auto node1 = m.extract(k1);     auto node2 = m.extract(k2);     if (node1.empty() || node2.empty()) {         if (!node1.empty()) m.insert(move(node1));         if (!node2.empty()) m.insert(move(node2));         return false;     }     swap(node1.key(), node2.key());     m.insert(move(node1));     m.insert(move(node2));     return true; }

  This function uses the map::extract() method to extract the specified elements from the map . These extracted elements are called nodes .

  A node is a new concept introduced with C++17. It allows an element to be extracted from a map -type structure without touching the element itself. The node is unlinked, and a node handle is returned. Once extracted, the node handle provides writable access to the key via the node's key() function. We can then swap the keys and insert them back into the map , without ever having to copy or manipulate the payload.

• We can call node_swap() at the end of main() to swap the positions of two racers like this:

      node_swap(racers, 3, 5);     printm(racers);

  Now our output looks like this:

  Rank: 1:Mario 2:Luigi 3:Bowser 4:Peach 5:Donkey Kong Jr Rank: 1:Mario 2:Luigi 3:Donkey Kong Jr 4:Peach 5:Bowser

  This is all made possible by the extract() method and the new node_handle class. Let's take a closer look at how this works.

How it works

This technique uses the new extract() method, which returns a node_handle object. As the name suggests, a node_handle is a handle to a node , which consists of an associative element and its related structures. The extract function disassociates the node, while leaving it in place, and returns a node_handle object. This has the effect of removing the node from the associative container without touching the data itself. The node_handle allows us to access the disassociated node.

The node_handle has a member function, key() , which returns a writable reference to the node key. This allows us to change the key, while it's disassociated from the container.

There's more…

There are a few things to keep in mind when using extract() and a node_handle :

• If the key is not found, the extract() function returns an empty node handle. You can test if a node handle is empty with the empty() function or with its boolean operator:

  auto node = mapthing.extract(key); if(node.empty()) {     // node handle is empty }

  or...

  if (!node) {     // node handle is empty }

• There are two overloads of the extract() function:

  node_type extract(const key_type& x); node_type extract(const_iterator position);

  We used the first form, by passing a key. You may also use an iterator, which should not require a lookup.

• Keep in mind that previous to C++23 you could not make a reference from a literal, so a call like extract(1) could crash with a segmentation fault
• Keys must remain unique when inserted into a map

  For example, if I try to change a key to a value already in the map:

  auto node_x = racers.extract(racers.begin()); node_x.key() = 5;  // 5 is Donkey Kong Jr auto status = racers.insert(move(node_x)); if (!status.inserted) {     println("insert failed, dup key: {}",         status.position->second); }

  The insert fails and we get the error message:

  insert failed, dup key: Donkey Kong Jr

  In this example I've passed the begin() iterator to extract() . I then assigned the key a value that's already in use ( 5 , Donkey Kong Jr ). The insert failed and the resulting status.inserted is false. status.position is an iterator to the found key. In the if() block, I used println() to print the value the inserted key.

Use unordered_map with custom keys

With an ordered map , the type of the key must be sortable, which means it must at least support the less-than < comparison operator. Suppose you want to use an associative container with a custom type that is not sortable. For example, a vector where (0, 1) is not smaller or larger than (1, 0) ; it simply points in a different direction. In such cases, you may use the unordered_map type. Let's look at how to do this.

How to do it

For this recipe we'll create an unordered_map object that uses x / y coordinates for the key. We will need a few support functions for this.

• First, we'll define a structure for the coordinates:

  struct Coord {     int x {};     int y {}; };

  This is a simple structure with two members, x and y , for the coordinates.

• Our map will use the Coord structure for the key, and an int for the value:

  using Coordmap = unordered_map<Coord, int>;

  The using alias makes it convenient to use our unordered_map .

• To use the Coord struct as a key, we need a couple of overloads. These are required for use with an unordered_map . First, we'll define an equality comparison operator:

  bool operator==(const Coord& lhs, const Coord& rhs) {     return lhs.x == rhs.x && lhs.y == rhs.y; }

  This is a simple function that compares x members and y members with each other.

• We also need a std::hash class specialization. This makes it possible to retrieve map elements with the key:

  namespace std {     template<>     struct hash<Coord> {         size_t operator()(const Coord& c) const noexcept {             size_t h1{std::hash<int>{}(c.x)};             size_t h2{std::hash<int>{}(c.y)};             return h1 ^ (h2 << 1);         }     }; }

  This provides a specialization for the default hash class used by the std::unordered_map class. It must be in the std namespace.

• We'll also write a print_Coordmap() function to print a Coordmap object:

  void print_Coordmap(const Coordmap& m) {     for (const auto& [key, value] : m) {         print("{{ ({}, {}): {} }} ",             key.x, key.y, value);     }     print("\n"); }

  This prints the x / y key and the value using the C++23 print() function. Notice the use of the double braces, {{ and }} , to print single braces.

• Now that we have all our support functions, we can write the main() function

  int main() {     Coordmap m {         { {0, 0}, 1 },         { {0, 1}, 2 },         { {2, 1}, 3 }     };     print_Coordmap(m); }

  Output:

  { (2, 1): 3 } { (0, 1): 2 } { (0, 0): 1 }

  Because it's an unordered map, the order of the elements may be different for you.

  At this point, we've defined a Coordmap object that accepts Coord objects for the keys and maps them to arbitrary values.

• We can also access individual members based on the Coord keys:

  Coord k{ 0, 1 }; print("{{ ({}, {}): {} }}\n", k.x, k.y, m.at(k));

  Output:

  { (0, 1): 2 }

  Here we define a Coord object named k , and we use that with the at() function to retrieve a value from the unordered_map .

How it works

The unordered_map class relies on a hash class to look up elements from the key. We normally instantiate an object like this:

std::unordered_map<key_type, value_type> my_map;

What's not obvious here is that, because we haven't defined one, unordered_map is using a default hash class . The full template type definition of the unordered_map class looks like this:

template<     class Key,     class T,     class Hash = std::hash<Key>,     class KeyEqual = std::equal_to<Key>,     class Allocator = std::allocator< std::pair<const Key,       T> > > class unordered_map;

The template provides default values for Hash , KeyEqual , and Allocator , so we don't always include them in our definitions. In our example, we've provided a specialization for the default std::hash class.

The STL contains specializations of std::hash for most of the standard types, like string , int , and so on. For it to work with our Coord class, we must provide a specialization.

We could have passed a functor to the template parameter, like this:

std::unordered_map<coord, value_type, my_hash_type> my_map;

That certainly would work. However, using a specialization for std::hash provides a more general solution which may be used with other hash-based containers, such as unordered_set , without repeatedly specifying a separate hash functor.

Sort and filter user input with set

The set class is an associative container where each element is a single value, which is both key and payload. Elements in a set are maintained in sorted order and duplicate elements are not allowed.

The set container is often misunderstood, and it does have fewer and more specific uses than more general containers such as vector and map . One common use for a set is to filter duplicates from a set of values.

How to do it

In this recipe we will read words from the standard input and filter out the duplicates.

• We start by defining an alias for an istream iterator. We'll use this to get input from the standard input.

  using input_it = istream_iterator<string>;

• In the main() function, we'll define a set for our words:

  set<string> words;

  The set is defined as a set of string elements.

• We define a pair of iterators for use with the inserter() function:

  input_it it {std::cin}; input_it end {};

  The end iterator is initialized with its default constructor. This is known as the end-of-stream iterator. At the end of input this iterator will compare equal with the cin iterator.

• The std::inserter() function is used to insert elements into the set container:

  std::copy(it, end, std::inserter(words, words.end()));

  We use std::copy() to conveniently copy words from the input stream.

• Now we can print out our set to see the results:

  for(const string & w : words) {        print("{} ", w); }  print("\n");

• We can run the program by piping a bunch of words to its input:

  $ echo "a a a b c this that this foo foo foo" | ./set-words a b c foo that this

  The set has eliminated the duplicates and retained a sorted list of the words that were inserted.

How it works

The set container is the heart of this recipe. It only holds unique elements. When you insert a duplicate, that insert will fail and you end up with a sorted list of each unique element.

But that's not the only interesting part of this recipe.

The istream_iterator is an input iterator that reads objects from a stream. We instantiated the input iterator like this:

istream_iterator<string> it {std::cin};

Now we have an input iterator of type string from the cin stream. Every time we dereference this iterator, it will return one word from the input stream.

We also instantiated another istream_iterator :

istream_iterator<string> end {};

This calls the default constructor, which gives us a special end-of-stream sentinel iterator. When the input iterator reaches the end of the stream, it will compare equal with the end sentinel. This is convenient for completing loops, such as the one created by the copy() algorithm.

The copy() algorithm takes three iterators: the beginning and end of the range to copy, and a destination iterator:

std::copy(it, end, std::inserter(words, words.end()));

The inserter() function takes a container and an iterator for the insertion point and returns an insert_iterator of the appropriate type for the container and its elements.

This combination of copy() and inserter() makes it easy to copy elements from a stream into the set container.

Create a simple RPN calculator with deque

In this recipe, we will build a simple RPN calculator using the std::deque container as a last-in, first-out (LIFO) stack.

A reverse polish notation (RPN) calculator is a stack-based calculator that uses postfix notation, where the operator follows the operands. It's commonly used in printing calculators and, notably, the most popular electronic calculator of all time, the HP 12C.

After becoming familiar with its operational modality, many people prefer an RPN calculator. (I've been using the HP 12C and 16C since they were first introduced in the early 1980s.) As an example of the difference between an algebraic and an RPN calculator, using conventional algebraic notation, to add 1 and 2 you would type 1 + 2 . Using RPN, you type 1 2 + . The operator comes after the operands.

Using an algebraic calculator, you press an = key to indicate that you want a result. With an RPN calculator this is unnecessary because the operator processes immediately, serving both purposes. On the other hand, an RPN calculator often requires an extra keypress ( Enter ) to push an operand onto the stack.

We can easily implement an RPN calculator using a stack-based data structure. For example, consider an RPN calculator with a four-position stack:

Figure 3.5: RPN addition operation

Each operand is pushed onto the stack as they are entered. When the operator is entered, the operands are popped off the stack, operated upon, and the result is pushed back onto the stack. The result may then be used in the next operation. For example, consider the case of (3+2)×3 :

Figure 3.6: RPN stack operations

One advantage of RPN is that you can leave operands on the stack for future calculations, reducing the need for separate memory registers. Consider the case of (9×6)+(2×3) :

Figure 3.7: RPN multiple stack operations

Notice that we first perform the operations within the parentheses, then the final operation on the intermediate results. This may seem more complex at first, but it makes a lot of sense once you get used to it.

Now, let's build a simple RPN calculator using the STL deque container.

How to do it

For this implementation, we'll use a deque container for our stack. Why not use a stack container? The stack class is a container-adapter, which uses another container (usually a deque ) for its storage. For our purposes, stack doesn't provide any tangible advantage over deque . And deque allows us to iterate over and display the RPN stack, like a paper tape calculator.

• First, we create a class to encapsulate our RPN calculator. There are a few advantages to using a class here. Encapsulation provides safety, reusability, extensibility, and a clean interface. We'll call this class RPN .

  class RPN {     deque<double> stk{};     constexpr static double zero {0.0};     constexpr static double inf         {std::numeric_limits<double>::infinity()}; ... };

  The deque data store, named stk , is in the private area of the class to protect it. This is where we store the RPN stack.

  The zero constant is used throughout the class, both as a return value and as a comparison operand. The inf constant is used for a divide-by-zero error. These constants are declared constexpr static so they don't take up space in every instance.

• We don't need an explicit constructor or destructor because the deque class manages its own resources. So, our public interface consists of just three functions:

  // process an operand/operator double op(const string & s) {     if (is_numeric(s)) {         double v{stod(s)};         stk.push_front(v);         return v;     }     else return optor(s); }  // empty the stack void clear() {     stk.clear(); }  // print the stack string get_stack_string() const {     string s{};     for(auto v : stk) {         s += format("{} ", v);     }     return s; }

  The double op() function is the main entry point for the RPN class. It takes a string , with either a number or an operator. If it's a number, it's converted to a double and pushed onto the stack. If it's an operator, we call optor() to perform the operation. This is the main logic of the class.

  The void clear() function simply calls clear() on the deque to empty the stack.

  And finally, the get_stack_string() function returns the contents of the stack in a string .

• In the private section, we have the supporting utilities that make the interface work. The pop_get2() function pops two operands from the stack and returns them as a pair. We use this as operands for the operators:

  pair<double, double> pop_get2() {     if (stk.size() < 2) return {zero, zero};     double v1 {stk.front()};     stk.pop_front();     double v2 {stk.front()};     stk.pop_front();     return {v2, v1}; }

• The is_numeric() function checks to see if the string is entirely numeric

      bool is_numeric(const string& s) {         size_t pos{};         try {             std::stod(s,&pos);             return pos == s.size();         }         catch (...) {             return false;         }     }

  The stod() function converts a string to a double . But in this case, we're simply using it to determine if a string is numeric. The stod() function throws an exception when it fails, so we simply catch any exception and return false for non-numeric values.

• The optor() function performs the operators. We use a map container to map an operator to a corresponding lambda function:

  double optor(const string& op) {     map<string, double (*)(double, double)> opmap {         {"+", [](double l, double r){ return l + r; }},         {"-", [](double l, double r){ return l - r; }},         {"*", [](double l, double r){ return l * r; }},         {"/", [](double l, double r){ return l / r; }},         {"^", [](double l, double r){ return pow(l, r); }},         {"%", [](double l, double r){ return fmod(l, r); }}     };      if (opmap.find(op) == opmap.end()) return zero;     auto [l, r] = pop_get2();      // don't divide by zero     if (op == "/" && r == zero) stk.push_front(inf);     else stk.push_front(opmap.at(op)(l, r));     return stk.front(); }

  The map container with lambda functions makes a quick and easy jump table. We use the find() function in map to test if we have a valid operator. After a test for divide-by-zero, the map is dereferenced, and the operator is called. The result of the operation is pushed onto the stack and returned.

• Those are all the function members of the RPN class. Now we can call it from our main() function:

  int main() {     RPN rpn;      for (string o{}; cin >> o; ) {         rpn.op(o);         auto stack_str = rpn.get_stack_string();         println("{}: {}", o, stack_str);     } }

  We test this is by piping a string into the program from the command line. We use a for loop to fetch each word from the cin stream and pass it to rpn.op() . I like the for loop here, as it's easy to contain the scope of the o variable. We then print the stack using the get_stack_string() function after each command line item.

• We can run the program by piping in an expression like this:

  $ echo "9 6 * 2 3 * +" | ./rpn 9: 9 6: 6 9 *: 54 2: 2 54 3: 3 2 54 *: 6 54 +: 60

This is actually quite simple. With the comments, the RPN class is less than 70 lines of code. The full rpn.cpp source code is in the GitHub repository.

How it works

The RPN class operates by first determining the nature of each chunk of input. If it's a number, we push it onto the stack. If it's an operator, we pop two operands off the top of the stack, apply the operation, and push the result back on the stack. If we don't recognize the input, we just ignore it.

The deque class is a double-ended queue. To use it as a stack, we pick an end and both push and pop from that same end. I chose the front end of the deque, but it would work just as well from the back . We just need to do everything from the same end.

If we determine that an input is numeric, we convert it to a double and push it onto the front of the deque using push_front() .

if (is_numeric(s)) {     double v {stod(s, nullptr)};     stk.push_front(v);     return v; }

When we need to use values from the stack, we pop them off the front of the deque . We use front() to get the value and then pop_front() to pop it off the stack.

    pair<double, double> pop_get2() {         if (stk.size() < 2) return {zero, zero};         double v1{stk.front()};         stk.pop_front();         double v2{stk.front()};         stk.pop_front();         return {v2, v1};     }

Using a map for our operators makes it easy to both check if an operator is valid and to execute the operation.

map<string, double (*)(double, double)> opmap {     {"+", [](double l, double r){ return l + r; }},     {"-", [](double l, double r){ return l - r; }},     {"*", [](double l, double r){ return l * r; }},     {"/", [](double l, double r){ return l / r; }},     {"^", [](double l, double r){ return pow(l, r); }},     {"%", [](double l, double r){ return fmod(l, r); }} };

We can test for the validity of an operator by using the find() function:

if (opmap.find(op) == opmap.end()) return zero;

Because opmap uses a lambda as its value, we can call the operator by dereferencing opmap with the at() function:

opmap.at(op)(l, r)

We both call the operator lambda and push the result onto the deque in one statement:

stk.push_front(opmap.at(op)(l, r));

There's more…

In this recipe, we use the cin stream to feed operations to the RPN calculator. It would be just as easy to do this with an STL container.

int main() {     RPN rpn;     vector<string> opv{ "9", "6", "*", "2", "3", "*", "+"       };     for(auto o : opv) {         rpn.op(o);         auto stack_str = rpn.get_stack_string();         println("{}: {}", o, stack_str);     } }

Output:

9: 9 6: 6 9 *: 54 2: 2 54 3: 3 2 54 *: 6 54 +: 60

By putting the RPN calculator in a class with a clean interface, we've created a flexible tool that can be used in many different contexts.

Count word frequency with map

This recipe uses the unique key property of the map container to count duplicate words from a stream of text.

The STL map container is an associative container. It consists of elements organized in key-value pairs . The keys are used for lookup and must be unique.

How to do it

There are a few parts to this task that we can solve separately.

1. We need to get the text from a file. We'll use the cin stream for this.
2. We need to separate words from punctuation and other non-word content. We'll use the regex (Regular Expression) library for this.
3. We need to count the frequency of each word. This is the main objective of the recipe. We'll use the STL map container for this.
4. Finally, we need to sort the results, first by frequency and then alphabetically by word within frequency. For this we'll use the STL sort algorithm with a vector container.

Even with all those tasks, the resulting code is relatively short, just about 70 lines with headers and all. Let's dive in:

• We'll start with some aliases for convenience:

  namespace ranges = std::ranges; namespace regex_constants = std::regex_constants;

  For namespaces within the std:: space, I like to make aliases that are shorter, but still let me know that I'm using a token in a particular namespace. Especially with the ranges namespace, which often re-uses the names of existing algorithms.

• We store the regular expression in a constant. I don't like to clutter up the global namespace because that can lead to collisions. I tend to use a namespace based on my initials for things like this:

  namespace bw {     constexpr const char * re {"(\\w+)"}; }

  It's easy enough to get it later using bw::re , and that tells me exactly what it is.

• At the top of main() , we define our data structures:

  map<string, int> wordmap {};   vector<pair<string, int>> wordvec {}; regex word_re(bw::re); size_t total_words {};

  Our main map is called wordmap . We have a vector named wordvec that we'll use as a sorting container. And finally, our regex class, word_re .

  Most of the work happens in a for loop. We read text from the cin stream, apply the regex , and store words in the map :

  for (string s {}; cin >> s; ) {     auto words_begin = sregex_iterator(s.begin(), s.end(),             word_re);     auto words_end = sregex_iterator();      for (auto r_it = words_begin; r_it != words_end;             ++r_it) {         smatch match {*r_it};         auto word_str = match.str();          ranges::transform(word_str, word_str.begin(),             [](unsigned char c){ return tolower(c); });          auto [map_it, result] =             wordmap.try_emplace(word_str, 0);         auto&[w,count]=*map_it;         ++total_words;         ++count;     } }

  I like a for loop for this because it allows me to contain the scope of the s variable.

  1. We start by defining iterators for the regex results. This allows us to distinguish multiple words even when surrounded only by punctuation. The for(r_it...) loop returns individual words from the cin string.
  2. The std::smatch type is a specialization of a regex string match class. It gives us the next word from our regex .
  3. We then use the transform algorithm to make the words lowercase – so we can count words regardless of case. (For example, "The" is the same word as "the" .)
  4. Next, we use try_emplace() to add the word to the map . If it's already there, it will not be replaced.
  5. Finally, we increment the count for the word in the map with ++count .

  Now we have the words and their frequency counts in our map . But they're in alphabetical order and we want them in descending order of frequency. For this, we put them in a vector and sort them:

  auto unique_words = wordmap.size(); wordvec.reserve(unique_words); ranges::move(wordmap, back_inserter(wordvec)); ranges::sort(wordvec, [](const auto& a, const auto& b) {     if (a.second != b.second)         return (a.second > b.second);     return (a.first < b.first); });  println("total word count: {}", total_words); println("unique word count: {}", unique_words);

  wordvec is a vector of pairs, with the word and the frequency count. We use the ranges::move() algorithm to populate the vector , then the ranges::sort() algorithm to sort the vector . Notice that the predicate lambda function sorts first by the count (descending) and then by the word (ascending).

• Finally, we print the results:

      for (int limit {20}; auto& [w, count] : wordvec) {         println("{}: {}", count, w);         if (--limit == 0) break;     }

  I set a limit to print only the first 20 entries. You can comment out the if(‑‑limit == 0) break; line to print the whole list.

• In the example files, I've included a text file with a copy of The Raven , by Edgar Allan Poe. This beautiful poem is in the public domain. We can use it to test the program:

  $ ./word-count < the-raven.txt total word count: 1098 unique word count: 439 56: the 38: and 32: i 24: my 21: of 17: that 17: this 15: a 14: door 11: chamber 11: is 11: nevermore 10: bird 10: on 10: raven 9: me 8: at 8: from 8: in 8: lenore

The Raven has 1,098 words total, and 439 of them are unique.

How it works

The core of this recipe is the use of a map object to count duplicate words. But there are other parts that merit consideration.

We use the cin stream to read text from the standard input . By default, cin will skip whitespace when reading into a string object. By putting a string object on the right-hand side of the >> operator ( cin >> s ) we get chunks of text separated by whitespace. This is a good enough definition of a word-at-a-time for many purposes, but we need linguistic words. And for that we will use a regular expression.

The regex class provides a choice of regular expression grammars and it defaults to ECMA grammar. In the ECMA grammar, the regular expression "(\w+)" is a shortcut for "([A‑Za‑z0‑9_]+)" . This will select words that include the Latin/Roman alphabet, both upper- and lower-case, the ten Arabic numerals, and the underscore _ character.

As we get each word from the regex engine, we use the map object's try_emplace() method to conditionally add the word to our wordmap . If the word is not in the map, we add it with a count of 0 . If the word is already in the map, the count is untouched. We increment the count later in the loop, so it's always correct.

After the map is populated with all the unique words from the file, we transfer it to a vector using the ranges::move() algorithm. The move() algorithm makes this transfer quick and efficient. Then we can sort the vector using ranges::sort() . The predicate lambda function for sorting includes comparisons for both sides of the pair , so we end up with a result that's sorted by both word count (descending) and the word itself (ascending).

Find long sentences with a vector of vectors

It can be useful for a writer to make sure they are using a variety of sentence lengths, or to ensure none of their sentences are too long. Let's build a tool that evaluates a text file for sentence length.

Choosing the appropriate container is key when using the STL. If you need something ordered, it's often best to use an associative container, such as map or multimap . In this case, however, since we need a custom sort, it's easier to sort a vector .

The vector is generally the most flexible of the STL containers. Whenever another container type seems appropriate, but is missing one important capability, the vector is often an effective solution. In this case, where we need a custom sort, the vector works great.

This recipe uses a vector of vectors . The inner vector stores the words of a sentence, and the outer vector stores the inner vectors . As you'll see, this affords a lot of flexibility while retaining all the relevant data.

How to do it

This program needs to read words from stdin , find the ends of sentences, store and sort the sentences, then print out the results.

• In main() , we start by defining the vector of vectors :

  vector<vector<string>> vv_sentences(1);

  This defines a vector of elements typed vector<string> named vv_sentences . The vv_sentences object is initialized with one empty vector for the first sentence. The inner vectors will each hold a sentence of words.

• Now we can process the stream of words:

  for (string s{}; cin >> s; ) {     vv_sentences.back().emplace_back(s);     if (is_eos(s)) {                vv_sentences.emplace_back()     } }

  The for loop returns one word at a time from the input stream. The back() method on the vv_sentences object is used to access the current vector of words, and the current word is added using emplace_back() . Then we call is_eos() to see if this was the end of a sentence. If so, we add a new empty vector to vv_sentences to start the next sentence.

• Because we always add a new empty vector to the end of vv_sentences after each end-of-sentence character, we will usually end up with an empty sentence vector at the end. Here we check for this, and delete it if necessary:

  // delete back if empty if (vv_sentences.back().empty())     vv_sentences.pop_back();

• Now we can sort the vv_sentences vector by the size of the sentences:

  sort(vv_sentences, [](const auto& l, const auto& r) {         return l.size() > r.size();     });

  This is why the vector is so convenient for this project. It's quick and easy to sort using the ranges::sort() algorithm with a simple predicate lambda for sorting by size in descending order.

• Now we can print our result:

  for (const auto& v : vv_sentences) {     constexpr auto WLIMIT = 10;     size_t size = v.size();     size_t limit {WLIMIT};     print("{}: ", size);     for (const auto& s : v) {         print("{} ", s);         if (--limit == 0) {             if (size > WLIMIT) print("...");             break;         }     }     print("\n"); } print("\n");

  The outer loop and the inner loop correspond to the outer and inner vectors. We simply loop through the vectors and print out the size of the inner vector with print("{}: ", size) and then each word with print("{} ", s) . We don't want to print the very long sentences in their entirety, so we define a limit of 10 words and print an ellipsis if there's more.

• The output looks like this, using the first few paragraphs of this recipe for input:

  $ ./sentences < sentences.txt 27: It can be useful for a writer to make sure ... 19: Whenever another container type seems appropriate, but is missing one ... 18: If you need something ordered, it's often best to use ... 17: The inner vector stores the words of a sentence, and ... 16: In this case, however, since we need a descending sort, ... 16: In this case, where we need our output sorted in ... 15: As you'll see, this affords a lot of flexibility while ... 12: Let's build a tool that evaluates a text file for ... 11: The vector is generally the most flexible of the STL ... 9: Choosing the appropriate container key when using the STL. 7: This recipe uses a vector of vectors.

How it works

We read the text file one word at a time using cin :

for (string s{}; cin >> s; ) {     ... }

This avoids the overhead of reading a large file into memory all at once. The vector will already be large, containing all the words of the file. It's not necessary to also hold the entire text file in memory. In the rare case that a file is too large, it would be necessary to find another strategy or use a database.

Finding punctuation is simple using the find_first_of() method in the string class:

for (string s {}; cin >> s; ) {     vv_sentences.back().emplace_back(s);     if (s.find_first_of(end_punct) != s.npos) {         vv_sentences.emplace_back();     } }

This provides a simple and efficient method of separating sentences.

The vector of vectors may look complex at first glance, but it's no more complicated than using two separate vectors:

vector<vector<string>> vv_sentences {vector<string>{}};

This declares an outer vector , with inner elements of type vector<string> . The outer vector is named vv_sentences . The inner vectors are anonymous; they require no name. This definition initializes the vv_sentences object with one element, an empty vector<string> object.

The current inner vector will always be available as vv_sentences.back() :

vv_sentences.back().emplace_back(s);

When we've completed one inner vector , we simply create a new one with:

vv_sentences.emplace_back();

This creates a new anonymous vector<string> object and emplaces it at the back of the vv_sentences object.

Create an efficient ToDo list using multimap

An ordered task list (or a ToDo list ) is a common computing application. Formally stated, it's a list of tasks associated with a priority, sorted in reverse numerical order.

You may be tempted to use a priority_queue for this, because as the name implies, it's already sorted in priority (reverse numerical) order. The disadvantage of a priority_queue is that it has no iterators, so it's difficult to operate upon individual elements without pushing and popping items to and from the queue.

For this recipe, we'll use a multimap for the ordered list. The multimap is an associative container which keeps items in order, and it can be accessed using reverse iterators for the proper sort order.

How to do it

This is a short and simple recipe that initializes a multimap and prints it in reverse order.

• We start with a type alias for our multimap :

  using todomap = multimap<int, string>;

  Our todomap is a multimap with an int key and a string payload.

• And we use a namespace alias for ranges :

  namespace views = std::views;

• We use a small utility function for printing the todomap in reverse order:

  void rprint(const todomap& todo) {     for (auto const& [priority, task] :       todo | views::reverse) {         println("{}: {}", priority, task);     }     print("\n"); }

  This uses views::reverse view to print the todomap in reverse order.

  The main() function is short and sweet:

  int main() {     todomap todo {         {1, "wash dishes"},         {0, "watch teevee"},         {2, "do homework"},         {0, "read comics"}     };     rprint(todo); }

  We initialize the todomap with tasks. Notice that the tasks are not in any particular order, but they do have assigned priority values in their keys. The rprint() function will print them in descending priority order.

• The output looks like this:

  $ ./todo 2: do homework 1: wash dishes 0: read comics 0: watch teevee

  The ToDo list prints out in priority order, just as we need it.

How it works

This is a short and simple recipe. It uses a multimap container to hold items for a prioritized list.

The only trick is in the rprint() function:

void rprint(const todomap& todo) {     for (auto const& [priority, task] : todo | views::reverse) {         println("{}: {}", priority, task);     }     print("\n"); }

While it's not possible to change the sort order of a multimap, views::reverse provides a reverse-ordered view that allows us to print our prioritized list in descending order.

Subscribe to Deep Engineering

Join thousands of developers and architects who want to understand how software is changing, deepen their expertise, and build systems that last.

Deep Engineering is a weekly expert-led newsletter for experienced practitioners, featuring original analysis, technical interviews, and curated insights on architecture, system design, and modern programming practice.

Scan the QR or visit the link to subscribe for free.