Understanding Containers and Iterators - Coding the Professional Way - Professional C++ (2014)

Professional C++ (2014)

Part IIICoding the Professional Way

Chapter 16Understanding Containers and Iterators

WHAT’S IN THIS CHAPTER?

· Explaining iterators

· Containers Overview: requirements on elements, general error handling, and iterators

· Sequential Containers: vector, deque, list, forward_list, and array

· Container Adapters: queue, priority_queue, and stack

· Associative Containers: the pair utility, map, multimap, set, and multiset

· Unordered Associative Containers/Hash Tables: unordered_map, unordered_multimap, unordered_set, and unordered_multiset

· Other Containers: standard C-style arrays, strings, streams, and bitset

WROX.COM DOWNLOADS FOR THIS CHAPTER

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

Chapter 15 introduces the STL, describes its basic philosophy, and provides an overview of the various containers and algorithms. This chapter begins a more-in-depth tour of the STL by covering the STL containers. A detailed list of available classes and methods can be found in a Standard Library Reference; for example, http://www.cppreference.com/ or http://www.cplusplus.com/reference/.

The next chapters go deeper on topics such as algorithms, regular expressions, and how you can customize and extend the STL.

CONTAINERS OVERVIEW

Containers in the STL are generic data structures useful for storing collections of data. You should rarely need to use a standard C-style array, write a linked list, or design a stack when you use the STL. The containers are implemented as templates, which allow you to instantiate them for any type that meets certain basic conditions outlined below. Most of the STL containers, except for array and bitset, are flexible in size and will automatically grow or shrink to accommodate more or fewer elements. This is a huge benefit compared to the old standard C-style arrays, which had a fixed size. Because of the fixed-size nature of standard C-style arrays, they are more vulnerable to overruns, which in the simplest cases merely cause the program to crash because data has been corrupted, but in the worst cases allow certain kinds of security attacks. By using STL containers your programs will be less vulnerable to these kinds of problems.

The STL provides 16 containers, divided into four categories.

  • Sequential containers
    • vector (dynamic array)
    • deque
    • list
    • forward_list
    • array
  • Associative containers
    • map
    • multimap
    • set
    • multiset
  • Unordered associative containers or hash tables
    • unordered_map
    • unordered_multimap
    • unordered_set
    • unordered_multiset
  • Container adapters
    • queue
    • priority_queue
    • stack

Additionally, C++ strings and streams can also be used as STL containers to a certain degree, and bitset can be used to store a fixed number of bits.

Everything in the STL is in the std namespace. The examples in this book usually use the blanket using namespace std; statement in source files (never use this in header files!), but you can be more selective in your own programs about which symbols from std to use.

Requirements on Elements

STL containers use value semantics on elements. That is, they store a copy of elements that they are given, assign to elements with the assignment operator, and destroy elements with the destructor. Thus, when you write classes that you intend to use with the STL, make sure they are copyable. When requesting an element from the container, a reference to the stored copy is returned.

If you prefer reference semantics, you must implement them yourself by storing pointers to elements instead of the elements themselves. When the containers copy a pointer, the result still refers to the same element.

WARNING If you want to store pointers in containers use unique_ptr if the container becomes owner of the pointed-to object, or shared_ptr if the container shares ownership with other owners. Do not use the old deprecated auto_ptr class in containers because it does not implement copying correctly (as far as the STL is concerned).

One of the template type parameters for STL containers is a so-called allocator. The container can use this allocator to allocate and deallocate memory for elements. Some containers, such as a map; also accept a comparator as one of the template type parameters. This comparator is used to order elements. Both of these template parameters have default values.

The specific requirements on elements in containers using the default allocator and comparator are shown in the following table:

METHOD

DESCRIPTION

NOTES

Copy Constructor

Creates a new element that is “equal” to the old one, but that can safely be destructed without affecting the old one

Used every time you insert an element, except when using an emplace method

Move Constructor

Creates a new element by moving all content from a source element to the new element

Used when the source element is an rvalue, and will be destroyed after the construction of the new element; also used when a vector grows in size, for example

Assignment Operator

Replaces the contents of an element with a copy of the source element

Used every time you modify an element

Move Assignment Operator

Replaces the contents of an element by moving all content from a source element

Used when the source element is an rvalue, and will be destroyed after the assignment operation

Destructor

Cleans up an element

Used every time you remove an element, or, for example, when a vector grows in size and the elements are not movable

Default Constructor

Constructs an element without any arguments

Required only for certain operations, such as the vector::resize() method with one argument, and the map::operator[] access

operator==

Compares two elements for equality

Required for keys in unordered containers, and for certain operations, such as operator== on two containers

operator<

Determines if one element is less than another

Required for keys in associative containers, and for certain operations, such as operator< on two containers

Chapter 8 shows you how to write these methods. Move semantics is discussed in Chapter 10. For move semantics to work properly with STL containers, the move constructor and the move assignment operator must be marked as noexcept.

WARNING The STL containers call the copy constructor and assignment operator for elements often, so make those operations efficient. You can also increase performance by implementing move semantics for your elements, as described in Chapter 10.

Exceptions and Error Checking

The STL containers provide limited error checking. Clients are expected to ensure that their uses are valid. However, some container methods and functions throw exceptions in certain conditions such as out-of-bounds indexing. This chapter mentions exceptions where appropriate. Consult a Standard Library Reference for a list of possible exceptions thrown from each method. However, it is impossible to list exhaustively the exceptions that can be thrown from these methods because they perform operations on user-specified types with unknown exception characteristics.

Iterators

The STL uses the iterator pattern to provide a generic abstraction for accessing the elements of the containers. Each container provides a container-specific iterator, which is a glorified smart pointer that knows how to iterate over the elements of that specific container. The iterators for all the different containers adhere to a specific interface defined in the C++ standard. Thus, even though the containers provide different functionality, the iterators present a common interface to code that wishes to work with elements of the containers.

You can think of an iterator as a pointer to a specific element of the container. Like pointers to elements in an array, iterators can move to the next element with operator++. Similarly, you can usually use operator* and operator-> on the iterator to access the actual element or field of the element. Some iterators allow comparison with operator== and operator!=, and support operator-- for moving to previous elements.

All iterators must be copy constructible, copy assignable, and destructible. Lvalues of iterators must be swappable. Different containers provide iterators with slightly different additional capabilities. The standard defines five categories of iterators, summarized in the following table.

ITERATOR CATEGORY

OPERATIONS REQUIRED

COMMENTS

Read (officially called “input” iterator)

operator++
operator*
operator->
copy constructor
operator=
operator==
operator!=

Provides read-only access, forward only (no operator-- to move backward).
Iterators can be assigned, copied, and compared for equality.

Write (officially called “output” iterator)

operator++
operator*
copy constructor
operator=

Provides write-only access, forward only.
Iterators can be assigned, but cannot be compared for equality.
Note the absence of operator->.

Forward

Capabilities of input iterators, plus: default constructor

Provides read/write access, forward only.
Iterators can be assigned, copied, and compared for equality.

Bidirectional

Capabilities of forward iterators, plus:
operator--

Provides everything forward iterator provides.
Iterators can also move backward to previous element.

Random Access

Bidirectional capability, plus:
operator+
operator-
operator+=
operator-=
operator<
operator>
operator<=
operator>=
operator[]

Equivalent to dumb pointers: Iterators support pointer arithmetic, array index syntax, and all forms of comparison.

Additionally, you can use std::distance() to compute the distance between two iterators of a container.

Iterators are implemented similarly to smart pointer classes in that they overload the specific desired operators. Consult Chapter 14 for details on operator overloading.

The basic iterator operations are similar to those supported by dumb pointers, so a dumb pointer can be a legitimate iterator for certain containers. In fact, the vector iterator could technically be implemented as a simple dumb pointer. However, as a client of the containers, you need not worry about the implementation details; you can simply use the iterator abstraction.

NOTE Iterators might not be implemented internally as pointers, so this text uses the term “refers to” instead of “points to” when discussing the elements accessible via an iterator.

Chapters 17 delves into more detail about iterators and the STL algorithms that use them. This chapter shows you the basics of using the iterators for each container.

NOTE Only the sequential containers, associative containers, and unordered associative containers provide iterators. The container adapters and bitset class do not support iteration over their elements.

Common Iterator typedefs and Methods

Every container class in the STL that supports iterators provides public typedefs for its iterator types called iterator and const_iterator. For example, a const iterator for a vector of ints has as type std::vector<int>::const_iterator. Containers that allow you to iterate over its elements in reverse order also provide public typedefs called reverse_iterator and const_reverse_iterator. This way, clients can use the container iterators without worrying about the actual types.

NOTE const_iterators and const_reverse_iterators provide read-only access to elements of the container.

The containers also provide a method begin() that returns an iterator referring to the first element in the container. The end() method returns an iterator to the “past-the-end” value of the sequence of elements. That is, end() returns an iterator that is equal to the result of applying operator++ to an iterator referring to the last element in the sequence. Together begin() and end() provide a half-open range that includes the first element but not the last. The reason for this apparent complication is to support empty ranges (containers without any elements), in which case begin() is equal to end(). The half-open range bounded by iterators begin() and end() is often written mathematically like this: [begin,end).

NOTE The half-open range concept also applies to iterator ranges that are passed to container methods such as insert() and erase(). See the specific container descriptions later in this chapter for details.

Similarly, there are:

· cbegin() and cend() methods that return const iterators.

· rbegin() and rend() methods that return reverse iterators.

· crbegin() and crend() methods that return const reverse iterators.

NOTE The standard library also provides global non-member functions called std::begin(), and end(), while C++14 adds std::cbegin(), cend(), rbegin(), rend(), crbegin(), and crend(). It’s recommended to use these non-member functions instead of the member versions.

SEQUENTIAL CONTAINERS

vector, deque, list, forward_list, and array are called sequential containers. The best way to learn about sequential containers is to jump in with an example of the vector container, which is the container most commonly used. The next section describes the vectorcontainer in detail, followed by briefer descriptions of deque, list, forward_list, and array. Once you become familiar with the sequential containers, it’s trivial to switch between them.

vector

The STL vector container is similar to a standard C-style array: the elements are stored in contiguous memory, each in its own “slot.” You can index into a vector, as well as add new elements to the back or insert them anywhere else. Inserting and deleting elements into and from a vector generally takes linear time, though these operations actually run in amortized constant time at the end of a vector, explained in the section “The vector Memory Allocation Scheme” later in this chapter. Random access of individual elements has a constant complexity.

vector Overview

vector is defined in the <vector> header file as a class template with two type parameters: the element type to store and an allocator type.

template <class T, class Allocator = allocator<T> > class vector;

The Allocator parameter specifies the type for a memory allocator object that the client can set in order to use custom memory allocation. This template parameter has a default value.

NOTE The default value for the Allocator type parameter is sufficient for most applications. This chapter assumes that you always use the default allocator. Chapter 20 provides more details in case you are interested.

Fixed-Length vectors

The simplest way to use a vector is as a fixed-length array. vector provides a constructor that allows you to specify the number of elements, and provides an overloaded operator[] in order to access and modify those elements. The C++ standard states that the result ofoperator[] is undefined when used to access an element outside the vector bounds. This means that any compiler can decide how to behave in that case. For example, the default behavior of Microsoft Visual C++ is to give a run-time error message when your program is compiled in debug mode, and to disable any bounds checking in release mode for performance reasons. You can change these default behaviors.

WARNING Like “real” array indexing, the operator[] on a vector does not provide bounds checking.

In addition to using operator[], you can access vector elements via at(), front(), and back(). The at() method is identical to operator[], except that it performs bounds checking, and throws an out_of_range exception if the index is out of bounds. front() and back()return references to the first and last elements of a vector, respectively. Calling front() or back() on an empty container causes undefined behavior.

NOTE All vector element accesses run with constant complexity.

Here is a small example program to “normalize” test scores so that the highest score is set to 100, and all other scores are adjusted accordingly. The program creates a vector of 10 doubles, reads in 10 values from the user, divides each value by the max score (times 100), and prints out the new values. For the sake of brevity, the program forsakes error checking.

vector<double> doubleVector(10); // Create a vector of 10 doubles.

// Initialize max to smallest number

double max = -numeric_limits<double>::infinity();

for (size_t i = 0; i < doubleVector.size(); i++) {

cout << "Enter score " << i + 1 << ": ";

cin >> doubleVector[i];

if (doubleVector[i] > max) {

max = doubleVector[i];

}

}

max /= 100.0;

for (auto& element : doubleVector) {

element /= max;

cout << element << " ";

}

As you can see from this example, you can use a vector just as you would use a standard C-style array. Note that the first for loop uses the size() method to determine the number of elements in the container. The example also demonstrates the use of a range-basedfor loop with a vector. In this example, the range-based for loop uses auto& and not auto because a reference is required so that the element can be modified in each iteration.

NOTE The operator[] on a vector normally returns a reference to the element, which can be used on the left-hand side of assignment statements. If operator[] is called on a const vector object, it returns a reference to a const element, which cannot be used as the target of an assignment. See Chapter 14 for details on how this trick is implemented.

Dynamic-Length vectors

The real power of a vector lies in its ability to grow dynamically. For example, consider the test score normalization program from the previous section with the additional requirement that it should handle any number of test scores. Here is the new version:

