Overview of the C++ Standard Library

WHAT’S IN THIS CHAPTER?

• The coding principles used throughout the Standard Library
• A high-level overview of the functionality provided by the Standard Library

WILEY.COM DOWNLOADS FOR THIS CHAPTER

Please note that all the code examples for this chapter are available as part of this chapter’s code download on the book’s website at www.wiley.com/go/proc++6e on the Download Code tab.

The most important library that you will use as a C++ programmer is the C++ Standard Library. As its name implies, this library is part of the C++ standard, so any standards-conforming compiler should include it. The Standard Library is not monolithic: it includes several disparate components, some of which you have been using already. You may even have assumed they were part of the core language. All Standard Library classes and functions are declared in the std namespace, or a subnamespace of std.

The heart of the C++ Standard Library is its generic containers and algorithms. Some people still call this subset of the library the Standard Template Library, or STL for short, because originally it was based on a third-party library called the Standard Template Library, which used templates abundantly. However, STL is not a term defined by the C++ standard itself, so this book does not use it. The power of the Standard Library is that it provides generic containers and generic algorithms in such a way that most of the algorithms work on most of the containers, no matter what type of data the containers store. Performance is an important aspect of the Standard Library. The goal is to make the Standard Library containers and algorithms as fast as, or faster than, handwritten code.

The C++ Standard Library also includes most of the C headers that are part of the C11 standard, but with new names. For example, you can access the functionality from the C <stdio.h> header by including <cstdio>. The former puts everything in the global namespace, while the latter puts everything in the std namespace. Though, technically, the former is allowed to put things in the std namespace as well, and the latter is allowed to additionally put things in the global namespace. The C11 headers <stdnoreturn.h>, <threads.h>, and their <c…> equivalents are not included in the C++ standard. The <stdatomic.h> header from C11 has been available since C++23, but no equivalent <cstdatomic> is provided. Furthermore, C++17 has deprecated, and C++20 has removed the following C headers:

• <ccomplex> and <ctgmath>: Replace the use of these with <complex> and/or <cmath>.
• <ciso646>, <cstdalign>, and <cstdbool>: These headers were useless in C++ as these were either empty or defined macros that are keywords in C++.

C headers are not guaranteed to be importable. Use #include instead of import to get access to the functionality defined by them.

Note

If there is a C++ equivalent of functionality provided by a C header, it is recommended to use the C++ equivalent.

A C++ programmer who wants to claim language expertise is expected to be familiar with the Standard Library. You can save yourself immeasurable time and energy by incorporating Standard Library containers and algorithms into your programs instead of writing and debugging your own versions. Now is the time to master this Standard Library.

This first chapter on the Standard Library provides a general overview of the available functionality. The next few chapters go into more detail on several aspects of the Standard Library, including containers, iterators, generic algorithms, predefined function object classes, regular expressions, random number generation, and much more. Additionally, Chapter 25, “Customizing and Extending the Standard Library,” is dedicated to customizing and extending the library with your own Standard Library–compliant algorithms and data structures.

Despite the depth of material found in this and the following chapters, the Standard Library is too large for this book to cover exhaustively. You should read these chapters to learn about the Standard Library, but keep in mind that they don’t mention every member function and data member that the various classes provide or show you the prototypes of every algorithm. Appendix C, “Standard Library Header Files,” summarizes all the header files in the Standard Library. Consult your favorite Standard Library Reference for a complete reference of all provided functionality.

CODING PRINCIPLES

The Standard Library makes heavy use of the C++ features called templates and operator overloading.

Use of Templates

Templates are used to allow generic programming. They make it possible to write code that can work with all kinds of objects, even objects unknown to the programmer when writing the code. The obligation of the programmer writing the template code is to specify the requirements of the classes that define these objects, for example, that they have an operator for comparison or a copy constructor, or whatever is deemed appropriate, and then making sure the code that is written uses only those required capabilities. The obligation of the programmer creating the objects is to supply those operators and member functions that the template requires.

Unfortunately, many programmers consider templates to be the most difficult part of C++ and, for that reason, tend to avoid them. However, even if you never write your own templates, you need to understand their syntax and capabilities to use the Standard Library. Templates are described in detail in Chapter 12, “Writing Generic Code with Templates.” If you skipped that chapter and are not familiar with templates, I suggest you first read Chapter 12 and then come back to learn more about the Standard Library.

Use of Operator Overloading

Operator overloading is another feature used extensively by the C++ Standard Library. Chapter 9, “Mastering Classes and Objects,” has a whole section devoted to operator overloading. Make sure you read that section and understand it before tackling this and subsequent chapters. In addition, Chapter 15, “Overloading C++ Operators,” presents much more detail on the subject of operator overloading, but those details are not required to understand the following chapters.

OVERVIEW OF THE C++ STANDARD LIBRARY

This section introduces the various components of the Standard Library from a design perspective. You will learn what facilities are available for you to use, but you will not learn many coding details. Those details are covered in other chapters.

Strings

C++ provides a built-in string class, defined in <string>. This C++ string class is superior in almost every way compared to C-style strings of character arrays. It handles the memory management; provides some bounds checking, assignment semantics, and comparisons; and supports manipulations such as concatenation, substring extraction, and substring or character replacement.

Note

Technically, std::string is a type alias for a char instantiation of the std::basic_string class template. However, you need not worry about these details; you can use string as if it were a bona fide nontemplate class.

The Standard Library also provides a string_view class, defined in <string_view>. It is a read-only view of any kind of string representation and can be used as a drop-in replacement for const string&, but without the overhead. It never copies strings!

C++ provides support for Unicode and localization. Unicode allows you to write programs that work with text in different languages, such as Arabic, Chinese, Japanese, and so on. Locales, defined in <locale>, allow you to format data such as numbers and dates according to the rules of a certain country or region.

C++ includes a powerful type-safe string formatting library, accessed through std::format() and defined in <format>. The library is extensible and allows you to add support for your own custom types. C++23 adds helper functions std::print() and println() to make it easier to print formatted text to the console.

In case you missed it, Chapter 2, “Working with Strings and String Views,” provides all the details of the string and string_view classes and the string formatting library, while Chapter 21, “String Localization and Regular Expressions,” discusses Unicode and localization.

Regular Expressions

Regular expressions are available through functionality provided by <regex>. They make it easy to perform pattern-matching, often used in text processing. Pattern-matching allows you to search for special patterns in strings and optionally to replace them with a new pattern. Regular expressions are discussed in Chapter 21.

I/O Streams

C++ includes a model for input and output called streams. The C++ library provides routines for reading and writing built-in types from and to files, console/keyboard, and strings. C++ also provides the facilities for coding your own routines for reading and writing your own objects. Most of the I/O functionality is defined in <fstream>, <iomanip>, <ios>, <iosfwd>, <iostream>, <istream>, <ostream>, <sstream>, <streambuf>, and <strstream>. C++23 introduces span-based streams, defined in <spanstream>. Chapter 1, “A Crash Course in C++ and the Standard Library,” reviews the basics of I/O streams, and Chapter 13, “Demystifying C++ I/O,” discusses streams in detail.

Smart Pointers

