Containers

Containers are objects that you use to store and organize other objects. A class that implements a linked list is an example of a container. You create a container class from an STL template by supplying the type of the object that you intend to store. For example, vector<T> is a template for a container that is a linear array that automatically increases in size when necessary. T is the type parameter that specifies the type of objects to be stored. Here are a couple of statements that create vector<T> containers:

std::vector<std::string> strings;     // Stores object of type string
std::vector<double> data;             // Stores values of type double

The first statement creates the strings container class that stores objects of type string, while the second statement creates the data container that stores values of type double.

You can store items of a fundamental type, or of any class type, in a container. If your type argument for a container template is a class type, the container can store objects of that type, or potentially of any derived class type. However, storing objects of a derived class type in a container created for base class objects will cause object slicing. Object slicing results in the derived part of an object being sliced off and occurs when you pass a derived class object by value for a parameter of a base class type. The base class copy constructor will be called to copy the derived class object, and because this constructor has no knowledge of derived class data members, they will not be copied. You can avoid slicing of objects of a derived type by storing pointers in the container. You can store pointers to a derived class type in a container that stores base class pointers.

The templates for the STL container classes are defined in the standard headers shown in the following table:

All the template names are defined within the std namespace. T is the template type parameter for the type of elements stored in a container; where keys are used, K is the type of key.

auto data = vector<CBox, My_Allocator<CBox>>();

map<K, T, Compare=less<K>, Allocator=allocator<pair<K,T>> >

Container Adapters

A container adapter is a template class that wraps an existing container class to provide a different, and typically more restricted, capability. The container adapters are defined in the headers in the following table.

Iterators

Iterators are objects that behave like pointers and are very important for accessing the contents of all containers except for those defined by a container adapter; container adapters do not support iterators. You can obtain an iterator from a container, which you can use to access the objects you have stored in it. You can also create iterators that will allow input and output of objects, or data items of a given type from or to a stream. Although basically all iterators behave like pointers, not all iterators provide the same functionality. However, they do share a base level of capability. Given two iterators, iter1 and iter2, accessing the same set of objects, the comparison operations iter1 == iter2, iter1 != iter2, and the assignment iter1 = iter2 are always possible, regardless of the types of iter1 and iter2.

Using unique_ptr Objects

A unique_ptr object stores a pointer uniquely. No other unique_ptr object can contain the same address so the object pointed to is effectively owned by the unique_ptr object. When the unique_ptr object is destroyed, the object to which it points is destroyed too.

You can create and initialize a smart pointer like this:

unique_ptr<CBox> pBox {new CBox {2,2,2}};

pBox will behave just like an ordinary pointer and you can use it in the same way to call public member functions for the CBox object. The big difference is that you no longer have to worry about deleting the CBox object from the heap.

Here’s a version of some code that you saw back in Chapter 5, modified to use a unique_ptr:

#include <iostream>
#include <memory>
        
std::unique_ptr<double> treble(double);     // Function prototype
        
int main()
{
   double num {5.0};
   std::unique_ptr<double> ptr {};
   ptr = treble(num);
   std::cout << "Three times num = " << 3.0*num << std::endl;
   std::cout << "Result = " << *ptr << std::endl;
}
        
std::unique_ptr<double> treble(double data)
{
   std::unique_ptr<double> result {new double {}};
   *result = 3.0*data;
   return result;
}

This produces the result you would expect. ptr points to a double value of 15.0 after the statement that calls treble() has executed. You cannot copy a unique_ptr object or pass it by value to a function. The treble() function creates a local unique_ptr<double> object, modifies the value that it points to, and returns it. How does the treble() function return a unique_ptr<double> object when it cannot be copied? When you return a unique_ptr object from a function, std::move()is used to move the pointer from the local unique_ptr object to the object that is received by the calling function. Moving the pointer from one unique_ptr to another transfers ownership of the object pointed to, so the source unique_ptr object will contain nullptr. This has implications when you store unique_ptr objects in a container. I’ll show you how you can store smart pointers in an STL container later in this chapter.

The make_unique<T>() function template creates a new T object on the heap and then creates a unique_ptr<T> object that points to the Tobject. The arguments that you pass to make_unique<T>() are the arguments to the T class constructor. Here’s how you could create a unique_ptr object holding the address of a CBox object:

auto pBox = std::make_unique<CBox>(2.0, 3.0, 4.0);

This creates a CBox object on the heap and stores its address in a new unique_ptr<CBox> object, pBox. Apart from the fact that it cannot be duplicated, you can use pBox just like an ordinary pointer.

Another version of make_unique<>() can create a unique_ptr object pointing to a new array in the free store. For example:

auto pBoxes = std::make_unique<CBox[]>(6);

This statement creates an array of six CBox objects on the heap and stores the address of the array in a unique_ptr<CBox[]> object. You put the array type as the function template argument and the array dimension as the argument to the function. You access the array elements by indexing the unique_ptr object, pBoxes. For example:

pBoxes[1] = CBox {1.0, 2.0, 3.0};

This sets the second element in the array to a CBox object with the dimensions you see. Thus the unique_ptr object acts just like the array name for a normal array.

Using shared_ptr Objects

You can define a shared_ptr object explicitly using the shared_ptr<T> constructor, but it is better to use the make_shared<T>() function that creates an object of type T on the heap and then returns a shared_ptr<T> object that points to it because the memory allocation is more efficient. Here’s an example:

auto pBox = make_shared<CBox>(1.0, 2.0, 3.0);  // Points to a CBox object

This creates a CBox object on the heap with length, width, and height values as 1.0, 2.0, and 3.0 and stores the shared_ptr<CBox> object that points to it in pBox.

In contrast to unique_ptr, you can have multiple shared_ptr objects pointing to the same object. The object pointed to will survive until the last shared_ptr object that points to it is destroyed, then it too will be destroyed. A shared_ptr object will be copied when you return it from a function.

You can initialize a shared_ptr with another shared_ptr:

std::shared_ptr<CBox> pBox2 {pBox};

pBox2 points to the same object as pBox.

Using a smart pointer works in the same way as an ordinary pointer:

std::cout << "Box volume = " << pBox->volume() << std::endl;

A smart pointer that you define with a base class type, can store a pointer to a derived class type. For example, given the CBox and CCandyBox classes that you saw in Chapter 9, you could define a shared_ptr like this:

shared_ptr<CBox> pBox {new CCandyBox {2,2,2}};

pBox points to a CCandyBox object so smart pointers work in the same way as ordinary pointers in this respect too.

If you use a local smart pointer in a function to point to an object on the heap, the memory for the object will be automatically released when the function returns — assuming that you are not returning the smart pointer from the function. You can use smart pointers as class members. If you are defining a class that uses smart pointers to keep track of heap objects, you won’t need to implement a destructor to be sure that the memory for the objects is released when the class object is destroyed. The default constructor will call the destructor for each member that is a smart pointer.

Accessing the Raw Pointer in a Smart Pointer

You will sometimes need access to the address that a smart pointer contains; this is called a raw pointer. You will see later in the book that there are circumstances with the MFC where you need a raw pointer because MFC member functions do not accept smart pointers as arguments. Calling the get() memberof a smart pointer object returns the raw pointer, which you can then pass to a function that requires it.

Calling the reset() member of a smart pointer resets the raw pointer to nullptr. This will cause the object that is pointed to be destroyed when there are no other smart pointers that contain the same address.

Casting Smart Pointers

