9.2. Container Library Overview

Fundamental

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

Type Aliases

Type Alias	Description
iterator	Type of the iterator for this container type
const_iterator	Iterator type that can read but not change its elements
size_type	Unsigned integral type big enough to hold the size of the largest possible container of this container type
difference_type	Signed integral type big enough to hold the distance between two iterators
value_type	Element type
reference	Element’s lvalue type; synonym for value_type&
const_reference	Element's const lvalue type (i.e., const value_type&)

Construction

Code	Description
C c;	Default constructor, empty container (array; see p. 336)
C c1(c2);	Construct c1 as a copy of c2
C c(b, e);	Copy elements from the range denoted by iterators b and e; (not valid for array)
C c(a, b, c);	List initialize c

Assignment and swap

Code	Description
c1 = c2	Replace elements in c1 with those in c2
c1 = {a, b, c, ...}	Replace elements in c1 with those in the list (not valid for array)
a.swap(p)	Swap elements in a with those in b
swap(a, b)	Equivalent to a.swap(b)

Size

Code	Description
c.size()	Number of clements in c (not valid for forward_list)
c.maxsize()	Maximum number of elements c can hold
c.empty()	false if c has any elements, true otherwise

Add/Remove Elements (not valid for array)

Note: the interface to these operations varies by container type

Code	Description
c.insert(args)	Copy element(s) as specified by args into c
c.emplace(inits)	Use inits to construct an element in c
c.erase(args)	Remove element(s) specified by args
c.clear()	Remove all elements from c; returns void

Equality and Relational Operators

Operators	Description
== !=	Equality valid for all container types
< <= > >=	Relationals (not valid for unordered associative containers)

Obtain Iterators

Code	Description
c.begin() c.end()	Return iterator to the first, one past the last element in c
c.cbegin() c.cend()	Return const_iterator

Additional Members of Reversible Containers (not valid for forward_list)

Code	Description
reverse_iterator	Iterator that addresses elements in reverse order
const_reverse_iterator	Reverse iterator that cannot write the elements
c.rbegin() c.rend()	Return iterator to the last, one past the first element in c
c.crbegin() c.crend()	Return const_reverse_iterator

• 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

Code	Description
C c;	Default constructor. If C is array, then the elements in c are default-initialized; otherwise c is empty.
C c1(c2) C c1 = c2	c1 is a copy of c2. c1 and c2 must have the same type (i.e., they must be the same container type and hold the same element type; for array must also have the same size).
C c(a, b, c, ...) C c = {a, b, c, ...}	c is a copy of the elements in the initializer list. Type of elements in the list must be compatible with the element type of C. For array, the list must have same number or fewer elements than the size of the array, any missing clements are value-initialized (§ 3.3.1, p. 98).
C c(b, e)	c is a copy of the elements in the range denoted by iterators b and e. Type of the elements must be compatible with the element type of C. (Not valid for array.)

Constructors that take a size are valid for sequential containers (not including array) only

Code	Description
C seq(n)	seq has n value-initialized elements; this constructor is explicit (§ 7.5.4, p. 296). (Not valid for string.)
C seq(n, t)	seq has n elements with value t.

• 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.

C++11

INFO

Older compilers may require a space between the angle brackets, for example, vector<vector<string> >.

Although we can store almost any type in a container, some container operations impose requirements of their own on the element type. We can define a container for a type that does not support an operation-specific requirement, but we can use an operation only if the element type meets that operation’s requirements.

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.

INFO

Exercises Section 9.2

Exercise 9.2: Define a list that holds elements that are deques that hold ints.

9.2.1. Iterators

Fundamental

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

INFO

The concept of an iterator range is fundamental to the standard library.

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.

INFO

Requirements on Iterators Forming an Iterator Range

Two iterators, begin and end, form an iterator range, if

• They refer to elements of, or one past the end of, the same container, and
• It is possible to reach end by repeatedly incrementing begin. In other words, end must not precede begin.

WARNING

The compiler cannot enforce these requirements. It is up to us to ensure that our programs follow these conventions.

Programming Implications of Using Left-Inclusive Ranges

The library uses left-inclusive ranges because such ranges have three convenient properties. Assuming begin and end denote a valid iterator range, then