One of the problems faced in robust programming is knowing when to delete an object. There are several failures that can happen. A first problem is not deleting the object at all (failing to free the storage). These are known as memory leaks, where objects accumulate and take up space but are not used. Another problem is where a piece of code deletes the storage while another piece of code is still pointing to that storage, resulting in pointers to storage that either is no longer in use or has been reallocated for another purpose. These are known as dangling pointers. Yet another problem is when one piece of code frees the storage and another piece of code attempts to free the same storage again. This is known as double deletion.

All of these problems tend to result in program failures of some sort. Some failures are readily detected and might crash your application; others cause the program to produce erroneous results. Most of these errors are difficult to discover and repair.

C++ addresses all these problems with smart pointers: unique_ptr, shared_ptr, and weak_ptr, all defined in <memory>. These smart pointers are discussed in Chapter 7, “Memory Management.”

Exceptions

The C++ language supports exceptions, which allow functions to pass errors of various types up to calling functions. The C++ Standard Library provides a class hierarchy of exceptions that you can use in your code as is, or that you can derive from to create your own exception types. Most of the exception support is defined in <exception>, <stdexcept>, and <system_error>. Chapter 14, “Handling Errors,” covers the details of exceptions and the standard exception classes.

Standard Integer Types

The <cstdint> header file defines a number of standard integer types such as intx_t and uintx_t with x equal to 8, 16, 32, or 64. It also includes macros specifying minimum and maximum values of those types. These integer types are discussed in the context of writing cross-platform code in Chapter 34, “Developing Cross-Platform and Cross-Language Applications.”

Numerics Library

The C++ Standard Library provides a collection of mathematical utility classes and functions.

A whole range of common mathematical functions is available, such as abs(), remainder(), fma(), exp(), log(), pow(), sqrt(), sin(), atan2(), sinh(), erf(), tgamma(), ceil(), floor(), and more. The library also supports a number of mathematical special functions to work with Legendre polynomials, beta functions, elliptic integrals, Bessel functions, cylindrical Neumann functions, and so on. These special functions have established names and notations and are often used in mathematical analysis, functional analysis, geometry, physics, and other applications. The lerp() function calculates a linear interpolation or extrapolation: lerp(a,b,t) calculates a+t(b-a). Linear interpolation calculates a certain value between given data points, while extrapolation calculates values that are either lower or higher than the minimum or maximum data point. Most of these functions are defined in <cmath>, some in <cstdlib>.

<numeric> defines gcd() and lcm() that calculate the greatest common divisor and least common multiple of two integer types, respectively. The midpoint() function calculates the midpoint of two values (integers, floating-point numbers, or pointers).

Starting with C++23, quite a few of these functions are marked as constexpr (see Chapter 9), so they can be used to perform compile-time computations. Consult your favorite Standard Library reference to learn exactly which functions are constexpr.

There is a complex number class called complex, defined in <complex>, which provides an abstraction for working with numbers that contain both real and imaginary components.

The compile-time rational arithmetic library provides a ratio class template, defined in <ratio>. This ratio class template can exactly represent any finite rational number defined by a numerator and denominator. This library is discussed in Chapter 22, “Date and Time Utilities.”

The Standard Library also contains a class called valarray, defined in <valarray>, which is similar to vector but is more optimized for high-performance numerical applications. The library provides several related classes to represent the concept of vector slices. From these building blocks, it is possible to build classes to perform matrix mathematics. There is no built-in matrix class; however, there are third-party libraries like Boost that include matrix support. The valarray class is not further discussed in this book.

A selection of often-used mathematical constants is available, all defined in <numbers> in the std::numbers namespace. Here are just a few of the available constants:

CONSTANT	DESCRIPTION	APPROXIMATION
pi	The value of pi (π)	3.141592653589793
inv_pi	The inverse of pi	0.3183098861837907
sqrt2	The square root of 2	1.4142135623730951
e	Euler’s number e	2.718281828459045
phi	The golden ratio	1.618033988749895

Integer Comparisons

The following comparison functions are available: std::cmp_equal(), cmp_not_equal(), cmp_less(), cmp_less_equal(), cmp_greater(), and cmp_greater_equal(), all defined in <utility>. These perform comparisons of two integers and are safe to use on mixed signed and unsigned comparisons.

For example, the following code compares the signed value -1 and the unsigned value 0u using operator>. The output is 1 (= true), because the -1 is first converted to an unsigned integer and hence becomes a big number such as 4,294,967,295, which is definitely greater than 0:

println("{}", (-1> 0u));            // true

Use cmp_greater() to get the correct output:

println("{}", cmp_greater(-1, 0u));  // false

Bit Manipulation

The Standard Library supports the following functions to work with bits, all defined in <bit>. All of these functions require an unsigned integral type as first argument:

FUNCTION	DESCRIPTION
has_single_bit()	Returns true if a given value contains only a single bit, that is, is an integral power of two.
bit_ceil()	Returns the smallest integral power of two greater than or equal to a given value.
bit_floor()	Returns the largest integral power of two smaller than or equal to a given value.
bit_width()	Returns the number of bits needed to store a given value.
rotl() rotr()	Rotates the bits of a given value to the left or right respectively over a given number of positions.
countl_zero() countl_one()	Returns the number of consecutive zero or one bits respectively in a given value starting from the left, that is, starting with the most-significant bit.
countr_zero() countr_one()	Returns the number of consecutive zero or one bits, respectively, in a given value starting from the right, that is, starting with the least-significant bit.
popcount()	Returns the number of one bits in a given value.
byteswap()	Reverses the individual bytes of integral types.

Here are a few examples:

println("{}", popcount(0b10101010u)); // 4

uint8_t value { 0b11101011u };
println("{}", countl_one(value));     // 3
println("{}", countr_one(value));     // 2

value = 0b10001000u;
println("{:08b}", rotl(value, 2));    // 00100010

value = 0b00001011u;
println("bit_ceil({0:08b} = {0}) = {1:08b} = {1}",
    value, bit_ceil(value));          // bit_ceil(00001011 = 11) = 00010000 = 16
println("bit_floor({0:08b} = {0}) = {1:08b} = {1}",
    value, bit_floor(value));         // bit_floor(00001011 = 11) = 00001000 = 8

uint32_t before { 0x12345678u };
println("{:x}", before);              // 12345678
uint32_t after { byteswap(before) };  // C++23 std::byteswap().
println("{:x}", after);               // 78563412

Time and Date Utilities

The Standard Library includes the chrono library, defined in <chrono>. This library makes it easy to work with dates and time, to time certain durations, and more. The library supports calendars to work with dates, and time zones, including functionality to convert times between different time zones. The <ctime> header provides a number of C-style time and date utilities.

Chapter 22 discusses the time and date utilities in detail.

Random Numbers

C++ already has support for generating pseudo-random numbers for a long time with the srand() and rand() functions. However, those functions provide only low-quality basic random numbers. For example, you cannot change the distribution of the generated random numbers.

Since C++11, a powerful random number generation library is available. This library is defined in <random> and comes with random number engines, random number engine adapters, and random number distributions. These can be used to generate high-quality random numbers and support different distributions, such as normal distributions, negative exponential distributions, and so on.

Consult Chapter 23, “Random Number Facilities,” for details on this library.

Initializer Lists

Initializer lists are defined in <initializer_list>. They make it easy to write functions that can accept a variable number of arguments and are discussed in Chapter 1.