You cannot use the standard cast operators such as static_cast, dynamic_cast, and const_cast with smart pointers. When you need to cast a smart pointer, you must use static_pointer_cast, dynamic_pointer_cast, and const_pointer_cast instead of the standard operators. When you use dynamic_pointer_cast to cast a shared_ptr<T> object to a shared_ptr<Base> object, the result will be a shared_ptr containing nullptr if Base is not a base class for T. The cast operations for smart pointers are defined as function templates in the memory header.

Creating Vector Containers

The simplest way to create a vector container is like this:

vector<int> mydata;

This creates a container that will store values of type int. The initial capacity is zero, so you will be allocating more memory right from the outset when you insert the first value.

The push_back() member function adds a new element to the end of a vector, so to store a value in this vector you would write:

mydata.push_back(99);

The argument to push_back() is the item to be stored. This statement stores 99 in the vector, so after executing this, the vector contains one element. The push_back() function is overloaded with an rvalue reference parameter version so it will move temporary objects into the vector rather than copy them.

Here’s another way to create a vector to store integers:

vector<int> mydata(100);

This creates a vector that contains 100 elements that are all initialized to zero. Note that you must use parentheses here. If you put 100 between braces, the vector will contain one element with the value 100. If you add new elements, the memory allocated for the vector will be increased automatically, so obviously it’s a good idea to choose a reasonably accurate value for the number of integers you are likely to store. This vector can be used just like an array. For example, to store a value in the third element, you can write:

mydata[2] = 999;

Of course, you can only use an index value to access elements that are within the range that exist in the vector. You can’t add new elements in this way though. To add a new element, you can use the push_back() function.

You can initialize the elements in a vector to a different value, when you create it by using this statement:

vector<int> mydata(100, -1);

You must use parentheses here too. The second argument is the initial value to be used for elements, so all 100 elements will be set to -1.

If you don’t want to create elements when you create a vector container, you can increase the capacity after you create it by calling its reserve() function:

vector<int> mydata;
mydata.reserve(100);

The argument to the reserve() function is the minimum number of elements to be accommodated. If the argument is less than the current capacity of the vector, then calling reserve() will have no effect. In this code fragment, calling reserve() causes the vector container to allocate sufficient memory for a total of 100 elements although the elements are not yet created.

When you want to specify a set of initial values for elements, you use an initializer list:

vector<int> values {100, 200, 300, 400);

This creates a vector containing four elements with the values from the list.

You can also create a vector with initial values for elements from an external array. For example:

double data[] {1.5, 2.5, 3.5, 4.5, 5.5, 6.5, 7.5, 8.5, 9.5, 10.5};
vector<double> mydata(data, data+8);

Here, the data array is created with 10 elements of type double, with the initial values shown. The second statement creates a vector storing elements of type double, with eight elements initially having the values corresponding to data[0] through data[7]. The arguments to the vector<double> constructor are pointers (and can also be iterators), where the first pointer points to the first initializing element in the array, and the second points to one past the last initializing element. Thus, the mydata vector will contain eight elements with initial values 1.5, 2.5, 3.5, 4.5, 5.5, 6.5, 7.5, and 8.5.

Because the constructor in the previous fragment can accept either pointer or iterator arguments, you can initialize a vector when you create it with values from another vector that contains elements of the same type. You just supply the constructor with an iterator pointing to the first element you want to use as an initializer, plus a second iterator pointing to one past the last element you want to use. Here’s an example:

vector<double> values(begin(mydata), end(mydata));

After executing this statement, the values vector will have elements that are duplicates of the mydata vector. As Figure 10-3 illustrates, the begin() template function returns a random access iterator that points to the first element in the argument, and end()returns a random access iterator pointing to one past the last element. A sequence of elements is typically specified in the STL by two iterators, one pointing to the first element and the other pointing to one past the last element, so you’ll see this time and time again.

Because begin() and end()return random access iterators, you can modify what they point to when you use them. For a vector<T>, the type of the iterators that begin() and end()return is vector<T>::iterator, where T is the type of object in the vector. Most of the time you can use the auto keyword to specify the iterator type.

Here’s a statement that creates a vector that is initialized with the third through the seventh elements from the mydata vector:

vector<double> values(begin(mydata)+2, end(mydata)-1);

Adding 2 to the first iterator makes it point to the third element in mydata. Subtracting 1 from the second iterator makes it point to the last element in mydata; remember that the second argument to the constructor is an iterator that points to a position that is one past the element to be used as the last initializer, so the object that the second iterator points to is not included in the set.

As I said earlier, it is pretty much standard practice in the STL to indicate a sequence of elements in a container by a begin iterator that points to the first element and an end iterator that points to one past the last element. This allows you to iterate over all the elements in a sequence by incrementing the begin iterator until it equals the end iterator. This means that the iterators only need to support the equality operator to allow you to walk through the sequence.

Occasionally, you may want to access the contents of a vector in reverse order. Calling the rbegin() function for a vector returns an iterator that points to the last element, while rend() points to one before the first element (that is, the position preceding the first element), as Figure 10-4 illustrates.

The iterators returned by rbegin() and rend() are called reverse iterators because they present the elements in reverse sequence. For a vector<T> container, reverse iterators are of type vector<T>::reverse_iterator. Figure 10-4 shows how adding a positive integer to the rbegin() iterator moves back through the sequence, and subtracting an integer from rend() moves forward through the sequence.

Here’s how you could create a vector containing the contents of another vector in reverse order:

double data[] {1.5, 2.5, 3.5, 4.5, 5.5, 6.5, 7.5, 8.5, 9.5, 10.5};
vector<double> mydata(data, data+8);
vector<double> values(rbegin(mydata), rend(mydate));

Because you are using reverse iterators as arguments to the constructor in the last statement, the values vector will contain the elements from mydata in reverse order.

When you want to use iterators to access the elements in a vector but do not want to modify the elements you can use the cbegin() and cend()template functions that return const iterators. For example, suppose you want to list the squares of the integer values stored in a vector:

  std::vector<int> mydata {1, 2, 3, 4, 5};
  for(auto iter = std::cbegin(mydata) ; iter != std::cend(mydata) ; ++iter)
    std::cout << (*iter) << " squared is " << (*iter)*(*iter) << std::endl;

Using cbegin() and cend(), there is no possibility of modifying the elements in mydata accidentally within the loop. You also have the standalone template functions and container member functions crbegin() and crend() available that provide const reverse iterators.

The Capacity and Size of a Vector Container

The capacity of a vector is the maximum number of objects it can currently accommodate without allocating more memory. The size is the number of objects actually stored in the container. Obviously the size cannot be greater than the capacity.

You can obtain the size and capacity of the data container by calling the size() and capacity() member functions. For example:

std::cout << "The capacity of the container is: " << data.capacity() << std::endl
          << "The size of the container is: " << data.size() << std::endl;

Calling capacity()for a vector returns the current capacity, and calling its size() function returns the current size, both values being returned as type vector<T>::size_type. This is an implementation-defined integer type that is defined within the vector<T> class template. To create a variable to store the value returned from the size() or capacity() function, you can specify it as type vector<T>::size_type, where you replace T with the type of object stored in the container. The following fragment illustrates this:

vector<double> values;
vector<double>::size_type cap {values.capacity()};

Of course, the auto keyword makes it much easier:

auto cap = values.capacity();

If the value returned by the size() function is zero, then clearly the vector contains no elements; thus, you can use it as a test for an empty vector. You can also call the empty() function for a vector to test for this:

if(values.empty())
  std::cout << "No more elements in the vector.";

The empty() function returns a value of type bool that is true when the vector is empty and false otherwise.