• If begin equals end, the range is empty
• If begin is not equal to end, there is at least one element in the range, and begin refers to the first element in that range
• We can increment begin some number of times until begin == end

These properties mean that we can safely write loops such as the following to process a range of elements:

while (begin != end) {
    *begin = val;     // ok: range isn't empty so begin denotes an element
    ++begin;          // advance the iterator to get the next element
}

Given that begin and end form a valid iterator range, we know that if begin == end, then the range is empty. In this case, we exit the loop. If the range is nonempty, we know that begin refers to an element in this nonempty range. Therefore, inside the body of the while, we know that it is safe to dereference begin because begin must refer to an element. Finally, because the loop body increments begin, we also know the loop will eventually terminate.

INFO

Exercises Section 9.2.1

Exercise 9.3: What are the constraints on the iterators that form iterator ranges?

Exercise 9.4: Write a function that takes a pair of iterators to a vector<int> and an int value. Look for that value in the range and return a bool indicating whether it was found.

Exercise 9.5: Rewrite the previous program to return an iterator to the requested element. Note that the program must handle the case where the element is not found.

Exercise 9.6: What is wrong with the following program? How might you correct it?

list<int> lst1;
list<int>::iterator iter1 = lst1.begin(),
                    iter2 = lst1.end();
while (iter1 < iter2) /* ... */

9.2.2. Container Type Members

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.

INFO

Exercises Section 9.2.2

Exercise 9.7: What type should be used as the index into a vector of ints?

Exercise 9.8: What type should be used to read elements in a list of strings? To write them?

9.2.3. begin and end Members

Fundamental

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.

C++11

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.

TIP

Best Practices

When write access is not needed, use cbegin and cend.

INFO

Exercises Section 9.2.3

Exercise 9.9: What is the difference between the begin and cbegin functions?

Exercise 9.10: What are the types of the following four objects?

vector<int> v1;
const vector<int> v2;
auto it1 = v1.begin(), it2 = v2.begin();
auto it3 = v1.cbegin(), it4 = v2.cbegin();

9.2.4. Defining and Initializing a Container

Fundamental

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());

INFO

When we initialize a container as a copy of another container, the container type and element type of both containers must be identical.

The constructor that takes two iterators uses them to denote a range of elements that we want to copy. As usual, the iterators mark the first and one past the last element to be copied. The new container has the same size as the number of elements in the range. Each element in the new container is initialized by the value of the corresponding element in the range.

Because the iterators denote a range, we can use this constructor to copy a subsequence of a container. For example, assuming it is an iterator denoting an element in authors, we can write

// copies up to but not including the element denoted by it
deque<string> authList(authors.begin(), it);

List Initialization

C++11

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.

INFO

The constructors that take a size are valid only for sequential containers; they are not supported for the associative containers.

Library arrays Have Fixed Size

Just as the size of a built-in array is part of its type, the size of a library array is part of its type. When we define an array, in addition to specifying the element type, we also specify the container size:

array<int, 42>    // type is: array that holds 42 ints
array<string, 10> // type is: array that holds 10 strings

To use an array type we must specify both the element type and the size:

array<int, 10>::size_type i; // array type includes element type and size
array<int>::size_type j;     // error: array<int> is not a type

Because the size is part of the array’s type, array does not support the normal container constructors. Those constructors, implicitly or explicitly, determine the size of the container. It would be redundant (at best) and error-prone to allow users to pass a size argument to an array constructor.

The fixed-size nature of arrays also affects the behavior of the constructors that array does define. Unlike the other containers, a default-constructed arrayis 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.

INFO

Exercises Section 9.2.4

Exercise 9.11: Show an example of each of the six ways to create and initialize a vector. Explain what values each vector contains.

Exercise 9.12: Explain the differences between the constructor that takes a container to copy and the constructor that takes two iterators.

Exercise 9.13: How would you initialize a vector<double> from a list<int>? From a vector<int>? Write code to check your answers.

9.2.5. Assignment and swap

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