Pair and Tuple

<utility> defines the pair class template, which can store two elements of possibly different types. This is known as storing heterogeneous elements. All Standard Library containers discussed further in this chapter store homogeneous elements, meaning that all the elements in the container must have the same type. A pair allows you to store exactly two elements of completely unrelated types in one object. The pair class template is introduced in Chapter 1.

tuple, defined in <tuple>, is a generalization of pair. It is a sequence with a fixed size that can have heterogeneous elements. The number and type of elements for a tuple instantiation is fixed at compile time. Tuples are discussed in Chapter 24, “Additional Vocabulary Types.”

Vocabulary Types

Vocabulary types are types that you will use all the time, just as much as primitive types such as int and double. Using vocabulary types makes your code safer, more efficient, and easier to write, read, and maintain. Examples of vocabulary types discussed earlier in this book are vector, optional, string, unique_ptr, shared_ptr, and so on.

Chapter 24 discusses the following additional vocabulary types:

• variant, defined in <variant>, can hold a single value of one of a given set of types.

• any, defined in <any>, can hold a single value of any type.

• tuple, defined in <tuple>, is a generalization of pair. It can store any number of values, each with its own specific type.

• optional, defined in <optional>, holds a value of a specific type or nothing. It can be used for class data members, function parameters, return types of a function, and so on, if you want to allow for values to be optional. It is introduced in Chapter 1. Chapter 24 explains that optionals support monadic operations, allowing you to easily chain operations on optionals without having to worry whether an optional is empty before applying another operation to it.

• expected, defined in <expected>, holds a value of a specific type, or an error value of a, possibly different, type. This can be useful as the return type of a function because it allows the function to return either the requested data back to the caller or the reason why something went wrong.

Function Objects

A class that implements a function call operator is called a function object. Function objects can, for example, be used as predicates for certain Standard Library algorithms. <functional> defines a number of predefined function objects and supports creating new function objects based on existing ones.

Function objects are discussed in detail in Chapter 19, “Function Pointers, Function Objects, and Lambda Expressions.”

Filesystem

Everything for the filesystem support library is defined in <filesystem> and lives in the std::filesystem namespace. It allows you to write portable code to work with a filesystem. You can use it for querying whether something is a directory or a file, iterating over the contents of a directory, manipulating paths, and retrieving information about files such as their size, extension, creation time, and so on. The filesystem support library is discussed in Chapter 13.

Multithreading

All major CPU vendors are selling processors with multiple cores. They are being used for everything from servers to consumer computers and even smartphones. If you want your software to take advantage of all these cores, then you need to write multithreaded code. The Standard Library provides a couple of basic building blocks for writing such code. Individual threads can be created using the thread class from <thread>. The library also defines jthread, a thread that can be cancelled and that automatically performs a join operation when it is destructed.

In multithreaded code you need to take care that several threads are not reading and writing to the same piece of data at the same time, because that will cause data races. To prevent this, you can use atomics, defined in <atomic>, which give you thread-safe atomic access to a piece of data. Other thread synchronization mechanisms are provided by <condition_variable> and <mutex>. There is also support for the following synchronization primitives: semaphores (<semaphore>), latches (<latch>), and barriers (<barrier>).

If you just need to calculate something, possibly on a different thread, and get the result back with proper exception handling, you can use async and future. These are defined in <future> and are easier to use than directly using thread or jthread.

Writing multithreaded code is discussed in detail in Chapter 27, “Multithreaded Programming with C++.”

Type Traits

Type traits are defined in <type_traits> and provide information about types at compile time. They are useful when writing advanced templates and are discussed in Chapter 26, “Advanced Templates.”

Standard Library Feature-Test Macros

Feature-test macros are available for Standard Library features. These are similar to the feature-test macros for core language features (discussed in Chapter 11, “Modules, Header Files, and Miscellaneous Topics”) and allow you to verify whether a certain feature is supported by your Standard Library implementation. All these macros start with __cpp_lib_. The following lists a few examples. Consult your favorite Standard Library Reference for a complete list of all possible Standard Library feature-test macros.

• __cpp_lib_concepts
• __cpp_lib_ranges
• __cpp_lib_scoped_lock
• __cpp_lib_atomic_float
• __cpp_lib_constexpr_vector
• __cpp_lib_constexpr_tuple
• __cpp_lib_filesystem
• __cpp_lib_three_way_comparison
• …

The value of such a macro is a number representing the month and year when a specific feature was added or updated. The date is formatted as YYYYMM. For example, the value of __cpp_lib_filesystem is 201703, i.e., March 2017.

As Chapter 11 explains, the core language feature-test macros are always available for you to use, without having to include any header. However, the Standard Library feature-test macros are defined in <version>. As all feature-test macros are macros, you know from Chapter 11 that importing the named module std or std.compat will not make those macros available to your code. Chapter 11 also explains that all C++ headers, such as <version>, are importable; thus, you have two options to get access to the macros defined in <version>:

import <version>;

or

#include <version>

Here is a full example:

import std;
import <version>; // Important to get access to the feature-test macros!
using namespace std;

int main()
{
#ifdef __cpp_lib_constexpr_vector
    println("std::vector is constexpr!");
#else
    println("Bummer! std::vector is NOT constexpr!");
#endif
}

Note

You will rarely need these feature-test macros, unless you are writing cross-platform and cross-compiler code. In that case, you might want to know if certain functionality is supported by a given Standard Library implementation so that you can provide fallback code in case a feature is missing. Chapter 34, “Developing Cross-Platform and Cross-Language Applications,” discusses cross-platform development.

<version> can be used to query for implementation-dependent information about the C++ Standard Library that you are using. What exactly your <version> provides depends on your library implementation. The following could possibly be exposed: version number, release date, and copyright notice.

Additionally, as explained in the previous section, <version> exposes all Standard Library feature-test macros.

Source Location

std::source:location, defined in <source:location>, can be used to query information about your source code, such as filename, function name, line number, and column number, and replaces the old C-style macros __FILE__ and __LINE__. Example use cases are to provide source code information when logging messages or when throwing exceptions. Chapter 14 gives an example of both these use cases.

Stack Trace

<stacktrace> defines the std::stacktrace and std::stacktrace:entry classes. These can be used to get a stack trace at any given moment in time and to iterate and inspect each individual entry, known as a frame. See Chapter 14 for an example.

Containers

The Standard Library provides implementations of commonly used data structures such as linked lists and queues. When you use C++, you should not need to write such data structures again. The data structures are implemented using a concept called containers, which store information called elements, in a way that implements the data structure (linked list, queue, and so on) appropriately. Different data structures have different insertion, deletion, and access behavior and performance characteristics. It is important to be familiar with the available data structures so that you can choose the most appropriate one for any given task.

All the containers in the Standard Library are class templates, so you can use them to store any type, from built-in types such as int and double to your own classes. Each container instance stores objects of only one type; that is, they are homogeneous collections. If you need non-fixed-sized heterogeneous collections, you can wrap each element in an std::any instance and store those any instances in a container. Alternatively, you can store std::variant instances in a container. A variant can be used if the number of different required types is limited and known at compile time. Or you can create a class that has multiple derived classes, and each derived class can wrap an object of your required type. Both any and variant are discussed in Chapter 24.