vector<double> doubleVector; // Create a vector with zero elements.

// Initialize max to smallest number

double max = -numeric_limits<double>::infinity();

for (size_t i = 1; true; i++) {

double temp;

cout << "Enter score " << i << " (-1 to stop): ";

cin >> temp;

if (temp == -1) {

break;

}

doubleVector.push_back(temp);

if (temp > max) {

max = temp;

}

}

max /= 100.0;

for (auto& element : doubleVector) {

element /= max;

cout << element << " ";

}

This version of the program uses the default constructor to create a vector with zero elements. As each score is read, it’s added to the vector with the push_back() method, which takes care of allocating space for the new element. The range-based for loop doesn’t require any changes.

vector Details

Now that you’ve had a taste of vectors, it’s time to delve into their details.

Constructors and Destructors

The default constructor creates a vector with 0 elements.

vector<int> intVector; // Creates a vector of ints with zero elements

You can specify a number of elements and, optionally, a value for those elements, like this:

vector<int> intVector(10, 100); // Creates vector of 10 ints with value 100

If you omit the default value, the new objects are zero-initialized. Zero-initialization constructs objects with the default constructor, initializes primitive integer types (such as char, int, etc.) to 0, primitive floating point types to 0.0, and pointer types to nullptr.

You can create vectors of built-in classes like this:

vector<string> stringVector(10, "hello");

User-defined classes can also be used as vector elements:

class Element

{

public:

Element() {}

virtual ~Element() {}

};

...

vector<Element> elementVector;

A vector can be constructed with an initializer_list containing the initial elements:

vector<int> intVector({ 1, 2, 3, 4, 5, 6 });

initializer_lists can also be used for so-called uniform initialization, as discussed in Chapter 10. Uniform initialization works on most STL containers. For example:

vector<int> intVector1 = { 1, 2, 3, 4, 5, 6 };

vector<int> intVector2{ 1, 2, 3, 4, 5, 6 };

You can allocate vectors on the heap as well:

auto elementVector = make_unique<vector<Element>>(10);

Copying and Assigning vectors

A vector stores copies of the objects, and its destructor calls the destructor for each of the objects. The copy constructor and assignment operator of the vector class perform deep copies of all the elements in the vector. Thus, for efficiency, you should pass vectors by reference or const reference to functions and methods. Consult Chapter 11 for the details on writing functions that take template instantiations as parameters.

In addition to normal copying and assignment, vectors provide an assign() method that removes all the current elements and adds any number of new elements. This method is useful if you want to reuse a vector. Here is a trivial example. intVector is created with 10 elements having the default value 0. Then assign() is used to remove all 10 elements and replace them with 5 elements with value 100.

vector<int> intVector(10);

// Other code . . .

intVector.assign(5, 100);

assign() can also accept an initializer_list as follows. intVector will now have 4 elements with the given values.

intVector.assign({ 1, 2, 3, 4 });

vectors also provide a swap() method that allows you to swap the contents of two vectors in constant time. Here is a simple example:

vector<int> vectorOne(10);

vector<int> vectorTwo(5, 100);

vectorOne.swap(vectorTwo);

// vectorOne now has 5 elements with the value 100.

// vectorTwo now has 10 elements with the value 0.

Comparing vectors

The STL provides the usual six overloaded comparison operators for vectors: ==, !=, <, >, <=, >=. Two vectors are equal if they have the same number of elements and all the corresponding elements in the two vectors are equal to each other. Two vectors are compared lexicographically, that is, one vector is “less than” another if all elements 0 through i–1 in the first vector are equal to elements 0 through i-1 in the second vector, but element i in the first is less than element i in the second, where i must be in the range0...n and n must be less than size().

NOTE Comparing two vectors with operator== or operator!= requires the individual elements to be comparable with operator==. Comparing two vectors with operator<, operator>, operator<=, or operator>= requires the individual elements to be comparable with operator<. If you intend to store objects of a custom class in a vector, make sure to write those operators.

Here is an example of a simple program that compares vectors of ints:

vector<int> vectorOne(10);

vector<int> vectorTwo(10);

if (vectorOne == vectorTwo) {

cout << "equal!" << endl;

} else {

cout << "not equal!" << endl;

}

vectorOne[3] = 50;

if (vectorOne < vectorTwo) {

cout << "vectorOne is less than vectorTwo" << endl;

} else {

cout << "vectorOne is not less than vectorTwo" << endl;

}

The output of the program is as follows:

equal!

vectorOne is not less than vectorTwo

vector Iterators

The section on “Iterators” at the beginning of this chapter explained the basics of container iterators. The discussion can get a bit abstract, so it’s helpful to jump in and look at a code example. Here is the test score normalization program from earlier with the range-based for loop replaced by a for loop using an iterator:

vector<double> doubleVector;

// Initialize max to smallest number

double max = -numeric_limits<double>::infinity();

for (size_t i = 1; true; i++) {

double temp;

cout << "Enter score " << i << " (-1 to stop): ";

cin >> temp;

if (temp == -1) {

break;

}

doubleVector.push_back(temp);

if (temp > max) {

max = temp;

}

}

max /= 100.0;

for (vector<double>::iterator iter = begin(doubleVector);

iter != end(doubleVector); ++iter) {

*iter /= max;

cout << *iter << " ";

}

First, take a look at the for loop initialization statement:

vector<double>::iterator iter = begin(doubleVector);

Recall that every container defines a type named iterator to represent iterators for that type of container. begin() returns an iterator of that type referring to the first element in the container. Thus, the initialization statement obtains in the variable iter an iterator referring to the first element of doubleVector. Next, look at the for loop comparison:

iter != end(doubleVector);

This statement simply checks if the iterator is past the end of the sequence of elements in the vector. When it reaches that point, the loop terminates. The increment statement, ++iter, increments the iterator to refer to the next element in the vector.

NOTE Use pre-increment instead of post-increment when possible because pre-increment is at least as efficient, and usually more efficient. iter++ must return a new iterator object, while ++iter can simply return a reference to iter. See Chapter 14 for details on implementing both versions of operator++.

The for loop body contains these two lines:

*iter /= max;

cout << *iter << " ";

As you can see, your code can both access and modify the elements over which it iterates. The first line uses * to dereference iter to obtain the element to which it refers, and assigns to that element. The second line dereferences iter again, but this time only to stream the element to cout.

The preceding for loop using iterators can be simplified by using the auto keyword:

for (auto iter = begin(doubleVector);

iter != end(doubleVector); ++iter) {

*iter /= max;

cout << *iter << " ";

}

In this example, the compiler will automatically deduce the type of the variable iter based on the right-hand side of the initializer, which in this case is the result of the call to begin().

Accessing Fields of Object Elements

If the elements of your container are objects, you can use the -> operator on iterators to call methods or access data members of those objects. For example, the following program creates a vector of 10 strings, then iterates over all of them appending a new string to the old one:

vector<string> stringVector(10, "hello");

for (auto it = begin(stringVector); it != end(stringVector); ++it) {

it->append(" there");

}

Or, using a range-based for loop, it can be written as follows:

vector<string> stringVector(10, "hello");

for (auto& str : stringVector) {

str.append(" there");

}

const_iterator

The normal iterator is read/write. However, if you call begin() or end() on a const object, or you call cbegin() or cend(), you receive a const_iterator. The const_iterator is read-only; you cannot modify the elements. An iterator can always be converted to aconst_iterator, so it’s always safe to write something like this:

vector<type>::const_iterator it = begin(myVector);

However, a const_iterator cannot be converted to an iterator. If myVector is const, the following line doesn’t compile:

vector<type>::iterator it = begin(myVector);

NOTE If you do not need to modify the elements of a vector, you should use a const_iterator. This rule will make it easier to guarantee correctness of your code and allows compilers to perform certain optimizations.

When using the auto keyword, using const_iterators looks a bit different. Suppose you write the following code:

vector<string> stringVector(10, "hello");

for (auto iter = begin(stringVector); iter != end(stringVector); ++iter) {

cout << *iter << endl;

}

Because of the auto keyword, the compiler will deduce the type of the iter variable automatically and will make it a normal iterator, meaning that you can read and write to the iterator. If you want a read-only const_iterator in combination with using auto, then you need to use cbegin() and cend() instead of begin() and end() as follows:

vector<string> stringVector(10, "hello");

for (auto iter = cbegin(stringVector); iter != cend(stringVector); ++iter) {

cout << *iter << endl;

}

Now the compiler will use the const_iterator as type for the variable iter because that’s what cbegin() returns.

NOTE The non-member functions cbegin() and cend() are available since C++14. In C++11 you should use the cbegin() and cend() member functions.

A range-based for loop can also be forced to use const iterators as follows:

vector<string> stringVector(10, "hello");

for (const auto& element : stringVector) {

cout << element << endl;

}

Iterator Safety

Generally, iterators are about as safe as pointers: extremely insecure. For example, you can write code like this:

vector<int> intVector;

auto iter = end(intVector);

*iter = 10; // BUG! iter doesn't refer to a valid element.

Recall that the iterator returned by end() is past the end of a vector, not an iterator referring to the last element. Trying to dereference it results in undefined behavior. Iterators are not required to perform any verification.

Another problem can occur if you use mismatched iterators. For example, the following code initializes an iterator from vectorTwo and tries to compare it to the end iterator for vectorOne. Needless to say, this loop will not do what you intended, and may never terminate. Dereferencing the iterator in the loop will likely produce undefined results.

vector<int> vectorOne(10);

vector<int> vectorTwo(10);

// Fill in the vectors.

// BUG! Infinite loop

for (auto iter = begin(vectorTwo); iter != end(vectorOne); ++iter) {

// Loop body

}

NOTE Microsoft Visual C++ by default gives an assertion error at run time for both of the preceding problems when running a debug build of your program. By default, no verification of iterators is performed for release builds. You can enable it for release builds as well, but it has a performance penalty.

Other Iterator Operations

The vector iterator is random access, which means that you can move it backward or forward, or jump around. For example, the following code eventually changes the fifth element (index 4) to the value 4:

vector<int> intVector(10);

auto it = begin(intVector);

it += 5;

--it;

*it = 4;

Iterators versus Indexing

Given that you can write a for loop that uses a simple index variable and the size() method to iterate over the elements of the vector, why should you bother using iterators? That’s a valid question, for which there are three main answers:

· Iterators allow you to insert and delete elements and sequences of elements at any point in the container. See the following “Adding and Removing Elements” section.

· Iterators allow you to use the STL algorithms, which are discussed in Chapter 17.

· Using an iterator to access each element sequentially is often more efficient than indexing the container to retrieve each element individually. This generalization is not true for vectors, but applies to lists, maps, and sets.

Adding and Removing Elements

As you have already read, you can append an element to a vector with the push_back() method. The vector provides a parallel remove method called pop_back().

WARNING pop_back() does not return the element that it removed. If you want the element you must first retrieve it with back().

You can also insert elements at any point in the vector with the insert() method, which adds one or more elements to a position specified by an iterator, shifting all subsequent elements down to make room for the new ones. There are five different overloaded forms of insert() that:

· insert a single element.

· insert n copies of a single element.

· insert elements from an iterator range. Recall that the iterator range is half-open, such that it includes the element referred to by the starting iterator but not the one referred to by the ending iterator.

· insert a single element by moving the given element to a vector using move semantics.

· insert a list of elements into a vector where the list of elements is given as an initializer_list.

NOTE There are versions of push_back() and insert() that take an lvalue or an rvalue as parameter. The lvalue versions allocate memory as needed to store the new elements, and store copies of the element arguments. The rvalue versions use move semantics to move ownership of the object to a vector instead of copying the object.

You can remove elements from any point in a vector with erase() and you can remove all elements with clear(). There are two forms of erase(): one accepting a single iterator to remove a single element, and one accepting two iterators specifying a range of elements to remove.

If you want to remove a number of elements that satisfy a certain condition, one solution would be to write a loop iterating over all the elements and erasing every element that matches the condition. However, this solution has quadratic complexity, which is very bad for performance. In this case, the quadratic complexity can be avoided by using the remove-erase-idiom, which has a linear complexity. The remove-erase-idiom is discussed in Chapter 17.

Here is a small program that demonstrates the methods for adding and removing elements. It uses a helper function printVector() that prints the contents of a vector to cout. The example includes demonstrations of the two-argument version of erase() and the following versions of insert():

· insert(const_iterator pos, const T& x): the value x will be inserted at position pos.

· insert(const_iterator pos, size_type n, const T& x): the value x will be inserted n times at position pos.

· insert(const_iterator pos, InputIterator first, InputIterator last): the elements in the range first, last are inserted at position pos.

· vector<int> vectorOne = { 1, 2, 3, 5 };

· vector<int> vectorTwo;

· // Oops, we forgot to add 4. Insert it in the correct place

· vectorOne.insert(cbegin(vectorOne) + 3, 4);

· // Add elements 6 through 10 to vectorTwo

· for (int i = 6; i <= 10; i++) {

· vectorTwo.push_back(i);

· }

· printVector(vectorOne);

· printVector(vectorTwo);

· // Add all the elements from vectorTwo to the end of vectorOne

· vectorOne.insert(cend(vectorOne), cbegin(vectorTwo), cend(vectorTwo));

· printVector(vectorOne);

· // Now erase the numbers 2 through 5 in vectorOne

