9.2. Container Library Overview

The operations on the container types form a kind of hierarchy:

• Some operations (Table 9.2 (p. 330)) are provided by all container types.

Table 9.2. Container Operations

 

 

• Other operations are specific to the sequential (Table 9.3 (p. 335)), the associative (Table 11.7 (p. 438)), or the unordered (Table 11.8 (p. 445)) containers.

Table 9.3. Defining and Initializing Containers

 

• Still others are common to only a smaller subset of the containers.

 

In this section, we’ll cover aspects common to all of the containers. The remainder of this chapter will then focus solely on sequential containers; we’ll cover operations specific to the associative containers in Chapter 11.

In general, each container is defined in a header file with the same name as the type. That is, deque is in the deque header, list in the list header, and so on. The containers are class templates (§ 3.3, p. 96). As with vectors, we must supply additional information to generate a particular container type. For most, but not all, of the containers, the information we must supply is the element type:

list<Sales_data>   // list that holds Sales_data objects
deque<double>      // deque that holds doubles

Constraints on Types That a Container Can Hold

Almost any type can be used as the element type of a sequential container. In particular, we can define a container whose element type is itself another container. We define such containers exactly as we do any other container type: We specify the element type (which in this case is a container type) inside angle brackets:

vector<vector<string>> lines;      // vector of vectors

Here lines is a vector whose elements are vectors of strings.

As an example, the sequential container constructor that takes a size argument (§ 3.3.1, p. 98) uses the element type’s default constructor. Some classes do not have a default constructor. We can define a container that holds objects of such types, but we cannot construct such containers using only an element count:

// assume noDefault is a type without a default constructor
vector<noDefault> v1(10, init); // ok: element initializer supplied
vector<noDefault> v2(10);       // error: must supply an element initializer

As we describe the container operations, we’ll note the additional constraints, if any, that each container operation places on the element type.

9.2.1. Iterators

As with the containers, iterators have a common interface: If an iterator provides an operation, then the operation is supported in the same way for each iterator that supplies that operation. For example, all the iterators on the standard container types let us access an element from a container, and they all do so by providing the dereference operator. Similarly, the iterators for the library containers all define the increment operator to move from one element to the next.

 

With one exception, the container iterators support all the operations listed in Table 3.6 (p. 107). The exception is that the forward_list iterators do not support the decrement (--) operator. The iterator arithmetic operations listed in Table 3.7 (p. 111) apply only to iterators for string, vector, deque, and array. We cannot use these operations on iterators for any of the other container types.

Iterator Ranges

An iterator range is denoted by a pair of iterators each of which refers to an element, or to one past the last element, in the same container. These two iterators, often referred to as begin and end—or (somewhat misleadingly) as first and last—mark a range of elements from the container.

The name last, although commonly used, is a bit misleading, because the second iterator never refers to the last element of the range. Instead, it refers to a point one past the last element. The elements in the range include the element denoted by first and every element from first up to but not including last.

This element range is called a left-inclusive interval. The standard mathematical notation for such a range is

[ begin, end)

indicating that the range begins with begin and ends with, but does not include, end. The iterators begin and end must refer to the same container. The iterator end may be equal to begin but must not refer to an element before the one denoted by begin.

Programming Implications of Using Left-Inclusive Ranges

Each container defines several types, shown in Table 9.2 (p. 330). We have already used three of these container-defined types: size_type (§ 3.2.2, p. 88), iterator, and const_iterator (§ 3.4.1, p. 108).

In addition to the iterator types we’ve already used, most containers provide reverse iterators. Briefly, a reverse iterator is an iterator that goes backward through a container and inverts the meaning of the iterator operations. For example, saying ++ on a reverse iterator yields the previous element. We’ll have more to say about reverse iterators in § 10.4.3 (p. 407).

The remaining type aliases let us use the type of the elements stored in a container without knowing what that type is. If we need the element type, we refer to the container’s value_type. If we need a reference to that type, we use reference or const_reference. These element-related type aliases are most useful in generic programs, which we’ll cover in Chapter 16.

To use one of these types, we must name the class of which they are a member:

// iter is the iterator type defined by list<string>
list<string>::iterator iter;
// count is the difference_type type defined by vector<int>
vector<int>::difference_type count;

These declarations use the scope operator (§ 1.2, p. 8) to say that we want the iterator member of the list<string> class and the difference_type defined by vector<int>, respectively.

