13
CONTAINERS

Fixing bugs in std::vector is equal parts delight (it is the bestest data structure) and terror (if I mess it up, the world explodes).
—Stephan T. Lavavej (Principal Developer, Visual C++ Libraries). Tweet dated 3:11 am on August 22, 2016.

The standard template library (STL) is the portion of the stdlib that provides containers and the algorithms to manipulate them, with iterators serving as the interface between the two. In the next three chapters, you’ll learn more about each of these components.

A container is a special data structure that stores objects in an organized way that follows specific access rules. There are three kinds of containers:

• Sequence containers store elements consecutively, as in an array.
• Associative containers store sorted elements.
• Unordered associative containers store hashed objects.

Associative and unordered associative containers offer rapid search for individual elements. All containers are RAII wrappers around their contained objects, so they manage the storage durations and lifetimes of the elements they own. Additionally, each container provides some set of member functions that perform various operations on the object collection.

Modern C++ programs use containers all the time. Which container you choose for a particular application depends on the required operations, the contained objects’ characteristics, and efficiencies under particular access patterns. This chapter surveys the vast container landscape covered between the STL and Boost. Because there are so many containers in these libraries, you’ll explore the most popular ones.

Sequence Containers

Sequence containers are STL containers that allow sequential member access. That is, you can start from one end of the container and iterate through to the other end. But except for this commonality, sequence containers are a varied and motley crew. Some containers have a fixed length; others can shrink and grow as program needs dictate. Some allow indexing directly into the container, whereas you can only access others sequentially. Additionally, each sequence container has unique performance characteristics that make it desirable in some situations and undesirable in others.

Working with sequence containers should feel intuitive because you’ve been acquainted with a primitive one since “Arrays” on page 42, where you saw the built-in or “C-style” array T[]. You’ll begin the survey of sequence containers by looking at the built-in array’s more sophisticated, cooler younger brother std::array.

Arrays

The STL provides std::array in the <array> header. An array is a sequential container that holds a fixed-size, contiguous series of elements. It combines the sheer performance and efficiency of built-in arrays with the modern conveniences of supporting copy/move construction/assignment, knowing its own size, providing bounds-checked member access, and other advanced features.

You should use array instead of built-in arrays in virtually all situations. It supports almost all the same usage patterns as operator[] to access elements, so there aren’t many situations in which you’ll need a built-in array instead.

Constructing

The array<T, S > class template takes two template parameters:

• The contained type T
• The fixed size of the array S

You can construct an array and built-in arrays using the same rules. To summarize these rules from “Arrays” on page 42, the preferred method is to use braced initialization to construct an array. Braced initialization fills the array with the values contained in the braces and fills the remaining elements with zeros. If you omit initialization braces, the array contains uninitialized values depending on its storage duration. Listing 13-1 illustrates braced initialization with several array declarations.

#include <array>

std::array<int, 10> static_array; ➊

TEST_CASE("std::array") {
  REQUIRE(static_array[0] == 0); ➋

  SECTION("uninitialized without braced initializers") {
    std::array<int, 10> local_array; ➌
    REQUIRE(local_array[0] != 0); ➍
  }

  SECTION("initialized with braced initializers") {
    std::array<int, 10> local_array{ 1, 1, 2, 3 }; ➎
    REQUIRE(local_array[0] == 1);
    REQUIRE(local_array[1] == 1);
    REQUIRE(local_array[2] == 2);
    REQUIRE(local_array[3] == 3);
    REQUIRE(local_array[4] == 0); ➏
  }
}

Listing 13-1: Initializing a std::array. You might get compiler warnings from REQUIRE(local_array[0] != 0); ➍, since local_array has uninitialized elements.

You declare an array of 10 int objects called static_array with static storage duration ➊. You haven’t used braced initialization, but its elements initialize to zero anyway ➋, thanks to the initialization rules covered in “Arrays” on page 42.

Next, you try declaring another array of 10 int objects, this time with automatic storage duration ➌. Because you haven’t used braced initialization, local_array contains uninitialized elements (that have an extremely low probability of equaling zero ➍).

Finally, you use braced initialization to declare another array and to fill the first four elements ➎. All remaining elements get set to zero ➏.

Element Access

The three main methods by which you can access arbitrary array elements are:

• operator[]
• at
• get

The operator[] and at methods take a single size_t argument corresponding to the index of the desired element. The difference between these two lies in bounds checking: if the index argument is out of bounds, at will throw a std::out_of_range exception, whereas operator[] will cause undefined behavior. The function template get takes a template parameter of the same specification. Because it’s a template, the index must be known at compile time.

A major bonus of using get is that you get compile-time bounds checking, as illustrated in Listing 13-2.

TEST_CASE("std::array access") {
   std::array<int, 4> fib{ 1, 1, 0, 3}; ➊

  SECTION("operator[] can get and set elements") {
    fib[2] = 2; ➋
    REQUIRE(fib[2] == 2); ➌
    // fib[4] = 5; ➍
  }

  SECTION("at() can get and set elements") {
    fib.at(2) = 2; ➎
    REQUIRE(fib.at(2) == 2); ➏
    REQUIRE_THROWS_AS(fib.at(4), std::out_of_range); ➐
  }
  SECTION("get can get and set elements") {
    std::get<2>(fib) = 2; ➑
    REQUIRE(std::get<2>(fib) == 2); ➒
    // std::get<4>(fib); ➓
  }
}

Listing 13-2: Accessing elements of an array. Uncommenting // fib[4] = 5; ➍ will cause undefined behavior, whereas uncommenting // std::get<4>(fib); ➓ will cause compilation failure.

You declare an array of length 4 called fib ➊. Using operator[] ➋ you can set elements and retrieve them ➌. The out of bounds write you’ve commented out would cause undefined behavior; there is no bounds checking with operator[] ➍.

You can use at for the same read ➎ and write ➏ operations, and you can safely perform an out-of-bounds operation thanks to bounds checking ➐.

Finally, you can use std::get to set ➑ and get ➒ elements. The get element also performs bounds checking, so // std::get<4>(fib); ➓ will fail to compile if uncommented.

You’ve also have a front and a back method, which return references to the first and last elements of the array. You’ll get undefined behavior if you call one of these methods if the array has zero length, as Listing 13-3 illustrates.

TEST_CASE("std::array has convenience methods") {
  std::array<int, 4> fib{ 0, 1, 2, 0 };

  SECTION("front") {
    fib.front() = 1; ➊
    REQUIRE(fib.front() == 1); ➋
    REQUIRE(fib.front() == fib[0]); ➌
  }

  SECTION("back") {
    fib.back() = 3; ➍
    REQUIRE(fib.back() == 3); ➎
    REQUIRE(fib.back() == fib[3]); ➏
  }
}

Listing 13-3: Using the convenience methods front and back on a std::array

You can use the front and back methods to set ➊➍ and get ➋➎ the first and last elements of an array. Of course, fib[0] is identical to fib.front() ➌, and fib[3] is identical to fib.back() ➏. The front() and back() methods are simply convenience methods. Additionally, if you’re writing generic code, some containers will offer front and back but not operator[], so it’s best to use the front and back methods.

Storage Model

An array doesn’t make allocations; rather, like a built-in array, it contains all of its elements. This means copies will generally be expensive, because each constituent element needs to be copied. Moves can be expensive, depending on whether the underlying type of the array also has move construction and move assignment, which are relatively inexpensive.

Each array is just a built-in array underneath. In fact, you can extract a pointer to the first element of an array using four distinct methods:

• The go-to method is to use the data method. As advertised, this returns a pointer to the first element.
• The other three methods involve using the address-of operator & on the first element, which you can obtain using operator[], at, and front.

You should use data. If the array is empty, the address-of-based approaches will return undefined behavior.

Listing 13-4 illustrates how to obtain a pointer using these four methods.

TEST_CASE("We can obtain a pointer to the first element using") {
  std::array<char, 9> color{ 'o',  'c', 't', 'a', 'r', 'i', 'n', 'e' };
  const auto* color_ptr = color.data(); ➊

  SECTION("data") {
    REQUIRE(*color_ptr == 'o'); ➋
  }
  SECTION("address-of front") {
    REQUIRE(&color.front() == color_ptr); ➌
  }
  SECTION("address-of at(0)") {
    REQUIRE(&color.at(0) == color_ptr); ➍
  }
  SECTION("address-of [0]") {
    REQUIRE(&color[0] == color_ptr); ➎
  }
}

Listing 13-4: Obtaining a pointer to the first element of a std::array

After initializing the array color, you obtain a pointer to the first element, the letter o, using the data method ➊. When you dereference the resulting color_ptr, you obtain the letter o as expected ➋. This pointer is identical to the pointer obtained from the address-of-plus-front ➌, -at ➍, and -operator[] ➎ approaches.

To conclude arrays, you can query the size of an array using either the size or max_size methods. (These are identical for an array.) Because an array has a fixed size, these method’s values are static and known at compile time.

A Crash Course in Iterators

The interface between containers and algorithms is the iterator. An iterator is a type that knows the internal structure of a container and exposes simple, pointer-like operations to a container’s elements. Chapter 14 is dedicated entirely to iterators, but you need to know the very basics here so you can explore how to use iterators to manipulate containers and how containers expose iterators to users.

Iterators come in various flavors, but they all support at least the following operations:

1. Get the current element (operator*)
2. Go to the next element (operator++)
3. Assign an iterator equal to another iterator (operator=)

You can extract iterators from all STL containers (including array) using their begin and end methods. The begin method returns an iterator pointing to the first element, and the end method returns a pointer to one element past the last element. Figure 13-1 illustrates where the begin and end iterators point in an array of three elements.

Figure 13-1: A half-open range over an array of three elements

The arrangement in Figure 13-1, where end() points after the last element, is called a half-open range. It might seem counterintuitive at first—why not have a closed range where end() points to the last element—but a half-open range has some advantages. For example, if a container is empty, begin() will return the same value as end(). This allows you to know that, regardless of whether the container is empty, if the iterator equals end(), you’ve traversed the container.

Listing 13-5 illustrates what happens with half-open range iterators and empty containers.

TEST_CASE("std::array begin/end form a half-open range") {
  std::array<int, 0> e{}; ➊
  REQUIRE(e.begin()➋ == e.end()➌);
}

