C++ Primer Plus

Like set and the other associative containers, the unordered associative containers allow fast data retrieval through the use of keys. The difference is that the associative containers use trees as the underlying data structure, whereas the unordered associative containers use hash tables.

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 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 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 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, 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 input;

string temp;

while (cin >> temp && temp != "quit")

    input.push_back(temp);

vector::iterator want=

    find(input.begin(), input.end(), string("bonus"));

if (want != input.end())

{

    vector::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::value_type s1 = input[0];  // s1 is type string

vector::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 &