Changes to C++98 Containers

C++11 brings three main changes to the container class methods.

First, the addition of rvalue references makes it possible to provide move semantics (Chapter 18, “Visiting with the New C++ Standard”) for containers. Accordingly, the STL now provides move constructors and move assignment operators for containers. These methods take an rvalue reference argument.

Second, the addition of the initializer_list template class (Chapter 18) has led to constructors and assignment operators that accept an initializer_list argument. This makes code like the following possible:

vector<int> vi{100, 99, 97, 98};
vi = {96, 99, 94, 95, 102};

Third, the addition of variadic templates and function parameter packs (Chapter 18) makes emplacement methods possible. What does this mean? Like move semantics, emplacement is a means to increase efficiency. Consider the following code snippets:

class Items
{
    double x;
    double y;
    int m;
public:
    Items();                             // #1
    Items (double xx, double yy, int mm); // #2
    ...
};
...
vector<Items> vt(10);
...
vt.push_back(Items(8.2, 2.8, 3));  //

The call to insert() causes the memory allocation function to create a default Items object at the end of vt. Next, the Items() constructor creates a temporary Items object; this object is copied to a location at the front of the vector vt and then the temporary object is deleted. With C++11, you can do this instead:

vi.emplace_back(8.2, 2.8, 3);

The emplace_back() method is a variadic template with a function parameter pack as its argument:

template <class... Args> void emplace_back(Args&&... args);