·vectorOne.erase(cbegin(vectorOne) + 1, cbegin(vectorOne) + 5);

·printVector(vectorOne);

·// Clear vectorTwo entirely

·vectorTwo.clear();

·// And add 10 copies of the value 100

·vectorTwo.insert(cbegin(vectorTwo), 10, 100);

·// Decide we only want 9 elements

·vectorTwo.pop_back();

printVector(vectorTwo);

The output of the program is as follows:

1 2 3 4 5

6 7 8 9 10

1 2 3 4 5 6 7 8 9 10

1 6 7 8 9 10

100 100 100 100 100 100 100 100 100

Recall that iterator pairs represent a half-open range, and insert() adds elements before the element referred to by the iterator position. Thus, you can insert the entire contents of vectorTwo into the end of vectorOne, like this:

vectorOne.insert(cend(vectorOne), cbegin(vectorTwo), cend(vectorTwo));

WARNING Methods such as insert() and erase() that take a vector range as arguments assume that the beginning and ending iterators refer to elements in the same container, and that the end iterator refers to an element at or past the begin iterator. The methods will not work correctly if these preconditions are not met!

Move Semantics

All STL containers implement move semantics by including a move constructor and move assignment operator. These use rvalue references, as described in Chapter 10. A big benefit of this is that you can easily return an STL container from a function by valuewithout performance degradation. Take a look at the following function:

vector<int> createVectorOfSize(size_t size)

{

vector<int> vec(size);

int contents = 0;

for (auto& i : vec) {

i = contents++;

}

return vec;

}

...

vector<int> myVector;

myVector = createVectorOfSize(123);

Without move semantics, createVectorOfSize() creates a local vector called vec. The return statement then makes a copy of vec, returns it from the function, and assigns it to myVector. With the move semantics support in the STL containers, this copying of the vector is avoided. Instead, the return statement moves the vector. Moving is possible in this case because vec will go out of scope.

Similarly, push operations can also make use of move semantics to improve performance in certain situations. For example, suppose you have a vector of elements of type Element as follows:

class Element

{

public:

Element(int i, const string& str) : mI(i), mStr(str) {}

private:

int mI;

string mStr;

};

...

vector<Element> vec;

Adding an element to this vector can be done as follows:

Element myElement(12, "Twelve");

vec.push_back(myElement);

However, since myElement is not a temporary object, push_back() makes a copy of myElement and puts it in the vector. This copying can be avoided if you call the push_back() method as follows:

vec.push_back(move(myElement));

Now you are explicitly saying that myElement should be moved into the vector. Note that after this call, you should not use myElement anymore! You can also call push_back() as follows:

vec.push_back(Element(12, "Twelve"));

The vector class defines a push_back(T&& val), which is the move equivalent of push_back(const T& val). The preceding call to push_back() triggers a call to the move version because the call to the Element constructor results in a temporary object. The push_back() method moves this temporary Element object into the vector, avoiding any copying.

Using uniform initialization the preceding can also be written as follows:

vec.push_back({12, "Twelve"});

Emplace Operations

C++ supports emplace operations on most STL containers, including vector. Emplace means “to put into place.” An example is emplace_back() on a vector object, which does not copy or move anything. Instead, it makes space in the container and constructs the objectin place. For example:

vec.emplace_back(12, "Twelve");

The emplace methods take a variable number of arguments as a variadic template. Variadic templates are discussed in Chapter 21, but those details are not required to understand how to use emplace_back(). The difference in performance between emplace_back() andpush_back() using move semantics depends on how your specific compiler implements these operations. In most situations you can pick the one based on the syntax that you prefer.

vec.push_back({12, "Twelve"});

// Or

vec.emplace_back(12, "Twelve");

There is also an emplace() method that constructs an object in place at a specific position in the vector.

Algorithmic Complexity and Iterator Invalidation

Inserting or erasing elements in a vector causes all subsequent elements to shift up or down to make room for, or fill in the holes left by, the affected elements. Thus, these operations take linear complexity. Furthermore, all iterators referring to the insertion or removal point or subsequent positions are invalid following the action. The iterators are not “magically” moved to keep up with the elements that are shifted up or down in the vector — that’s up to you.

Also keep in mind that an internal vector reallocation can cause invalidation of all iterators referring to elements in the vector, not just those referring to elements past the point of insertion or deletion. See the next section for details.

The vector Memory Allocation Scheme

A vector allocates memory automatically to store the elements that you insert. Recall that the vector requirements dictate that the elements must be in contiguous memory, like in standard C-style arrays. Because it’s impossible to request to add memory to the end of a current chunk of memory, every time a vector allocates more memory it must allocate a new, larger chunk in a separate memory location and copy/move all the elements to the new chunk. This process is time-consuming, so vector implementations attempt to avoid it by allocating more space than needed when they have to perform a reallocation. That way, they can avoid reallocating memory every time you insert an element.

One obvious question at this point is why you, as a client of vector, care how it manages its memory internally. You might think that the principle of abstraction should allow you to disregard the internals of the vector memory allocation scheme. Unfortunately, there are two reasons why you need to understand how it works:

1. Efficiency. The vector allocation scheme can guarantee that an element insert runs in amortized constant time: Most of the time the operation is constant, but once in a while (if it requires a reallocation), it’s linear. If you are worried about efficiency you can control when a vector performs reallocations.

2. Iterator invalidations. A reallocation invalidates all iterators referring to elements in a vector.

Thus, the vector interface allows you to query and control the vector reallocations. If you don’t control the reallocations explicitly, you should assume that all insertions cause a reallocation and thus invalidate all iterators.

Size and Capacity

vector provides two methods for obtaining information about its size: size() and capacity(). The size() method returns the number of elements in a vector, while capacity() returns the number of elements that it can hold without a reallocation. Thus, the number of elements that you can insert without causing a reallocation is capacity() – size().

NOTE You can query whether a vector is empty with the empty() method. A vector can be empty but have nonzero capacity.

Reserving Capacity

If you don’t care about efficiency or iterator invalidations, there is never a need to control the vector memory allocation explicitly. However, if you want to make your program as efficient as possible, or want to guarantee that iterators will not be invalidated, you can force a vector to preallocate enough space to hold all of its elements. Of course, you need to know how many elements it will hold, which is sometimes impossible to predict.

One way to preallocate space is to call reserve(), which allocates enough memory to hold the specified number of elements. The next section shows an example of the reserve() method in action.

WARNING Reserving space for elements changes the capacity, but not the size. That is, it doesn’t actually create elements. Don’t access elements past a vector’s size.

Another way to preallocate space is to specify, in the constructor or with the resize() method, how many elements you want a vector to store. This method actually creates a vector of that size (and probably of that capacity).

vector Example: A Round-Robin Class

A common problem in computer science is distributing requests among a finite list of resources. For example, a simple operating system could keep a list of processes and assign a time slice (for example, 100ms) to each process to let the process perform some of its work. After the time slice is finished, the OS suspends the process and the next process in the list is given a time slice to perform some of its work. One of the simplest algorithmic solutions to this problem is round-robin scheduling. When the time slice of the last process is finished, the scheduler starts over again with the first process. For example, in the case of three processes, the first time slice would go to the first process, the second to the second process, the third to the third process, and the fourth back to the first process. The cycle would continue in this way indefinitely.

Suppose that you decide to write a generic round-robin scheduling class that can be used with any type of resource. The class should support adding and removing resources, and should support cycling through the resources in order to obtain the next one. You could use a vector directly, but it’s often helpful to write a wrapper class that provides more directly the functionality you need for your specific application. The following example shows a RoundRobin class template with comments explaining the code. First, here is the class definition:

// Class template RoundRobin

// Provides simple round-robin semantics for a list of elements.

template <typename T>

class RoundRobin

{

public:

// Client can give a hint as to the number of expected elements for

// increased efficiency.

RoundRobin(size_t numExpected = 0);

virtual ~RoundRobin();

// prevent assignment and pass-by-value

RoundRobin(const RoundRobin& src) = delete;

RoundRobin& operator=(const RoundRobin& rhs) = delete;

// Appends elem to the end of the list. May be called

// between calls to getNext().

void add(const T& elem);

// Removes the first (and only the first) element

// in the list that is equal (with operator==) to elem.

// May be called between calls to getNext().

void remove(const T& elem);

// Returns the next element in the list, starting with the first,

// and cycling back to the first when the end of the list is

// reached, taking into account elements that are added or removed.

T& getNext();

private:

std::vector<T> mElems;

typename std::vector<T>::iterator mCurElem;

};

As you can see, the public interface is straightforward: only three methods plus the constructor and destructor. The resources are stored in the vector called mElems. The iterator mCurElem always refers to the element that was previously returned by a call to getNext(). IfgetNext() hasn’t been called yet, mCurElem is equal to end(mElems). Note the use of the typename keyword in front of the line declaring mCurElem. So far, you’ve only seen that keyword used to specify template parameters, but there is another use for it. You must specifytypename explicitly whenever you access a type based on one or more template parameters. In this case, the template parameter T is used to access the iterator type. Thus, you must specify typename. This is another example of arcane C++ syntax.

The class also prevents assignment and pass-by-value because of the mCurElem data member. To make assignment and pass-by-value work, you would have to implement an assignment operator and copy constructor and make sure mCurElem is valid in the destination object. This is omitted in this example.

The implementation of the RoundRobin class follows with comments explaining the code. Note the use of reserve() in the constructor, and the extensive use of the iterator in add(), remove(), and getNext(). The trickiest aspect is handling mCurElem in the add() andremove() methods.

template <typename T> RoundRobin<T>::RoundRobin(size_t numExpected)

{

// If the client gave a guideline, reserve that much space.

mElems.reserve(numExpected);

// Initialize mCurElem even though it isn't used until

// there's at least one element.

mCurElem = end(mElems);

}

template <typename T> RoundRobin<T>::~RoundRobin()

{

// nothing to do here -- the vector will delete all the elements

}

// Always add the new element at the end

template <typename T> void RoundRobin<T>::add(const T& elem)

{

// Even though we add the element at the end, the vector could

// reallocate and invalidate the iterator with the push_back() call.

// Take advantage of the random access iterator features to save our

// spot. When getNext() hasn't been called yet, mCurElem is equal

// to end(mElems) (see constructor), in which case pos is set to -1.

int pos = (mCurElem == end(mElems) ? -1 : mCurElem - begin(mElems));

// Add the element.

mElems.push_back(elem);

// Reset our iterator to make sure it is valid.

// If getNext() hasn't been called yet, reset mCurElem to end(mElems).

mCurElem = (pos == -1 ? end(mElems) : begin(mElems) + pos);

}

template <typename T> void RoundRobin<T>::remove(const T& elem)

{

for (auto it = begin(mElems); it != end(mElems); ++it) {

if (*it == elem) {

// Removing an element will invalidate our mCurElem iterator if

// it refers to an element past the point of the removal.

// Take advantage of the random access features of the iterator

// to track the position of the current element after removal.

int newPos;

// If current iterator is before or at the one we're removing,

// the new position is the same as before.

if (mCurElem <= it) {

newPos = mCurElem - begin(mElems);

} else {

// otherwise, it's one less than before

newPos = mCurElem - begin(mElems) - 1;

}

// Erase the element (and ignore the return value).

mElems.erase(it);

// Now reset our iterator to make sure it is valid.

mCurElem = begin(mElems) + newPos;

return;

}

}

}

template <typename T> T& RoundRobin<T>::getNext()

{

// First, make sure there are any elements.

if (mElems.empty()) {

throw std::out_of_range("No elements in the list");

}

// If getNext() hasn't been called yet, mCurElem is equal to end(mElems)

// (see constructor). In that case wrap to the beginning.

if (mCurElem == end(mElems)) {

mCurElem = begin(mElems);

} else {

// getNext() has been called before.

// Increment the iterator modulo the number of elements.

++mCurElem;

if (mCurElem == end(mElems)) {

mCurElem = begin(mElems);

}

}

// Return a reference to the element.

return *mCurElem;

}

Here’s a simple implementation of a scheduler that uses the RoundRobin class template, with comments explaining the code:

// Simple Process class.

class Process

{

public:

// Constructor accepting the name of the process.

Process(const string& name) : mName(name) {}

// Implementation of doWorkDuringTimeSlice would let the process

// perform its work for the duration of a time slice.

// Actual implementation omitted.

void doWorkDuringTimeSlice() {

cout << "Process " << mName

<< " performing work during time slice." << endl;

}

// Needed for the RoundRobin::remove method to work.

bool operator==(const Process& rhs) {

return mName == rhs.mName;

}

private:

string mName;

};

// Simple round-robin based process scheduler.

class Scheduler

{

public:

// Constructor takes a vector of processes.

Scheduler(const vector<Process>& processes);

// Selects the next process using a round-robin scheduling

// algorithm and allows it to perform some work during

// this time slice.

void scheduleTimeSlice();

// Removes the given process from the list of processes.

void removeProcess(const Process& process);

private:

RoundRobin<Process> rr;

};

Scheduler::Scheduler(const vector<Process>& processes)

{

// Add the processes

for (auto& process : processes) {

rr.add(process);

}

}

void Scheduler::scheduleTimeSlice()

{

try {

rr.getNext().doWorkDuringTimeSlice();

} catch (const out_of_range&) {

cerr << "No more processes to schedule." << endl;

}

}