Listing 13-5: With an empty array, the begin iterator equals the end iterator.

Here, you construct an empty array e ➊, and the begin ➋ and end ➌ iterators are equal.

Listing 13-6 examines how to use iterators to perform pointer-like operations over a non-empty array.

TEST_CASE("std::array iterators are pointer-like") {
  std::array<int, 3> easy_as{ 1, 2, 3 }; ➊
  auto iter = easy_as.begin(); ➋
  REQUIRE(*iter == 1); ➌
  ++iter; ➍
  REQUIRE(*iter == 2);
  ++iter;
  REQUIRE(*iter == 3); ➎
  ++iter; ➏
  REQUIRE(iter == easy_as.end()); ➐
}

Listing 13-6: Basic array iterator operations

The array easy_as contains the elements 1, 2, and 3 ➊. You invoke begin on easy_as to obtain an iterator iter pointing to the first element ➋. The dereference operator yields the first element 1, because this is the first element in the array ➌. Next, you increment iter so it points to the next element ➍. You continue in this fashion until you reach the last element ➎. Incrementing the pointer one last time puts you 1 past the last element ➏, so iter equals easy_as.end(), indicating that you’ve traversed the array ➐.

Recall from “Range Expressions” on page 235 that you can build your own types for use in range expressions by exposing a begin and an end method, as implemented in the FibonacciIterator in Listing 8-29. Well, containers already do all this work for you, meaning you can use any STL container as a range expression. Listing 13-7 illustrates by iterating over an array.

TEST_CASE("std::array can be used as a range expression") {
  std::array<int, 5> fib{ 1, 1, 2, 3, 5 }; ➊
  int sum{}; ➋
  for (const auto element : fib) ➌
    sum += element; ➍
  REQUIRE(sum == 12);
}

Listing 13-7: Range-based for loops and arrays

You initialize an array ➊ and a sum variable ➋. Because array is a valid range, you can use it in a ranged-based for loop ➌. This enables you to accumulate the sum of each element ➍.

A Partial List of Supported Operations

Table 13-1 provides a partial list of array operations. In this table, a, a1, and a2 are of type std::array<T, S>, t is of type T, S is the fixed length of the array, and i is of type size_t.

Table 13-1: A Partial List of std::array Operations

Vectors

The std::vector available in the STL’s <vector> header is a sequential container that holds a dynamically sized, contiguous series of elements. A vector manages its storage dynamically, requiring no outside help from the programmer.

The vector is the workhorse of the sequential-data-structure stable. For a very modest overhead, you gain substantial flexibility over the array. Plus, vector supports almost all of the same operations as an array and adds a slew of others. If you have a fixed number of elements on hand, you should strongly consider an array because you’ll get some small reductions in overhead versus a vector. In all other situations, your go-to sequential container is the vector.

Constructing

The class template std::vector<T, Allocator> takes two template parameters. The first is the contained type T, and the second is the allocator type Allocator, which is optional and defaults to std::allocator<T>.

You have much more flexibility in constructing vectors than you do with arrays. A vector supports user-defined allocators because vectors need to allocate dynamic memory. You can default construct a vector so it contains no elements. You might want to construct an empty vector so you can fill it with a variable number of elements depending on what happens during runtime. Listing 13-8 illustrates default constructing a vector and checking that it contains no elements.

#include <vector>
TEST_CASE("std::vector supports default construction") {
  std::vector<const char*➊> vec; ➋
  REQUIRE(vec.empty()); ➌
}

Listing 13-8: A vector supports default construction.

You declare a vector containing elements of type const char* ➊ called vec. Because it’s been default constructed ➋, the vector contains no elements, and the empty method returns true ➌.

You can use braced initialization with a vector. Similar to how you brace initialize an array, this fills the vector with the specified elements, as Listing 13-9 illustrates.

TEST_CASE("std::vector supports braced initialization ") {
    std::vector<int> fib{ 1, 1, 2, 3, 5 }; ➊
    REQUIRE(fib[4] == 5); ➋
}

Listing 13-9: A vector supports braced initializers.

Here, you construct a vector called fib and use braced initializers ➊. After initialization, the vector contains the five elements 1, 1, 2, 3, and 5 ➋.

If you want to populate a vector with many identical values, you can use one of the fill constructors. To fill construct a vector, you first pass a size_t corresponding to the number of elements you want to fill. Optionally, you can pass a const reference to an object to copy. Sometimes you want to initialize all your elements to the same value, for example, to keep track of counts related to particular indices. You might also have a vector of some user-defined type that keeps track of program state, and you might need to keep track of such state by index.

Unfortunately, the general rule to use braced initialization to construct objects breaks down here. With vector, you must use parentheses to invoke these constructors. To the compiler, std::vector<int>{ 99, 100 } specifies an initialization list with the elements 99 and 100, which will construct a vector with the two elements 99 and 100. What if you want a vector with 99 copies of the number 100?

In general, the compiler will try very hard to treat the initializer list as elements to fill the vector with. You can try to memorize the rules (refer to Item 7 of Effective Modern C++ by Scott Meyers) or just commit to using parentheses for stdlib container constructors.

Listing 13-10 highlights the initializer list/braced initialization general rule for STL containers.

TEST_CASE("std::vector supports") {
  SECTION("braced initialization") {
    std::vector<int> five_nine{ 5, 9 }; ➊
    REQUIRE(five_nine[0] == 5); ➋
    REQUIRE(five_nine[1] == 9); ➌
  }
  SECTION("fill constructor") {
    std::vector<int> five_nines(5, 9); ➍
    REQUIRE(five_nines[0] == 9); ➎
    REQUIRE(five_nines[4] == 9); ➏
  }
}

Listing 13-10: A vector supports braced initializers and fill constructors.

The first example uses braced initialization to construct a vector with two elements ➊: 5 at index 0 ➋ and 9 at index 1 ➌. The second example uses parentheses to invoke the fill constructor ➍, which fills the vector with five copies of the number 9, so the first ➎ and last ➏ elements are both 9.

You can also construct vectors from a half-open range by passing in the begin and end iterators of the range you want to copy. In various programming contexts, you might want to splice out a subset of some range and copy it into a vector for further processing. For example, you could construct a vector that copies all the elements contained by an array, as in Listing 13-11.

TEST_CASE("std::vector supports construction from iterators") {
  std::array<int, 5> fib_arr{ 1, 1, 2, 3, 5 }; ➊
  std::vector<int> fib_vec(fib_arr.begin(), fib_arr.end()); ➋
  REQUIRE(fib_vec[4] == 5); ➌
  REQUIRE(fib_vec.size() == fib_arr.size()); ➍
}

Listing 13-11: Constructing a vector from a range

You construct the array fib_arr with five elements ➊. To construct the vector fib_vec with the elements contained in fib_arr, you invoke the begin and end methods on fib_arr ➋. The resulting vector has copies of the array’s elements ➌ and has the same size ➍.

At a high level, you can think of this constructor as taking pointers to the beginning and the end of some target sequence. It will then copy that target sequence.

Move and Copy Semantics

With vectors, you have full copy/move construction/assignment support. Any vector copy operation is potentially very expensive, because these are element-wise or deep copies. Move operations, on the other hand, are usually very fast, because the contained elements reside in dynamic memory and the moved-from vector can simply pass ownership to the moved-into vector; there’s no need to move the contained elements.

Element Access

A vector supports most of the same element access operations as array: at, operator[], front, back, and data.

As with an array, you can query the number of contained elements in a vector using the size method. This method’s return value can vary at runtime. You can also determine whether a vector contains any elements with the empty method, which returns true if the vector contains no elements; otherwise, it returns false.

Adding Elements

You can use various methods to insert elements into a vector. If you want to replace all the elements in a vector, you can use the assign method, which takes an initialization list and replaces all the existing elements. If needed, the vector will resize to accommodate a larger list of elements, as Listing 13-12 illustrates.

TEST_CASE("std::vector assign replaces existing elements") {
  std::vector<int> message{ 13, 80, 110, 114, 102, 110, 101 }; ➊
  REQUIRE(message.size() == 7); ➋
  message.assign({ 67, 97, 101, 115, 97, 114 }); ➌
  REQUIRE(message[5] == 114); ➍
  REQUIRE(message.size() == 6); ➎
}

Listing 13-12: The assign method of a vector

Here, you construct a vector ➊ with seven elements ➋. When you assign a new, smaller initializer list ➌, all the elements get replaced ➍, and the vector’s size updates to reflect the new contents ➎.

If you want to insert a single new element into a vector, you can use the insert method, which expects two arguments: an iterator and an element to insert. It will insert a copy of the given element just before the existing element pointed to by the iterator, as shown in Listing 13-13.

TEST_CASE("std::vector insert places new elements") {
  std::vector<int> zeros(3, 0); ➊
  auto third_element = zeros.begin() + 2; ➋
  zeros.insert(third_element, 10); ➌
  REQUIRE(zeros[2] == 10); ➍
  REQUIRE(zeros.size() == 4); ➎
}

Listing 13-13: The insert method of a vector

You initialize a vector with three zeros ➊ and generate an iterator pointing to the third element of zeros ➋. Next, you insert the value 10 immediately before the third element by passing the iterator and the value 10 ➌. The third element of zeros is now 10 ➍. The zeros vector now contains four elements ➎.

Any time you use insert, existing iterators become invalid. For example, in Listing 13-13 you must not reuse third_element: the vector could have resized and relocated in memory, leaving the old iterator dangling in garbage memory.

To insert an element to the end of a vector, you use the push_back method. Unlike insert, push_back doesn’t require an iterator argument. You simply provide the element to copy into the vector, as shown in Listing 13-14.

TEST_CASE("std::vector push_back places new elements") {
  std::vector<int> zeros(3, 0); ➊
  zeros.push_back(10); ➋
  REQUIRE(zeros[3] == 10); ➌
}

Listing 13-14: The push_back method of a vector

Again, you initialize a vector with three zeros ➊, but this time you insert the element 10 to the back of the vector using the push_back method ➋. The vector now contains four elements, the last of which equals 10 ➌.

