Because keys in a multi container need not be unique, insert on these types always inserts an element:
authors;
// adds the first element with the key Barth, John
authors.insert({"Barth, John", "Sot-Weed Factor"});
// ok: adds the second element with the key Barth, John
authors.insert({"Barth, John", "Lost in the Funhouse"});
For the containers that allow multiple keys, the insertoperation that takes a single element returns an iterator to the new element. There is no need to return a bool, because insert always adds a new element in these types.
11.3.3 ERASING ELEMENTS
Table 11.5. Removing Elements from an Associative Container
11.3.4 SUBSCRIPTING A MAP
The map and unordered_map containers provide the subscript operator and a corresponding at function. The set types do not support subscripting because there is no “value” associated with a key in a set. The elements are themselves keys, so the operation of
“fetching the value associated with a key” is meaningless. We cannot subscript a multimap or an unordered_multimap because there may be more than one value associated with a given key.
map word_count; // empty map
// insert a value-initialized element with key Anna; then assign 1 to its value
word_count["Anna"] = 1;
Because the subscript operator might insert an element, we may use subscript only on a map that is not const.
Ordinarily, the type returned by dereferencing an iterator and the type returned by the subscript operator are the same. Not so for maps: when we subscript a map, we get a mapped_type object; when we dereference a map iterator, we get a value_type object
In common with other subscripts, the map subscript operator returns an lvalue. Because the return is an lvalue, we can read or write the element:
The fact that the subscript operator adds an element if it is not already in the map allows us to write surprisingly succinct programs such as the loop inside our wordcounting program. On the other hand, sometimes we only want to know whether an element
is present and do notwant to add the element if it is not. In such cases, we must not use the subscript operator.
11.3.5 ACCESSING ELEMENTS
The associative containers provide various ways to find a given element, which are described in Table 11.7.
Sometimes,we want to know if an element with a given key is present without changing the map. We cannot use the subscript operator to determine whether an element is present, because the subscript operator inserts a new element if the key is not already
there. In such cases, we should use find:
if(word_count.find("foobar") == word_count.end())
cout << "foobar is not in the map" << endl;
Finding Elements in a multimap or multiset:
string search_item("Alain de Botton"); // author we'll look for
auto entries = authors.count(search_item); // number of elements
auto iter = authors.find(search_item); // first entry for this author
// loop through the number of entries there are for this author
while(entries) {
cout << iter->second << endl; // print each title
++iter; // advance to the next title
--entries; // keep track of how many we've printed
}
A Different, Iterator-Oriented Solution
// definitions of authors and search_item as above
// beg and end denote the range of elements for this author
for (auto beg = authors.lower_bound(search_item),end = authors.upper_bound(search_item);beg != end; ++beg)
cout << beg->second << endl; // print each title
The equal_range Function
This function takes a key and returns a pairof iterators. If the key is present, then the first iterator refers to the first instance of the key and the second iterator refers one past the last instance of the key.
// definitions of authors and search_item as above
// pos holds iterators that denote the range of elements for this key
for (auto pos = authors.equal_range(search_item);
pos.first != pos.second; ++pos.first)
cout << pos.first->second << endl; // print each title
11.4 THE UNORDERED CONTAINERS
The new standard defines four unordered associative containers. Rather than using a comparison operation to organize their elements, these containers use a hash function and the key type’s ==operator. An unordered container
is most useful when we have a key type for which there is no obvious ordering relationship among the elements.
Although hashing gives better average case performance in principle, achieving good results in practice often requires a fair bit of performance testing and tweaking. As a result, it is usually easier (and often yields better performance) to use an ordered
container. Use an unordered container if the key type is inherently unordered or if performance testing reveals problems that hashing might solve.
Aside from operations that manage the hashing, the unordered containers provide the same operations (find, insert, and so on) as the ordered containers. That means that the operations we’ve used on map and set apply to unordered_map and unordered_setas well.
Similarly for the unordered versions of the containers that allow multiple keys.
As a result, we can usually use an unordered container in place of the corresponding ordered container, and vice versa. However, because the elements are not stored in order, the output of a program that uses an unordered container will (ordinarily) differ
from the same program using an ordered container.
The unordered containers are organized as a collection of buckets, each of which holds zero or more elements. These containers use a hash function to map elements to buckets. To access an element, the container first computes the element’s hash code, which
tells which bucket to search. The container puts all of its elements with a given hash value into the same bucket. If the container allows multiple elements with a given key, all the elements with the same key will be in the same bucket. As a result, the performance
of an unordered container depends on the quality of its hash function and on the number and size of its buckets.
The unordered containers provide a set of functions, listed in Table 11.8, that let us manage the buckets. These members let us inquire about the state of the container and force the container to reorganize itself as needed.
Table11.8. Unordered Container Management Operations
By default, the unordered containers use the ==operator on the key type to compare elements.
They also use an object of type hash to generate the hash code for each element. The library supplies versions of the hash template for the builtin types, including pointers.It also defines hash for some of the library types, including strings and
the smart pointer types that we will describe in Chapter 12. Thus, we can directly define unordered containers whose key is one of the built-in types (including pointer types), or a string, or a smart pointer.