void Scheduler::removeProcess(const Process& process)

{

rr.remove(process);

}

int main()

{

vector<Process> processes = { Process("1"), Process("2"), Process("3") };

Scheduler sched(processes);

for (int i = 0; i < 4; ++i)

sched.scheduleTimeSlice();

sched.removeProcess(processes[1]);

cout << "Removed second process" << endl;

for (int i = 0; i < 4; ++i)

sched.scheduleTimeSlice();

return 0;

}

The output should be as follows:

Process 1 performing work during time slice.

Process 2 performing work during time slice.

Process 3 performing work during time slice.

Process 1 performing work during time slice.

Removed second process

Process 3 performing work during time slice.

Process 1 performing work during time slice.

Process 3 performing work during time slice.

Process 1 performing work during time slice.

The vector<bool> Specialization

The standard requires a partial specialization of vector for bools, with the intention that it optimizes space allocation by “packing” the Boolean values. Recall that a bool is either true or false, and thus could be represented by a single bit, which can take on exactly two values. C++ does not have a native type that stores exactly one bit. Some compilers represent a Boolean value with a type the same size as a char. Some other compilers use an int. The vector<bool> specialization is supposed to store the “array of bools” in single bits, thus saving space.

NOTE You can think of the vector<bool> as a bit-field instead of a vector. The bitset container described later in this chapter provides a more full-featured bit-field implementation than does vector<bool>. However, the benefit of vector<bool> is that it can change size dynamically.

In a half-hearted attempt to provide some bit-field routines for the vector<bool>, there is one additional method: flip(). This method can be called on either the container, in which case it complements all the elements in the container; or on a single reference returned from operator[] or a similar method, in which case it complements that single element.

At this point, you should be wondering how you can call a method on a reference to bool. The answer is that you can’t. The vector<bool> specialization actually defines a class called reference that serves as a proxy for the underlying bool (or bit). When you calloperator[], at(), or a similar method, the vector<bool> returns a reference object, which is a proxy for the real bool.

WARNING The fact that references returned from vector<bool> are really proxies means that you can’t take their addresses to obtain pointers to the actual elements in the container.

In practice, the little amount of space saved by packing bools hardly seems worth the extra effort. Even worse, accessing and modifying elements in a vector<bool> is much slower than, for example, in a vector<int>. Many C++ experts recommend avoiding vector<bool>in favor of the bitset, or vector<int> if you need a dynamically sized bit field.

deque

deque (abbreviation for double-ended queue) is almost identical to vector, but is used far less frequently. It is defined in the <deque> header file. The principle differences are as follows:

· Elements are not stored contiguously in memory.

· A deque supports true constant-time insertion and removal of elements at both the front and the back (a vector supports amortized constant time at just the back).

· A deque provides push_front(), pop_front(), and emplace_front(), which the vector omits.

· A deque does not expose its memory management scheme via reserve() or capacity().

deques are rarely used, as opposed to vectors and lists, so they are not further discussed. Consult a Standard Library Reference for a detailed list of all supported methods.

list

The STL list class, defined in the <list> header file, is a standard doubly linked list. It supports constant-time insertion and deletion of elements at any point in the list, but provides slow (linear) time access to individual elements. In fact, the list does not even provide random-access operations like operator[]. Only through iterators can you access individual elements.

Most of the list operations are identical to those of vector, including the constructors, destructor, copying operations, assignment operations, and comparison operations. This section focuses on those methods that differ from those of vector.

Accessing Elements

The only methods provided by a list to access elements are front() and back(), both of which run in constant time. These methods return a reference to the first and last element in a list. All other element access must be performed through iterators.

A list supports begin(), returning an iterator referring to the first element in the list, and end(), returning an iterator referring to one past the last element in the list. It also supports cbegin(), cend(), rbegin(), rend(), crbegin(), and crend().

WARNING Lists do not provide random access to elements.

Iterators

A list iterator is bidirectional, not random access like a vector iterator. That means that you cannot add and subtract list iterators from each other, or perform other pointer arithmetic on them. For example, if p is a list iterator, you can traverse through the elements of the list by doing ++p or --p, but you cannot use the addition or subtraction operator; p+n or p-n does not work.

Adding and Removing Elements

A list supports the same add element and remove element methods as a vector, including push_back(), pop_back(), emplace(), emplace_back(), the five forms of insert(), the two forms of erase(), and clear(). Like a deque, it also provides push_front(), emplace_front(), and pop_front(). The amazing thing about a list is that all these methods (except for clear()) run in constant time, once you’ve found the correct position. Thus, a list is appropriate for applications that perform many insertions and deletions from the data structure, but do not need quick index-based element access.

list Size

Like deques, and unlike vectors, lists do not expose their underlying memory model. Consequently, they support size(), empty()and resize(), but not reserve() or capacity(). Note that the size() method on a list has constant complexity, which is not the case for thesize() method on a forward_list.

Special list Operations

A list provides several special operations that exploit its quick element insertion and deletion. This section provides an overview and examples. Consult a Standard Library Reference — for example http://www.cppreference.com/ orhttp://www.cplusplus.com/reference/ — for a thorough reference of all the methods.

Splicing

The linked-list characteristics of a list allow it to splice, or insert, an entire list at any position in another list in constant time. The simplest version of this method works as follows:

// Store the a words in the main dictionary.

list<string> dictionary{ "aardvark", "ambulance" };

// Store the b words.

list<string> bWords{ "bathos", "balderdash" };

// Add the c words to the main dictionary

dictionary.push_back("canticle");

dictionary.push_back("consumerism");

// splice the b words into the main dictionary.

if (bWords.size() > 0) {

// Get an iterator to the last b word.

auto iterLastB = --(cend(bWords));

// Iterate up to the spot where we want to insert bs.

auto it = cbegin(dictionary);

for (; it != cend(dictionary); ++it) {

if (*it > *iterLastB)

break;

}

// Add in the bwords. This action removes the elements from bWords.

dictionary.splice(it, bWords);

}

// print out the dictionary

for (const auto& word : dictionary) {

cout << word << endl;

}

The result from running this program looks like this:

aardvark

ambulance

bathos

balderdash

canticle

consumerism

There are also two other forms of splice(): one that inserts a single element from another list and one that inserts a range from another list. Additionally, all forms of splice() are available with either a normal reference or a rvalue reference to the source list.

WARNING Splicing is destructive to the list passed as an argument: It removes the spliced elements from one list in order to insert them into the other.

More Efficient Versions of Algorithms

In addition to splice(), a list provides special implementations of several of the generic STL algorithms. The generic forms are covered in Chapter 17. Here, only the specific versions provided by list are discussed.

NOTE When you have a choice, use the list specific methods rather than the generic STL algorithms because the former are more efficient. Sometimes you don’t have a choice and you must use the list specific methods; for example, std::sort()requires RandomAccessIterators, which a list does not provide.

The following table summarizes the algorithms for which list provides special implementations as methods. See Chapter 17 for more details on the algorithms.

METHOD

DESCRIPTION

remove()
remove_if()

Removes certain elements from a list.

unique()

Removes duplicate consecutive elements from a list, based on operator== or a user-supplied binary predicate.

merge()

Merges two lists. Both lists must be sorted to start, according to operator< or a user-defined comparator. Like splice(), merge() is destructive to the list passed as an argument.

sort()

Performs a stable sort on elements in a list.

reverse()

Reverses the order of the elements in a list.

list Example: Determining Enrollment

Suppose that you are writing a computer registration system for a university. One feature you might provide is the ability to generate a complete list of enrolled students in the university from lists of the students in each class. For the sake of this example, assume that you must write only a single function that takes a vector of lists of student names (as strings), plus a list of students that have been dropped from their courses because they failed to pay tuition. This method should generate a complete list of all the students in all the courses, without any duplicates, and without those students who have been dropped. Note that students might be in more than one course.

Here is the code for this method, with comments explaining the code. With the power of STL lists, the method is practically shorter than its written description! Note that the STL allows you to “nest” containers: in this case, you can use a vector of lists.

// courseStudents is a vector of lists, one for each course. The lists

// contain the students enrolled in those courses. They are not sorted.

//

// droppedStudents is a list of students who failed to pay their

// tuition and so were dropped from their courses.

//

// The function returns a list of every enrolled (non-dropped) student in

// all the courses.

list<string> getTotalEnrollment(const vector<list<string>>& courseStudents,

const list<string>& droppedStudents)

{

list<string> allStudents;

// Concatenate all the course lists onto the master list

for (auto& lst : courseStudents) {

allStudents.insert(cend(allStudents), cbegin(lst), cend(lst));

}

// Sort the master list

allStudents.sort();

// Remove duplicate student names (those who are in multiple courses).

allStudents.unique();

// Remove students who are on the dropped list.

// Iterate through the drop list, calling remove on the

// master list for each student in the dropped list.

for (auto& str : droppedStudents) {

allStudents.remove(str);

}

// done!

return allStudents;

}

forward_list

A forward_list, defined in the <forward_list> header file, is similar to a list except that it is a singly linked list while a list is a doubly linked list. This means that forward_list supports only forward iteration and, because of this, ranges need to be specified differently compared to a list. If you want to modify any list, you need access to the element before the first element of interest. Since a forward_list does not have an iterator that supports going backward, there is no easy way to get to the preceding element. For this reason, ranges that will be modified; for example, ranges supplied to erase() and splice(), must be open at the beginning. The begin() function seen earlier returns an iterator to the first element and thus can be used only to construct a range that is closed at the beginning. The forward_list class therefore defines a before_begin() method, which returns an iterator that points to an imaginary element before the beginning of the list. You cannot dereference this iterator as it points to invalid data. However, incrementing this iterator by one will make it the same as the iterator returned by begin(); so it can be used to make a range that is open at the beginning. The following table sums up the differences between a list and a forward_list:

OPERATION

LIST

FORWARD_LIST

assign()

x

x

back()

x

before_begin()

x

begin()

x

x

cbefore_begin()

x

cbegin()

x

x

cend()

x

x

clear()

x

x

crbegin()

x

crend()

x

emplace()

x

emplace_after()

x

emplace_back()

x

emplace_front()

x

x

empty()

x

x

end()

x

x

erase()

x

erase_after()

x

front()

x

x

insert()

x

insert_after()

x

iterator / const_iterator

x

x

max_size()

x

x

merge()

x

x

pop_back()

x

pop_front()

x

x

push_back()

x

push_front()

x

x

rbegin()

x

remove()

x

x

remove_if()

x

x

rend()

x

resize()

x

x

reverse()

x

x

reverse_iterator / const_reverse_iterator

x

size()

x

sort()

x

x

splice()

x

splice_after()

x

swap()

x

x

unique()

x

x

Constructors and assignment operators are similar between a list and a forward_list. The C++ standard states that forward_lists should try to use minimal space. That’s the reason why there is no size() method, because by not providing it, there is no need to store the size of the list. The following example demonstrates the use of forward_lists:

// Create 3 forward lists and use an initializer_list

// to initialize their elements (uniform initialization).

forward_list<int> lst1 = { 5, 6 };

forward_list<int> lst2 = { 1, 2, 3, 4 };

forward_list<int> lst3 = { 7, 8, 9 };

// Insert lst2 at the front of lst1 using splice.

lst1.splice_after(lst1.before_begin(), lst2);

// Add number 0 at the beginning of the lst1.

lst1.push_front(0);

// Insert lst3 at the end of lst1.

// For this, we first need an iterator to the last element.

auto iter = lst1.before_begin();

auto iterTemp = iter;

while (++iterTemp != end(lst1)) {

++iter;

}

lst1.insert_after(iter, cbegin(lst3), cend(lst3));

// Output the contents of lst1.

for (auto& i : lst1) {

cout << i << ' ';

}

To insert lst3, we need an iterator to the last element in the list. However, since this is a forward_list, we cannot use --end(lst1), so we need to iterate over the list from the beginning and stop at the last element. The output of this example is as follows:

0 1 2 3 4 5 6 7 8 9

array

An array, defined in the <array> header file, is similar to a vector except that it is of a fixed size; it cannot grow or shrink in size. The purpose of this is to allow an array to be allocated on the stack, rather than always demanding heap access as vector does. Just likevectors, arrays support random-access iterators, and elements are stored in contiguous memory. It has support for front(), back(), at(), and operator[]. It also supports a fill() method to fill the array with a specific element. Because it is fixed in size, it does not support push_back(), pop_back(), insert(), erase(), clear(), resize(), reserve(), and capacity(). A disadvantage compared to a vector is that the swap() method of an array runs in linear time while it has constant complexity for a vector. arrays can also not be moved in constant time, while vectors can. An array has a size() method, which is a clear advantage over C-style arrays. The following example demonstrates how to use the array class. Note that the array declaration requires two template parameters; the first specifies the type of the elements, and the second specifies the fixed number of elements in the array.

// Create array of 3 integers and initialize them

// with the given initializer_list using uniform initialization.

array<int, 3> arr = { 9, 8, 7 };

// Output the size of the array.

cout << "Array size = " << arr.size() << endl;

// Output the contents using the range-based for loop.

for (const auto& i : arr) {

cout << i << endl;

}

cout << "Performing arr.fill(3)..." << endl;

// Use the fill method to change the contents of the array.

arr.fill(3);

// Output the contents of the array using iterators.