Note

The C++ Standard Library containers are homogeneous: they allow elements of only one type in each container.

The C++ standard specifies the interface, but not the implementation, of each container and algorithm. Thus, different vendors are free to provide different implementations. However, the standard also specifies performance requirements as part of the interface, which the implementations must meet.

This section provides an overview of the various containers available in the Standard Library.

Sequential Containers

The Standard Library provides five sequential containers: vector, list, forward_list, deque, and array.

vector

vector is defined in <vector> and stores a sequence of elements while providing random access to these elements. You can think of a vector as an array of elements that grows dynamically as you insert elements and additionally provides some bounds checking. Like an array, the elements of a vector are stored in contiguous memory.

Note

A vector in C++ is a synonym for a dynamic array: an array that grows and shrinks automatically in response to the number of elements it stores.

vector provides fast element insertion and deletion (amortized constant time) at the end of the vector. Amortized constant time insertion means that most of the time insertions are done in constant time O(1) (Chapter 4, “Designing Professional C++ Programs,” explains big-O notation). However, sometimes the vector needs to grow in size to accommodate new elements, which has a complexity of O(N). On average, this results in O(1) complexity or amortized constant time. Details are explained in Chapter 18, “Standard Library Containers.” A vector has slower (linear time) insertion and deletion anywhere else, because the operation must move all the elements “up” or “down” by one to make room for the new element or to fill the space left by the deleted element. Like arrays, vectors provide fast (constant time) access to any of their elements.

Even though inserting and removing elements in the middle of a vector requires moving other elements up or down, a vector should be your default container! Often, a vector will be faster than, for example, a linked list, even for inserting and removing elements in the middle. The reason is that a vector is stored contiguously in memory, while a linked list is scattered around in memory. Computers are extremely efficient to work with contiguous data, which makes vector operations fast. You should only use something like a linked list if a performance profiler (discussed in Chapter 29, “Writing Efficient C++”) tells you that it performs better than a vector.

Note

The vector container should be your default container.

There is a template specialization available for vector<bool> to store Boolean values in a vector. This specialization optimizes space allocation for the Boolean elements; however, the standard does not specify how an implementation of vector<bool> should optimize space. The difference between the vector<bool> specialization and the bitset discussed later in this chapter is that the bitset container is of fixed size, while vector<bool> automatically grows or shrinks when needed.

list

list is a doubly linked list structure and is defined in <list>. Like an array or vector, it stores a sequence of elements. However, unlike an array or vector, the elements of a list are not necessarily contiguous in memory. Instead, each element in the list specifies where to find the next and previous elements in the list (usually via pointers), which is why it’s called a doubly linked list.

The performance characteristics of a list are the exact opposite of a vector. They provide slow (linear time) element lookup and access, but quick (constant time) insertion and deletion of elements once the relevant position has been found. Still, as discussed in the previous section, a vector is usually faster than a list. Use a profiler (discussed in Chapter 29) to be sure.

forward_list

forward_list, defined in <forward_list>, is a singly linked list, compared to the list container, which is doubly linked. forward_list supports forward iteration only and requires a bit less memory than a list. Like list, forward_list allows constant-time insertion and deletion anywhere once the relevant position has been found, and there is no fast random access to elements.

deque

The name deque is an abbreviation for a double-ended queue. A deque, defined in <deque>, provides quick (constant time) element access. It also provides fast (constant time) insertion and deletion at both ends of the sequence, but it provides slow (linear time) insertion and deletion in the middle of the sequence. The elements of a deque are not stored contiguously in memory, and thus a deque might be slower than a vector.

You could use a deque instead of a vector when you need to insert or remove elements from either end of the sequence but still need fast access to all elements. However, this requirement does not apply to many programming problems; in most cases, a vector is recommended.

array

array, defined in <array>, is a replacement for standard C-style arrays. Sometimes you know the exact number of elements in your container up front, and you don’t need the flexibility of a vector or a list, which are able to grow dynamically to accommodate new elements. An array is perfect for such fixed-sized collections, and it has a bit less overhead compared to a vector; it’s basically a thin wrapper around standard C-style arrays. There are a number of advantages in using arrays instead of standard C-style arrays: they always know their own size and do not automatically get cast to a pointer to avoid certain types of bugs. Also, arrays do not provide insertion or deletion; they have a fixed size. The advantage of having a fixed size is that this allows an array to be allocated on the stack, rather than always demanding access to the free store as vector does. Access to elements is very fast (constant time), just as with vectors.

Note

The vector, list, forward_list, deque, and array containers are called sequential containers because they store a sequence of elements.

Sequential Views

The Standard Library provides two sequential views: span and mdspan.

span

A span, defined in <span>, represents a view on a contiguous sequence of data. It can be either a read-only view or a view with read/write access to the underlying elements. A span allows you to write a single function that can work with data coming from, for example, vectors, arrays, C-style arrays, and so on. Chapter 18 discusses span in more detail.

Note

When writing a function accepting, for example, a const vector<T>&, consider accepting a span<const T> instead, so the function can work with views and subviews of data sequences coming from vectors, arrays, C-style arrays, and more.

mdspan

An mdspan, defined in <mdspan>, is similar to a span but represents a multidimensional view on a contiguous sequence of data. Just as a span, it can be a read-only view or a view with read/write access to the underlying elements. Chapter 18 discusses mdspan in more detail.

Container Adapters

The Standard Library provides three nonassociative container adapters: queue, priority_queue, and stack.

queue

The name queue comes directly from the definition of the English word queue, which means a line of people or objects. The queue container is defined in <queue> and provides standard first in, first out (or FIFO) semantics. A queue is a container in which you insert elements at one end and take them out at the other end. Both insertion (amortized constant time) and removal (constant time) of elements are quick.

You should use a queue structure when you want to model real-life “first-come, first-served” semantics. For example, consider a bank. As customers arrive at the bank, they get in line. As tellers become available, they serve the next customer in line, thus providing “first-come, first-served” behavior. You could implement a bank simulation by storing customer objects in a queue. As customers arrive at the bank, they are added to the end of the queue. As tellers serve customers, they start with customers at the front of the queue.

priority_queue

A priority_queue, also defined in <queue>, provides queue functionality in which each element has a priority. Elements are removed from the queue in priority order. In the case of priority ties, the order in which elements are removed is undefined. priority_queue insertion and deletion are generally slower than simple queue insertion and deletion, because the elements must be reordered to support the priority ordering.

You can use priority_queues to model “queues with exceptions.” For example, in the earlier bank simulation, suppose that customers with business accounts take priority over regular customers. Many real-life banks implement this behavior with two separate lines: one for business customers and one for everyone else. Any customers in the business queue are taken before customers in the other line. However, banks could also provide this behavior with a single line in which business customers move to the front of the line ahead of any non-business customers. In your program, you could use a priority_queue in which customers have one of two priorities: business or regular. All business customers would be serviced before all regular customers.

stack

<stack> defines the stack class, which provides standard first-in, last-out (FILO) semantics, also known as last-in, first-out (LIFO). Like a queue, elements are inserted and removed from the container. However, in a stack, the most recent element inserted is the first one removed. The name stack derives from a visualization of this structure as a stack of objects in which only the top object is visible. When you add an object to the stack, you hide all the objects underneath it.