Code	Description
c1 = c2	Replace the elements in c1 with copies of the elements in c2. c1 and c2 must be the same type.
c = {a, b, c, ...}	Replace the elements in c1 with copies of the elements in the initializer list. (Not valid for array.)
swap(c1, c2) c1.swap(c2)	Exchanges elements in c1 with those in c2. c1 and c2 must be the same type. swap is usually much faster than copying elements from c2 to c1.
seq.assign(b, e)	Replaces elements in seq with those in the range denoted by iterators b and e. The iterators b and e must not refer to elements in seq.
seq.assign(il)	Replaces the elements in seq with those in the initializer list il.
seq.assign(n, t)	Replaces the elements in seq with n elements with value t.

WARNING

• Assignment related operations invalidate iterators, references, and pointers into the left-hand container. Aside from string they remain valid after a swap, and (excepting arrays) the containers to which they refer are swapped.
• Assign operations not valid for associative containers or array.

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:

array<int, 10> a1 = {0,1,2,3,4,5,6,7,8,9};
array<int, 10> a2 = {0}; // elements all have value 0
a1 = a2;  // replaces elements in a1
a2 = {0}; // error: cannot assign to an array from a braced list

Because the size of the right-hand operand might differ from the size of the left-hand operand, the array type does not support assign and it does not allow assignment from a braced list of values.

Using assign (Sequential Containers Only)

The assignment operator requires that the left-hand and right-hand operands have the same type. It copies all the elements from the right-hand operand into the left-hand operand. The sequential containers (except array) also define a member named assign that lets us assign from a different but compatible type, or assign from a subsequence of a container. The assign operation replaces all the elements in the left-hand container with (copies of) the elements specified by its arguments. For example, we can use assign to assign a range of char* values from a vector into a list of string:

list<string> names;
vector<const char*> oldstyle;
names = oldstyle;  // error: container types don't match
// ok: can convert from const char*to string
names.assign(oldstyle.cbegin(), oldstyle.cend());

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.

WARNING

Because the existing elements are replaced, the iterators passed to assign must not refer to the container on which assign is called.

A second version of assign takes an integral value and an element value. It replaces the elements in the container with the specified number of elements, each of which has the specified element value:

// equivalent to slist1.clear();
// followed by slist1.insert(slist1.begin(), 10, "Hiya!");
list<string> slist1(1);     // one element, which is the empty string
slist1.assign(10, "Hiya!"); // ten elements; each one is Hiya !

Using swap

The swap operation exchanges the contents of two containers of the same type. After the call to swap, the elements in the two containers are interchanged:

vector<string> svec1(10); // vector with ten elements
vector<string> svec2(24); // vector with 24 elements
swap(svec1, svec2);

After the swap, svec1 contains 24 string elements and svec2 contains ten. With the exception of arrays, swapping two containers is guaranteed to be fast—the elements themselves are not swapped; internal data structures are swapped.

INFO

Excepting array, swap does not copy, delete, or insert any elements and is guaranteed to run in constant time.

The fact that elements are not moved means that, with the exception of string, iterators, references, and pointers into the containers are not invalidated. They refer to the same elements as they did before the swap. However, after the swap, those elements are in a different container. For example, had iter denoted the string at position svec1 [3] before the swap, it will denote the element at position svec2[3] after the swap. Differently from the containers, a call to swap on a string may invalidate iterators, references and pointers.

Unlike how swap behaves for the other containers, swapping two arrays does exchange the elements. As a result, swapping two arrays requires time proportional to the number of elements in the array.

After the swap, pointers, references, and iterators remain bound to the same element they denoted before the swap. Of course, the value of that element has been swapped with the corresponding element in the other array.

C++11

In the new library, the containers offer both a member and nonmember version of swap. Earlier versions of the library defined only the member version of swap. The nonmember swap is of most importance in generic programs. As a matter of habit, it is best to use the nonmember version of swap.

INFO

Exercises Section 9.2.5

Exercise 9.14: Write a program to assign the elements from a list of char* pointers to C-style character strings to a vector of strings.

9.2.6. Container Size Operations

Fundamental

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

INFO

We can use a relational operator to compare two containers only if the appropriate comparison operator is defined for the element type.

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

INFO

Exercises Section 9.2.7

Exercise 9.15: Write a program to determine whether two vector<int>s are equal.

Exercise 9.16: Repeat the previous program, but compare elements in a list<int> to a vector<int>.

Exercise 9.17: Assuming c1 and c2 are containers, what (if any) constraints does the following usage place on the types of c1 and c2?

if (c1 < c2)