for (auto iter = cbegin(arr); iter != cend(arr); ++iter) {

cout << *iter << endl;

}

The output of the preceding code is as follows:

Array size = 3

9

8

7

Performing arr.fill(3)...

3

3

3

CONTAINER ADAPTERS

In addition to the standard sequential containers, the STL provides three container adapters: queue, priority_queue, and stack. Each of these adapters is a wrapper around one of the sequential containers. They allow you to swap the underlying container without having to change the rest of the code. The intent of the adapters is to simplify the interface and to provide only those features that are appropriate for the stack or queue abstraction. For example, the adapters don’t provide iterators or the capability to insert or erase multiple elements simultaneously.

queue

The queue container adapter, defined in the header file <queue>, provides standard “first-in, first-out” (FIFO) semantics. As usual, it’s written as a class template, which looks like this:

template <class T, class Container = deque<T> > class queue;

The T template parameter specifies the type that you intend to store in the queue. The second template parameter allows you to stipulate the underlying container that the queue adapts. However, the queue requires the sequential container to support both push_back()and pop_front(), so you have only two built-in choices: deque and list. For most purposes, you can just stick with the default deque.

queue Operations

The queue interface is extremely simple: there are only eight methods plus the constructor and the normal comparison operators. The push()and emplace() methods add a new element to the tail of the queue, and pop() removes the element at the head of the queue. You can retrieve references to, without removing, the first and last elements with front() and back(), respectively. As usual, when called on const objects, front() and back() return const references; and when called on non-const objects they return non-const(read/write) references.

WARNING pop() does not return the element popped. If you want to retain a copy, you must first retrieve it with front().

The queue also supports size(), empty(), and swap().

queue Example: A Network Packet Buffer

When two computers communicate over a network, they send information to each other divided up into discrete chunks called packets. The networking layer of the computer’s operating system must pick up the packets and store them as they arrive. However, the computer might not have enough bandwidth to process all of them at once. Thus, the networking layer usually buffers, or stores, the packets until the higher layers have a chance to attend to them. The packets should be processed in the order they arrive, so this problem is perfect for a queue structure. The following is a small PacketBuffer class, with comments explaining the code, which stores incoming packets in a queue until they are processed. It’s a template so that different layers of the networking layer can use it for different kinds of packets, such as IP packets or TCP packets. It allows the client to specify a maximum size because operating systems usually limit the number of packets that can be stored, so as not to use too much memory. When the buffer is full, subsequently arriving packets are ignored.

template <typename T>

class PacketBuffer

{

public:

// If maxSize is 0, the size is unlimited, because creating

// a buffer of size 0 makes little sense. Otherwise only

// maxSize packets are allowed in the buffer at any one time.

PacketBuffer(size_t maxSize = 0);

// Stores a packet in the buffer.

// Returns false if the packet has been discarded because

// there is no more space in the buffer, true otherwise.

bool bufferPacket(const T& packet);

// Returns the next packet. Throws out_of_range

// if the buffer is empty.

T getNextPacket();

private:

std::queue<T> mPackets;

size_t mMaxSize;

};

template <typename T> PacketBuffer<T>::PacketBuffer(size_t maxSize/* = 0 */)

: mMaxSize(maxSize)

{

}

template <typename T> bool PacketBuffer<T>::bufferPacket(const T& packet)

{

if (mMaxSize > 0 && mPackets.size() == mMaxSize) {

// No more space. Drop the packet.

return false;

}

mPackets.push(packet);

return true;

}

template <typename T> T PacketBuffer<T>::getNextPacket()

{

if (mPackets.empty()) {

throw std::out_of_range("Buffer is empty");

}

// retrieve the head element

T temp = mPackets.front();

// pop the head element

mPackets.pop();

// return the head element

return temp;

}

A practical application of this class would require multiple threads. C++ provides synchronization classes to allow thread-safe access to shared objects. Without explicit synchronization, no STL class can be used safely from multiple threads. Synchronization is discussed in Chapter 23. The focus in this example is on the queue class, so here is a single-threaded example of using the PacketBuffer:

class IPPacket

{

public:

IPPacket(int id) : mID(id) {}

int getID() const { return mID; }

private:

int mID;

};

int main()

{

PacketBuffer<IPPacket> ipPackets(3);

// Add 4 packets

for (int i = 1; i <= 4; ++i) {

if (!ipPackets.bufferPacket(IPPacket(i))) {

cout << "Packet " << i << " dropped (queue is full)." << endl;

}

}

while (true) {

try {

IPPacket packet = ipPackets.getNextPacket();

cout << "Processing packet " << packet.getID() << endl;

} catch (const out_of_range&) {

cout << "Queue is empty." << endl;

break;

}

}

return 0;

}

The output of this program is as follows:

Packet 4 dropped (queue is full).

Processing packet 1

Processing packet 2

Processing packet 3

Queue is empty.

priority_queue

A priority queue is a queue that keeps its elements in sorted order. Instead of a strict FIFO ordering, the element at the head of the queue at any given time is the one with the highest priority. This element could be the oldest on the queue or the most recent. If two elements have equal priority, their relative order in the queue is undefined.

The priority_queue container adapter is also defined in <queue>. Its template definition looks something like this (slightly simplified):

template <class T, class Container = vector<T>,

class Compare = less<T> >;

It’s not as complicated as it looks. You’ve seen the first two parameters before: T is the element type stored in the priority_queue and Container is the underlying container on which the priority_queue is adapted. The priority_queue uses vector as the default, but dequeworks as well. list does not work because the priority_queue requires random access to its elements. The third parameter, Compare, is trickier. As you’ll learn more about in Chapter 17, less is a class template that supports comparison of two objects of type T withoperator<. What this means for you is that the priority of elements in the queue is determined according to operator<. You can customize the comparison used, but that’s a topic for Chapter 17. For now, just make sure that you define operator< appropriately for the types stored in the priority_queue.

NOTE The head element of the priority_queue is the one with the “highest” priority, by default, determined according to operator< such that elements that are “less” than other elements have lower priority.

priority_queue Operations

The priority_queue provides even fewer operations than does the queue. The push() and emplace() methods allow you to insert elements, pop() allows you to remove elements, and top() returns a const reference to the head element.

WARNING top() returns a const reference even when called on a non-const object, because modifying the element might change its order, which is not allowed. The priority_queue provides no mechanism to obtain the tail element.

WARNING pop() does not return the element popped. If you want to retain a copy, you must first retrieve it with top().

Like the queue, the priority_queue supports size(), empty(), and swap(). However, it does not provide any comparison operators.

priority_queue Example: An Error Correlator

Single failures on a system can often cause multiple errors to be generated from different components. A good error-handling system uses error correlation to process the most important errors first. You can use a priority_queue to write a very simple error correlator. Assume all error events encode their own priority. The error correlator simply sorts error events according to their priority, so that the highest-priority errors are always processed first. Here is the class definition:

// Sample Error class with just a priority and a string error description.

class Error

{

public:

Error(int priority, const std::string& errMsg)

: mPriority(priority), mError(errMsg) {}

int getPriority() const { return mPriority; }

const std::string& getErrorString() const { return mError; }

friend bool operator<(const Error& lhs, const Error& rhs);

friend std::ostream& operator<<(std::ostream& os, const Error& err);

private:

int mPriority;

std::string mError;

};

// Simple ErrorCorrelator class that returns highest priority errors first.

class ErrorCorrelator

{

public:

// Add an error to be correlated.

void addError(const Error& error);

// Retrieve the next error to be processed.

Error getError();

private:

std::priority_queue<Error> mErrors;

};

Here are the definitions of the functions and methods:

bool operator<(const Error& lhs, const Error& rhs)

{

return (lhs.mPriority < rhs.mPriority);

}

ostream& operator<<(ostream& os, const Error& err)

{

os << err.mError << " (priority " << err.mPriority << ")";

return os;

}

void ErrorCorrelator::addError(const Error& error)

{

mErrors.push(error);

}

Error ErrorCorrelator::getError()

{

// If there are no more errors, throw an exception.

if (mErrors.empty()) {

throw out_of_range("No more errors.");

}

// Save the top element.

Error top = mErrors.top();

// Remove the top element.

mErrors.pop();

// Return the saved element.

return top;

}

Here is a simple unit test showing how to use the ErrorCorrelator. Realistic use would require multiple threads so that one thread adds errors, while another processes them. As mentioned earlier with the queue example, this requires explicit synchronization, discussed in Chapter 23.

ErrorCorrelator ec;

ec.addError(Error(3, "Unable to read file"));

ec.addError(Error(1, "Incorrect entry from user"));

ec.addError(Error(10, "Unable to allocate memory!"));

while (true) {

try {

Error e = ec.getError();

cout << e << endl;

} catch (const out_of_range&) {

cout << "Finished processing errors" << endl;

break;

}

}

The output of this program is as follows:

Unable to allocate memory! (priority 10)

Unable to read file (priority 3)

Incorrect entry from user (priority 1)

Finished processing errors

stack

A stack is almost identical to a queue, except that it provides first-in, last-out (FILO) semantics, also known as last-in, first-out (LIFO), instead of FIFO. It is defined in the <stack> header file. The template definition looks like this:

template <class T, class Container = deque<T> > class stack;

You can use vector, list, or deque as the underlying container for the stack.

stack Operations

Like the queue, the stack provides push(), emplace(), and pop(). The difference is that push() adds a new element to the top of the stack, “pushing down” all elements inserted earlier, and pop() removes the element from the top of the stack, which is the most recently inserted element. The top() method returns a const reference to the top element if called on a const object and a non-const reference if called on a non-const object.

WARNING pop() does not return the element popped. If you want to retain a copy, you must first retrieve it with top().

The stack supports empty(), size(), swap(), and the standard comparison operators.

stack Example: Revised Error Correlator

You can rewrite the previous ErrorCorrelator class so that it gives out the most recent error instead of the one with the highest priority. The only change required is to change mErrors from a priority_queue to a stack. With this change, the errors will be distributed in LIFO order instead of priority order. Nothing in the method definitions needs to change because the push(), pop(), top(), and empty() methods exist on both the priority_queue and stack.

ASSOCIATIVE CONTAINERS

Unlike the sequential containers, the associative containers do not store elements in a linear configuration. Instead, they provide a mapping of keys to values. They generally offer insertion, deletion, and lookup times that are equivalent to each other.

There are four ordered associative containers provided by the STL: map, multimap, set, and multiset. Each of these containers stores its elements in a sorted, tree-like, data structure. There are also four unordered associative containers: unordered_map, unordered_multimap, unordered_set, and unordered_multiset. These are discussed later in this chapter.

The pair Utility Class

Before learning about the associative containers, you must become familiar with the pair class, which is defined in the <utility> header file. pair is a class template that groups together two values of possibly different types. The values are accessible through the firstand second public data members. operator== and operator< are defined for pairs to compare both the first and second elements. Here are some examples:

// Two-argument constructor and default constructor

pair<string, int> myPair("hello", 5);

pair<string, int> myOtherPair;

// Can assign directly to first and second

myOtherPair.first = "hello";

myOtherPair.second = 6;

// Copy constructor

pair<string, int> myThirdPair(myOtherPair);

// operator<

if (myPair < myOtherPair) {

cout << "myPair is less than myOtherPair" << endl;

} else {

cout << "myPair is greater than or equal to myOtherPair" << endl;

}

// operator==

if (myOtherPair == myThirdPair) {

cout << "myOtherPair is equal to myThirdPair" << endl;

} else {

cout << "myOtherPair is not equal to myThirdPair" << endl;

}

The output is as follows:

myPair is less than myOtherPair

myOtherPair is equal to myThirdPair

The library also provides a utility function template, make_pair(), that constructs a pair from two values. For example:

pair<int, int> aPair = make_pair(5, 10);

Of course, in this case you could have just used the two-argument constructor. However, make_pair() is more useful when you want to pass a pair to a function, or assign it to a pre-existing variable. Unlike class templates, function templates can infer types from parameters, so you can use make_pair() to construct a pair without explicitly specifying the types. You can also use make_pair() in combination with the auto keyword as follows:

auto aSecondPair = make_pair(5, 10);

WARNING Using plain old pointer types in pairs is risky because the pair copy constructor and assignment operator perform only shallow copies and assignments of pointer types. However, you can safely store smart pointers like shared_ptr in apair.

map

A map, defined in the <map> header file, stores key/value pairs instead of just single values. Insertion, lookup, and deletion are all based on the key; the value is just “along for the ride.” The term “map” comes from the conceptual understanding that the container “maps” keys to values.

A map keeps elements in sorted order, based on the keys, so that insertion, deletion, and lookup all take logarithmic time. Because of the order, when you enumerate the elements, they come out in the ordering imposed by the type’s operator< or a user-defined comparator. It is usually implemented as some form of balanced tree, such as a red-black tree. However, the tree structure is not exposed to the client.

You should use a map whenever you need to store and retrieve elements based on a “key” and you would like to have them in a certain order.

Constructing maps

The map template takes four types: the key type, the value type, the comparison type, and the allocator type. As always, the allocator is ignored in this chapter. The comparison type is similar to the comparison type for priority_queue described earlier. It allows you to specify a different comparison class than the default. In this chapter, only the default less comparison is used. When using the default, make sure that your keys all respond to operator< appropriately. If you’re interested in further detail, Chapter 17 explains how to write your own comparison classes.