You can construct new elements in place using the emplace and emplace_back methods. The emplace method is a variadic template that, like insert, accepts an iterator as its first argument. The remaining arguments get forwarded to the appropriate constructor. The emplace_back method is also a variadic template, but like push_back, it doesn’t require an iterator. It accepts any number of arguments and forwards those to the appropriate constructor. Listing 13-15 illustrates these two methods by emplacing a few pairs into a vector.

#include <utility>

TEST_CASE("std::vector emplace methods forward arguments") {
  std::vector<std::pair<int, int>> factors; ➊
  factors.emplace_back(2, 30); ➋
  factors.emplace_back(3, 20); ➌
  factors.emplace_back(4, 15); ➍
  factors.emplace(factors.begin()➎, 1, 60);
  REQUIRE(factors[0].first == 1); ➏
  REQUIRE(factors[0].second == 60); ➐
}

Listing 13-15: The emplace_back and emplace methods of a vector

Here, you default construct a vector containing pairs of ints ➊. Using the emplace_back method, you push three pairs onto the vector: 2, 30 ➋; 3, 20 ➌; and 4, 15 ➍. These values get forwarded directly to the constructor of pair, which gets constructed in place. Next, you use emplace to insert a new pair at the beginning of the vector by passing the result of factors.begin() as the first argument ➎. This causes all the elements in the vector to shift down to make room for the new pair (1 ➏, 60 ➐).

Because the emplacement methods can construct elements in place, it seems they should be more efficient than the insertion methods. This intuition is often correct, but for complicated and unsatisfying reasons it’s not always faster. As a general rule, use the emplacement methods. If you determine a performance bottleneck, also try the insertion methods. See Item 42 of Effective Modern C++ by Scott Meyers for a treatise.

Storage Model

Although vector elements are contiguous in memory, like an array, the similarities stop there. A vector has dynamic size, so it must be able to resize. The allocator of a vector manages the dynamic memory underpinning the vector.

Because allocations are expensive, a vector will request more memory than it needs to contain the current number of elements. Once it can no longer add any more elements, it will request additional memory. The memory for a vector is always contiguous, so if there isn’t enough space at the end of the existing vector, it will allocate a whole new region of memory and move all the elements of the vector into the new region. The number of elements a vector holds is called its size, and the number of elements it could theoretically hold before having to resize is called its capacity. Figure 13-2 illustrates a vector containing three elements with additional capacity for three more.

Figure 13-2: The vector storage model

As Figure 13-2 shows, the vector continues past the last element. The capacity determines how many elements the vector could hold in this space. In this figure, the size is three and the capacity is six. You can think of the memory in a vector as an auditorium: it might have a capacity of 500 but a crowd size of only 250.

The upshot of this design is that inserting at the end of a vector is extremely fast (unless the vector needs to resize). Inserting anywhere else incurs additional cost, because the vector needs to move elements around to make room.

You can obtain the vector’s current capacity via the capacity method, and you can obtain the absolute maximum capacity that a vector could resize to with the max_size method.

If you know ahead of time that you’ll need a certain capacity, you can use the reserve method, which takes a single size_t argument corresponding to the number of elements you want capacity for. On the other hand, if you’ve just removed several elements and want to return memory to the allocator, you can use the shrink_to_fit method, which declares that you have excess capacity. The allocator can decide to reduce capacity or not (it’s a non-binding call).

Additionally, you can delete all the elements in a vector and set its size to zero using the clear method.

Listing 13-16 demonstrates all these storage-related methods in a cohesive story: you create an empty vector, reserve a bunch of space, add some elements, release excess capacity, and finally empty the vector.

#include <cstdint>
#include <array>

TEST_CASE("std::vector exposes size management methods") {
  std::vector<std::array<uint8_t, 1024>> kb_store; ➊
  REQUIRE(kb_store.max_size() > 0);
  REQUIRE(kb_store.empty()); ➋

  size_t elements{ 1024 };
  kb_store.reserve(elements); ➌
  REQUIRE(kb_store.empty());
  REQUIRE(kb_store.capacity() == elements); ➍

  kb_store.emplace_back();
  kb_store.emplace_back();
  kb_store.emplace_back();
  REQUIRE(kb_store.size() == 3); ➎

  kb_store.shrink_to_fit();
  REQUIRE(kb_store.capacity() >= 3); ➏

  kb_store.clear(); ➐
  REQUIRE(kb_store.empty());
  REQUIRE(kb_store.capacity() >= 3); ➑
}

Listing 13-16: The storage management functions of a vector. (Strictly speaking, kb_store.capacity() >= 3 ➏ ➑ is not guaranteed because the call is non-binding.)

You construct a vector of array objects called kb_store, which stores 1 KiB chunks ➊. Unless you’re using a peculiar platform with no dynamic memory, kb_store.max_size() will be greater than zero; because you default initialize the vector, it’s empty ➋.

Next, you reserve 1,024 elements ➌, which doesn’t change the vector’s empty status but increases its capacity to match ➍. The vector now has 1,024 × 1 KiB = 1 MiB of contiguous space reserved. After reserving space, you emplace three arrays and check that kb_store.size() increased accordingly ➎.

You’ve reserved space for 1,024 elements. To release the 1,024 – 3 = 1,021 elements you aren’t using back to the allocator, you call shrink_to_fit, which reduces the capacity to 3 ➏.

Finally, you invoke clear on the vector ➐, which destructs all elements and reduces its size to zero. However, the capacity remains unchanged because you haven’t made another call to shrink_to_fit ➑. This is significant because the vector doesn’t want to do extra work if you’re going to add elements again.

A Partial List of Supported Operations

Table 13-2 provides a partial list of vector operations. In this table, v, v1, and v2 are of type std::vector<T>, t is of type T, alc is an appropriate allocator, and itr is an iterator. An asterisk (*) indicates that this operation invalidates raw pointers and iterators to v’s elements in at least some circumstances.

Table 13-2: A Partial List of std::vector Operations

Niche Sequential Containers

The vector and array containers are the clear choice in most situations in which you need a sequential data structure. If you know the number of elements you’ll need ahead of time, use an array. If you don’t, use a vector.

You might find yourself in a niche situation where vector and array don’t have the performance characteristics you desire. This section highlights a number of alternative sequential containers that might offer superior performance characteristics in such a situation.

Deque

A deque (pronounced “deck”) is a sequential container with fast insert and remove operations from the front and back. Deque is a portmanteau of double-ended queue. The STL implementation std::deque is available from the <deque> header.

A vector and a deque have very similar interfaces, but internally their storage models are totally different. A vector guarantees that all elements are sequential in memory, whereas a deque’s memory is usually scattered about, like a hybrid between a vector and a list. This makes large resizing operations more efficient and enables fast element insertion/deletion at the container’s front.

Constructing and accessing members are identical operations for vectors and deques.

Because the internal structure of deque is complex, it doesn’t expose a data method. In exchange, you gain access to push_front and emplace_front, which mirror the push_back and emplace_back that you’re familiar with from vector. Listing 13-17 illustrates how to use push_back and push_front to insert values into a deque of chars.

#include <deque>

TEST_CASE("std::deque supports front insertion") {
  std::deque<char> deckard;
  deckard.push_front('a'); ➊ //  a
  deckard.push_back('i'); ➋ //  ai
  deckard.push_front('c');   // cai
  deckard.push_back('n');    // cain
  REQUIRE(deckard[0] == 'c'); ➌
  REQUIRE(deckard[1] == 'a');
  REQUIRE(deckard[2] == 'i');
  REQUIRE(deckard[3] == 'n');
}

Listing 13-17: A deque supports push_front and push_back.

After constructing an empty deque, you push alternating letters to the front ➊ and back ➋ of the deque so it contains the elements c, a, i, and n ➌.

The vector methods not implemented by deque, along with an explanation for their absence, are as follows:

capacity, reserve Because the internal structure is complicated, it might not be efficient to compute capacity. Also, deque allocations are relatively fast because a deque doesn’t relocate existing elements, so reserving memory ahead of time is unnecessary.

data The elements of deque are not contiguous.

Table 13-3 summarizes the additional operators offered by a deque but not by a vector. In this table, d is of type std::deque<T> and t is of type T. An asterisk (*) indicates that this operation invalidates iterators to v’s elements in at least some circumstances. (Pointers to existing elements remain valid.)

Table 13-3: A Partial List of std::deque Operations

List

A list is a sequence container with fast insert/remove operations everywhere but with no random element access. The STL implementation std::list is available from the <list> header.

The list is implemented as a doubly linked list, a data structure composed of nodes. Each node contains an element, a forward link (“flink”), and a backward link (“blink”). This is completely different from a vector, which stores elements in contiguous memory. As a result, you cannot use operator[] or at to access arbitrary elements in a list, because such operations would be very inefficient. (These methods are simply not available in list because of their horrible performance characteristics.) The trade-off is that inserting and removing elements in a list is much faster. All you need to update are the flinks and blinks of an element’s neighbors rather than shuffling potentially large, contiguous element ranges.

The list container supports the same constructor patterns as vector.

You can perform special operations on lists, such as splicing elements from one list into another using the splice method, removing consecutive duplicate elements using the unique method, and even sorting the elements of a container using the sort method. Consider, for example, the remove_if method. The remove_if method accepts a function object as a parameter, and it traverses the list while invoking the function object on each element. If the result is true, remove_if removes the element. Listing 13-18 illustrates how to use the remove_if method to eliminate all the even numbers of a list with a lambda predicate.

#include <list>

TEST_CASE("std::list supports front insertion") {
  std::list<int> odds{ 11, 22, 33, 44, 55 }; ➊
  odds.remove_if([](int x) { return x % 2 == 0; }); ➋
  auto odds_iter = odds.begin(); ➌
  REQUIRE(*odds_iter == 11); ➍
  ++odds_iter; ➎
  REQUIRE(*odds_iter == 33);
  ++odds_iter;
  REQUIRE(*odds_iter == 55);
  ++odds_iter;
  REQUIRE(odds_iter == odds.end()); ➏
}

Listing 13-18: A list supports remove_if.

Here, you use braced initialization to fill a list of int objects ➊. Next, you use the remove_if method to remove all the even numbers ➋. Because only even numbers modulo 2 equal zero, this lambda tests whether a number is even. To establish that remove_if has extracted the even elements 22 and 44, you create an iterator pointing at the beginning of the list ➌, check its value ➍, and increment ➎ until you reach the end of the list ➏.