You are unlikely to need it very often, but you can discover the maximum possible number of elements in a vector by calling its max_size() function. For example:

std::vector<std::string> strings;
std::cout << "Maximum length of strings vector: " 
          << strings.max_size() << std::endl;

Executing this fragment produces the output:

Maximum length of strings vector: 153391689

The maximum length is returned as type vector<string>::size_type. Note that the maximum length of a vector will depend on the type of element stored. If you try this with a vector storing values of type int, you will get 1073741823 as the maximum length, and for a vector storing values of type double it is 536870911.

You can increase or decrease the size of a vector by calling its resize() function. If you specify a new size that is less than the current size, sufficient elements will be deleted from the end of the vector to reduce it to its new size. If the new size is greater than the old, new elements will be added to the end of the vector to increase its length to the new size. Here’s code illustrating this:

vector<int> values(5, 66);   // Contains 66 66 66 66 66
values.resize(7, 88);        // Contains 66 66 66 66 66 88 88
values.resize(10);           // Contains 66 66 66 66 66 88 88 0 0 0
values.resize(4);            // Contains 66 66 66 66

The first argument to resize() is the new size. The second argument, when it is present, is the value to be used for new elements that need to be added to make up the new size. If you are increasing the size and you don’t specify a value for new elements, the default value will be used. In the case of a vector storing objects of a class type, the default value will be the object produced by the no-arg constructor for the class.

Accessing the Elements in a Vector

You have already seen that you can access the elements in a vector by using the subscript operator, just as you would for an array. You can also use the at() member function where the argument is the index of the element you want to access. Here’s how you could list the contents of the numbers vector in the previous example using at():

  for(vector<int>::size_type i {}; i<numbers.size() ;i++)
    std::cout << " " << numbers.at(i);

The operation of at()differs from the subscript operator, []. If you use a subscript with the subscript operator that is outside the valid range, the result is undefined. If you do the same with at(), an exception of type out_of_range will be thrown. If there’s the potential for subscript values outside the legal range to arise, it’s better to use the at() function and catch the exception than to allow the possibility for undefined results.

Of course, when you want to access all the elements in a vector, the range-based for loop always provides a simpler mechanism:

  for(auto number : numbers)
    std::cout << " " << number;

To access the first or last element in a vector you can call the front() or back() function, respectively:

std::cout << "The value of the first element is: " << numbers.front() << std::endl;
std::cout << "The value of the last element is: " << numbers.back() << std::endl;

Both functions come in two versions; one returns a reference to the element, and the other returns a const reference. The latter will be called when the vector object is const. If you call front() for a const vector, you cannot use the reference that is returned to modify the element and you cannot store the return value in a non-const variable.

Inserting and Deleting Elements in a Vector

In addition to the push_back() function you have seen, a vector container supports the pop_back() operation that deletes the last element. Both operations execute in constant time, that is, the time to execute will be the same, regardless of the number of elements in the vector. The pop_back() function is very simple to use:

vec.pop_back();

This statement removes the last element from the vector vec and reduces the size by 1. If you call pop_back() for an empty vector the behavior is undefined.

You could remove all the elements in a vector by calling the pop_back() function repeatedly, but the clear() function does this much more simply:

vec.clear();

This statement removes all the elements from vec, so the size will be zero. Of course, the capacity will be left unchanged.

vector<int> vec(5, 99);
vec.insert(begin(vec)+1, 88);

99 88 99 99 99 99

vec.insert(begin(vec)+2, 3, 77);

99 88 77 77 77 99 99 99 99

vector<int> newvec(5, 22);
newvec.insert(begin(newvec)+1, begin(vec)+1, begin(vec)+5);

22 88 77 77 77 22 22 22 22

std::vector<CBox> boxes;

boxes.push_back(CBox {1, 2, 3});
boxes.push_back(CBox {2, 4, 6});
boxes.push_back(CBox {3, 6, 9});

boxes.emplace_back(1, 2, 3);
boxes.emplace_back(2, 4, 6);
boxes.emplace_back(3, 6, 9);

newvec.erase(end(newvec)-2);

newvec.erase(begin(newvec)+1, begin(newvec)+4);

vector<int> first(5, 77);              // Contains 77 77 77 77 77
vector<int> second(8, -1);             // Contains -1 -1 -1 -1 -1 -1 -1 -1
first.swap(second);

vector<double> values;
for(int i {1}; i <= 50 ;++i)
  values.emplace_back(2.5*i);
vector<double> newdata(5, 3.5);
newdata.assign(begin(values)+1, end(values)-1);

newdata.assign(30, 99.5);

Storing Class Objects in a Vector

You can store objects of any class type in a vector, but the class must meet certain minimum criteria. Here’s a minimum specification for a given class T to be compatible with a vector or, in fact, any sequence container:

class T
{
public:
  T();                                 // Default constructor
  T(const T& t);                       // Copy constructor
  ~T();                                // Destructor
  T& operator=(const T& t);            // Assignment operator
};

The compiler will supply default versions of these class members if you don’t define them, so it’s not difficult for a class to meet these requirements. The important thing to note is that they are required and are likely to be used, so when the default implementation that the compiler supplies will not suffice, you must provide your own implementation.

If you store objects of your own class types in a vector, it’s highly recommended that you implement a move constructor and a move assignment operator for your class because the vector container fully supports move semantics. For example, if the vector needs to resize itself to allow more elements to be added, without move semantics the following sequence of events will occur:

1. A new vector with the new size is allocated.
2. All objects from the old vector are copied to the new vector.
3. All objects in the old vector are destroyed.
4. The old vector is deallocated.

With move semantics support in your class, this is what happens:

1. A new vector with the new size is allocated.
2. All objects from the old vector are moved to the new vector.
3. All objects in the old vector are destroyed.
4. The old vector is deallocated.

This will be significantly faster because no copying is necessary.

Let’s try an example.

Sorting Vector Elements

The sort<T>() function template that is defined in the algorithm header will sort a sequence of objects of any type as long as the required comparisons are supported. Objects are sorted in ascending sequence by default so the < operation must be supported. You identify the sequence by two random access iterators that point to the first and one-past-the-last objects. Note that random access iterators are essential; iterators with lesser capability will not suffice. The type parameter, T, specifies the type of random access iterator that the function will use. Thus, the sort<T>() template can sort the contents of any container that provides random access iterators, as long as the object type supports comparisons.

In the previous example, you implemented operator <() in the Person class, so you could sort a sequence of Person objects. Here’s how you could sort the contents of the vector<Person> container:

std::sort(stdbegin(people), stdend(people));

This sorts the contents of the vector in ascending sequence. You can add an #include directive for algorithm, and put the statement in main() before the output loop, to see the sort in action. Note that you can use sort<T>() to sort arrays. The only requirement is that the < operator should work with the type of the elements. Here’s a code fragment showing how you could use it to sort an array of integers:

const size_t N {100};
int data[N];
std::cout << "Enter up to " << N << " non-zero integers. Enter 0 to end:
";
int value {};
size_t count {};
for(size_t i {} ;i<N ;i++)            // Read up to N integers
{
  std::cin >> value;                  // Read a value
  if(!value)                          // If it is zero,
    break;                            // we are done
  data[count++] = value;
}
std::sort(data, data+count);          // Sort the integers

Note how the pointer marking the end of the sequence of elements to be sorted must still be one past the last element.

When you need to sort a sequence in descending order, you can use the version of the sort<T>() algorithm that accepts a third argument that is a function object that defines a binary predicate. The functional header defines a complete set of function object types for comparison predicates:

less<T>   less_equal<T>   equal<T>   greater_equal<T>   greater<T>

Each of these templates creates a class type for function objects that you can use with sort() and other algorithms for sorting objects of type T. The sort() function used in the previous fragment uses a less<int> function object by default. To specify a different function object to be used as the sort criterion, you add it as a third argument, like this:

std::sort(data, data+count, std::greater<int>());     // Sort the integers

The third argument to the function is an expression that calls the constructor for the greater<int> type, so you are passing an object of this type to the sort() function. This statement will sort the contents of the data array in descending sequence. If you are trying these fragments out, don’t forget that you need the functional header to be included for the function object. The comparison predicates also come in the form of transparent operator functors. They are referred to as transparent because they perform perfect forwarding of the arguments. When you want to use the transparent form with an algorithm, you just omit the template type argument, like this:

std::sort(data, data+count, std::greater<>());

This sorts the container contents with perfect forwarding of the objects to be compared.

Storing Pointers in a Vector

A vector container, like other containers, makes a copy of the objects you add to it. This has tremendous advantages in many circumstances, but it could be very inconvenient in some situations. For example, if your objects are large, there could be considerable overhead in copying each object as you add it to the container. This is an occasion where you might be better off storing smart pointers to the objects in the container. You could create a new version of the Ex10_02.cpp example to store pointers to Person objects in a container.

Array Containers

The array<T,N> template that is defined in the array header defines a container that is similar to an ordinary array in that it is of fixed length, N, and you can use the subscript operator to access the elements. You can also initialize an array container with an initializer list. For example:

std::array<double, 5> values {1.5, 2.5, 3.5, 4.5, 5.5};

If you supply fewer initializers than there are elements, the remaining elements will be initialized with the equivalent of zero. This means nullptr if the elements are pointers, and objects created by the default constructor if the elements are objects of a class type. If you supply too many initializers, the code won’t compile.

You can define an array container without initializing it:

std::array<int, 4> data;

The size is fixed and the four elements of type int will be created containing junk values. Array container elements of a fundamental type will not be initialized by default, but elements of a class type will be initialized by calling the no-arg constructor. You could construct an array of Person objects where the Person class is as in Ex10_03:

std::array<Person, 10> people;

This container has 10 elements of type Person, all with the firstname and secondname members as nullptr.

An array container knows its size, so you can use the range-based for loop when it is passed to a function. For example, here’s a function template that will list any array container of Person objects:

template<size_t N>
void listPeople(const std::array<Person, N>& folks)
{
  for(const auto& p : folks)
    p.showPerson();
}

Defining the function by a template with a parameter, N, allows it to be used to list an array of any number of Person objects. If your application classes use a standard function to display an object, you could add a template type parameter for the type of element stored and get a function that will list any of your arrays of any length or type. Remember, though, that each unique set of template parameter values will produce a separate instance of the template.

Because the elements of an array container are always created when you define it, you can reference an element using the subscript operator and use it as an lvalue. For example:

people[1] = Person("Joe", "Bloggs");

This stores a Person object in the second element in the array.

Here’s a summary of some of the most useful members of an array container type:

• void fill(const T& arg) sets all the array elements to arg:

  people.fill(Person("Ned", "Kelly"));   // Fill array with Ned Kellys

• size() returns the size of the array as an integer.
• back() returns a reference to the last array element:

  people.back().showPerson();            // Output the last person

• begin() returns an iterator pointing to the first array element.
• end() returns an iterator pointing to one past the last array element.
• rbegin() returns a reverse iterator pointing to the last array element.
• rend() returns a reverse iterator pointing to before the first array element.
• swap(array& right) swaps the current array with right. The current array and right must store the same type of elements and have the same size.

  array<int, 3> left = {1, 2, 3};
  array<int, 3> right = {10, 20, 30};
  left.swap(right);           // Swap contents of left and right

You can use any of the comparison operators, <, <=, ==, >=, >, and !=, to compare two array containers as long as they store the same number of elements of the same type. Corresponding elements are compared in sequence to determine the result. For example, array1<array2 will result in true if array1 has the first occurring element that is less than the corresponding element in array2. Two arrays are equal if all corresponding elements are equal and unequal if any pair of corresponding elements differ.

Let’s see an example of an array in use.

Double-ended Queue Containers

The double-ended queue container template, deque<T>, is defined in the deque header. A double-ended queue is very similar to a vector in that it can do everything a vector container can, and includes the same function members, but you can also add and delete elements efficiently at the beginning of the sequence as well as at the end. You could replace the vector in Ex10_02.cpp with a double-ended queue, and it would work just as well:

  std::deque<Person> people;               // Double-ended queue of Person objects

The push_front() member function adds an element to the front of the container and you can delete the first element by calling pop_front(). There’s also an emplace_front() member so if you were using a deque<Person> container in Ex10_02.cpp, you could add elements at the front instead of the back:

    people.emplace_front(firstname, secondname);

Using this statement to add elements, the order of elements in the double-ended queue would be the reverse of those in the vector.

Here are examples of constructors for a deque<T> container:

deque<string> strings;            // An empty container
deque<int> items(50);             // 50 elements initialized to default value
deque<double> values(5, 0.5);     // 5 elements of 0.5
deque<int> data(cbegin(items), cend(items));  // Initialized with a sequence
deque<int> numbers {1, 3, 5, 7, 9, 11};

Although a double-ended queue is very similar to a vector and does everything a vector can do, it does have one disadvantage. Because of the additional capability, the memory management for a double-ended queue is more complicated than for a vector, so it will be slightly slower. Unless you need to add elements to the front of the container, a vector is a better choice. Let’s see a double-ended queue in action.

Using List Containers

The list<T> container template from the list header implements a doubly-linked list. The big advantage this has over a vector or a double-ended queue is that you can insert or delete elements anywhere in the sequence in constant time. The main drawback is that a list cannot directly access an element by its position. It’s necessary to traverse the elements in a list from a known position when you want to do this, usually the first or the last. The range of constructors for a list container is similar to that for a vector or double-ended queue. This statement creates an empty list:

std::list<std::string> names;

You can also create a list with a given number of default elements:

std::list<std::string> sayings(20);              // A list of 20 empty strings

Here’s how you create a list containing a given number of identical elements:

std::list<double> values(50, 2.71828);

This creates a list of 50 values of type double equal to 2.71828.

You can also construct a list initialized with values from a sequence specified by two iterators:

std::list<double> samples(++cbegin(values), --cend(values));

This creates a list from the contents of the values list, omitting the first and last elements. The iterators returned by the begin() and end() functions for a list are bidirectional iterators, so you do not have the same flexibility as with a vector or a deque container that support random access iterators. You can only change the value of a bidirectional iterator using the increment or decrement operators.

Just like the other sequence containers, you can discover the number of elements in a list by calling its size() member. You can also change the number of elements by calling its resize() function. If the argument to resize() is less than the number of elements, elements will be deleted from the end; if the argument is greater, elements will be added using the default constructor for the type of elements stored.

std::list<int> data(20, 1);           // List of 20 elements value 1
data.insert(++begin(data), 77);       // Insert 77 as the second element

1 77 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

auto iter = begin(data); 
  std::advance(iter, 9);    // Increment iterator by 9
data.insert(iter, 3, 88);   // Insert 3 copies of 88 starting at the 10th

1 77 1 1 1 1 1 1 1 88 88 88 1 1 1 1 1 1 1 1 1 1 1 1