9.2.3. begin and end Members

 

The begin and end operations (§ 3.4.1, p. 106) yield iterators that refer to the first and one past the last element in the container. These iterators are most often used to form an iterator range that encompasses all the elements in the container.

As shown in Table 9.2 (p. 330), there are several versions of begin and end: The versions with an r return reverse iterators (which we cover in § 10.4.3 (p. 407)). Those that start with a c return the const version of the related iterator:

list<string> a = {"Milton", "Shakespeare", "Austen"};
auto it1 = a.begin();  // list<string>::iterator
auto it2 = a.rbegin(); // list<string>::reverse_iterator
auto it3 = a.cbegin(); // list<string>::const_iterator
auto it4 = a.crbegin();// list<string>::const_reverse_iterator

The functions that do not begin with a c are overloaded. That is, there are actually two members named begin. One is a const member (§ 7.1.2, p. 258) that returns the container’s const_iterator type. The other is nonconst and returns the container’s iterator type. Similarly for rbegin, end, and rend. When we call one of these members on a nonconst object, we get the version that returns iterator. We get a const version of the iterators only when we call these functions on a const object. As with pointers and references to const, we can convert a plain iterator to the corresponding const_iterator, but not vice versa.

The c versions were introduced by the new standard to support using auto with begin and end functions (§ 2.5.2, p. 68). In the past, we had no choice but to say which type of iterator we want:

// type is explicitly specified
list<string>::iterator it5 = a.begin();
list<string>::const_iterator it6 = a.begin();
// iterator or const_iterator depending on a's type of a
auto it7 = a.begin();  // const_iterator only if a is const
auto it8 = a.cbegin(); // it8 is const_iterator

When we use auto with begin or end, the iterator type we get depends on the container type. How we intend to use the iterator is irrelevant. The c versions let us get a const_iterator regardless of the type of the container.

9.2.4. Defining and Initializing a Container

 

Every container type defines a default constructor (§ 7.1.4, p. 263). With the exception of array, the default constructor creates an empty container of the specified type. Again excepting array, the other constructors take arguments that specify the size of the container and initial values for the elements.

Initializing a Container as a Copy of Another Container

There are two ways to create a new container as a copy of another one: We can directly copy the container, or (excepting array) we can copy a range of elements denoted by a pair of iterators.

To create a container as a copy of another container, the container and element types must match. When we pass iterators, there is no requirement that the container types be identical. Moreover, the element types in the new and original containers can differ as long as it is possible to convert (§ 4.11, p. 159) the elements we’re copying to the element type of the container we are initializing:

// each container has three elements, initialized from the given initializers
list<string> authors = {"Milton", "Shakespeare", "Austen"};
vector<const char*> articles = {"a", "an", "the"};
list<string> list2(authors);     // ok: types match
deque<string> authList(authors); // error: container types don't match
vector<string> words(articles);  // error: element types must match
// ok: converts const char* elements to string
forward_list<string> words(articles.begin(), articles.end());

List Initialization

Under the new standard, we can list initialize (§ 3.3.1, p. 98) a container:

// each container has three elements, initialized from the given initializers
list<string> authors = {"Milton", "Shakespeare", "Austen"};
vector<const char*> articles = {"a", "an", "the"};

When we do so, we explicitly specify values for each element in the container. For types other than array, the initializer list also implicitly specifies the size of the container: The container will have as many elements as there are initializers.

Sequential Container Size-Related Constructors

In addition to the constructors that sequential containers have in common with associative containers, we can also initialize the sequential containers (other than array) from a size and an (optional) element initializer. If we do not supply an element initializer, the library creates a value-initialized one for us § 3.3.1 (p. 98):

vector<int> ivec(10, -1);        // ten int elements, each initialized to -1
list<string> svec(10, "hi!");    // ten strings; each element is  "hi!"
forward_list<int> ivec(10);      // ten elements, each initialized to 0
deque<string> svec(10);          // ten elements, each an empty string

We can use the constructor that takes a size argument if the element type is a built-in type or a class type that has a default constructor (§ 9.2, p. 329). If the element type does not have a default constructor, then we must specify an explicit element initializer along with the size.