All the vector methods not implemented by list, along with an explanation for their absence, are as follows:

capacity, reserve, shrink_to_fit Because list acquires memory incrementally, it doesn’t require periodic resizing.

operator[], at Random element access is prohibitively expensive on lists.

data Unneeded because list elements are not contiguous.

Table 13-4 summarizes the additional operators offered by a list but not by a vector. In this table, lst, lst1, and lst2 are of type std::list<T>, and t is of type T. The arguments itr1, itr2a, and itr2b are list iterators. An asterisk (*) indicates that the operation invalidates iterators to v’s elements in at least some circumstances. (Pointers to existing elements remain valid.)

Table 13-4: A Partial List of std::list Operations

Stacks

The STL provides three container adapters that encapsulate other STL containers and expose special interfaces for tailored situations. The adapters are the stack, the queue, and the priority queue.

A stack is a data structure with two fundamental operations: push and pop. When you push an element onto a stack, you insert the element onto the stack’s end. When you pop an element off a stack, you remove the element from the stack’s end. This arrangement is called last-in, first-out: the last element to be pushed onto a stack is the first to be popped off.

The STL offers the std::stack in the <stack> header. The class template stack takes two template parameters. The first is the underlying type of the wrapped container, such as int, and the second is the type of the wrapped container, such as deque or vector. This second argument is optional and defaults to deque.

To construct a stack, you can pass a reference to a deque, a vector, or a list to encapsulate. This way, the stack translates its operations, such as push and pop, into methods that the underlying container understands, like push_back and pop_back. If you provide no constructor argument, the stack uses a deque by default. The second template parameter must match this container’s type.

To obtain a reference to the element on top of a stack, you use the top method.

Listing 13-19 illustrates how to use a stack to wrap a vector.

#include <stack>

TEST_CASE("std::stack supports push/pop/top operations") {
  std::vector<int> vec{ 1, 3 }; ➊  // 1 3
  std::stack<int, decltype(vec)> easy_as(vec); ➋
  REQUIRE(easy_as.top() == 3); ➌
  easy_as.pop(); ➍                 // 1
  easy_as.push(2); ➎               // 1 2
  REQUIRE(easy_as.top() == 2); ➏
  easy_as.pop();                 // 1
  REQUIRE(easy_as.top() == 1);
  easy_as.pop();                 //
  REQUIRE(easy_as.empty()); ➐
}

Listing 13-19: Using a stack to wrap a vector

You construct a vector of ints called vec containing the elements 1 and 3 ➊. Next, you pass vec into the constructor of a new stack, making sure to supply the second template parameter decltype(vec) ➋. The top element in stack is now 3, because this is the last element in vec ➌. After the first pop ➍, you push a new element 2 onto the stack ➎. Now, the top element is 2 ➏. After another pop-top-pop series, the stack is empty ➐.

Table 13-5 summarizes the operations of stack. In this table, s, s1, and s2 are of type std::stack<T>; t is of type T; and ctr is a container of type ctr_type<T>.

Table 13-5: A Summary of std::stack Operations

Queues

A queue is a data structure that, like a stack, has push and pop as its fundamental operations. Unlike a stack, a queue is first-in, first-out. When you push an element into a queue, you insert onto the queue’s end. When you pop an element off the queue, you remove from the queue’s beginning. This way, the element that has been in the queue the longest is the one to get popped off.

The STL offers the std::queue in the <queue> header. Like stack, queue takes two template parameters. The first parameter is the underlying type of the wrapped container, and the optional second parameter is the type of the wrapped container, which also defaults to deque.

Among STL containers, you can only use deque or list as the underlying container for a queue, because pushing and popping from the front of a vector is inefficient.

You can access the element at the front or back of a queue using the front and back methods.

Listing 13-20 shows how to use a queue to wrap a deque.

#include <queue>

TEST_CASE("std::queue supports push/pop/front/back") {
  std::deque<int> deq{ 1, 2 }; ➊
  std::queue<int> easy_as(deq); ➋ // 1 2

  REQUIRE(easy_as.front() == 1); ➌
  REQUIRE(easy_as.back() == 2); ➍
  easy_as.pop(); ➎                // 2
  easy_as.push(3); ➏              // 2 3
  REQUIRE(easy_as.front() == 2); ➐
  REQUIRE(easy_as.back() == 3); ➑
  easy_as.pop();                   // 3
  REQUIRE(easy_as.front() == 3);
  easy_as.pop();                   //
  REQUIRE(easy_as.empty()); ➒
}

Listing 13-20: Using a queue to wrap a deque

You start with a deque containing the elements 1 and 2 ➊, which you pass into a queue called easy_as ➋. Using the front and back methods, you can validate that the queue begins with a 1 ➌ and ends with a 2 ➍. When you pop the first element, 1, you’re left with a queue containing just the single element 2 ➎. You then push 3 ➏, so the method front yields 2 ➐ and back yields 3 ➑. After two more iterations of pop-front, you’re left with an empty queue ➒.

Table 13-6 summarizes the operations of queue. In this table, q, q1, and q2 are of type std::queue<T>; t is of type T; and ctr is a container of type ctr_type<T>.

Table 13-6: A Summary of std::queue Operations

Priority Queues (Heaps)

A priority queue (also called a heap) is a data structure that supports push and pop operations and keeps elements sorted according to some user-specified comparator object. The comparator object is a function object invokable with two parameters, returning true if the first argument is less than the second. When you pop an element from a priority queue, you remove the element that is greatest, according to the comparator object.

The STL offers the std::priority_queue in the <queue> header. A priority_queue has three template parameters:

• The underlying type of the wrapped container
• The type of the wrapped container
• The type of the comparator object

Only the underlying type is mandatory. The wrapped container type defaults to vector (probably because it’s the most widely used sequential container), and the comparator object type defaults to std::less.

The priority_queue has an identical interface to a stack. The only difference is that stacks pop elements according to the last-in, first-out arrangement, whereas priority queues pop elements according to the comparator object criteria.

Listing 13-21 illustrates the basic usage of priority_queue.

#include <queue>

TEST_CASE("std::priority_queue supports push/pop") {
  std::priority_queue<double> prique; ➊
  prique.push(1.0); // 1.0
  prique.push(2.0); // 2.0 1.0
  prique.push(1.5); // 2.0 1.5 1.0

  REQUIRE(prique.top() == Approx(2.0)); ➋
  prique.pop();     // 1.5 1.0
  prique.push(1.0); // 1.5 1.0 1.0
  REQUIRE(prique.top() == Approx(1.5)); ➌
  prique.pop();     // 1.0 1.0
  REQUIRE(prique.top() == Approx(1.0)); ➍
  prique.pop();     // 1.0
  REQUIRE(prique.top() == Approx(1.0)); ➎
  prique.pop();     //
  REQUIRE(prique.empty()); ➏
}

Listing 13-21: Basic priority_queue usage

Here, you default construct a priority_queue ➊, which internally initializes an empty vector to hold its elements. You push the elements 1.0, 2.0, and 1.5 into the priority_queue, which sorts the elements in descending order so the container represents them in the order 2.0 1.5 1.0.

You assert that top yields 2.0 ➋, pop this element off the priority_queue, and then invoke push with the new element 1.0. The container now represents them in the order 1.5 ➌ 1.0 ➍ 1.0 ➎, which you verify with a series of top-pop operations until the container is empty ➏.

Table 13-7 summarizes the operations of priority_queue. In this table, pq, pq1, and pq2 are of type std::priority_queue<T>; t is of type T; ctr is a container of type ctr_type<T>; and srt is a container of type srt_type<T>.

Table 13-7: A Summary of std::priority_queue Operations

Bitsets

A bitset is a data structure that stores a fixed-size bit sequence. You can manipulate each bit.

The STL offers the std::bitset in the <bitset> header. The class template bitset takes a single template parameter corresponding to the desired size. You could achieve similar functionality using a bool array, but bitset is optimized for space efficiency and provides some special convenience operations.

A default constructed bitset contains all zero (false) bits. To initialize bitsets with other contents, you can provide an unsigned long long value. This integer’s bitwise representation sets the value of bitset. You can access individual bits in the bitset using operator[]. Listing 13-22 demonstrates how to initialize a bitset with an integer literal and extract its elements.

#include <bitset>

TEST_CASE("std::bitset supports integer initialization") {
  std::bitset<4> bs(0b0101); ➊
  REQUIRE_FALSE(bs[0]); ➋
  REQUIRE(bs[1]); ➌
  REQUIRE_FALSE(bs[2]); ➍
  REQUIRE(bs[3]); ➎
}

Listing 13-22: Initializing a bitset with an integer

You initialize a bitset with the 4-bit nybble 0101 ➊. So, the first ➋ and third ➍ elements are zero, and the second ➌ and fourth ➎ elements are 1.

You can also provide a string representation of the desired bitset, as shown in Listing 13-23.

TEST_CASE("std::bitset supports string initialization") {
  std::bitset<4> bs1(0b0110); ➊
  std::bitset<4> bs2("0110"); ➋
  REQUIRE(bs1 == bs2); ➌
}

Listing 13-23: Initializing a bitset with a string

Here, you construct a bitset called bs1 using the same integer nybble 0b0110 ➊ and another bitset called bs2 using the string literal 0110 ➋. Both of these initialization approaches produce identical bitset objects ➌.

Table 13-8 summarizes the operations of bitset. In this table, bs, bs 1, and bs 2 are of type std::bitset<N>, and i is a size_t.

Table 13-8: A Summary of std::bitset Operations

Special Sequential Boost Containers

Boost provides an abundance of special containers, and there simply isn’t enough room to explore all their features here. Table 13-9 provides the names, headers, and brief descriptions of a number of them.

Table 13-9: Special Boost Containers

Associative Containers

Associative containers allow for very fast element search. Sequential containers have some natural ordering that allows you to iterate from the beginning of the container to the end in a well-specified order. Associative containers are a bit different. This container family splits along three axes:

• Whether elements contain keys (a set) or key-value pairs (a map)
• Whether elements are ordered
• Whether keys are unique

Sets

The std::set available in the STL’s <set> header is an associative container that contains sorted, unique elements called keys. Because set stores sorted elements, you can insert, remove, and search efficiently. In addition, set supports sorted iteration over its elements, and you have complete control over how keys sort using comparator objects.