If you ignore the comparison and allocator parameters, constructing a map is just like constructing a vector or a list, except that you specify the key and value types separately in the template. For example, the following code constructs a map that uses ints as the key and stores objects of the Data class:

class Data

{

public:

explicit Data(int val = 0) { mVal = val; }

int getVal() const { return mVal; }

void setVal(int val) { mVal = val; }

private:

int mVal;

};

...

map<int, Data> dataMap;

maps also support uniform initialization:

map<string, int> m = {

{ "Marc G.", 123 },

{ "Warren B.", 456 },

{ "Peter V.W.", 789 }

};

Inserting Elements

Inserting an element into sequential containers such as vector and list always requires you to specify the position at which the element is to be added. A map, along with the other associative containers, is different. The map internal implementation determines the position in which to store the new element; you need only to supply the key and the value.

NOTE map and the other associative containers do provide a version of insert() that takes an iterator position. However, that position is only a “hint” to the container as to the correct position. The container is not required to insert the element at that position.

When inserting elements, it is important to keep in mind that maps require unique keys: every element in the map must have a different key. If you want to support multiple elements with the same key, you have two options. You can either use a map and store another container such as a vector or an array as the element for a key, or you can use multimaps, described later.

There are two ways to insert an element into the map: one clumsy and one not so clumsy.

The insert() Method

The clumsy mechanism to add an element to a map is the insert() method, but it has the advantage of allowing you to detect if the key already exists. One problem is that you must specify the key/value pair as a pair object or as an initializer_list. The second problem is that the return value from the basic form of insert() is a pair of an iterator and a bool. The reason for the complicated return value is that insert() does not overwrite an element value if one already exists with the specified key. The bool element of the returned pair specifies whether the insert() actually inserted the new key/value pair or not. The iterator refers to the element in the map with the specified key (with a new or old value, depending on whether the insert succeeded or failed). map iterators are discussed in more detail in the next section. Continuing the map example from the previous section, you can use insert() as follows:

map<int, Data> dataMap;

auto ret = dataMap.insert({ 1, Data(4) }); // Using an initializer_list

if (ret.second) {

cout << "Insert succeeded!" << endl;

} else {

cout << "Insert failed!" << endl;

}

ret = dataMap.insert(make_pair(1, Data(6))); // Using a pair object

if (ret.second) {

cout << "Insert succeeded!" << endl;

} else {

cout << "Insert failed!" << endl;

}

The output of the program is as follows:

Insert succeeded!

Insert failed!

Without the auto keyword, you would have to declare the correct type for ret yourself as follows:

pair<map<int, Data>::iterator, bool> ret;

The type of ret is a pair. The first element of the pair is a map iterator for a map with keys of type int and values of type Data. The second element of the pair is a Boolean value.

operator[]

The less clumsy way to insert an element into a map is through the overloaded operator[]. The difference is mainly in the syntax: you specify the key and value separately. Additionally, operator[] always succeeds. If no element value with the given key exists, it creates a new element with that key and value. If an element with the key exists already, operator[] replaces the element value with the newly specified value. Here is the previous example using operator[] instead of insert():

map<int, Data> dataMap;

dataMap[1] = Data(4);

dataMap[1] = Data(6); // Replaces the element with key 1

There is, however, one major caveat to operator[]: it always constructs a new value object, even if it doesn’t need to use it. Thus, it requires a default constructor for your element values, and can be less efficient than insert().

The fact that operator[] creates a new element in a map if the requested element does not already exist means that this operator is not marked as const. This sounds obvious, but might sometimes look counter intuitive. For example, suppose you have the following function:

void func(const map<int, int>& m)

{

cout << m[1] << endl; // Error

}

This will fail to compile, even though you appear to be just reading the value m[1]. It fails because the variable m is a const reference to a map, and operator[] is not marked as const. Instead, you should use the find() method described in the “Looking Up Elements” section.

map Iterators

map iterators work similarly to the iterators on the sequential containers. The major difference is that the iterators refer to key/value pairs instead of just the values. In order to access the value, you must retrieve the second field of the pair object. Here is how you can iterate through the map from the previous example:

for (auto iter = cbegin(dataMap); iter != cend(dataMap); ++iter) {

cout << iter->second.getVal() << endl;

}

Take another look at the expression used to access the value:

iter->second.getVal()

iter refers to a key/value pair, so you can use the -> operator to access the second field of that pair, which is a Data object. You can then call the getVal() method on that Data object.

Note that the following code is functionally equivalent:

(*iter).second.getVal()

Using the range-based for loop, the loop can be written even more elegantly as follows:

for (const auto& p : dataMap) {

cout << p.second.getVal() << endl;

}

WARNING You can modify element values through non-const iterators, but the compiler will generate an error if you try to modify the key of an element, even through a non-const iterator, because it would destroy the sorted order of the elements in the map.

map iterators are bidirectional, meaning you can traverse them in both directions.

Looking Up Elements

A map provides logarithmic lookup of elements based on a supplied key. If you already know that an element with a given key is in a map, the simplest way to look it up is through operator[] as long as you call it on a non-const map or a non-const reference to a map. The nice thing about operator[] is that it returns a reference to the element that you can use and modify directly, without worrying about pulling the value out of a pair object. Here is an extension to the preceding example to call the setVal() method on the Data object value at key 1:

map<int, Data> dataMap;

dataMap[1] = Data(4);

dataMap[1] = Data(6);

dataMap[1].setVal(100);

However, if you don’t know whether the element exists, you may not want to use operator[], because it will insert a new element with that key if it doesn’t find one already. As an alternative, map provides a find() method that returns an iterator referring to the element with the specified key, if it exists, or the end() iterator if it’s not in the map. Here is an example using find() to perform the same modification to the Data object with key 1:

auto it = dataMap.find(1);

if (it != end(dataMap)) {

it->second.setVal(100);

}

As you can see, using find() is a bit clumsier, but it’s sometimes necessary.

If you only want to know whether or not an element with a certain key is in a map, you can use the count() method. It returns the number of elements in a map with a given key. For maps, the result will always be 0 or 1 because there can be no elements with duplicate keys.

Removing Elements

A map allows you to remove an element at a specific iterator position or to remove all elements in a given iterator range, in amortized constant and logarithmic time, respectively. From the client perspective, these two erase() methods are equivalent to those in the sequential containers. A great feature of a map, however, is that it also provides a version of erase() to remove an element matching a key. Here is an example:

map<int, Data> dataMap;

dataMap[1] = Data(4);

cout << "There are " << dataMap.count(1) << " elements with key 1" << endl;

dataMap.erase(1);

cout << "There are " << dataMap.count(1) << " elements with key 1" << endl;

The output is as follows:

There are 1 elements with key 1

There are 0 elements with key 1

map Example: Bank Account

You can implement a simple bank account database using a map. A common pattern is for the key to be one field of a class or struct that is stored in a map. In this case, the key is the account number. Here are simple BankAccount and BankDB classes:

class BankAccount

{

public:

BankAccount(int acctNum, const std::string& name)

: mAcctNum(acctNum), mClientName(name) {}

void setAcctNum(int acctNum) { mAcctNum = acctNum; }

int getAcctNum() const { return mAcctNum; }

void setClientName(const std::string& name) { mClientName = name; }

const std::string& getClientName() const { return mClientName; }

private:

int mAcctNum;

std::string mClientName;

};

class BankDB

{

public:

// Adds acct to the bank database. If an account exists already

// with that number, the new account is not added. Returns true

// if the account is added, false if it's not.

bool addAccount(const BankAccount& acct);

// Removes the account acctNum from the database.

void deleteAccount(int acctNum);

// Returns a reference to the account represented

// by its number or the client name.

// Throws out_of_range if the account is not found.

BankAccount& findAccount(int acctNum);

BankAccount& findAccount(const std::string& name);

// Adds all the accounts from db to this database.

// Deletes all the accounts from db.

void mergeDatabase(BankDB& db);

private:

std::map<int, BankAccount> mAccounts;

};

Here are the implementations of the BankDB methods, with comments explaining the code:

bool BankDB::addAccount(const BankAccount& acct)

{

// Do the actual insert, using the account number as the key

auto res = mAccounts.insert(make_pair(acct.getAcctNum(), acct));

// Return the bool field of the pair specifying success or failure

return res.second;

}

void BankDB::deleteAccount(int acctNum)

{

mAccounts.erase(acctNum);

}

BankAccount& BankDB::findAccount(int acctNum)

{

// Finding an element via its key can be done with find()

auto it = mAccounts.find(acctNum);

if (it == end(mAccounts)) {

throw out_of_range("No account with that number.");

}

// Remember that iterators into maps refer to pairs of key/value

return it->second;

}

BankAccount& BankDB::findAccount(const string& name)

{

// Finding an element by a non-key attribute requires a linear

// search through the elements.

for (auto& p : mAccounts) {

if (p.second.getClientName() == name) {

// found it!

return p.second;

}

}

throw out_of_range("No account with that name.");

}

void BankDB::mergeDatabase(BankDB& db)

{

// Just insert copies of all the accounts in the old db

// to the new database.

mAccounts.insert(begin(db.mAccounts), end(db.mAccounts));

// Now delete all the accounts in the old database.

db.mAccounts.clear();

}

You can test the BankDB class with the following code:

BankDB db;

db.addAccount(BankAccount(100, "Nicholas Solter"));

db.addAccount(BankAccount(200, "Scott Kleper"));

try {

auto& acct = db.findAccount(100);

cout << "Found account 100" << endl;

acct.setClientName("Nicholas A Solter");

auto& acct2 = db.findAccount("Scott Kleper");

cout << "Found account of Scott Kelper" << endl;

auto& acct3 = db.findAccount(1000);

} catch (const out_of_range&) {

cout << "Unable to find account" << endl;

}

The output is as follows:

Found account 100

Found account of Scott Kelper

Unable to find account

multimap

A multimap is a map that allows multiple elements with the same key. Like maps, multimaps support uniform initialization. The interface is almost identical to the map interface, with the following changes:

· multimaps do not provide operator[]. The semantics of this operator do not make sense if there can be multiple elements with a single key.

· Inserts on multimaps always succeed. Thus, the multimap insert() method that adds a single element returns only an iterator.

NOTE multimaps allow you to insert identical key/value pairs. If you want to avoid this redundancy, you must check explicitly before inserting a new element.

The trickiest aspect of multimaps is looking up elements. You can’t use operator[], because it is not provided. find() isn’t very useful because it returns an iterator referring to any one of the elements with a given key (not necessarily the first element with that key).

However, multimaps store all elements with the same key together and provide methods to obtain iterators for this subrange of elements with the same key in the container. The lower_bound() and upper_bound() methods each return a single iterator referring to the first and one-past-the-last elements matching a given key. If there are no elements matching that key, the iterators returned by lower_bound() and upper_bound() will be equal to each other.

If you need to obtain both iterators bounding the elements with a given key, it’s more efficient to use equal_range() instead of calling lower_bound() followed by calling upper_bound(). equal_range() returns a pair of the two iterators that would be returned bylower_bound() and upper_bound().

NOTE The lower_bound(), upper_bound(), and equal_range() methods exist for maps as well, but their usefulness is limited because a map cannot have multiple elements with the same key.

multimap Example: Buddy Lists

Most of the numerous online chat programs allow users to have a “buddy list” or list of friends. The chat program confers special privileges on users in the buddy list, such as allowing them to send unsolicited messages to the user.

One way to implement the buddy lists for an online chat program is to store the information in a multimap. One multimap could store the buddy lists for every user. Each entry in the container stores one buddy for a user. The key is the user and the value is the buddy. For example, if Harry Potter and Ron Weasley had each other on their individual buddy lists, there would be two entries of the form “Harry Potter” maps to “Ron Weasley” and “Ron Weasley” maps to “Harry Potter.”

A multimap allows multiple values for the same key, so the same user is allowed multiple buddies. Here is the BuddyList class definition:

class BuddyList

{

public:

// Adds buddy as a friend of name.

void addBuddy(const std::string& name, const std::string& buddy);

// Removes buddy as a friend of name

void removeBuddy(const std::string& name, const std::string& buddy);

// Returns true if buddy is a friend of name, false otherwise.

bool isBuddy(const std::string& name, const std::string& buddy) const;

// Retrieves a list of all the friends of name.

std::list<std::string> getBuddies(const std::string& name) const;

private:

std::multimap<std::string, std::string> mBuddies;

};

Here is the implementation, with comments explaining the code. It demonstrates the use of lower_bound(), upper_bound(), and equal_range():

void BuddyList::addBuddy(const string& name, const string& buddy)

{

// Make sure this buddy isn't already there. We don't want

// to insert an identical copy of the key/value pair.

if (!isBuddy(name, buddy)) {

mBuddies.insert({ name, buddy }); // Using initializer_list

}

}

void BuddyList::removeBuddy(const string& name, const string& buddy)

{

// Obtain the beginning and end of the range of elements with

// key 'name'. Use both lower_bound() and upper_bound() to demonstrate

// their use. Otherwise, it's more efficient to call equal_range().

auto iter = mBuddies.lower_bound(name); // Start of the range

auto end = mBuddies.upper_bound(name); // End of the range

// Iterate through the elements with key 'name' looking

// for a value 'buddy'

for (; iter != end; ++iter) {

if (iter->second == buddy) {

// We found a match! Remove it from the map.

mBuddies.erase(iter);

break;

}

}

}