The three arguments 8.2, 2.8, and 3 are packed into the args parameter. These parameters are passed along to the allocation function, which then can unpack the parameters and use the Items constructor with three arguments (#2) instead of the default constructor (#1). That is, it can use Items(args...), which, in this example, expands to Items(8.2, 2.8, 3). Thus, the desired object is constructed in place in the vector rather than at a temporary location and then copied to the vector.

The STL uses this technique with several emplacement methods.

Members Common to All or Most Containers

All containers define the types in Table G.1. In this table, X is a container type, such as vector<int>, and T is the type stored in the container, such as int. The examples following the table clarify the meanings.

Table G.1. Types Defined for All Containers

The class definition uses a typedef to define these members. You can use these types to declare suitable variables. For example, the following code uses a roundabout way to replace the first occurrence of "bonus" in a vector of string objects with "bogus" in order to show how you can use member types to declare variables:

using namespace std;
vector<string> input;
string temp;
while (cin >> temp && temp != "quit")
    input.push_back(temp);
vector<string>::iterator want=
    find(input.begin(), input.end(), string("bonus"));
if (want != input.end())
{
    vector<string>::reference r = *want;
    r = "bogus";
}

This code makes r a reference to the element in input to which want points. Similarly, continuing with the preceding example, you can write code like the following:

vector<string>::value_type s1 = input[0];  // s1 is type string
vector<string>::reference s2 = input[1];   // s2 is type string &

This results in s1 being a new string object that’s a copy of input[0] and in s2 being a reference to input[1]. In this example, given that you already know that the template is based on the string type, it would be simpler to write the following code, which is equivalent in its effect:

string s1 = input[0];     // s1 is type string
string & s2 = input[1];   // s2 is type string &

However, the more elaborate types from Table G.1 can also be used in more general code in which the type of container and element are generic. For example, suppose you want a min() function that takes as its argument a reference to a container and returns the smallest item in the container. This assumes that the < operator is defined for the value type used to instantiate the template and that you don’t want to use the STL min_element() algorithm, which uses an iterator interface. Because the argument could be vector<int> or list<string> or deque<double>, you use a template with a template parameter, such as Bag, to represent the container. (That is, Bag is a template type that might be instantiated as vector<int>, list<string>, or some other container type.) So the argument type for the function is const Bag & b. What about the return type? It should be the value type for the container—that is, Bag::value_type. However, at this point, Bag is just a template parameter, and the compiler has no way of knowing that the value_type member is actually a type. But you can use the typename keyword to clarify that a class member is a typedef:

vector<string>::value_type st;    // vector<string> a defined class
typename Bag::value_type m;       // Bag an as yet undefined type

For the first definition here, the compiler has access to the vector template definition, which states that value_type is a typedef. For the second definition, the typename keyword promises that, whatever Bag may turn out to be, the combination Bag::value_type is the name of a type. These considerations lead to the following definition:

template<typename Bag>
typename Bag::value_type min(const Bag & b)
{
    typename Bag::const_iterator it;
    typename Bag::value_type m = *b.begin();
    for (it = b.begin(); it != b.end(); ++it)
        if (*it < m)
            m = *it;
    return m;
}

You then could use this template function as follows:

vector<int> temperatures;
// input temperature values into the vector
int coldest = min(temperatures);

The temperatures parameter would cause Bag to be evaluated as vector<int> and typename Bag::value_type to be evaluated as vector<int>::value_type, which, in turn, is int.

All containers also contain the member functions or operations listed in Table G.2. Again, X is a container type, such as vector<int>, and T is the type stored in the container, such as int. Also a and b are values of type X, u is an identifier, r is a non-const value of type X, and rv is a non-const rvalue of type X. The move operations were added by C++11.

Table G.2. Operations Defined for All Containers

Containers that use a bi-directional or random iterator (vector, list, deque, queue, array, set, and map) are reversible and provide the methods in Table G.3.

Table G.3. Types and Operations Defined for Reversible Containers

The unordered set and unordered map containers are not required to support the optional container operations in Table G.4, but the remaining containers do support them.

Table G.4. Optional Container Operations

The > operator for a container assumes that the > operator is defined for the value type. A lexicographic comparison is a generalization of alphabetical sorting. It compares two containers, element-by-element, until it encounters an element in one container that doesn’t equal the corresponding element in the other container. In that case, the containers are considered to be in the same order as the noncorresponding pair of elements. For example, if two containers are identical through the first 10 elements, but the 11th element in the first container is less than the 11th element in the second container, the first container precedes the second. If two containers compare equally until one runs out of elements, the shorter container precedes the longer.

Additional Members for Sequence Containers

The vector, forward_list, list, deque, and array template classes are all sequence containers, and they all have the methods listed previously, with the exception that forward_list isn’t reversible and doesn’t support the methods of Table G.3. A sequence container, not surprisingly, holds a homogeneous set of items in linear order. If the sequence has a fixed number of elements, array is the usual choice. Otherwise, vector, which combines the random access of array with the ability to add and delete items should be your first recourse. However, if there are frequent additions in the middle of the sequence, consider using list or forward_list. And if additions and deletions primarily occur at the two ends of the sequence, consider deque.

The fixed size of an array object prevents array from using many of the sequence methods. Table G.5 lists additional methods available for sequence containers other than array. (forward_list has somewhat different definitions for resize().) Again, X is a container type, such as vector<int>, and T is the type stored in the container, such as int. a is a value of type X. t is an lvalue or const rvalue of type X::value_type. rv is a non-const rvalue of that same type. i and j are input iterators. [i, j) is a valid range. il is an object of type initializer_list<value_type>. p is a valid const iterator to a. q is a valid dereferenceable const iterator to a. [q1,q2) is a valid range of const iterators. n is an integer of X::size_type. Args is a template parameter pack, and args is a function parameter pack with the pattern Args&&.

Table G.5. Additional Operations Defined for Sequence Containers

Table G.6 lists methods common to some of the sequence classes (vector, forward_list, list, and deque).

Table G.6. Operations Defined for Some Sequences

The vector template additionally has the methods in Table G.7. Here, a is a vector container and n is an integer of X::size_type.

Table G.7. Additional Operations for Vectors

The list template additionally has the methods in Table G.8. Here, a and b are list containers, and T is the type stored in the list, such as int, t is a value of type T, i and j are input iterators, q2 and p are iterators, q and q1 are dereferenceable iterators, and n is an integer of X::size_type. The table uses the standard STL notation [i, j), meaning the range from i up to, but not including, j.

Table G.8. Additional Operations for Lists

The forward-list operations are similar. However, because a forward_list template class iterator can’t go backwards, some methods have to be adjusted. Thus, the insert(), erase(), and splice() methods are replaced with the insert_after(), erase_after(), and splice_after() methods, all of which operate on the position following an iterator position rather than preceding it.

Additional Operations for Sets and Maps

Associative containers, of which sets and maps are models, have a Key template parameter and a Compare template parameter, which indicate, respectively, the type of the key used to order the contents and the function object, termed a comparison object, used to compare key values. For the set and multiset containers, the stored keys are the stored values, so the key type is the same as the value type. For the map and multimap containers, the stored values of one type (template parameter T) are associated with a key type (template parameter Key), and the value type is pair<const Key, T>. Associative containers have additional members to describe these features, as listed in Table G.9.

Table G.9. Types Defined for Associative Containers

Associative containers provide the methods listed in Table G.10. In general, the comparison object need not require that values with the same key be identical; the term equivalent keys means that two values, which may or may not be equal, have the same key. In the table, X is a container class, and a is an object of type X. If X uses unique keys (that is, is set or map), a_uniq is an object of type X. If X uses multiple keys (that is, is multiset or multimap), a_eq is an object of type X. As before, i and j are input iterators referring to elements of value_type, [i, j) is a valid range, p and q2 are iterators to a, q and q1 are dereferenceable iterators to a, [q1, q2) is a valid range, t is a value of X::value_type (which may be a pair), and k is a value of X::key_type. Also il is an initializer_list<value_type> object.

Table G.10. Operations Defined for Sets, Multisets, Maps, and Multimaps

Unordered Associative Containers (C++11)

As mentioned earlier, the unordered associative containers (unordered_set, unordered_multiset, unordered_map, and unordered_multimap) use keys and hash tables to provide rapid access to data. Let’s take a simple look at these concepts. A hash function converts a key to an index value. For example, if the key were a string, the hash function could sum the numeric codes for the characters in the string and take that sum modulus 13, thus giving an index in the range 0–12. The unordered container would use 13 buckets to store strings. Any string with, say, an index of 4 would be placed in bucket 4. If you wished to search the container for a key, you would apply the hash function to the key and just search the bucket with the corresponding index. Ideally, you would have enough buckets that each one would contain only a few strings.

The C++11 library provides a hash<Key> template that the unordered associative containers use by default. Specializations are defined for the various integer and floating-point types, for pointers, and for some template classes, such as string.

Table G.11 lists types used for these containers.

Table G.11. Types Defined for Unordered Associative Containers

The interface for the unordered associative containers is similar to that of the associative containers. In particular, Table G.10 also applies to the unordered associative containers with the following exceptions: The lower_bound() and upper_bound() methods are not required, nor is the X(i,j,c) constructor. The fact that the regular associative containers are ordered allows them to use a comparison predicate that expresses the “less than” concept. Such a comparison doesn’t apply to unordered associative containers, so, instead, they use a comparison predicate that is based on the “is equivalent to” concept.

In addition to the Table G.10 methods, the unordered associative containers require several more methods, as listed in Table G.12. In this table, X is an unordered associative container class, a is an object of type X, b is a possibly constant object of type X, a_uniq is an object of type unordered_set or unordered_map, a_eq is an object of type unordered_multiset or unordered_multimap, hf is a value of type hasher, eq is a value of type key_equal, n is a value of type size_type, and z is a value of type float. As before, i and j are input iterators referring to elements of value_type, [i, j) is a valid range, p and q2 are iterators to a, q and q1 are dereferenceable iterators to a, [q1, q2) is a valid range, t is a value of X::value_type (which may be a pair), and k is a value of X::key_type. Also il is an initializer_list<value_type> object.

Table G.12. Additional Operations Defined for Unordered Sets, Multisets, Maps, and Multimaps

STL Functions

The STL algorithm library, supported by the algorithm and numeric header files, provides a large number of nonmember, iterator-based template functions. As discussed in Chapter 16, the template parameter names are chosen to indicate what concept particular parameters should model. For example, ForwardIterator is used to indicate that a parameter should, at the minimum, model the requirements of a forward iterator, and Predicate is used to indicate a parameter that should be a function object with one argument and a bool return value. The C++ Standard divides the algorithms into four groups: nonmodifying sequence operations, mutating sequence operations, sorting and related operators, and numeric operations. (C++11 moves numeric operations from the STL to the numeric library, but that doesn’t affect how they are used.) The term sequence operation indicates that the function takes a pair of iterators as arguments to define a range, or sequence, to be operated on. The term mutating means the function is allowed to alter the container.