std::vector<int> numbers(10, 5);         // Vector of 10 elements with value 5
data.insert(--(--end(data)), cbegin(numbers), cend(numbers));

1 77 1 1 1 1 1 1 1 88 88 88 1 1 1 1 1 1 1 1 1 1 5 5 5 5 5 5 5 5 5 5 1 1

  std::list<std::string> strings;
  strings.emplace_back("first");
  std::string second("second");
  strings.emplace_back(std::move(second));
  strings.emplace_front("third");
  strings.emplace(++begin(strings), "fourth");

third  fourth  first  second

  std::list<std::string> strings;
  strings.emplace_back("first");
  std::string second("second");
  strings.emplace_back(std::move(second));
  strings.emplace_front("third");
  strings.emplace(++begin(strings), "fourth");
  for(const auto& s : strings) 
    std::cout << s << std::endl;

 strings.sort(std::greater<std::string>());     // Descending sequence

strings.sort(std::greater<>());                 // Perfect forwarding

std::list<int> numbers {10, 22, 4, 56, 89, 77, 13, 9};
numbers.erase(++begin(numbers));      // Remove the second element
        
// Remove all except the first and the last two
numbers.erase(++begin(numbers), --(--end(numbers)));

10 4 56 89 77 13 9

10 13 9

numbers.remove(22);

std::list<int> numbers {10, 22, 4, 56, 89, 77, 13, 9};
numbers.assign(10, 99);         // Replace contents by 10 copies of 99
numbers.assign(data+1, data+4); // Replace contents by 22 4 56

std::list<int> numbers {10, 22, 4, 10, 89, 22, 89, 10} ; // 10 22 4 10 89 22 89 10
numbers.sort();                                          // 4 10 10 10 22 22 89 89
numbers.unique();                                        // 4 10 22 89

std::list<int> numbers {1, 2, 3};                        // 1 2 3
std::list<int> values {5, 6, 7, 8};                      // 5 6 7 8
numbers.splice(++begin(numbers), values);                // 1 5 6 7 8 2 3

std::list<int> numbers {1, 2, 3};                        // 1 2 3
std::list<int> values {5, 6, 7, 8};                      // 5 6 7 8
numbers.splice(begin(numbers), values, --end(values));   // 8 1 2 3

std::list<int> numbers {1, 2, 3};                        // 1 2 3
std::list<int> values {5, 6, 7, 8};                      // 5 6 7 8
numbers.splice(++begin(numbers), values, ++begin(values),
                                          --end(values));// 1 6 7 2 3

5 8

std::list<int> numbers {1, 2, 3};                        // 1 2 3
std::list<int> values {2, 3, 4, 5, 6, 7, 8};             // 2 3 4 5 6 7 8
numbers.merge(values);                                   // 1 2 2 3 3 4 5 6 7 8

numbers.sort(std::greater<>());                          // 3 2 1
values.sort(std::greater<>());                           // 8 7 6 5 4 3 2
numbers.merge(values, std::greater<>());                 // 8 7 6 5 4 3 3 2 2 1

template<class _Arg, class _Result>
struct unary_function
{ // base class for unary functions
  typedef _Arg argument_type;
  typedef _Result result_type;
};

Using forward_list Containers

The forward_list header defines the forward_list<T> container template that implements a singly linked list of elements of type T, where each element contains a pointer to the next element. This means that, unlike a list<T> container, you can only traverse the elements forwards. Like the list<T> container, you cannot access an element by its position. The only way to access an element is to traverse the list from the beginning. Because the operations for a forward_list<T> container are similar to those for a list<T>, I’ll just highlight a few of them.

The front() member function returns a reference to the first element in the list as long as the list is not empty and the reference will be const if the container object is const. You can test whether or not the list is empty using the empty() member, which returns false as long as there is at least one element in the list. The remove() function removes the element that matches the object you supply as the argument. There’s also the remove_if() member for which you supply a predicate as an argument, which can be a function object or a lambda expression. All elements for which the predicate is true are removed.

Because it is a singly linked list, a forward_list<T> container only has forward iterators. You can use the global functions to obtain iterators such as begin() and end() with it, except for those that return reverse iterators.

You can add an element to a forward_list using either push_front() or emplace_front(). The emplace_front() function creates an object from the arguments that you supply and inserts it at the front of the list. The push_front() function inserts the object you supply as the argument at the front of the list.

For example:

std::forward_list<std::string> words;
std::string s1 {"first"};
words.push_front(s1);
words.emplace_front("second");
std::string s2 {"third"};
words.emplace_front(std::move(s2));
words.emplace_front("fourth");

After executing this fragment, words will contain:

fourth  third  second  first

A forward_list<T> container also has a before_begin() function that returns an iterator pointing to the position before the first element. This is for use with the insert_after() and emplace_after() member functions. You can insert one or more objects after a given position in the list using the insert_after() function. There are several versions of this. Here are some examples:

std::forward_list<int> datalist;
 
// Returns an iterator pointing to the inserted element, 11
auto iter = datalist.insert_after(datalist.before_begin(), 11); // 11
 
// Inserts 3 copies of the 3rd argument after iter and increments iter 
iter = datalist.insert_after(iter, 3, 15);                  // 11 15 15 15
 
// Insert a range following iter, and increments iter to point to 5  
int data[] {1, 2, 4, 5};
iter = datalist.insert_after(
                 iter, std::cbegin(data), std::cend(data)); // 11 15 15 15 1 2 4 5

iter will be of type forward_list<int>::iterator.

You can insert an element after a given position in the list using the emplace_after() function. The first argument is an iterator specifying the element after which the new element should be inserted. The second and subsequent arguments are passed to the constructor for the class type of the object to be inserted. For example:

  words.emplace_after(std::cbegin(words), "fifth");

After executing this statement with words as it was left by the previous fragment adding elements, the list will contain:

fourth  fifth  third  second  first

The function created a string("fifth") object and stored it following the position pointed to by the first argument.

A forward_list<T> container provides better performance than a list<T> container. Having only one link to maintain makes it faster in operation and there is no size member keeping track of the number of elements. If you need to know the number of elements, you can obtain it using the distance() function from the algorithm header:

  std::cout << "Size = " << std::distance(std::cbegin(words), std::cend(words));

The arguments are iterators specifying the first element and one past the last element to be counted.

Using Other Sequence Containers

The remaining sequence containers are implemented through container adapters that I introduced at the beginning of this chapter. I’ll discuss each of them briefly and illustrate their operation with examples.

std::queue<std::string> names;

std::queue<std::string, std::list<std::string>> names;

std::priority_queue<int> numbers;

numbers.push(99);                      // Add 99 to the queue

std::priority_queue<int, std::deque<int>, std::greater<>> numbers;

std::priority_queue<int, std::vector<int>, std::greater<>> numbers;

std::stack<Person> people;

std::stack<std::string, std::list<std::string>> names;

The tuple Class Template

The tuple<> class template that is defined in the tuple header is a useful adjunct to the array<> container, and to other sequence containers such as the vector<>. As its name suggests, a tuple<> object encapsulates a number of different items of different types. If you were working with fixed records from a file, or possibly from an SQL database, you could use a vector<> or an array<> container to store tuple<> objects that encapsulate the fields in a record. Let’s look at a specific example.

Suppose you are working with personnel records that contain an integer employee number, a first name, a second name, and the age of the individual in years. You could define an alias for a tuple<> instance to encapsulate an employee record like this:

using Record = std::tuple<int, std::string, std::string, int>;