bool BuddyList::isBuddy(const string& name, const string& buddy) const

{

// Obtain the beginning and end of the range of elements with

// key 'name' using equal_range().

auto range = mBuddies.equal_range(name);

auto iter = range.first; // Start of the range

auto end = range.second; // End of the range

// Iterate through the elements with key 'name' looking

// for a value 'buddy'. If there are no elements with key 'name',

// iter equals end, so the loop body doesn't execute.

for (; iter != end; ++iter) {

if (iter->second == buddy) {

// We found a match!

return true;

}

}

// No matches

return false;

}

list<string> BuddyList::getBuddies(const string& name) const

{

// Obtain the beginning and end of the range of elements with

// key 'name' using equal_range().

auto range = mBuddies.equal_range(name);

auto iter = range.first; // Start of the range

auto end = range.second; // End of the range

// Create a list with all names in the range (all buddies of name).

list<string> buddies;

for (; iter != end; ++iter) {

buddies.push_back(iter->second);

}

return buddies;

}

Note that removeBuddy() can’t simply use the version of erase() that erases all elements with a given key, because it should erase only one element with the key, not all of them. Note also that getBuddies() can’t use insert() on the list to insert the elements in the range returned by equal_range(), because the elements referred to by the multimap iterators are key/value pairs, not strings. The getBuddies() method must iterate explicitly through the list extracting the string from each key/value pair and pushing it onto the new list to be returned.

Here is a test of the BuddyList:

BuddyList buddies;

buddies.addBuddy("Harry Potter", "Ron Weasley");

buddies.addBuddy("Harry Potter", "Hermione Granger");

buddies.addBuddy("Harry Potter", "Hagrid");

buddies.addBuddy("Harry Potter", "Draco Malfoy");

// That's not right! Remove Draco.

buddies.removeBuddy("Harry Potter", "Draco Malfoy");

buddies.addBuddy("Hagrid", "Harry Potter");

buddies.addBuddy("Hagrid", "Ron Weasley");

buddies.addBuddy("Hagrid", "Hermione Granger");

auto harryBuds = buddies.getBuddies("Harry Potter");

cout << "Harry's friends: " << endl;

for (const auto& name : harryBuds) {

cout << "\t" << name << endl;

}

The output is as follows:

Harry's friends:

Ron Weasley

Hermione Granger

Hagrid

set

A set, defined in <set>, is very similar to a map. The difference is that instead of storing key/value pairs, in sets the value itself is the key. sets are useful for storing information in which there is no explicit key, but which you want to have in sorted order without any duplicates, with quick insertion, lookup, and deletion.

The interface supplied by set is almost identical to that of map. The main difference is that set doesn’t provide operator[].

You cannot change the key/value of elements in a set because modifying elements of a set while they are in the container would destroy the order.

set Example: Access Control List

One way to implement basic security on a computer system is through access control lists. Each entity on the system, such as a file or a device, has a list of users with permissions to access that entity. Users can generally be added to and removed from the permissions list for an entity only by users with special privileges. Internally, a set provides a nice way to represent the access control list. You could use one set for each entity, containing all the usernames who are allowed to access the entity. Here is a class definition for a simple access control list:

class AccessList

{

public:

// Default constructor

AccessList() = default;

// Constructor to support uniform initialization.

AccessList(const std::initializer_list<std::string>& initlst);

// Adds the user to the permissions list.

void addUser(const std::string& user);

// Removes the user from the permissions list.

void removeUser(const std::string& user);

// Returns true if the user is in the permissions list.

bool isAllowed(const std::string& user) const;

// Returns a list of all the users who have permissions.

std::list<std::string> getAllUsers() const;

private:

std::set<std::string> mAllowed;

};

Here are the method definitions:

AccessList::AccessList(const initializer_list<string>& initlst)

{

for (auto& user : initlst) {

addUser(user);

}

}

void AccessList::addUser(const string& user)

{

mAllowed.insert(user);

}

void AccessList::removeUser(const string& user)

{

mAllowed.erase(user);

}

bool AccessList::isAllowed(const string& user) const

{

return (mAllowed.count(user) != 0);

}

list<string> AccessList::getAllUsers() const

{

list<string> users;

users.insert(end(users), begin(mAllowed), end(mAllowed));

return users;

}

Finally, here is a simple test program:

AccessList fileX = { "pvw", "mgregoire", "baduser" };

fileX.removeUser("baduser");

if (fileX.isAllowed("mgregoire")) {

cout << "mgregoire has permissions" << endl;

}

if (fileX.isAllowed("baduser")) {

cout << "baduser has permissions" << endl;

}

auto users = fileX.getAllUsers();

for (const auto& user : users) {

cout << user << " ";

}

The output of this program is as follows:

mgregoire has permissions

mgregoire pvw

One of the constructors for AccessList uses an initializer_list as a parameter so that you can use the uniform initialization syntax, as demonstrated in the test program for initializing fileX.

multiset

A multiset is to a set what a multimap is to a map. A multiset supports all the operations of a set, but it allows multiple elements that are equal to each other to be stored in the container simultaneously. An example of a multiset is not shown because it’s so similar to setand multimap.

UNORDERED ASSOCIATIVE CONTAINERS/HASH TABLES

The STL has support for unordered associative containers or hash tables. There are four of them: unordered_map, unordered_multimap, unordered_set, and unordered_multiset. The map, multimap, set, and multiset containers discussed earlier sort their elements, while these unordered variants do not sort their elements.

Hash Functions

The unordered associative containers are also called hash tables. That is because the implementation makes use of so called hash functions. The implementation usually consists of some kind of array where each element in the array is called a bucket. Each bucket has a specific numerical index like 0, 1, 2, up until the last bucket. A hash function transforms a key into a bucket index. The value associated with that key is then stored in that bucket. The result of a hash function is not always unique. The situation in which two or more keys hash to the same bucket index is called a collision. There are many approaches to handling collisions; for example, quadratic re-hashing, linear chaining, etc. Those who are interested may consult one of the references in the Algorithms and Data Structures section in Appendix B. The STL standard does not specify which collision-handling algorithm is required, but most current implementations have chosen to resolve collisions by linear chaining. With linear chaining, buckets do not directly contain the data values associated with the keys, but contain a pointer to a linked list. This linked list contains all the data values for that specific bucket. Figure 16-1 shows how this works.

image

FIGURE 16-1

In Figure 16-1, applying the hash function to the keys “Marc G.” and “John D.” results in the same bucket index 128. This bucket then points to a linked list containing the keys “Marc G.” and “John D.” together with their associated data values. From Figure 16-1, it is also clear how lookups based on keys work and what the complexity is. A lookup involves a single hash function call to calculate the bucket index and after that one or more equality operations to find the right key in the linked list. This shows that lookups can be much faster compared to lookups with normal maps, but it all depends on how many collisions there are.

The choice of the hash function is very important. A hash function that creates no collisions is known as a “perfect hash.” A perfect hash has a lookup time that is constant; a regular hash has a lookup time that is, on average, close to 1, independent of the number of elements. As the number of collisions increases, the lookup time increases, reducing performance. Collisions can be reduced by increasing the basic hash table size, but you need to take cache sizes into account.

The C++ standard provides hash functions for pointers and all primitive data types such as bool, char, int, float, double, and so on. Hash functions are also provided for error_code, bitset, unique_ptr, shared_ptr, type_index, string, vector<bool>, and thread. If there is no standard hash function available for the type of key you want to use, then you have to implement your own hash function. Creating a perfect hash is a nontrivial exercise, even when the set of keys is fixed and known. Creating one that is good enough for use with the unordered associative containers is not that hard.

The following example demonstrates how to write a custom hash function. This example simply forwards the request to one of the standard hash functions available. The code defines a class IntWrapper that just wraps a single integer. An operator== is provided because that’s a requirement for keys used in unordered associative containers.

class IntWrapper

{

public:

IntWrapper(int i) : mI(i) {}

int getValue() const { return mI; }

friend bool operator==(const IntWrapper& lhs, const IntWrapper& rhs);

private:

int mI;

};

bool operator==(const IntWrapper& lhs, const IntWrapper& rhs)

{

return lhs.mI == rhs.mI;

}

To write a hash function for IntWrapper, you write a specialization of the std::hash template for IntWrapper. The std::hash template is defined in <functional>. This specialization needs an implementation of the function call operator that calculates and returns the hash of a given IntWrapper instance. For this example, the request is simply forwarded to the standard hash function for integers:

namespace std

{

template<> struct hash<IntWrapper>

{

typedef IntWrapper argument_type;

typedef size_t result_type;

result_type operator()(const argument_type& f) const {

return std::hash<int>()(f.getValue());

}

};

}

Note that you normally are not allowed to put anything in the std namespace, however, std class template specializations are an exception to this rule. The two type definitions are required by the hash class template. The implementation of the function call operator is just one line. It creates an instance of the standard hash function for integers: std::hash<int>() and then calls the function call operator on it with an argument f.getValue(). Note that this forwarding works in this example because IntWrapper contains just one data member, an integer. If the class would contain multiple data members, then a hash needs to be calculated taking all these data members into account; however, these details fall outside the scope of this book.

unordered_map

unordered_map is defined in <unordered_map> as a class template:

template <class Key,

class T,

class Hash = hash<Key>,

class Pred = std::equal_to<Key>,

class Alloc = std::allocator<std::pair<const Key, T> > >

class unordered_map;

There are five template parameters: the key type, the value type, the hash type, the equal comparison type, and the allocator type. With the last three parameters you can define your own hash function, equal comparison function, and allocator function, respectively. These parameters can usually be ignored because they have default values. I recommend you keep those default values when possible. The most important parameters are the first two. As with maps, uniform initialization can be used to initialize an unordered_map, as shown in the following example:

unordered_map<int, string> m = {

{1, "Item 1"},

{2, "Item 2"},

{3, "Item 3"},

{4, "Item 4"}

};

for (const auto& p : m) {

cout << p.first << " = " << p.second << endl;

}

The following table summarizes the differences between a map and an unordered_map.

OPERATION

MAP

UNORDERED_MAP

at()

x

x

begin()

x

x

bucket()

x

bucket_count()

x

bucket_size()

x

cbegin()

x

x

cend()

x

x

clear()

x

x

count()

x

x

crbegin()

x

crend()

x

emplace()

x

x

emplace_hint()

x

x

empty()

x

x

end()

x

x

equal_range()

x

x

erase()

x

x

find()

x

x

insert()

x

x

iterator / const_iterator

x

x

load_factor()

x

local_iterator / const_local_iterator

x

lower_bound()

x

max_bucket_count()

x

max_load_factor()

x

max_size()

x

x

operator[]

x

x

rbegin()

x

rehash()

x

rend()

x

reserve()

x

reverse_iterator / const_reverse_iterator

x

size()

x

x

swap()

x

x

upper_bound()

x

As with a normal map, all keys in an unordered_map should be unique. The preceding table includes a number of hash-specific methods. For example, load_factor() returns the average number of elements per bucket to give you an indication on the number of collisions. The bucket_count() method returns the number of buckets in the container. It also provides a local_iterator and const_local_iterator allowing you to iterate over the elements in a single bucket; but, these may not be used to iterate across buckets. The bucket(key)method returns the index of the bucket that contains the given key; begin(n) returns a local_iterator referring to the first element in the bucket with index n, and end(n) returns a local_iterator referring to one-past-the-last element in the bucket with index n. The example in the next section demonstrates how to use these methods.

unordered_map Example: Phone Book

The following example uses an unordered_map to represent a phone book. The name of a person is the key while the phone number is the value associated with that key.

template<class T>

void printMap(const T& m)

{

for (auto& p : m) {

cout << p.first << " (Phone: " << p.second << ")" << endl;

}

cout << "-------" << endl;

}

int main()

{

// Create a hash table.

unordered_map<string, string> um = {

{ "Marc G.", "123-456789" },

{ "Scott K.", "654-987321" } };

printMap(um);

// Add/remove some phone numbers.

um.insert(make_pair("John D.", "321-987654"));

um["Johan G."] = "963-258147";

um["Freddy K."] = "999-256256";

um.erase("Freddy K.");

printMap(um);

// Find the bucket index for a specific key.

int bucket = um.bucket("Marc G.");

cout << "Marc G. is in bucket " << bucket

<< " which contains the following "

<< um.bucket_size(bucket) << " elements:" << endl;

// Get begin and end iterators for the elements in this bucket.

// 'auto' is being used here. The compiler will derive the type

// of both iterators as unordered_map<string, string>::const_local_iterator

auto liter = um.cbegin(bucket);

auto literEnd = um.cend(bucket);

while (liter != literEnd) {

cout << "\t" << liter->first << " (Phone: " << liter->second << ")" << endl;

++liter;

}

cout << "-------" << endl;

// Print some statistics about the hash table

cout << "There are " << um.bucket_count() << " buckets." << endl;

cout << "Average number of elements in a bucket is " << um.load_factor() << endl;

return 0;

}

A possible output is as follows. Note that the output can be different on a different system because it depends on the implementation of the hash functions in the STL being used.

Scott K. (Phone: 654-987321)

Marc G. (Phone: 123-456789)

-------

Scott K. (Phone: 654-987321)

Marc G. (Phone: 123-456789)