Constructing

The class template set<T, Comparator, Allocator> takes three template parameters:

• The key type T
• The comparator type that defaults to std::less
• The allocator type that defaults to std::allocator<T>

You have a lot of flexibility when constructing sets. Each of the following constructors accepts an optional comparator and allocator (whose types must match their corresponding template parameters):

• A default constructor that initializes an empty set
• Move and copy constructors with the usual behavior
• A range constructor that copies the elements from the range into the set
• A braced initializer

Listing 13-24 showcases each of these constructors.

#include <set>

TEST_CASE("std::set supports") {
  std::set<int> emp; ➊
  std::set<int> fib{ 1, 1, 2, 3, 5 }; ➋
  SECTION("default construction") {
    REQUIRE(emp.empty()); ➌
  }
  SECTION("braced initialization") {
    REQUIRE(fib.size() == 4); ➍
  }
  SECTION("copy construction") {
    auto fib_copy(fib);
    REQUIRE(fib.size() == 4); ➎
    REQUIRE(fib_copy.size() == 4); ➏
  }
  SECTION("move construction") {
    auto fib_moved(std::move(fib));
    REQUIRE(fib.empty()); ➐
    REQUIRE(fib_moved.size() == 4); ➑
  }
  SECTION("range construction") {
    std::array<int, 5> fib_array{ 1, 1, 2, 3, 5 };
    std::set<int> fib_set(fib_array.cbegin(), fib_array.cend());
    REQUIRE(fib_set.size() == 4); ➒
  }
}

Listing 13-24: The constructors of a set

You default construct ➊ and brace initialize ➋ two different sets. The default constructed set called emp is empty ➌, and the braced initialized set called fib has four elements ➍. You include five elements in the braced initializer, so why only four elements? Recall that set elements are unique, so the 1 enters only once.

Next, you copy construct fib, which results in two sets with size 4 ➎ ➏. On the other hand, the move constructor empties the moved-from set ➐ and transfers the elements to the new set ➑.

Then you can initialize a set from a range. You construct an array with five elements and then pass it as a range to a set constructor using the cbegin and cend methods. As with the braced initialization earlier in the code, the set contains only four elements because duplicates are discarded ➒.

Move and Copy Semantics

In addition to move/copy constructors, move/copy assignment operators are also available. As with other container copy operations, set copies are potentially very slow because each element needs to get copied, and move operations are usually fast because elements reside in dynamic memory. A set can simply pass ownership without disturbing the elements.

Element Access

You have several options for extracting elements from a set. The basic method is find, which takes a const reference to a key and returns an iterator. If the set contains an element-matching key, find will return an iterator pointing to the found element. If the set does not, it will return an iterator pointing to end. The lower_bound method returns an iterator to the first element not less than the key argument, whereas the upper_bound method returns the first element greater than the given key.

The set class supports two additional lookup methods, mainly for compatibility of non-unique associative containers:

• The count method returns the number of elements matching the key. Because set elements are unique, count returns either 0 or 1.
• The equal_range method returns a half-open range containing all the elements matching the given key. The range returns a std::pair of iterators with first pointing to the matching element and second pointing to the element after first. If equal_range finds no matching element, first and second both point to the first element greater than the given key. In other words, the pair returned by equal_range is equivalent to a pair of lower_bound as first and upper_bound as second.

Listing 13-25 illustrates these two access methods.

TEST_CASE("std::set allows access") {
  std::set<int> fib{ 1, 1, 2, 3, 5 }; ➊
  SECTION("with find") { ➋
    REQUIRE(*fib.find(3) == 3);
    REQUIRE(fib.find(100) == fib.end());
  }
  SECTION("with count") { ➌
    REQUIRE(fib.count(3) == 1);
    REQUIRE(fib.count(100) == 0);
  }
  SECTION("with lower_bound") { ➍
    auto itr = fib.lower_bound(3);
    REQUIRE(*itr == 3);
  }
  SECTION("with upper_bound") { ➎
    auto itr = fib.upper_bound(3);
    REQUIRE(*itr == 5);
  }
  SECTION("with equal_range") { ➏
    auto pair_itr = fib.equal_range(3);
    REQUIRE(*pair_itr.first == 3);
    REQUIRE(*pair_itr.second == 5);
  }
}

Listing 13-25: A set member access

First, you construct a set with the four elements 1 2 3 5 ➊. Using find, you can extract an iterator to the element 3. You can also determine that 8 isn’t in the set, because find returns an iterator pointing to end ➋. You can determine similar information with count, which returns 1 when you give the key 3 and 0 when you give the key 8 ➌. When you pass 3 to the lower_bound method, it returns an iterator pointing to 3 because this is the first element that’s not less than the argument ➍. When you pass this to upper_bound, on the other hand, you obtain a pointer to the element 5, because this is the first element greater than the argument ➎. Finally, when you pass 3 to the equal_range method, you obtain a pair of iterators. The first iterator points to 3, and the second iterator points to 5, the element just after 3 ➏.

A set also exposes iterators through its begin and end methods, so you can use range-based for loops to iterate through the set from least element to greatest.

Adding Elements

You have three options when adding elements to a set:

• insert to copy an existing element into the set
• emplace to in-place construct a new element into the set
• emplace_hint to in-place construct a new element, just like emplace (because adding an element requires sorting). The difference is the emplace_hint method takes an iterator as its first argument. This iterator is the search’s starting point (a hint). If the iterator is close to the correct position for the newly inserted element, this can provide a substantial speedup.

  Listing 13-26 illustrates the several ways to insert elements into a set.

TEST_CASE("std::set allows insertion") {
  std::set<int> fib{ 1, 1, 2, 3, 5 };
  SECTION("with insert") { ➊
    fib.insert(8);
    REQUIRE(fib.find(8) != fib.end());
  }
  SECTION("with emplace") { ➋
    fib.emplace(8);
    REQUIRE(fib.find(8) != fib.end());
  }
  SECTION("with emplace_hint") { ➌
    fib.emplace_hint(fib.end(), 8);
    REQUIRE(fib.find(8) != fib.end());
  }
}

Listing 13-26: Inserting into a set

Both insert ➊ and emplace ➋ add the element 8 into fib, so when you invoke find with 8, you get an iterator pointing to the new element. You can achieve the same effect a bit more efficiently with emplace_hint ➌. Because you know ahead of time that the new element 8 is greater than all the other elements in the set, you can use end as the hint.

If you attempt to insert, emplace, or emplace_hint a key that’s already present in the set, the operation has no effect. All three of these methods return a std::pair<Iterator, bool> where the second element indicates whether the operation resulted in insertion (true) or not (false). The iterator at first points to either the newly inserted element or the existing element that prevented insertion.

Removing Elements

You can remove elements from a set using erase, which is overloaded to accept a key, an iterator, or a half-open range, as shown in Listing 13-27.

TEST_CASE("std::set allows removal") {
  std::set<int> fib{ 1, 1, 2, 3, 5 };
  SECTION("with erase") { ➊
    fib.erase(3);
    REQUIRE(fib.find(3) == fib.end());
  }
  SECTION("with clear") { ➋
    fib.clear();
    REQUIRE(fib.empty());
  }
}

Listing 13-27: Removing from a set

In the first test, you call erase with the key 3, which removes the corresponding element from the set. When you invoke find on 3, you get an iterator pointing to the end, indicating that no matching element was found ➊. In the second test, you invoke clear, which eliminates all the elements from the set ➋.

Storage Model

Set operations are fast because sets are typically implemented as red-black trees. These structures treat each element as a node. Each node has one parent and up to two children, its left and right legs. Each node’s children are sorted so all children to the left are less than the children to the right. This way, you can perform searches much quicker than with linear iteration, as long as a tree’s branches are roughly balanced (equal in length). Red-black trees have additional facilities for rebalancing branches after insertions and deletions.

A Partial List of Supported Operations

Table 13-10 summarizes the operations of set. Operations s, s1, and s2 are of type std::set<T,[cmp_type<T>]>. T is the contained element/key type, and itr, beg, and end are set iterators. The variable t is a T. A dagger (†)denotes a method that returns a std::pair<Iterator, bool>, where the iterator points to the resulting element and the bool equals true if the method inserted an element and false if the element already existed.

Table 13-10: A Summary of std::set

Multisets

The std::multiset available in the STL’s <set> header is an associative container that contains sorted, non-unique keys. A multiset supports the same operations as a set, but it will store redundant elements. This has important ramifications for two methods:

• The method count can return values other than 0 or 1. The count method of multiset will tell you how many elements matched the given key.
• The method equal_range can return half-open ranges containing more than one element. The equal_range method of multiset will return a range containing all the elements matching the given key.

You might want to use a multiset rather than a set if it’s important that you store multiple elements with the same key. For example, you could store all of an address’s occupants by treating the address as a key and each member of the house as an element. If you used a set, you’d be stuck having only a single occupant.

Listing 13-28 illustrates using a multiset.

TEST_CASE("std::multiset handles non-unique elements") {
  std::multiset<int> fib{ 1, 1, 2, 3, 5 };
  SECTION("as reflected by size") {
    REQUIRE(fib.size() == 5); ➊
  }
  SECTION("and count returns values greater than 1") {
    REQUIRE(fib.count(1) == 2); ➋
  }
  SECTION("and equal_range returns non-trivial ranges") {
    auto [begin, end] = fib.equal_range(1); ➌
    REQUIRE(*begin == 1); ➍
    ++begin;
    REQUIRE(*begin == 1); ➎
    ++begin;
    REQUIRE(begin == end); ➏
  }
}

Listing 13-28: Accessing multiset elements

Unlike set in Listing 13-24, multiset permits multiple 1s, so size returns 5, the number of elements you provided in the braced initializers ➊. When you count the number of 1s, you get 2 ➋. You can use equal_range to iterate over these elements. Using structured binding syntax, you obtain a begin and end iterator ➌. You iterate over the two 1s ➍ ➎ and arrive at the end of the half-open range ➏.

Every operation in Table 13-10 works for multiset.

Unordered Sets

The std::unordered_set available in the STL’s <unordered_set> header is an associative container that contains unsorted, unique keys. The unordered_set supports most of the same operations as set and multiset, but its internal storage model is completely different.