An alias is very useful for reducing the verbosity of the type specification. The Record type name is the equivalent of a tuple<> that stores values of type int, string, string, and int, corresponding to a person’s ID, first name, second name, and age. You could now define an array<> container to store Record objects:

std::array<Record, 5> personnel { Record {1001, "Joan", "Jetson", 35},
                                  Record {1002, "Jim" , "Jones" , 26},
                                  Record {1003, "June", "Jello" , 31},
                                  Record {1004, "Jack", "Jester", 39} };

This defines the personnel container, which is an array that can store five Record objects. If you wanted flexibility in the number of tuples you were dealing with, you could use a vector<> or a list<>. Here, you initialize four of the five elements in personnel from the initializer list. Here’s how you might store a fifth element:

personnel[4] = Record {1005, "Jean", "Jorell", 29};

This uses the index operator to access the fifth element in the array container. You also have the option of creating a tuple<> object using the make_tuple() function template:

personnel[4] = std::make_tuple(1005, "Jean", "Jorell", 29);

The make_tuple() function creates a tuple<> instance that is equivalent to our Record type because the deduced type parameters are the same.

To access the fields in a tuple, you use the get() template function. The template parameter is the index position of the field you want, indexed from zero. The argument to the function is the tuple that you are accessing. Here’s how you could list the records in the personnel container:

std::cout << std::setiosflags(std::ios::left);      // Left align output
for (const auto& r : personnel)
{
  std::cout << std::setw(10) << std::get<0>(r) << std::setw(10) << std::get<1>(r)
            << std::setw(10) << std::get<2>(r) << std::setw(10) << std::get<3>(r)
            << std::endl;
}

You need to include iomanip to compile this fragment. This outputs the fields in each tuple in personnel on a single line, with the fields left-justified in a field width of 10 characters, so it looks tidy. Note that the type parameter to the get() function template must be a compile-time constant. This implies that you cannot use a loop index variable as the type parameter, so you can’t iterate over the fields in a loop at runtime. It is helpful to define some integer constants that you can use to identify the fields in a tuple in a more readable way. For example, you could define the following constants:

const size_t ID {}, firstname {1}, secondname {2}, age {3};

Now you can use these variables as type parameters in get() function instantiations making it much clearer which field you are retrieving:

for (const auto& r : personnel))
{
  std::cout << std::setw(10) << std::get<ID>(r) 
            << std::setw(10) << std::get<firstname>(r)
            << std::setw(10) << std::get<secondname>(r)
            << std::setw(10) << std::get<age>(r) << std::endl;
}

Let’s put some of the fragments together into something you can compile and run.

Using Map Containers

When you create a map<K,T> container, K is the type of key you use to store an object of type T. Key/object pairs are stored as objects of type pair<K,T> that is defined in the utility header. The utility header is included into the map header so this type definition is automatically available. Here’s an example of creating a map:

std::map<Person, std::string> phonebook;

This defines an empty map container that stores entries that are key/object pairs, with keys of type Person and objects of type string.

You can also create a map that is initialized with a sequence of pair<K,T> objects from another container:

std::map<Person, std::string> phonebook {iter1, iter2};

iter1 and iter2 are a pair of iterators defining a series of key/object pairs from another container in the usual way, with iter2 specifying a position one past the last pair to be included in the sequence. These iterators can be input iterators although the iterators you obtain from a map are bidirectional. You obtain iterators to access the contents of a map using the begin() and end() functions, just as you would for a sequence container.

The entries in a map are ordered based on a function object of type less<Key> by default, so they will be stored in ascending key sequence. You can change the type function object used for ordering entries by supplying a third template type parameter. For example:

std::map<Person, std::string, std::greater<>> phonebook;

This map stores entries that are Person/string pairs, where Person is the key with an associated string object. The ordering of entries will be determined by a function object of type greater<>, so the entries will be in descending key sequence.

auto entry = std::pair<Person, std::string>
                                {Person {"Mel", "Gibson"}, "213 345 5678"};

auto entry = std::make_pair(Person {"Nell", "Gwynne"}, "213 345 5678");

using Entry = std::pair<Person, std::string> ;

Entry entry1 {Person {"Jack", "Jones"}, "213 567 1234"};

phonebook.insert(entry1);

auto checkpair = phonebook.insert(entry1);
if(checkpair.second)
  std::cout << "Insertion succeeded." << std::endl;
else
  std::cout << "Insertion failed." << std::endl;

std::cout << "The key for the entry is:" << std::endl;
checkpair.first->first.showPerson();

phonebook[Person {"Jack", "Jones"}] = "213 567 1234";

Entry him {Person {"Jack", "Spratt"}, "213 456 7899"};
auto checkpair = phonebook.emplace(std::move(him));

auto checkpair = phonebook.emplace(Person {"Jack", "Spratt"}, "213 456 7899");

string number {phonebook[Person{"Jack", "Jones"}]};

std::string number;
Person key {"Jack", "Jones"};
auto iter = phonebook.find(key);
        
if(iter != phonebook.end())
{
  number = iter->second;
  std::cout << "The number is " << number << std::endl;
}
else
{
  std::cout << "No number for the key ";
  key.showPerson();
}

Person key {"Jack", "Jones"};
auto count = phonebook.erase(key);
if(!count)
  std::cout << "Entry was not found." << std::endl;

Person key {"Jack", "Jones"};
auto iter = phonebook.find(key);
if(iter != phonebook.end())
  iter = phonebook.erase(iter);
if(iter == phonebook.end())
  std::cout << "End of the map reached." << std::endl;

Using a Multimap Container

A multimap works very much like the map container, in that it supports the same range of functions — except for the subscript operator, which you cannot use with a multimap. The principle difference between a map and a multimap is that you can have multiple entries with the same key in a multimap, and this affects the way some of the functions behave. Obviously, with the possibility of several keys having the same value, overloading operator[]() would not make much sense.

The insert() function flavors for a multimap are a little different from those for a map. The simplest version accepts a pair<K,T> object as an argument and returns an iterator pointing to the entry that was inserted. The equivalent function for a map returns a pair object because this provides an indication of when the key already exists in the map and the insertion is not possible; of course, this cannot arise with a multimap. A multimap also has a version of insert() with two arguments: the second being the pair object to be inserted, and the first being an iterator pointing to the position from which to start searching for an insertion point. This gives you some control over where a pair is inserted when the same key already exists. This version of insert() also returns an iterator pointing to the element that was inserted. A third version of insert() accepts two iterator arguments that specify a range of elements to be inserted from another source and this version doesn’t return anything.

When you pass a key to erase()for a multimap, it erases all entries with the same key, and the value returned indicates how many were deleted. The significance of having a version of erase()that accepts an iterator as an argument should now be apparent — it allows you to delete a single element. You also have a version of erase() that accepts two iterators to delete a range of entries.

The find() member function can only find the first element with a given key. You really need a way to find several elements with the same key and the lower_bound(), upper_bound(), and equal_range() functions provide you with a way to do this. For example, given a phonebook object that is of type multimap<Person, string>, you could list the phone numbers corresponding to a given key like this:

Person person("Jack", "Jones");
auto iter = phonebook.lower_bound(person);
if(iter == phonebook.end())
  std::cout << "There are no entries for " << person.getName() << std::endl;
else
{
  std::cout << "The following numbers are listed for " << person.getName()
            << ":" << std::endl;
  auto upper = phonebook.upper_bound(person);
  for (; iter != upper; ++iter)
    std::cout << iter->second << std::endl;
}