The stack container provides fast (constant time) insertion and removal of elements. You should use the stack structure when you want FILO semantics. For example, an error-processing tool might want to store errors on a stack so that the most recent error is the first one available for a human administrator to read. Processing errors in a FILO order is often useful because newer errors sometimes obviate older ones.

Note

Technically, the queue, priority_queue, and stack containers are container adapters. They are simple interfaces built on top of one of the standard sequential containers vector, list, or deque.

Ordered Associative Containers

The Standard Library provides four ordered associative containers: set, multiset, map, and multimap. They are called sorted or ordered associative containers because they sort their elements.

set

The set class template is defined in <set>, and, as the name suggests, it is a set of elements, loosely analogous to the notion of a mathematical set: each element is unique, and there is at most one instance of the element in the set. One difference between the mathematical concept of set and set as implemented in the Standard Library is that in the Standard Library the elements are kept in an order. The reason for the order is that an order makes it much faster to verify whether a certain element is already in a set. When a client enumerates the elements, they’ll come out in the ordering imposed by the type’s operator< or a user-defined comparator. The set provides logarithmic insertion, deletion, and lookup. This means that, in theory, insertions and deletions are faster than for a vector but slower than for a list; while lookups are faster than for a list, but slower than for a vector. As always, use a profiler to make sure which container is faster for your use case.

You could use a set when you need the elements to be in an order, to have equal amounts of insertion/deletion and lookups, and you want to optimize performance for both as much as possible. For example, an inventory-tracking program in a busy bookstore might want to use a set to store the books. The list of books in stock must be updated whenever books arrive or are sold, so insertion and deletion should be quick. Customers also need the ability to look for a specific book, so the program should provide fast lookup as well.

Elements in a set cannot be modified, because this could invalidate the order of the elements. If you need to change an element, remove that element first and insert a new one with the new value.

Note

A set could be an option instead of a vector or list if you need order and want equal performance for insertion, deletion, and lookup. It could also be an option if you want to enforce that there are no duplicate elements.

A set does not allow duplicate elements. That is, each element in a set must be unique.

multiset

The multiset class template, also defined in <set>, is almost identical to set, except that a multiset can store duplicate elements.

map

<map> defines the map class template, which is an associative array. You can use it as an array in which the index can be any type, for example, a string. A map stores key/value pairs and keeps its elements in sorted order, based on the keys, not the values. It also provides an operator[], which a set does not provide. In most other respects, it is identical to a set. You could use a map when you want to associate keys and values. For example, in the earlier bookstore example, you might want to store the books in a map where the key is the ISBN number of the book and the value is a Book object containing detailed information for that specific book.

multimap

<map> also defines the multimap class template, which is virtually identical to map, except that a multimap can store elements with duplicate keys.

Note

The set, multiset, map, and multimap containers are called associative containers because they associate keys and values. This term might be slightly confusing when applied to sets and multisets, because for these the keys are themselves the values.

Unordered Associative Containers/Hash Tables

The Standard Library supports hash tables, also called unordered associative containers. There are four unordered associative containers:

• unordered_map and unordered_multimap
• unordered_set and unordered_multiset

The first two containers are defined in <unordered_map>, while the latter two are defined in <unordered_set>. Better names would have been hash_map, hash_set, and so on. Unfortunately, hash tables were not part of the C++ Standard Library before C++11, which means a lot of third-party libraries implemented hash tables themselves by using names with “hash” as a prefix, like hash_map. Because of this, the C++ standard committee decided to use the prefix “unordered” instead of “hash” to avoid name clashes.

These unordered associative containers behave similar to their ordered counterparts. An unordered_map is similar to a standard map except that the standard map sorts its elements, while the unordered_map doesn’t sort its elements.

Insertion, deletion, and lookup with these unordered associative containers can be done on average in constant time. In a worst-case scenario, it will be in linear time. Lookup of elements in an unordered container can be much faster than with a normal map or set, especially when there are a lot of elements in the container.

Chapter 18 explains how these unordered associative containers work and why they are called hash tables.

Flat Associative Container Adapters

C++23 introduces four flat associative container adapters:

• flat_map and flat_multimap defined in <flat_map>
• flat_set and flat_multiset defined in <flat_set>

These are adapters on top of sequential containers and provide an associative container interface. The adapted sequential containers must support random-access iterators, such as vector and deque. The flat_map and flat_multimap adapters require two underlying sequential containers, one to store the keys and another one to store the values. flat_set and flat_multiset require only one underlying sequential container to store their keys.

The interface provided by these adapters is almost identical to their ordered counterpart associative container. The only difference is that the flat adapters don’t provide any of the node-related member functions, as the flat adapters are not node-based data structures. Besides that, they are almost an immediate drop-in replacement for their ordered counterparts.

Chapter 18 gives more details about these flat associative container adapters.

bitset

C and C++ programmers commonly store a set of flags in a single int or long, using one bit for each flag. Bits are set and accessed with the bitwise operators: &, |, ^, ˜, <<, and >>. The C++ Standard Library provides a bitset class that abstracts this bit field manipulation, so you shouldn’t need to use the bit manipulation operators anymore for such use cases.

<bitset> defines the bitset container, but this is not a container in the normal sense, in that it does not implement a specific data structure in which you insert and remove elements. A bitset has a fixed size. You can think of them as a sequence of Boolean values that you can read and write. However, unlike the C-style way of handling bits, the bitset is not limited to the size of an int or other elementary data types. Thus, you can have a 40-bit bitset or a 213-bit bitset. The implementation will use as much storage as it needs to implement N bits when you declare your bitset with bitset<N>.

Summary of Standard Library Containers

The following table summarizes the containers provided by the Standard Library. It uses the big-O notation introduced in Chapter 4 to present the performance characteristics on a container of N elements. An N/A entry in the table means that the operation is not part of the container semantics:

NAME	TYPE	INSERT PERFORMANCE	DELETE PERFORMANCE	LOOKUP PERFORMANCE
vector	Sequential	Amortized O(1) at the end; O(N) otherwise.	O(1) at the end; O(N) otherwise.	O(1)
When to Use: This should be your default container. Only use another container after using a profiler to confirm it is faster than a vector.
list	Sequential	O(1) at the beginning and the end, and once you are at the position where you want to insert the element.	O(1) at the beginning and the end, and once you are at the position where you want to delete the element.	O(1) to access the first or last element; O(N) otherwise.
When to Use: Rarely. You should use a vector, unless a profiler tells you a list is faster for your use case.
forward_list	Sequential	O(1) at the beginning, and once you are at the position where you want to insert the element.	O(1) at the beginning, and once you are at the position where you want to delete the element.	O(1) to access the first element; O(N) otherwise.
When to Use: Rarely. You should use a vector, unless a profiler tells you a forward_list is faster for your use case.
deque	Sequential	O(1) at the beginning or end; O(N) otherwise.	O(1) at the beginning or end; O(N) otherwise.	O(1)
When to Use: Not usually needed; use a vector instead.
array	Sequential	N/A	N/A	O(1)
When to Use: When you need a fixed-size array to replace a standard C-style array.
queue	Container adapter	Depends on the underlying container; O(1) for list and deque.	Depends on the underlying container; O(1) for list and deque.	N/A
When to Use: When you want a FIFO structure.
priority_queue	Container adapter	Depends on the underlying container; amortized O(log(N)) for vector, O(log(N)) for deque.	Depends on the underlying container; O(log(N)) for vector and deque.	N/A
When to Use: When you want a queue with priority.
stack	Container adapter	Depends on the underlying container; O(1) for list and deque, amortized O(1) for vector.	Depends on the underlying container; O(1) for list, vector, and deque.	N/A
When to Use: When you want a FILO/LIFO structure.
set multiset	Sorted associative	O(log(N))	O(log(N))	O(log(N))
When to Use: When you want a sorted collection of elements with equal lookup, insertion, and deletion times. Use a set when you want a collection of elements without duplicates.
map multimap	Sorted associative	O(log(N))	O(log(N))	O(log(N))
When to Use: When you want a sorted collection to associate keys with values, that is, an associative array, with equal lookup, insertion, and deletion times.
unordered_map unordered_multimap	Unordered associative / hash table	Average case O(1); worst case O(N).	Average case O(1); worst case O(N).	Average case O(1); worst case O(N).
When to Use: When you want to associate keys with values with equal lookup, insertion, and deletion times, and you don’t require the elements to be sorted. Performance can be better than with a normal map, but that depends on the elements.
unordered_set unordered_multiset	Unordered associative/hash table	Average case O(1); worst case O(N).	Average case O(1); worst case O(N).	Average case O(1); worst case O(N).
When to Use: When you want a collection of elements with equal lookup, insertion, and deletion times, and you don’t require the elements to be sorted. Performance can be better than with a normal set, but that depends on the elements.
flat_set flat_multiset	Flat set associative container adapter	O(N)	O(N)	O(log(N))
When to Use: When you want a sorted collection of elements. Because the adapters use underlying sequential containers that have very cache-friendly memory layout, the performance is often better than the corresponding ordered container.
flat_map flat_multimap	Flat map associative container adapter	O(N)	O(N)	O(log(N))
When to Use: When you want a sorted collection to associate keys with values. Because the adapters use underlying sequential containers that have very cache-friendly memory layout, the performance is often better than the corresponding ordered container.
bitset	Special	N/A	N/A	O(1)
When to Use: When you want a collection of flags.

Note that strings are technically containers as well. Thus, some of the algorithms described in the material that follows also work on strings.

Note

vector should be your default container! In practice, insertion and deletion in a vector are often faster than in a list or forward_list. This is because of how memory and caches work on modern CPUs and because of the fact that for a list or forward_list, you first need to iterate to the position where you want to insert or delete an element. Memory for a list or forward_list might be fragmented, so iteration is much slower than for a vector.

Algorithms

In addition to containers, the Standard Library provides implementations of many generic algorithms. An algorithm is a strategy for performing a particular task, such as sorting or searching. These algorithms are implemented as function templates, so they work on most of the different container types. Note that the algorithms are not generally part of the containers. The Standard Library takes the approach of separating the data (containers) from the functionality (algorithms). Although this approach seems counter to the spirit of object-oriented programming, it is necessary in order to support generic programming in the Standard Library. The guiding principle of orthogonality maintains that algorithms and containers are independent, with (almost) any algorithm working with (almost) any container.

Note

Although the algorithms and containers are theoretically independent, some containers provide certain algorithms in the form of class member functions because the generic algorithms do not perform well on those particular containers. For example, set provides its own find() algorithm that is faster than the generic find() algorithm. You should use the container-specific member function form of an algorithm, if provided, because it is generally more efficient or appropriate for the container at hand.

Note that the generic algorithms do not work directly on containers; instead, they either use iterators or work on ranges, both discussed in detail in Chapter 17, “Understanding Iterators and the Ranges Library.”

This section gives an overview of what kinds of algorithms are available in the Standard Library without going into detail. Chapter 20, “Mastering Standard Library Algorithms,” discusses a selection of algorithms with coding examples. For the exact prototypes of all the available algorithms, consult your favorite Standard Library reference.

There are more than 100 algorithms in the Standard Library. The following sections divide these algorithms into different categories. The algorithms are defined in <algorithm> unless otherwise noted. Note that whenever the following algorithms are specified as working on a “sequence” of elements, that sequence is presented to the algorithm via iterators.

Note

When examining the list of algorithms, remember that the Standard Library is designed with generality in mind, so it adds generality that might never be used but that, if required, would be essential. You may not need every algorithm or need to worry about the more obscure parameters that are there for anticipated generality. It is important only to be aware of what’s available in case you ever find it useful.

Non-modifying Sequence Algorithms

The non-modifying algorithms are those that look at a sequence of elements and return some information about the elements. As “non-modifying” algorithms, they cannot change the values of elements or the order of elements within the sequence. This category contains three types of algorithms: searching, comparing, and counting. The following sections briefly summarize the various non-modifying algorithms. With these algorithms, you should rarely need to write a for loop to iterate over a sequence of values.

Searching Algorithms

These algorithms do not require the sequence to be sorted. N is the size of the sequence to search in, and M is the size of the pattern to find:

NAME	SYNOPSIS	COMPLEXITY
adjacent_find()	Finds the first instance of two consecutive elements that are equal to each other or are equivalent to each other as specified by a predicate.	O(N)
find() find_if()	Finds the first element that matches a value or causes a predicate to return true.	O(N)
find_first_of()	Like find, but searches for one of several elements at the same time.	O(N*M)
find_if_not()	Finds the first element that causes a predicate to return false.	O(N)
find_end()	Finds the last subsequence in a sequence that matches another sequence or whose elements are equivalent, as specified by a predicate.	O(M*(N-M))
search()	Finds the first subsequence in a sequence that matches another sequence or whose elements are equivalent, as specified by a predicate1.	O(N*M)1
search_n()	Finds the first instance of n consecutive elements that are equal to a given value or relate to that value according to a predicate.	O(N)

[^1] search() accepts an optional extra parameter to specify the searching algorithm to use (default_searcher, boyer_moore_searcher, or boyer_moore_horspool_searcher). With the Boyer–Moore searchers, the worst-case complexity is O(N+M) when the pattern is not found, and O(N*M) when the pattern is found.

Comparison Algorithms

The following comparison algorithms are provided. None of them requires the source sequences to be ordered. All of them have a linear worst-case complexity:

NAME	SYNOPSIS
equal()	Determines whether two sequences are equal by checking whether parallel elements are equal or match a predicate.
mismatch()	Returns the first element in each sequence that does not match the element in the same location in the other sequence.
lexicographical_compare()	Compares two sequences to determine their “lexicographical” ordering. This algorithm compares each element of the first sequence with its equivalent element in the second. If one element is less than the other, that sequence is lexicographically first. If the elements are equal, it compares the next elements in order.
lexicographical_compare_three_way()	Compares two sequences to determine their “lexicographical” ordering using three-way comparisons and returns a comparison category type (strong_ordering, weak_ordering, or partial_ordering).
all_of()	Returns true if a given predicate returns true for all the elements in the sequence or if the sequence is empty; false otherwise.
any_of()	Returns true if a given predicate returns true for at least one element in the sequence; false otherwise.
none_of()	Returns true if a given predicate returns false for all the elements in the sequence or if the sequence is empty; false otherwise.