Rather than using a comparator to sort elements into a red-black tree, an unordered_set is usually implemented as a hash table. You might want to use an unordered_set in a situation in which there is no natural ordering among the keys and you don’t need to iterate through the collection in such an order. You might find that in many situations, you could use either a set or an unordered_set. Although they appear quite similar, their internal representations are fundamentally different, so they’ll have different performance characteristics. If performance is an issue, measure how both perform and use the one that’s more appropriate.

Storage Model: Hash Tables

A hash function, or a hasher, is a function that accepts a key and returns a unique size_t value called a hash code. The unordered_set organizes its elements into a hash table, which associates a hash code with a collection of one or more elements called a bucket. To find an element, an unordered_set computes its hash code and then searches through the corresponding bucket in the hash table.

If you’ve never seen a hash table before, this information might be a lot to take in, so let’s look at an example. Imagine you had a large group of people that you needed to sort into some kind of sensible groups to find an individual easily. You could group people by birthday, which would give you 365 groups (well, 366 if you count February 29 for leap years). The birthday is like a hash function that returns one of 365 values for each person. Each value forms a bucket, and all people in the same bucket have the same birthday. In this example, to find a person, you first determine their birthday, which gives you the correct bucket. Then you can search through the bucket to find the person you’re looking for.

As long as the hash function is quick and there aren’t too many elements per bucket, unordered_sets have even more impressive performance than their ordered counterparts: the contained element count doesn’t increase insertion, search, and deletion times. When two different keys have the same hash code, it’s called a hash collision. When you have a hash collision, it means that the two keys will reside in the same bucket. In the preceding birthday example, many people will have the same birthday, so there will be a lot of hash collisions. The more hash collisions there are, the larger the buckets will be, and the more time you’ll spend searching through a bucket for the correct element.

A hash function has several requirements:

• It accepts a Key and returns a size_t hash code.
• It doesn’t throw exceptions.
• Equal keys yield equal hash codes.
• Unequal keys yield unequal hash codes with high probability. (There is a low probability of a hash collision.)

The STL provides the hasher class template std::hash<T> in the <functional> header, which contains specializations for fundamental types, enumeration types, pointer types, optional, variant, smart pointers, and more. As an example, Listing 13-29 illustrates how std::hash<long> meets the equivalence criteria.

#include <functional>
TEST_CASE("std::hash<long> returns") {
  std::hash<long> hasher; ➊
  auto hash_code_42 = hasher(42); ➋
  SECTION("equal hash codes for equal keys") {
    REQUIRE(hash_code_42 == hasher(42)); ➌
  }
  SECTION("unequal hash codes for unequal keys") {
    REQUIRE(hash_code_42 != hasher(43)); ➍
  }
}

Listing 13-29: The std::hash<long> returns equal hash codes for equal keys and unequal hash codes for unequal keys.

You construct a hasher of type std::hash<long> ➊ and use it to compute the hash code of 42, storing the result into size_t hash_code_42 ➋. When you invoke hasher with 42 again, you obtain the same value ➌. When you invoke hasher with 43 instead, you obtain a different value ➍.

Once an unordered_set hashes a key, it can obtain a bucket. Because the bucket is a list of possible matching elements, you need a function object that determines equality between a key and a bucket element. The STL provides the class template std::equal_to<T> in the <functional> header, which simply invokes operator== on its arguments, as Listing 13-30 illustrates.

#include <functional>
TEST_CASE("std::equal_to<long> returns") {
  std::equal_to<long> long_equal_to; ➊
  SECTION("true when arguments equal") {
    REQUIRE(long_equal_to(42, 42)); ➋
  }
  SECTION("false when arguments unequal") {
    REQUIRE_FALSE(long_equal_to(42, 43)); ➌
  }
}

Listing 13-30: The std::equal_to<long> calls operator== on its arguments to determine equality.

Here, you’ve initialized an equal_to<long> called long_equal_to ➊. When you invoke long_equal_to with equal arguments, it returns true ➋. When you invoke it with unequal arguments, it returns false ➌.

Constructing

The class template std::unordered_set<T, Hash, KeyEqual, Allocator> takes four template parameters:

• Key type T
• The Hash hash function type, which defaults to std::hash<T>
• The KeyEqual equality function type, which defaults to std::equal_to<T>
• The Allocator allocator type, which defaults to std::allocator<T>

An unordered_set supports equivalent constructors to set with adjustments for the different template parameters (set needs a Comparator, whereas unordered_set needs a Hash and a KeyEqual). For example, you can use unordered_set as a drop-in replacement for set in Listing 13-24, because unordered_set has range constructors and copy/move constructors and supports braced initialization.

Supported set Operations

An unordered_set supports all set operations in Table 13-10 except for lower_bound and upper_bound, because unordered_set doesn’t sort its elements.

Bucket Management

Generally, the reason you reach for an unordered_set is its high performance. Unfortunately, this performance comes at a cost: unordered_set objects have a somewhat complicated interior structure. You have various knobs and dials you can use to inspect and modify this internal structure at runtime.

The first control measure you have is to customize the bucket count of the unordered_set (that is, the number of buckets, not the number of elements in a particular bucket). Each unordered_set constructor takes a size_t bucket_count as its first argument, which defaults to some implementation-defined value. Table 13-11 lists the main unordered_set constructors.

Table 13-11: The unordered_set Constructors

You can inspect the number of buckets in an unordered_set using the bucket_count method. You can also obtain the maximum bucket count using the max_bucket_count method.

An important concept in the runtime performance of unordered_set is its load factor, the average number of elements per bucket. You can obtain the load factor of an unordered_set using the load_factor method, which is equivalent to size() divided by bucket_count(). Each unordered_set has a maximum load factor, which triggers an increase in the bucket count and a potentially expensive rehashing of all the contained elements. A rehashing is an operation where elements get reorganized into new buckets. This requires that you generate new hashes for each element, which can be a relatively computationally expensive operation.

You can obtain the maximum load factor using the max_load_factor, which is overloaded, so you can set a new maximum load factor (it defaults to 1.0).

To avoid expensive rehashing at inopportune times, you can manually trigger a rehashing using the rehash method, which accepts a size_t argument for the desired bucket count. You can also use the reserve method, which instead accepts a size_t argument for the desired element count.

Listing 13-31 illustrates some of these basic bucket management operations.