It’s important to check the iterator returned by lower_bound(). If you don’t, you could end up referencing an entry one beyond the last entry.

Using Input Stream Iterators

Here’s an example of how you create an input stream iterator:

std::istream_iterator<int> numbersInput {std::cin};

This creates the iterator numbersInput of type istream_iterator<int> that can point to objects of type int in a stream. The argument to the constructor specifies the stream to which the iterator relates, so this is an iterator that can read integers from cin, the standard input stream.

The default istream_iterator<T> constructor creates an end-of-stream iterator, which will be equivalent to the end iterator for a container that you have been obtaining by calling the end() function. Here’s how you could create an end-of-stream iterator, complementing the numbersInput iterator:

std::istream_iterator<int> numbersEnd;

Now you have a pair of iterators that defines a sequence of values of type int from cin. You could use these to load values from cin into a vector<int> container:

std::vector<int> numbers;
std::cout << "Enter integers separated by spaces then a letter to end:" 
          << std::endl;
std::istream_iterator<int> numbersInput {std::cin}, numbersEnd;
while(numbersInput != numbersEnd)
  numbers.push_back(*numbersInput++);

After defining the vector container to hold values of type int, you create two input stream iterators: numbersInput is an input stream iterator reading values of type int from cin, and numbersEnd is an end-of-stream iterator. The while loop continues as long as numbersInput is not equal to the end-of-stream iterator, numbersEnd. When you execute this fragment, input continues until end-of-stream is recognized for cin. But what produces that condition? The end-of-stream condition will arise if you enter Ctrl+Z to close the input stream, or if you enter an invalid character such as a letter.

Of course, you are not limited to using input stream iterators as loop control variables. You can use them to pass data to an algorithm, such as accumulate(), which is defined in the numeric header:

std::cout << "Enter integers separated by spaces then a letter to end:"
          << std::endl;
std::istream_iterator<int> numbersInput {std::cin}, numbersEnd;
std::cout << "The sum of the input values that you entered is "
          << std::accumulate(numbersInput, numbersEnd, 0) << std::endl;

This fragment outputs the sum of however many integers you enter. You will recall that the arguments to accumulate() are an iterator pointing to the first value in the sequence, an iterator pointing to one past the last value, and the initial value for the sum. Here, you are transferring data directly from cin to the algorithm.

The sstream header defines the basic_istringstream<T> template that defines an object type that can access data from a stream buffer such as a string object. The header also defines the istringstream type as basic_istringstream<char>, which will be a stream of characters of type char. You can construct an istringstream object from a string object, which means you can read data from the string object, just as you read from cin. Because an istringstream object is a stream, you can pass it to an input iterator constructor and use the iterator to access the data in the underlying stream buffer. Here’s an example:

std::string data {"2.4 2.5 3.6 2.1 6.7 6.8 94 95 1.1 1.4 32"};
std::istringstream input {data};
std::istream_iterator<double> begin(input), end;
std::cout << "The sum of the values from the data string is "
          << std::accumulate(begin, end, 0.0) << std::endl;

You create the istringstream object, input, from the string object, data, so you can read from data as a stream. You create two stream iterators that can access double values in the input stream, and you use these to pass the contents of the input stream to the accumulate() algorithm. Note that the type of the third argument to the accumulate() function determines the type of the result, so you must specify this as a value of type double to get the sum produced correctly. Let’s try an example.

Using Inserter Iterators

An inserter iterator can add new elements to the sequence containers vector<T>, deque<T>, and list<T>. There are three templates that create inserter iterators defined in the iterator header:

• back_insert_iterator<T> — Inserts elements at the end of a container of type T. The container must provide the push_back() member function for this to work.
• front_insert_iterator<T> — Inserts elements at the beginning of a container of type T. This depends on push_front() being available for the container so it won’t work with a vector.
• insert_iterator<T> — Inserts elements starting at a specified position within a container of type T. The container must have an insert()member function that accepts an iterator as the first argument, and an item to be inserted as the second argument. This also works with sorted/ordered associative containers because they satisfy the requirements.

The constructors for the first two inserter iterator types expect a single argument specifying the container. For example:

std::list<int> numbers;
std::front_insert_iterator<std::list<int>> iter {numbers};

Here, you create an iterator that can insert data at the beginning of the list<int> container numbers.

Inserting a value into the container is very simple:

*iter = 99;                  // Insert 99 at the front of the numbers container

You could also use front_inserter() with the numbers container, like this:

std::front_inserter (numbers) = 99;

This creates a front inserter for the numbers list and uses it to insert 99 at the beginning of the list. The argument to front_inserter() is the container to which the iterator is to be applied.

The constructor for an insert_iterator<T> iterator requires two arguments:

std::vector<int> values;
std::insert_iterator<std::vector<int>> iter_anywhere {values, std::begin(values)};

The second argument is an iterator specifying where data is to be inserted — the start of the sequence in this instance. You can use this iterator in exactly the same way as the previous one. Here’s how you could insert a series of values into the vector using this iterator:

for(int i {}; i < 100; i++)
  *iter_anywhere = i + 1;

This loop inserts the integers 1 to 100 in the values container at the beginning. After executing this, the first 100 elements will be 1, 2, and so on, through to 100.

You could also use inserter() to insert the elements in reverse order:

for(int i {}; i < 100; i++)
  std::inserter(values, std::begin(values)) = i + 1;

The first argument to inserter() is the container, and the second is an iterator identifying the position where data is to be inserted. The values will be in reverse order from 100 down to 1.

The inserter iterators can be used in conjunction with the copy() algorithm in a particularly useful way. Here’s how you could read values from cin and transfer them to a list<T> container:

std::list<double> values;
std::cout << "Enter a series of values separated by spaces"
          << " followed by Ctrl+Z or a letter to end:" << std::endl;
std::istream_iterator<double> input {std::cin}, input_end;
std::copy(input, input_end, std::back_inserter<std::list<double>> {values});

You first create a list container that stores double values. After prompting for input, you create two input stream iterators for double values. The first iterator points to cin, and the second is an end-of-stream iterator created by the default constructor. You specify the input to the copy() algorithm with the two iterators; the destination for the copy operation is a back inserter iterator that you create in the third argument to the copy() function. The back inserter iterator adds the data transferred by the copy operation to the list container, values. This is quite powerful stuff. If you ignore the prompt, in two statements you read an arbitrary number of values from the standard input stream and transfer them to a list container.

Using Output Stream Iterators

Complementing the input stream iterator template, the ostream_iterator<T> template provides output stream iterators for writing objects of type T to an output stream. There are two constructors for output stream iterators. One creates an iterator that transfers data to the destination stream:

std::ostream_iterator<int> out {std::cout};

The template type argument, int, specifies the type of data to be handled, while the constructor argument, cout, specifies the stream that will be the destination for data, so the out iterator can write values of type int to the standard output stream. Here’s how you might use this iterator:

   int data[] {1, 2, 3, 4, 5, 6, 7, 8, 9};
   std::copy(std::cbegin(data), std::cend(data), out);

The copy() algorithm that is defined in the algorithm header copies the sequence of objects specified by the first two iterator arguments to the output iterator specified by the third argument. Here, the function copies the elements from the data array to the out iterator, which will write the elements to cout. The result of executing this fragment will be:

123456789

As you can see, the values are written to the output stream with no spaces in between. The second constructor can improve on this:

std::ostream_iterator<int> out{std::cout, ", "};

The second argument is a string to be used as a delimiter for output values. If you use this iterator as the third argument to the copy() function in the previous fragment, the output will be:

1, 2, 3, 4, 5, 6, 7, 8, 9,

The delimiter string that you specify as a second constructor argument is written to the stream following each value.

Let’s see how an output stream iterator works in practice.

The Capture Clause

The lambda introducer can contain a capture clause that determines how the body of the lambda can access variables in the enclosing scope. In the previous section, the lambda expression had nothing between the square brackets, indicating that no variables in the enclosing scope can be accessed within the body of the lambda. A lambda that does not access anything from the enclosing scope is called a stateless lambda.

The first possibility is to specify a default capture clause that applies to all variables in the enclosing scope. You have two options for this. If you place = between the square brackets, the body has access to all automatic variables in the enclosing scope by value — that is, the values of the variables are made available within the lambda expression, but the original variables cannot be changed. If you put & between the square brackets, all the variables in the enclosing scope are accessible by reference, and therefore can be changed by the code in the body of the lambda. Look at this code fragment:

double factor {5.0};
double values[] { 2.5, -3.5, 4.5, -5.5, 6.5, -7.5};
std::vector<double> cubes(_countof(values));
std::transform(std::begin(values), std::end(values), std::begin(cubes),
                                         [=](double x){ return factor*x*x*x;} );

In this fragment, the = capture clause allows all the variables in scope to be accessible by value from within the body of the lambda. Note that this is not quite the same as passing arguments by value. The value of the variable factor is available within the lambda, but you cannot update the copy of factor because it is effectively const. The following statement will not compile, for example:

std::transform(std::begin(values), std::end(values),std::begin(cubes),
           [=](double x)  { factor += 10.0;          // Not allowed!
                            return factor*x*x*x;} );

If you want to modify the temporary copy of a variable in scope from within the lambda, adding the mutable keyword will enable this:

std::transform(std::begin(values), std::end(values),std::begin(cubes),
           [=](double x)mutable { factor += 10.0;          // OK
                                   return factor*x*x*x;} );

Now you can modify the copy of any variable within the enclosing scope without changing the original variable. After executing this statement, the value of factor will still be 5.0. The lambda remembers the local value of factor from one call to the next, so for the first element factor will be 5 + 10 = 15, for the second element it will be 15 + 10 = 25, and so on.

If you want to change the original value of factor from within the lambda, just use & as the capture clause:

std::transform(std::begin(values), std::end(values),std::begin(cubes),
             [&](double x){ factor += 10.0;   // Changes original variable
                            return factor*x*x*x;} );
std::cout << "factor = " << factor << std::endl;

You don’t need the mutable keyword here. All variables within the enclosing scope are available by reference, so you can use and alter their values. The result of executing this will be that factor is 65. If you thought it was going to be 15.0, remember that the lambda expression executes once for each element in data, and the cubes of the elements will be multiplied by successive values of factor from 15.0 to 65.0.

Capturing Specific Variables

You can explicitly identify the variables in the enclosing scope that you want to access. You could rewrite the previous transform() statement as:

std::transform(std::begin(values), std::end(values),std::begin(cubes),
      [&factor](double x) { factor += 10.0;    // Changes original variable
                            return factor*x*x*x;} );

Now, factor is the only variable from the enclosing scope that is accessible, and it is available by reference. If you omit the &, factor would be available by value and not updatable. If you want to identify several variables in the capture clause, just separate them with commas. You could include = in the capture clause list, as well as explicit variable names. For example, with the capture clause [=,&factor] the lambda would have access to factor by reference and all other variables in the enclosing scope by value. Conversely, putting [&,factor] as the capture clause would capture factor by value and all other variables by reference. Note that in a function member of a class, you can include the this pointer in the capture clause for a lambda expression, which allows access to the other functions and data members that belong to the class.

A lambda expression can also include a throw() exception specification that indicates that the lambda does not throw exceptions. Here’s an example:

std::transform(std::begin(values), std::end(values),std::begin(cubes),
      [&factor](double x)throw() { factor += 10.0;
                                   return factor*x*x*x;} );

If you want to include the mutable specification, as well as the throw() specification, the mutable keyword must precede throw() and must be separated from it by one or more spaces.

Templates and Lambda Expressions

You can use a lambda expression inside a template. Here’s an example of a function template that uses a lambda expression:

template <class T>
T average(const vector<T>& vec)
{
  static_assert(std::is_arithmetic<T>::value,
                            "Type parameter for average() must be arithmetic.");
  T sum {};
  std::for_each(std::cbegin(vec), std::cend(vec),
    [&sum](const T& value){ sum += value; });
  return sum/vec.size();
}

This template generates functions for calculating the average of a set of numerical values stored in a vector. The algorithm header defines for_each(). The lambda expression uses the template type parameter in the lambda parameter specification, and accumulates the sum of all the elements in a vector. The sum variable is accessed from the lambda by reference, so it is able to accumulate the sum there. The last line of the function returns the average, which is calculated by dividing sum by the number of elements in the vector. Let’s try an example.

Naming a Lambda Expression

You can assign a stateless lambda — one that does not reference anything in an external scope — to a variable that is a function pointer, thus giving the lambda a name. You can then use the function pointer to call the lambda as many times as you like. For example:

  auto sum = [](int a,int b){return a+b; };

The function pointer, sum, points to the lambda expression, so you can use it as many times as you like:

  std::cout << "5 + 10 equals " << sum(5,10) << std::endl;
  std::cout << "15 + 16 equals " << sum(15,16) << std::endl;

This is quite useful, but there’s a much more powerful capability. An extension to the functional header defines the function<> class template that you can use to define a wrapper for a function object; this includes a lambda expression. The function<> template is referred to as a polymorphic function wrapper because an instance of the template can wrap a variety of function objects with a given parameter list and return type. I won’t discuss all the details of the function<> class template, but I’ll just show how you can use it to wrap a lambda expression. Using the function<> template to wrap a lambda effectively gives a name to the lambda, which not only provides the possibility of recursion within a lambda expression, it also allows you to use the lambda in multiple statements or pass it to several different functions. The same function wrapper could also wrap different lambda expressions at different times.

To create a wrapper object from the function<> template you need to supply information about the return type, and the types of any parameters, to a lambda expression. Here’s how you could create an object of type function that can wrap a function object that has one parameter of type double and returns a value of type int:

std::function<int(double)> f = [](double x)->int{ return static_cast<int>(x*x); };

The type specification for the function template is the return type for the function object to be wrapped, followed by its parameter types between parentheses, and separated by commas. Let’s try a working example that uses the basic capability that is built into the C++ language as well as the function<T> template.

EXERCISES

1. Write a program that will read some text from the standard input stream, possibly involving several lines of input, and store the letters from the text in a list<T> container. Sort the letters in ascending sequence and output them.
2. Use a priority_queue<T> container to achieve the same result as in Exercise 1.
3. Modify Ex10_12.cpp so that it allows multiple phone numbers to be stored for a given name. The functionality in the program should reflect this: The getEntry() function should display all numbers for a given name, and the deleteEntry() function should delete a particular person/number combination.
4. Write a program to implement a phone book capability that will allow a name to be entered to retrieve one or more numbers, or a number to be entered to retrieve a name.
5. As you know, the Fibonacci series consists of the sequence of integers 0, 1, 1, 2, 3, 5, 8, 13, 21, ... where each integer after the first two is the sum of the two preceding integers (note the series sometimes omits the initial zero). Write a program that uses a lambda expression to initialize a vector of integers with values from the Fibonacci series.

WHAT YOU LEARNED IN THIS CHAPTER