Counting Algorithms

The following counting algorithms are available. None of them requires the source sequences to be ordered. All of them have a linear worst-case complexity:

NAME	SYNOPSIS
count() count_if()	Counts the number of elements matching a value or that cause a predicate to return true.

Modifying Sequence Algorithms

The modifying algorithms modify some or all of the elements in a sequence. Some of them modify elements in place so that the original sequence changes. Others copy the results to a different sequence so that the original sequence remains unchanged. All of them have a linear worst-case complexity. The following table summarizes the modifying algorithms:

NAME	SYNOPSIS
copy() copy_backward()	Copies elements from one sequence to another.
copy_if()	Copies elements for which a predicate returns true from one sequence to another.
copy_n()	Copies n elements from one sequence to another.
fill()	Sets all elements in the sequence to a new value.
fill_n()	Sets the first n elements in the sequence to a new value.
generate()	Calls a given function to generate a new value for each element in the sequence.
generate_n()	Calls a given function to generate a new value for the first n elements in the sequence.
move() move_backward()	Moves elements from one sequence to another using efficient move semantics (see Chapter 9).
remove() remove_if() remove_copy() remove_copy_if()	Removes all elements that match a given value or that cause a predicate to return true, either in place or by copying the results to a different sequence.
replace() replace:if() replace:copy() replace:copy_if()	Replaces all elements matching a value or that cause a predicate to return true with a new element, either in place or by copying the results to a different sequence.
reverse() reverse_copy()	Reverses the order of the elements in the sequence, either in place or by copying the results to a different sequence.
rotate() rotate_copy()	Swaps the first and second “halves” of the sequence, either in place or by copying the results to a different sequence. The two subsequences to be swapped need not be equal in size.
sample()	Selects n random elements from the sequence.
shift_left() shift_right()	Shifts the elements in a sequence left or right by a given number of positions. Elements are moved to their new position. Elements that fall of either end of the sequence are removed. shift_left() returns an iterator to the end of the new sequence; shift_right() returns an iterator to the beginning of the new sequence.
shuffle() random_shuffle()	Shuffles the sequence by randomly reordering the elements. It is possible to specify the properties of the random number generator used for shuffling. random_shuffle() is deprecated since C++14, and is removed starting with C++17.
transform()	Calls a unary function on each element of a sequence or a binary function on parallel elements of two sequences, and stores the results in a destination sequence. If the source and destination sequences are the same, the transformation happens in-place.
unique() unique_copy()	Removes consecutive duplicates from the sequence, either in place or by copying results to a different sequence.

Operational Algorithms

Operational algorithms execute a function on individual elements of a sequence. There are two operational algorithms provided. Both have a linear complexity and do not require the source sequence to be ordered:

NAME	SYNOPSIS
for_each()	Executes a function on each element in the sequence. The sequence is specified with a begin and end iterator.
for_each_n()	Similar to for_each() but only processes the first n elements in the sequence. The sequence is specified by a begin iterator and a number of elements (n).

Swap Algorithms

The C++ Standard Library provides the following swap algorithms:

NAME	SYNOPSIS
iter_swap() swap_ranges()	Swaps two elements or sequences of elements.

Partitioning Algorithms

A sequence is partitioned on a certain predicate, if all elements for which the predicate returns true are before all elements for which it returns false. The first element in the sequence that does not satisfy the predicate is called the partition point. The Standard Library provides the following partition algorithms:

NAME	SYNOPSIS	COMPLEXITY
is_partitioned()	Returns true if all elements for which a predicate returns true are before all elements for which it returns false.	Linear
partition()	Sorts the sequence such that all elements for which a predicate returns true are before all elements for which it returns false, without preserving the original order of the elements within each partition.	Linear
stable_partition()	Sorts the sequence such that all elements for which a predicate returns true are before all elements for which it returns false, while preserving the original order of the elements within each partition.	Linear logarithmic
partition_copy()	Copies elements from one sequence to two different sequences. The target sequence is selected based on the result of a predicate, either true or false.	Linear
partition_point()	Returns an iterator such that all elements before this iterator return true for a predicate and all elements after this iterator return false for that predicate.	Logarithmic

Sorting Algorithms

The Standard Library provides several different sorting algorithms with varying performance guarantees:

NAME	SYNOPSIS	COMPLEXITY
is_sorted()	Returns true if a sequence is sorted, false otherwise.	Linear
is_sorted_until()	Finds the largest sorted subrange starting at the beginning of the given range of elements.	Linear
nth_element()	Relocates the nth element of the sequence such that the element in the position pointed to by nth is the element that would be in that position if the whole range were sorted, and it rearranges all elements such that all elements preceding the nth element are less than the new nth element, and the ones following it are greater than the new nth element.	Linear
partial_sort() partial_sort_copy()	Partially sorts the sequence: the first n elements (specified by iterators) are sorted; the rest are not. They are sorted either in place or by copying them to a new sequence.	Linear logarithmic
stable_sort() sort()	Sorts elements in place, either preserving the order of duplicate elements (stable) or not.	Linear logarithmic

Binary Search Algorithms

The following binary search algorithms are normally used on sorted sequences. Technically, they only require the sequence to be at least partitioned on the element that is searched for. This could, for example, be achieved by applying std::partition(). A sorted sequence also meets this requirement. All these algorithms have logarithmic complexity:

NAME	SYNOPSIS
lower_bound()	Finds the first element in a sequence not less than (that is, greater or equal to) a given value.
upper_bound()	Finds the first element in a sequence greater than a given value.
equal_range()	Returns a pair containing the result of both lower_bound() and upper_bound().
binary_search()	Returns true if a given value is found in a sequence; false otherwise.

Set Algorithms on Sorted Sequences

Set algorithms are special modifying algorithms that perform set operations on sequences. They are most appropriate on sequences from set containers, but work on sorted sequences from most containers:

NAME	SYNOPSIS	COMPLEXITY
includes()	Determines whether every element from one sorted sequence is in another sorted sequence.	Linear
set_union() set_intersection() set_difference() set_symmetric_difference()	Performs the specified set operation on two sorted sequences, copying results to a third sorted sequence.	Linear

Other Algorithms on Sorted Sequences

The Standard Library provides the following additional algorithms that work on sorted sequences:

NAME	SYNOPSIS	COMPLEXITY
inplace:merge()	Merges two sorted sequences in place.	Linear logarithmic
merge()	Merges two sorted sequences by copying them to a new sequence.	Linear

Heap Algorithms

A heap is a standard data structure in which the elements of an array or sequence are ordered in a semi-sorted fashion so that finding the “top” element is quick. For example, a heap data structure is typically used to implement a priority_queue. Six algorithms allow you to work with heaps:

NAME	SYNOPSIS	COMPLEXITY
is_heap()	Returns true if a range of elements is a heap, false otherwise.	Linear
is_heap_until()	Finds the largest subrange that is a heap, starting at the beginning of the given range of elements.	Linear
make_heap()	Creates a heap from a range of elements.	Linear
push_heap() pop_heap()	Adds an element to, or removes an element from, a heap.	Logarithmic
sort_heap()	Converts a heap into a range of ascending sorted elements.	Linear logarithmic

Minimum/Maximum Algorithms

The following algorithms are provided to find minimum and maximum elements and to clamp values:

NAME	SYNOPSIS
clamp()	Makes sure a value (v) is between a given minimum (lo) and maximum (hi). Returns a reference to lo if v < lo; returns a reference to hi if v > hi; otherwise returns a reference to v.
min() max()	Returns the minimum or maximum of two or more values.
minmax()	Returns the minimum and maximum of two or more values as a pair.
min_element() max_element()	Returns the minimum or maximum element in a sequence.
minmax_element()	Returns the minimum and maximum element in a sequence as a pair.

Numerical Processing Algorithms

The following numerical processing algorithms are defined in <numeric>. None of them require the source sequences to be ordered. All of them have a linear complexity:

NAME	SYNOPSIS
iota()	Fills a sequence with successively incrementing values starting with a given value.
adjacent_difference()	Generates a new sequence in which each element is the difference (or other binary operation) of the second and first of each adjacent pair of elements in the source sequence.
partial_sum()	Generates a new sequence in which each element is the sum (or other binary operation) of an element and all its preceding elements in the source sequence.
exclusive_scan() inclusive_scan()	These are similar to partial_sum(). An inclusive scan is identical to a partial sum if the given summation operation is associative. However, inclusive_scan() sums in a nondeterministic order, while partial_sum() left to right, so for nonassociative summation operations the result of the former is nondeterministic. The exclusive_scan() algorithm also sums in a nondeterministic order. For inclusive_scan(), the ith element is included in the ith sum, just as for partial_sum(). For exclusive_scan(), the ith element is not included in the ith sum.
transform_exclusive_scan() transform_inclusive_scan()	Applies a transformation to each element in a sequence, then performs an exclusive/inclusive scan.
accumulate()	“Accumulates” the values of all the elements in a sequence. The default behavior is to sum the elements, but the caller can supply a different binary function instead.
inner_product()	Similar to accumulate(), but works on two sequences. This algorithm calls a binary function (multiplication by default) on parallel elements in the sequences, accumulating the result using another binary function (addition by default). If the sequences represent mathematical vectors, the algorithm calculates the dot product of the vectors.
reduce()	Similar to accumulate(), but supports parallel execution. The order of evaluation for reduce() is nondeterministic, while it’s from left to right for accumulate(). This means that the behavior of the former is nondeterministic if the given binary operation is not associative or not commutative.
transform_reduce()	Applies a transformation to each element in a sequence, then performs a reduce().

Permutation Algorithms

A permutation of a sequence contains the same elements but in a different order. The following algorithms are provided to work with permutations:

NAME	SYNOPSIS	COMPLEXITY
is_permutation()	Returns true if the elements in one range are a permutation of the elements in another range.	Quadratic
next_permutation() prev_permutation()	Modifies the sequence by transforming it into its “next” or “previous” lexicographical permutation. Successive calls to one or the other will permute the sequence into all possible permutations of its elements, if you start with a properly sorted sequence. This algorithm returns false if no more permutations exist.	Linear

Choosing an Algorithm

The number and capabilities of the algorithms might overwhelm you at first. It can be difficult to see how to apply them in the beginning. However, now that you have an idea of the available options, you are better able to tackle your program designs. The following chapters cover the details of how to use these algorithms in your code.

Ranges Library

The ranges library makes it easier and more elegant to work with sequences of elements. Ranges provide nicer and easier-to-read syntax and eliminate the possibility of mismatching begin/end iterators. Additionally, range adapters allow you to lazily transform and filter underlying sequences, and range factories are provided to build up ranges.

Most algorithms discussed in the previous sections have variants that work with ranges in addition to iterators. Those variants are often called range-based algorithms or constrained algorithms because they have proper template type parameter constraints in the form of concepts. This allows the compiler to issue better error messages if such a constrained algorithm is used wrongly.

Additionally, C++23 introduces the following algorithms that are available only in a constrained variant. All of them have a linear complexity.

NAME	SYNOPSIS
contains() contains_subrange()	Returns true if a given range contains a given value, respectively, a given subrange, false otherwise.
starts_with() ends_with()	Returns true if a given range starts, respectively, ends with another given range, false otherwise.
find_last() find_last_if() find_last_if_not()	Finds the last element in a given range that either matches a given value, or for which a given predicate returns true, or for which a given predicate returns false. The result is a subrange starting at the found element until the end of the range.
fold_left() fold_left_first() fold_right() fold_right_last() fold_left_with_iter() fold_left_first_with_iter()	Folds the elements of a given range left or right. fold_left() and fold_right() accept an initial value as one of their arguments, and return the result of the fold operation. fold_left_first() uses the first element in a given range as the starting value, while fold_right_last() uses the last element in a given range as the starting value. Both of these return an optional containing the result, or an empty optional if applied to an empty range. The last two variants return an instance of fold_left_with_iter_result, respectively, fold_left_first_with_iter_result that you can use to inspect the result of the fold operation.

The ranges library is defined in <ranges> and lives in the std::ranges namespace. Chapter 17 discusses the ranges library, while Chapter 20 discusses unconstrained and constrained algorithms with coding examples.

What’s Missing from the Standard Library

The Standard Library is powerful, but it’s not perfect. Here are two examples of missing functionality:

• The Standard Library does not guarantee any thread safety for accessing containers simultaneously from multiple threads.
• The Standard Library does not provide any generic tree or graph structures. Although map and set are generally implemented as balanced binary trees, the Standard Library does not expose this implementation in the interface. If you need a tree or graph structure for something like writing a parser, you need to implement your own or find an implementation in another library.

It is important to keep in mind that the Standard Library is extensible. You can write your own containers and algorithms that work with existing algorithms and containers. So, if the Standard Library doesn’t provide exactly what you need, consider writing your desired code such that it works with the Standard Library. Chapter 25 covers the topic of customizing and extending the Standard Library with custom algorithms and custom containers. Alternatively, you can consider buying or licensing a Standard Library-compliant third-party library that provides the required functionality. See Chapter 4, “Designing Professional C++ Programs,” for a discussion on using third-party libraries and licensing options.

SUMMARY

This chapter provided an overview of the C++ Standard Library, which is the most important library that you will use in your code. It subsumes the C library and includes additional facilities for strings, I/O, error handling, and other tasks. It also includes generic containers, algorithms, and the ranges library. The following chapters describe the Standard Library in more detail.

EXERCISES

By solving the following exercises, you can practice the material discussed in this chapter. Solutions to all exercises are available with the code download on the book’s website at www.wiley.com/go/proc++6e. However, if you are stuck on an exercise, first reread parts of this chapter to try to find an answer yourself before looking at the solution from the website.

1. Exercise 16-1: The C++ Standard Library provides a whole selection of containers for you to choose from. What should be your preferred container and why?
2. Exercise 16-2: What are the differences between a map and an unordered_map?
3. Exercise 16-3: What are vocabulary types? Besides the vocabulary types already used earlier in this book, this chapter introduced a few additional vocabulary types provided by the C++ Standard Library. What are they?
4. Exercise 16-4: A self-service restaurant usually has a spring-loaded mechanism containing plates. As a customer, you take a plate from the top. When plates are cleaned and ready to be used again, they are placed on top of any remaining plates in the mechanism. How would you model such a system in C++?
5. Exercise 16-5: What is a partition?