#include <unordered_set>
TEST_CASE("std::unordered_set") {
  std::unordered_set<unsigned long> sheep(100); ➊
  SECTION("allows bucket count specification on construction") {
    REQUIRE(sheep.bucket_count() >= 100); ➋
    REQUIRE(sheep.bucket_count() <= sheep.max_bucket_count()); ➌
    REQUIRE(sheep.max_load_factor() == Approx(1.0)); ➍
  }
  SECTION("allows us to reserve space for elements") {
    sheep.reserve(100'000); ➎
    sheep.insert(0);
    REQUIRE(sheep.load_factor() <= 0.00001); ➏
    while(sheep.size() < 100'000)
      sheep.insert(sheep.size()); ➐
    REQUIRE(sheep.load_factor() <= 1.0); ➑
  }
}

Listing 13-31: The unordered_set bucket management

You construct an unordered_set and specify a bucket count of 100 ➊. This results in a bucket_count of at least 100 ➋, which must be less than or equal to the max_bucket_count ➌. By default, the max_load_factor is 1.0 ➍.

In the next test, you invoke reserve with enough space for a hundred thousand elements ➎. After inserting an element, the load_factor should be less than or equal to one one-hundred-thousandth (0.00001) ➏ because you’ve reserved enough space for a hundred thousand elements. As long as you stay below this threshold, you won’t need a rehashing. After inserting a hundred thousand elements ➐, the load_factor should still be less than or equal to 1 ➑. This demonstrates that you needed no rehashing, thanks to reserve.

Unordered Multisets

The std::unordered_multiset available in the STL’s <unordered_set> header is an associative container that contains unsorted, non-unique keys. An unordered_multiset supports all the same constructors and operations as an unordered_set, but it will store redundant elements. This relationship is analogous to unordered_sets and sets: both equal_range and count have slightly different behavior to account for the non-uniqueness of keys.

Maps

The std::map available in the STL’s <map> header is an associative container that contains key-value pairs. The keys of a map are sorted and unique, and map supports all the same operations as set. In fact, you can think of a set as a special kind of map containing keys and empty values. Accordingly, map supports efficient insertion, removal, and search, and you have control over sorting with comparator objects.

The major advantage of working with a map instead of a set of pairs is that map works as an associative array. An associative array takes a key rather than an integer-valued index. Think of how you use the at and operator[] methods to access indices in sequential containers. Because sequential containers have a natural ordering of elements, you use an integer to refer to them. The associative array allows you to use types other than integers to refer to elements. For example, you could use a string or a float as a key.

To enable associative array operations, map supports a number of useful operations; for example, allowing you to insert, modify, and retrieve values by their associated keys.

Constructing

The class template map<Key, Value, Comparator, Allocator> takes four template parameters. The first is the key type Key. The second is the value type Value. The third is the comparator type, which defaults to std::less. The fourth parameter is the allocator type, which defaults to std::allocator<T>.

The map constructors are direct analogues to the constructors of set: a default constructor that initializes an empty map; move and copy constructors with the usual behavior; a range constructor that copies the elements from the range into the map; and a braced initializer. The main difference is in the braced initializer, because you need to initialize key-value pairs instead of just keys. To achieve this nested initialization, you use nested initializer lists, as Listing 13-32 illustrates.

#include <map>

auto colour_of_magic = "Colour of Magic";
auto the_light_fantastic = "The Light Fantastic";
auto equal_rites = "Equal Rites";
auto mort = "Mort";

TEST_CASE("std::map supports") {
  SECTION("default construction") {
    std::map<const char*, int> emp; ➊
    REQUIRE(emp.empty()); ➋
  }
  SECTION("braced initialization") {
    std::map<const char*, int> pub_year { ➌
      { colour_of_magic, 1983 }, ➍
      { the_light_fantastic, 1986 },
      { equal_rites, 1987 },
      { mort, 1987 },
    };
    REQUIRE(pub_year.size() == 4); ➎
  }
}

Listing 13-32: A std::map supports default construction and braced initialization.

Here, you default construct a map with keys of type const char* and values of type int ➊. This results in an empty map ➋. In the second test, you again have a map with keys of type const char* and values of type int ➌, but this time you use braced initialization ➍ to pack four elements into the map ➎.

Move and Copy Semantics

The move and copy semantics of map are identical to those of set.

Storage Model

Both map and set use the same red-black tree internal structure.

Element Access

The major advantage to using a map instead of a set of pair objects is that map offers two associative array operations: operator[] and at. Unlike the sequential containers supporting these operations, like vector and array, which take a size_t index argument, map takes a Key argument and returns a reference to the corresponding value. As with sequential containers, at will throw a std::out_of_range exception if the given key doesn’t exist in the map. Unlike with sequential containers, operator[] won’t cause undefined behavior if the key doesn’t exist; instead, it will (silently) default construct a Value and insert the corresponding key-value pair into the map, even if you only intended to perform a read, as Listing 13-33 illustrates.

TEST_CASE("std::map is an associative array with") {
  std::map<const char*, int> pub_year { ➊
    { colour_of_magic, 1983 },
    { the_light_fantastic, 1986 },
  };
  SECTION("operator[]") {
    REQUIRE(pub_year[colour_of_magic] == 1983); ➋

    pub_year[equal_rites] = 1987; ➌
    REQUIRE(pub_year[equal_rites] == 1987); ➍

    REQUIRE(pub_year[mort] == 0); ➎
  }
  SECTION("an at method") {
    REQUIRE(pub_year.at(colour_of_magic) == 1983); ➏

    REQUIRE_THROWS_AS(pub_year.at(equal_rites), std::out_of_range); ➐
  }
}

Listing 13-33: A std::map is an associative array with several access methods.

You construct a map called pub_year containing two elements ➊. Next, you use operator[] to extract the value corresponding to the key colour_of_magic ➋. You also use operator[] to insert the new key-value pair equal_rites, 1987 ➌ and then retrieve it ➍. Notice that when you attempt to retrieve an element with the key mort (which doesn’t exist), the map has silently default-initialized an int for you ➎.

Using at, you can still set and retrieve ➏ elements, but if you attempt to access a key that doesn’t exist, you get a std::out_of_range exception ➐.

A map supports all the set-like, element-retrieval operations. For example, map supports find, which accepts a key argument and returns an iterator pointing to the key-value pair or, if no matching key is found, to the end of map. Also similarly supported are count, equal_range, lower_bound, and upper_bound.

Adding Elements

In addition to the element access methods operator[] and at, you also have all the insert and emplace methods available from set. You simply need to treat each key-value pair as a std::pair<Key, Value>. As with set, insert returns a pair containing an iterator and a bool. The iterator points to the inserted element, and the bool answers whether insert added a new element (true) or not (false), as Listing 13-34 illustrates.

TEST_CASE("std::map supports insert") {
  std::map<const char*, int> pub_year; ➊
  pub_year.insert({ colour_of_magic, 1983 }); ➋
  REQUIRE(pub_year.size() == 1); ➌

  std::pair<const char*, int> tlfp{ the_light_fantastic, 1986 }; ➍
  pub_year.insert(tlfp); ➎
  REQUIRE(pub_year.size() == 2); ➏

  auto [itr, is_new] = pub_year.insert({ the_light_fantastic, 9999 }); ➐
  REQUIRE(itr->first == the_light_fantastic);
  REQUIRE(itr->second == 1986); ➑
  REQUIRE_FALSE(is_new); ➒
  REQUIRE(pub_year.size() == 2); ➓
}

Listing 13-34: A std::map supports insert to add new elements.

You default construct a map ➊ and use the insert method with a braced initializer for a pair ➋. This construction is roughly equivalent to the following:

pub_year.insert(std::pair<const char*, int>{ colour_of_magic, 1983 });

After insertion, the map now contains one element ➌. Next, you create a stand-alone pair ➍ and then pass it as an argument to insert ➎. This inserts a copy into the map, so it now contains two elements ➏.

When you attempt to invoke insert with a new element with the same the_light_fantastic key ➐, you get an iterator pointing to the element you already inserted ➎. The key (first) and the value (second) match ➑. The return value is_new indicates that no new element was inserted ➒, and you still have two elements ➓. This behavior mirrors the insert behavior of set.

A map also offers an insert_or_assign method, which, unlike insert, will overwrite an existing value. Also unlike insert, insert_or_assign accepts separate key and value arguments, as Listing 13-35 illustrates.

TEST_CASE("std::map supports insert_or_assign") {
  std::map<const char*, int> pub_year{ ➊
    { the_light_fantastic, 9999 }
  };
  auto [itr, is_new] = pub_year.insert_or_assign(the_light_fantastic, 1986); ➋
  REQUIRE(itr->second == 1986); ➌
  REQUIRE_FALSE(is_new); ➍
}

Listing 13-35: A std::map supports insert_or_assign to overwrite existing elements.

You construct a map with a single element ➊ and then call insert_or _assign to reassign the value associated with the key the_light_fantastic to 1986 ➋. The iterator points to the existing element, and when you query the corresponding value with second, you see the value updated to 1986 ➌. The is_new return value also indicates that you’ve updated an existing element rather than inserting a new one ➍.

Removing Elements

Like set, map supports erase and clear to remove elements, as shown in Listing 13-36.

TEST_CASE("We can remove std::map elements using") {
    std::map<const char*, int> pub_year {
      { colour_of_magic, 1983 },
      { mort, 1987 },
    }; ➊
  SECTION("erase") {
    pub_year.erase(mort); ➋
    REQUIRE(pub_year.find(mort) == pub_year.end()); ➌
  }
  SECTION("clear") {
    pub_year.clear(); ➍
    REQUIRE(pub_year.empty()); ➎
  }
}

Listing 13-36: A std::map supports element removal.

You construct a map with two elements ➊. In the first test, you invoke erase on the element with key mort ➋, so when you try to find it, you get back end ➌. In the second test, you clear map ➍, which causes empty to return true ➎.

List of Supported Operations

Table 13-12 summarizes the supported operations of map. A key k has type K. A value v has type V. P is the type pair<K, V>, and p is of type P. The map m is map<K, V>. A dagger (†) denotes a method that returns a std::pair<Iterator, bool>, where the iterator points to the resulting element and the bool equals true if the method inserted an element and false if the element already existed.

Table 13-12: A Partial List of Supported map Operations

Multimaps

The std::multimap available in the STL’s <map> header is an associative container that contains key-value pairs with non-unique keys. Because the keys are not unique, multimap doesn’t support the associative array features that map does. Namely, operator[] and at aren’t supported. As with multiset, multimap offers element access primarily through the equal_range method, as Listing 13-37 illustrates.

TEST_CASE("std::multimap supports non-unique keys") {
  std::array<char, 64> far_out {
    "Far out in the uncharted backwaters of the unfashionable end..."
  }; ➊
  std::multimap<char, size_t> indices; ➋
  for(size_t index{}; index<far_out.size(); index++)
    indices.emplace(far_out[index], index); ➌

  REQUIRE(indices.count('a') == 6); ➍

  auto [itr, end] = indices.equal_range('d'); ➎
  REQUIRE(itr->second == 23); ➏
  itr++;
  REQUIRE(itr->second == 59); ➐
  itr++;
  REQUIRE(itr == end);
}

Listing 13-37: A std::multimap supports non-unique keys.

You construct an array containing a message ➊. You also default construct a multimap<char, size_t> called indices that you’ll use to store the index of every character in the message ➋. By looping through the array, you can store each character in the message along with its index as a new element in multimap ➌. Because you’re allowed to have non-unique keys, you can use the count method to reveal how many indices you insert with the key a ➍. You can also use the equal_range method to obtain the half-open range of indices with the key d ➎. Using the resulting begin and end iterators, you can see that the message has the letter d at indices 23 ➏ and 59 ➐.

Aside from operator[] and at, every operation in Table 13-12 works for multimap as well. (Note that the count method can take on values other than 0 and 1.)

Unordered Maps and Unordered Multimaps

Unordered maps and unordered multimaps are completely analogous to unordered sets and unordered multisets. The std::unordered_map and std::unordered_multimap are available in the STL’s <unordered_map> header. These associative containers typically use a red-black tree like their set counterparts. They also require a hash function and an equivalence function, and they support the bucket interface.

Niche Associative Containers

Use set, map, and their associated non-unique and unordered counterparts as the default choices when you need associative data structures. When special needs arise, Boost libraries offer a number of specialized associative containers, as highlighted in Table 13-13.

Table 13-13: Special Boost Containers

Graphs and Property Trees

This section discusses two specialized Boost libraries that serve niche but valuable purposes: modeling graphs and property trees. A graph is a set of objects in which some have a pairwise relation. The objects are called vertices,and their relations are called edges. Figure 13-3 illustrates a graph containing four vertices and five edges.

Figure 13-3:A graph containing four vertices and five edges

Each square represents a vertex, and each arrow represents an edge.

A property tree is a tree structure storing nested key-value pairs. The hierarchical nature of a property tree’s key-value pairs makes it a hybrid between a map and a graph; each key-value pair has a relation to other key-value pairs. Figure 13-4 illustrates an example property tree containing nested key-value pairs.

Figure 13-4: An example property tree

The root element has three children: name, year, and features. In Figure 13-4, name has a value finfisher, year has a value 2014, and features has three children: process with value LSASS, driver with value mssounddx.sys, and arch with value 32.

The Boost Graph Library

The Boost Graph Library (BGL) is a set of collections and algorithms for storing and manipulating graphs. The BGL offers three containers that represent graphs:

• The boost::adjacency_list in the <boost/graph/adjacency_list.hpp> header
• The boost::adjacency_matrix in the <boost/graph/adjacency_matrix.hpp> header
• The boost::edge_list in the <boost/graph/ edge_list.hpp> header

You use two non-member functions to build graphs: boost::add_vertex and boost::add_edge. To add a vertex to one of the BGL graph containers, you pass the graph object to add_vertex, which will return reference to the new vertex object. To add an edge, we pass the source vertex, the destination vertex, then the graph to add_edge.

BGL contains a number of graph-specific algorithms. You can count the number of vertices in a graph object by passing it to the non-member function boost::num_vertices and the number of edges using boost::num_edges. You can also query a graph for adjacent vertices. Two vertices are adjacent if they share an edge. To get the vertices adjacent to a particular vertex, you can pass it and the graph object to the non-member function boost::adjacent_ vertices. This returns a half-open range as a std::pair of iterators.

Listing 13-38 illustrates how you can build the graph represented in Figure 13-3, count its vertices and edges, and compute adjacent vertices.

#include <set>
#include <boost/graph/adjacency_list.hpp>

TEST_CASE("boost::adjacency_list stores graph data") {
  boost::adjacency_list<> graph{}; ➊
  auto vertex_1 = boost::add_vertex(graph);
  auto vertex_2 = boost::add_vertex(graph);
  auto vertex_3 = boost::add_vertex(graph);
  auto vertex_4 = boost::add_vertex(graph); ➋
  auto edge_12 = boost::add_edge(vertex_1, vertex_2, graph);
  auto edge_13 = boost::add_edge(vertex_1, vertex_3, graph);
  auto edge_21 = boost::add_edge(vertex_2, vertex_1, graph);
  auto edge_24 = boost::add_edge(vertex_2, vertex_4, graph);
  auto edge_43 = boost::add_edge(vertex_4, vertex_3, graph); ➌

  REQUIRE(boost::num_vertices(graph) == 4); ➍
  REQUIRE(boost::num_edges(graph) == 5); ➎

  auto [begin, end] = boost::adjacent_vertices(vertex_1, graph); ➏
  std::set<decltype(vertex_1)> neighboors_1 { begin, end }; ➐
  REQUIRE(neighboors_1.count(vertex_2) == 1); ➑
  REQUIRE(neighboors_1.count(vertex_3) == 1); ➒
  REQUIRE(neighboors_1.count(vertex_4) == 0); ➓
}

Listing 13-38: The boost::adjacency_list stores graph data.

Here, you’ve constructed an adjacency_list called graph ➊, then added four vertices using add_vertex ➋. Next, you add all the edges represented in Figure 13-3 using add_edge ➌. Then num_vertices shows you that you’ve added four vertices ➍, and num_edges tells you that you’ve added five edges ➎.

Finally, you’ve determined the adjacent_vertices to vertex_1, which you unpack into the iterators begin and end ➏. You use these iterators to construct a std::set ➐, which you use to show that vertex_2 ➑ and vertex_3 ➒ are adjacent, but vertex_4 is not ➓.

Boost Property Trees

Boost offers the boost::property_tree::ptree in the <boost/property_tree/ptree.hpp> header. This is a property tree that permits us to build and query property trees, as well as some limited serialization into various formats.

The tree ptree is default constructible. Default constructing will build an empty ptree.

You can insert elements into a ptree using its put method, which takes a path and a value argument. A path is a sequence of one or more nested keys separated by a period (.), and a value is an arbitrarily typed object.

You can remove subtrees from a ptree using the get_child method, which takes the path of the desired subtree. If the subtree does not have any children (a so-called leaf node), you can also use the method template get_value to extract the corresponding value from the key-value pair; get_value takes a single template parameter corresponding to the desired output type.

Finally, ptree supports serialization and deserialization to several formats including Javascript object notation (JSON), the Windows initialization file (INI) format, the extensible markup language (XML), and a custom, ptree-specific format called INFO. For example, to write a ptree into a file in JSON format, you could use the boost::property_tree::write_json function from the <boost/property_tree/json_parser.hpp> header. The function write_json accepts two arguments: the path to the desired output file and a ptree reference.

Listing 13-39 highlights these basic ptree functions by building a ptree representing the property tree in Figure 13-4, writing the ptree to file as JSON, and reading it back.

#include <boost/property_tree/ptree.hpp>
#include <boost/property_tree/json_parser.hpp>

TEST_CASE("boost::property_tree::ptree stores tree data") {
  using namespace boost::property_tree;
  ptree p; ➊
  p.put("name", "finfisher");
  p.put("year", 2014);
  p.put("features.process", "LSASS");
  p.put("features.driver", "mssounddx.sys");
  p.put("features.arch", 32); ➋
  REQUIRE(p.get_child("year").get_value<int>() == 2014); ➌

  const auto file_name = "rootkit.json";
  write_json(file_name, p); ➍

  ptree p_copy;
  read_json(file_name, p_copy); ➎
  REQUIRE(p_copy == p); ➏
}
--------------------------------------------------------------------------
{
    "name": "finfisher",
    "year": "2014",
    "features": {
        "process": "LSASS",
        "driver": "mssounddx.sys",
        "arch": "32"
    }
} ➍

Listing 13-39: The boost::property_tree::ptree method stores tree data. Output shows the contents of rootkit.json.

Here, you’ve default constructed a ptree ➊, which you populate with the key values shown in Figure 13-4. Keys with parents, such as arch ➋, use periods to show the appropriate path. Using get_child, you’ve extracted the subtree for key year. Because it’s a leaf node (having no children), you also invoke get_value, specifying the output type as int ➌.

Next, you write the ptree’s JSON representation to the file rootkit.json ➍. To ensure that you get the same property tree back, you default construct another ptree called p_copy and pass it into read_json ➎. This copy is equivalent to the original ➏, illustrating that the serialization-deserialization operation is successful.

Initializer Lists

You can accept initializer lists in your user-defined types by incorporating the std::initializer_list container available in the STL’s <initializer_list> header. The initializer_list is a class template that takes a single template parameter corresponding to the underlying type contained in the initializer list. This template serves as a simple proxy for accessing the elements of an initializer list.

The initializer_list is immutable and supports three operations:

• The size method returns the number of elements in the initializer_list.
• The begin and end methods return the usual half-open-range iterators.

Generally, you should design functions to accept an initializer_list by value.

Listing 13-40 implements a SquareMatrix class that stores a matrix with equal numbers of rows and columns. Internally, the class will hold elements in a vector of vectors.

#include <cmath>
#include <stdexcept>
#include <initializer_list>
#include <vector>

size_t square_root(size_t x) { ➊
  const auto result = static_cast<size_t>(sqrt(x));
  if (result * result != x) throw std::logic_error{ "Not a perfect square." };
  return result;
}

template <typename T>
struct SquareMatrix {
  SquareMatrix(std::initializer_list<T> val) ➋
    : dim{ square_root(val.size()) }, ➌
      data(dim, std::vector<T>{}) { ➍
    auto itr = val.begin(); ➎
    for(size_t row{}; row<dim; row++){
      data[row].assign(itr, itr+dim); ➏
      itr += dim; ➐
    }
  }
  T& at(size_t row, size_t col) {
    if (row >= dim || col >= dim)
      throw std::out_of_range{ "Index invalid." }; ➑
    return data[row][col]; ➒
  }
  const size_t dim;
private:
  std::vector<std::vector<T>> data;
};

Listing 13-40: An implementation of a SquareMatrix

Here, you declare a convenience square_root function that finds the square root of a size_t, throwing an exception if the argument isn’t a perfect square ➊. The SquareMatrix class template defines a single constructor that accepts a std::initializer called val ➋. This permits braced initialization.

First, you need to determine the dimensions of SquareMatrix. Use the square_root function to compute the square root of val.size() ➌ and store this into the dim field, which represents the number of rows and columns of the SquareMatrix instance. You can then use dim to initialize the vector of vectors data using its fill constructor ➍. Each of these vectors will correspond to a row in SquareMatrix. Next, you extract an iterator pointing to the first element in initializer_list ➎. You iterate over each row in SquareMatrix, assigning the corresponding vector to the appropriate half-open range ➏. You increment the iterator on each iteration to point to the next row ➐.

Finally, you implement an at method to permit element access. You perform bounds checking ➑ and then return a reference to the desired element by extracting the appropriate vector and element ➒.

Listing 13-41 illustrates how to use braced initialization to generate a SquareMatrix object.

TEST_CASE("SquareMatrix and std::initializer_list") {
  SquareMatrix<int> mat { ➊
     1,  2,  3,  4,
     5,  0,  7,  8,
     9, 10, 11, 12,
    13, 14, 15, 16
  };
  REQUIRE(mat.dim == 4); ➋
  mat.at(1, 1) = 6; ➌
  REQUIRE(mat.at(1, 1) == 6); ➍
  REQUIRE(mat.at(0, 2) ==  3); ➎
}

Listing 13-41: Using braced initializers with a SquareMatrix

You use braced initializers to set up SquareMatrix ➊. Because the initializer list contains 16 elements, you end up with a dim of 4 ➋. You can use at to obtain a reference to any element, meaning you can set ➌ and get ➍➎ elements.

Summary

This chapter began with a discussion of the two go-to sequence containers, array and vector, which offer you a great balance between performance and features in a wide range of applications. Next, you learned about several sequence containers—deque, list, stack, queue, priority_queue, and bitset—that fill in when vector doesn’t meet the demands of a particular application. Then you explored the major associative containers, set and map, and their unordered/multipermutations. You also learned about two niche Boost containers, graph and ptree. The chapter wrapped up with a brief discussion of incorporating initializer_lists into user-defined types.

#include <chrono>
#include <cstdio>
#include <random>

long fib_sum(size_t n) { ➊
  // TODO: Adapt code from Exercise 12.1
  return 0;
}

long random() { ➋
  static std::mt19937_64 mt_engine{ 102787 };
  static std::uniform_int_distribution<long> int_d{ 1000, 2000 };
  return int_d(mt_engine);
}

struct Stopwatch { ➌
  Stopwatch(std::chrono::nanoseconds& result)
    : result{ result },
    start{ std::chrono::system_clock::now() } { }
  ~Stopwatch() {
    result = std::chrono::system_clock::now() - start;
  }
private:
  std::chrono::nanoseconds& result;
  const std::chrono::time_point<std::chrono::system_clock> start;
};

long cached_fib_sum(const size_t& n) { ➍
  static std::map<long, long> cache;
  // TODO: Implement me
  return 0;
}

int main() {

  size_t samples{ 1'000'000 };
  std::chrono::nanoseconds elapsed;

  {
    Stopwatch stopwatch{elapsed};
    volatile double answer;
    while(samples--) {
      answer = fib_sum(random()); ➎
      //answer = cached_fib_sum(random()); ➏
    }
  }
  printf("Elapsed: %g s.
", elapsed.count() / 1'000'000'000.); ➐
}