The fixed-size nature of arrays also affects the behavior of the constructors that array does define. Unlike the other containers, a default-constructed array is not empty: It has as many elements as its size. These elements are default initialized (§ 2.2.1, p. 43) just as are elements in a built-in array (§ 3.5.1, p. 114). If we list initialize the array, the number of the initializers must be equal to or less than the size of the array. If there are fewer initializers than the size of the array, the initializers are used for the first elements and any remaining elements are value initialized (§ 3.3.1, p. 98). In both cases, if the element type is a class type, the class must have a default constructor in order to permit value initialization:

array<int, 10> ia1;  // ten default-initialized ints
array<int, 10> ia2 = {0,1,2,3,4,5,6,7,8,9};  // list initialization
array<int, 10> ia3 = {42};  // ia3[0] is 42, remaining elements are 0

It is worth noting that although we cannot copy or assign objects of built-in array types (§ 3.5.1, p. 114), there is no such restriction on array:

int digs[10] = {0,1,2,3,4,5,6,7,8,9};
int cpy[10] = digs;  // error: no copy or assignment for built-in arrays
array<int, 10> digits = {0,1,2,3,4,5,6,7,8,9};
array<int, 10> copy = digits;  // ok: so long as array types match

As with any container, the initializer must have the same type as the container we are creating. For arrays, the element type and the size must be the same, because the size of an array is part of its type.

The assignment-related operators, listed in Table 9.4 (overleaf) act on the entire container. The assignment operator replaces the entire range of elements in the left-hand container with copies of the elements from the right-hand operand:

c1 = c2;      // replace the contents of c1 with a copy of the elements in c2
c1 = {a,b,c}; // after the assignment c1 has size 3

Table 9.4. Container Assignment Operations

 

After the first assignment, the left- and right-hand containers are equal. If the containers had been of unequal size, after the assignment both containers would have the size of the right-hand operand. After the second assignment, the size of c1 is 3, which is the number of values provided in the braced list.

 

Unlike built-in arrays, the library array type does allow assignment. The left-and right-hand operands must have the same type:

The call to assign replaces the elements in names with copies of the elements in the range denoted by the iterators. The arguments to assign determine how many elements and what values the container will have.

9.2.6. Container Size Operations

 

With one exception, the container types have three size-related operations. The size member (§ 3.2.2, p. 87) returns the number of elements in the container; empty returns a bool that is true if size is zero and false otherwise; and max_size returns a number that is greater than or equal to the number of elements a container of that type can contain. For reasons we’ll explain in the next section, forward_list provides max_size and empty, but not size.

9.2.7. Relational Operators

Every container type supports the equality operators (== and !=); all the containers except the unordered associative containers also support the relational operators (>, >=, <, <=). The right- and left-hand operands must be the same kind of container and must hold elements of the same type. That is, we can compare a vector<int> only with another vector<int>. We cannot compare a vector<int> with a list<int> or a vector<double>.

Comparing two containers performs a pairwise comparison of the elements. These operators work similarly to the string relationals (§ 3.2.2, p. 88):

• If both containers are the same size and all the elements are equal, then the two containers are equal; otherwise, they are unequal.

• If the containers have different sizes but every element of the smaller one is equal to the corresponding element of the larger one, then the smaller one is less than the other.

• If neither container is an initial subsequence of the other, then the comparison depends on comparing the first unequal elements.

The following examples illustrate how these operators work:

vector<int> v1 = { 1, 3, 5, 7, 9, 12 };
vector<int> v2 = { 1, 3, 9 };
vector<int> v3 = { 1, 3, 5, 7 };
vector<int> v4 = { 1, 3, 5, 7, 9, 12 };
v1 < v2  // true; v1 and v2 differ at element [2]: v1[2] is less than v2[2]
v1 < v3  // false; all elements are equal, but v3 has fewer of them;
v1 == v4 // true; each element is equal and v1 and v4 have the same size()
v1 == v2 // false; v2 has fewer elements than v1

Relational Operators Use Their Element’s Relational Operator

The container equality operators use the element’s == operator, and the relational operators use the element’s < operator. If the element type doesn’t support the required operator, then we cannot use the corresponding operations on containers holding that type. For example, the Sales_data type that we defined in Chapter 7 does not define either the == or the < operation. Therefore, we cannot compare two containers that hold Sales_data elements:

vector<Sales_data> storeA, storeB;
if (storeA < storeB) // error: Sales_data has no less-than operator