Johan G. (Phone: 963-258147)

John D. (Phone: 321-987654)

-------

Marc G. is in bucket 1 which contains the following 2 elements:

Scott K. (Phone: 654-987321)

Marc G. (Phone: 123-456789)

-------

There are 8 buckets.

Average number of elements in a bucket is 0.5

unordered_multimap

An unordered_multimap is an unordered_map that allows multiple elements with the same key. Their interfaces are almost identical, with the following changes:

· unordered_multimaps do not provide operator[]. The semantics of this operator do not make sense if there can be multiple elements with a single key.

· Inserts on unordered_multimaps always succeed. Thus, the unordered_multimap::insert() method that adds a single element returns only an iterator.

NOTE unordered_multimaps allow you to insert identical key/value pairs. If you want to avoid this redundancy, you must check explicitly before inserting a new element.

As discussed earlier with multimaps, looking up elements in unordered_multimaps cannot be done using operator[] because it is not provided. You can use find() but it returns an iterator referring to any one of the elements with a given key (not necessarily the first element with that key). Instead, it’s best to use the equal_range() method, which returns a pair of iterators: one referring to the first element matching a given key and one referring to one-past-the-last element matching a given key. The use of equal_range() is exactly the same as discussed for multimaps, so you can look at the example given for multimaps to see how it works.

unordered_set/unordered_multiset

The <unordered_set> header file defines unordered_set and unordered_multiset, which are very similar to set and multiset, respectively; except that they do not sort their keys and that they use a hash function. The differences between unordered_set and unordered_map are similar to the differences between set and map as discussed earlier in this chapter, so they are not discussed in detail here. Consult a Standard Library Reference for a thorough summary of unordered_set and unordered_multiset operations.

OTHER CONTAINERS

There are several other parts of the C++ language that work with the STL to varying degrees, including standard C-style arrays, strings, streams, and bitset.

Standard C-Style Arrays

Recall that “dumb” pointers are bona fide iterators because they support the required operators. This point is more than just a piece of trivia. It means that you can treat standard C-style arrays as STL containers by using pointers to their elements as iterators. Standard C-style arrays, of course, don’t provide methods like size(), empty(), insert(), and erase(), so they aren’t true STL containers. Nevertheless, because they do support iterators through pointers, you can use them in the algorithms described in Chapter 17 and in some of the methods described in this chapter.

For example, you could copy all the elements of a standard C-style array into a vector using the insert() method of a vector that takes an iterator range from any container. This insert() method prototype looks like this:

template <class InputIterator> iterator insert(const_iterator position,

InputIterator first, InputIterator last);

If you want to use a standard C-style int array as the source, then the templatized type of InputIterator becomes int*. Here is a full example:

const size_t count = 10;

unsigned int arr[count]; // standard C-style array

// Initialize each element of the array to the value of its index.

for (unsigned int i = 0; i < count; i++) {

arr[i] = i;

}

vector<int> vec; // STL vector

// Insert the contents of the array at the end of the vector.

vec.insert(end(vec), arr, arr + count);

// Print the contents of the vector.

for (const auto& i : vec) {

cout << i << " ";

}

Note that the iterator referring to the first element of the array is the address of the first element, which is arr in this case. The name of an array alone is interpreted as the address of the first element. The iterator referring to the end must be one-past-the-last element, so it’s the address of the first element plus 10, or arr+10.

It’s easier to use std::begin() or std::cbegin() to get an iterator to the first element of a stack-based array, and std::end() or std::cend() to get an iterator to one-past-the-last element of a stack-based array. For example, the call to insert() in the previous example can be written as follows:

vec.insert(end(vec), cbegin(arr), cend(arr));

WARNING Functions such as std::begin() and std::end() only work on stack-based C-style arrays, not on heap-based C-style arrays.

strings

You can think of a string as a sequential container of characters. Thus, it shouldn’t be surprising to learn that a C++ string is a full-fledged sequential container. It contains begin() and end() methods that return iterators into the string, insert(), push_back() anderase() methods, size(), empty(), and all the rest of the sequential container basics. It resembles a vector quite closely, even providing methods reserve() and capacity().

You can use string as an STL container just as you would use vector. Here is an example:

string str1;

str1.insert(cend(str1), 'h');

str1.insert(cend(str1), 'e');

str1.push_back('l');

str1.push_back('l');

str1.push_back('o');

for (const auto& letter : str1) {

cout << letter;

}

cout << endl;

for (auto it = cbegin(str1); it != cend(str1); ++it) {

cout << *it;

}

cout << endl;

In addition to the STL sequential container methods, strings provide a whole host of useful methods and friend functions. The string interface is actually quite a good example of a cluttered interface, one of the design pitfalls discussed in Chapter 6. The string class is discussed in detail in Chapter 2.

Streams

Input and output streams are not containers in the traditional sense: they do not store elements. However, they can be considered sequences of elements, and as such share some characteristics with STL containers. C++ streams do not provide any STL-related methods directly, but the STL supplies special iterators called istream_iterator and ostream_iterator that allow you to “iterate” through input and output streams. Chapter 20 explains how to use them.

bitset

A bitset is a fixed-length abstraction of a sequence of bits. A bit can represent only two values, 1 and 0, which can be referred to as on/off, true/false, etc. A bitset also uses the terminology set and unset. You can toggle or flip a bit from one value to the other.

A bitset is not a true STL container: it’s of fixed size, it’s not templatized on an element type, and it doesn’t support iteration. However, it’s a useful utility, which is often lumped with the containers, so a brief introduction is provided here. Consult a Standard Library Reference for a thorough summary of the bitset operations.

bitset Basics

A bitset, defined in <bitset>, is templatized on the number of bits it stores. The default constructor initializes all fields of a bitset to 0. An alternative constructor creates a bitset from a string of 0 and 1 characters.

You can adjust the values of individual bits with the set(), reset(), and flip() methods, and you can access and set individual fields with an overloaded operator[]. Note that operator[] on a non-const object returns a proxy object to which you can assign a Boolean value, call flip(), or complement with ~. You can also access individual fields with the test() method. Additionally, you can stream bitsets with the normal insertion and extraction operators. A bitset is streamed as a string of 0 and 1 characters.

Here is a small example:

bitset<10> myBitset;

myBitset.set(3);

myBitset.set(6);

myBitset[8] = true;

myBitset[9] = myBitset[3];

if (myBitset.test(3)) {

cout << "Bit 3 is set!"<< endl;

}

cout << myBitset << endl;

The output is as follows:

Bit 3 is set!

1101001000

Note that the leftmost character in the output string is the highest numbered bit. This corresponds to our intuitions about binary number representations, where the low-order bit representing 20 = 1 is the rightmost bit in the printed representation.

Bitwise Operators

In addition to the basic bit manipulation routines, a bitset provides implementations of all the bitwise operators: &, |, ^, ~, <<, >>, &=, |=, ^=, <<=, and >>=. They behave just as they would on a “real” sequence of bits. Here is an example:

auto str1 = "0011001100";

auto str2 = "0000111100";

bitset<10> bitsOne(str1);

bitset<10> bitsTwo(str2);

auto bitsThree = bitsOne & bitsTwo;

cout << bitsThree << endl;

bitsThree <<= 4;

cout << bitsThree << endl;

The output of the program is as follows:

0000001100

0011000000

bitset Example: Representing Cable Channels

One possible use of bitsets is tracking channels of cable subscribers. Each subscriber could have a bitset of channels associated with his or her subscription, with set bits representing the channels to which he or she actually subscribes. This system could also support “packages” of channels, also represented as bitsets, which represent commonly subscribed combinations of channels.

The following CableCompany class is a simple example of this model. It uses two maps, each of string/bitset, storing the cable packages as well as the subscriber information.

const size_t kNumChannels = 10;

class CableCompany

{

public:

// Adds the package with the specified channels to the database.

void addPackage(const std::string& packageName,

const std::bitset<kNumChannels>& channels);

// Removes the specified package from the database

void removePackage(const std::string& packageName);

// Adds customer to database with initial channels found in package.

// Throws out_of_range if the package name is invalid.

// Throws invalid_argument if the customer is already known.

void newCustomer(const std::string& name, const std::string& package);

// Adds customer to database with given initial channels.

// Throws invalid_argument if the customer is already known.

void newCustomer(const std::string& name,

const std::bitset<kNumChannels>& channels);

// Adds the channel to the customers profile.

// Throws invalid_argument if the customer is unknown.

void addChannel(const std::string& name, int channel);

// Removes the channel from the customers profile.

// Throws invalid_argument if the customer is unknown.

void removeChannel(const std::string& name, int channel);

// Adds the specified package to the customers profile.

// Throws out_of_range if the package name is invalid.

// Throws invalid_argument if the customer is unknown.

void addPackageToCustomer(const std::string& name,

const std::string& package);

// Removes the specified customer from the database.

void deleteCustomer(const std::string& name);

// Retrieves the channels to which a customer subscribes.

// Throws invalid_argument if the customer is unknown.

std::bitset<kNumChannels>& getCustomerChannels(const std::string& name);

private:

typedef std::map<std::string, std::bitset<kNumChannels>> MapType;

MapType mPackages, mCustomers;

};

Here are the implementations of all methods, with comments explaining the code:

void CableCompany::addPackage(const string& packageName,

const bitset<kNumChannels>& channels)

{

// Just make a key/value pair and insert it into the packages map.

mPackages.insert({ packageName, channels });

}

void CableCompany::removePackage(const string& packageName)

{

// Just erase the package from the package map

mPackages.erase(packageName);

}

void CableCompany::newCustomer(const string& name, const string& package)

{

// Get a reference to the specified package.

auto it = mPackages.find(package);

if (it == end(mPackages)) {

// That package doesn't exist. Throw an exception.

throw out_of_range("Invalid package");

}

// Create the account with the bitset representing that package.

// Note that 'it' refers to a name/bitset pair. The bitset is the

// second field.

auto result = mCustomers.insert({ name, it->second });

if (!result.second) {

// Customer was already in the database. Nothing changed.

throw invalid_argument("Duplicate customer");

}

}

void CableCompany::newCustomer(const string& name,

const bitset<kNumChannels>& channels)

{

// Just add the customer/channels pair to the customers map.

auto result = mCustomers.insert({ name, channels });

if (!result.second) {

// Customer was already in the database. Nothing changed.

throw invalid_argument("Duplicate customer");

}

}

void CableCompany::addChannel(const string& name, int channel)

{

// Find a reference to the customer.

auto it = mCustomers.find(name);

if (it != end(mCustomers)) {

// We found this customer; set the channel.

// Note that 'it' is a reference to a name/bitset pair.

// The bitset is the second field.

it->second.set(channel);

} else {

throw invalid_argument("Unknown customer");

}

}

void CableCompany::removeChannel(const string& name, int channel)

{

// Find a reference to the customer.

auto it = mCustomers.find(name);

if (it != end(mCustomers)) {

// We found this customer; remove the channel.

// Note that 'it' is a reference to a name/bitset pair.

// The bitset is the second field.

it->second.reset(channel);

} else {

throw invalid_argument("Unknown customer");

}

}

void CableCompany::addPackageToCustomer(const string& name,

const string& package)

{

// Find the package.

auto itPack = mPackages.find(package);

if (itPack == end(mPackages)) {

// That package doesn't exist. Throw an exception.

throw out_of_range("Invalid package");

}

// Find the customer.

auto itCust = mCustomers.find(name);

if (itCust != end(mCustomers)) {

// Or-in the package to the customers existing channels.

// Note that the iterators are references to name/bitset pairs.

// The bitset is the second field.

itCust->second |= itPack->second;

} else {

throw invalid_argument("Unknown customer");

}

}

void CableCompany::deleteCustomer(const string& name)

{

// Remove the customer with this name

mCustomers.erase(name);

}

bitset<kNumChannels>& CableCompany::getCustomerChannels(const string& name)

{

// Find the customer

auto it = mCustomers.find(name);

if (it != end(mCustomers)) {

// Found it.

// Note that 'it' is a reference to a name/bitset pair.

// The bitset is the second field.

return it->second;

}

// Didn't find it. Throw an exception.

throw invalid_argument("Unknown customer");

}

Finally, here is a simple program demonstrating how to use the CableCompany class:

CableCompany myCC;

auto basic_pkg = "1111000000";

auto premium_pkg = "1111111111";

auto sports_pkg = "0000100111";

myCC.addPackage("basic", bitset<kNumChannels>(basic_pkg));

myCC.addPackage("premium", bitset<kNumChannels>(premium_pkg));

myCC.addPackage("sports", bitset<kNumChannels>(sports_pkg));

myCC.newCustomer("Marc G.", "basic");

myCC.addPackageToCustomer("Marc G.", "sports");

cout << myCC.getCustomerChannels("Marc G.") << endl;

SUMMARY

This chapter introduced the standard template library containers. It presented sample code illustrating a variety of uses for these containers. Hopefully, you appreciate the power of vector, deque, list, forward_list, array, stack, queue, priority_queue, map, multimap, set, multiset, unordered_map, unordered_multimap, unordered_set, unordered_multiset, string, and bitset. Even if you don’t incorporate them into your programs immediately, at least keep them in the back of your mind for future projects.

Now that you are familiar with the containers, the next chapter can illustrate the true power of the STL with a discussion on generic algorithms.