Chapter 11. Associative Container

Associative containers support efficient lookup and retrieval by a key. The two primary associative container types are map and set. The elements in a map are key-value pairs: The key serves as an index into the map, and the value represents the data associated with that index. A set element contains only a key; a set supports efficient queries as to whether a given key is present.

Associative Types	Description
map	Associative array; holds key-value pairs.
set	Container in which the key is the value.
multimap	map in which a key can appear multiple times.
multiset	set in which a key can appear multiple times.
unordered_map	map organised by a hash function.
unordered_set	set organised by a hash function.
unordered_multimap	Hashed map; keys can appear multiple times.
unordered_multiset	Hashed set; keys can appear multiple times.

11.1 Using an Associative Container

Using a map

map<string, size_t> word_count;
string word;
while (cin >> word)
    ++word_count[word];

Using a set

A set can hold the words we want to ignore and count only those words that are not in this set.

11.2 Overview of the Associative Containers

11.2.1 Defining an Associative Container

When we define a map, we must indicate both the key and value type; when we define a set, we specify only a key type.

When we initialise a map, we have to supply both the key and the value {key, value}

map<string, string> authors = { {"Joyce", "James"},
                                {"Austen", "Jane"},
                                {"Dickens", "Charles"} };

The keys in a map or a set must be unique; there can be only one element with a given key. The multimap and multiset containers have no such restriction; there can be several elements with the same key.

11.2.2 Requirements on Key Type

For the ordered containers, map, multimap, set, and multiset, the key type must define a way to compare the elements. By default , the library uses the < operator for the key type to compare.

We can also supply our own operation to use in place of the < operator on keys. The specified operation must define a strict weak ordering over the key type. The comparison function must have the following properties:

• Two keys cannot both be "less than" each other; if k1 is "less than" k2, then k2 must never be "less than" k1.

• If k1 is "less than" k2 is "less than" k3, then k1 must be "less than" k3.

• If there are two keys, and neither key is "less than" the other, then we will say that those keys are "equivalent". If k1 is "equivalent" to k2 and k2 is "equivalent" to k3, then k1 must be "equivalent" to k3.

Using a Comparison Function for the Key Type

bool compareIsbn(const Sales_data &lhs, const Sales_data &rhs) {
    return lhs.isbn() < rhs.isbn();
}

multiset<Sales_data, decltype(compareIsbn)*> bookstore(compareIsbn);

Here, we use decltype to specify the type of our operation, we must add a * to indicate that we are using a pointer to the given function type.

11.2.3 The pair Type

The pair defines in the utility header, A pair holds two data members, it is a template from which we generate specific types. We must supply two type names when we create a pair.

The default pair constructor value initialises the data members.

Operations on pairs	Description
pair<T1, T2> p;	p is a pair with value initialised members of types T1 and T2,m respectively.
pair<T1, T2> p(v1, v2);	p is a pair with types T1 and T2; the first and second members are initialised from v1 and v2, respectively.
pair<T1, T2> p = {v1, v2};	Equivalent to p(v1, v2).
make_pair<v1, v2);	Returns a pair initialised from v1 and v2.
p.first	Returns the data member of p named first.
p.second	Returns the data member of p named second.
p1 relop p2	Relational operators.
p1 == p2	Two pairs are equal if their first and second members are respectively equal.
p1 != p2

The data members of pair are public.m These members are named first and second, respectively.

Imagine we have a function that needs to return a pair. Under the new standard we can list initialise the return value.

pair<string, int> process(vector<string>& v) {
    if (!v.empty())
        return {v.back(), v.back().size()};
    else
        return pair<string, int>();
}

Under earlier version of C++, we couldn't use braced initialisers to return a type like pair. Instead, we might have written both returns to explicitly construct the return value:

pair<string, int>(v.back(), v.back().size());

Alternatively, we could have used make_pair to generate a new pair of the appropriate type from its two arguments:

make_pair(v.back(), v.back().size());

11.3 Operations on Associative Containers

Associative Container Additional Type Aliases	Description
key_type	Type of the key for this container type.
mapped_type	Type associated with each key; map types only.
value_type	For sets, same as the key_type.

For the set types, the key_type and the value_type are the same. Only the map type define mapped_type.

11.3.1 Associative Container Iterator

It is essential to remember that the value_type of a map is pair and that we can change the value but not the key member of that pair.

Although the set types define both the iterator and const_iterator types, both types of iterators give use read-only access to the elements in the set.

The map and set types provide all the begin and end operations, we can use to traverse the container.

11.3.2 Adding Elements

The insert members add one element or a range of elements.

Associative Container insert Operations	Description
c.insert(v);	v value_type object; args used to construct an element.
c.emplace(args);
c.insert(b, e);	b and e are iterators that denote a range of c::value_type values.
c.insert(il);	il is a braced list of such values.
c.insert(p, v);	Like insert(v), but uses iterator p as a hint for where to begin the search for where the new element should be stored.
c.emplace(p, v);

11.3.3 Erasing Elements

For the containers with unique keys, the return from erase is always either zero or one. If the return value is zero, then the element we wanted to erase was not in the container.

Removing Elements from an Associative Container	Description
c.erase(k);	Removes every element with key k from c.
c.erase(p);	Removes the element denoted by the iterator p from c.
c.erase(b, e);	Removes the elements in the range denoted by the iterator pair b, e.

11.3.4 Subscripting a map

Subscript Operation for map and unordered_map	Description
c[k]	Return the element with key k.
c.at(k)	Checked access to the element with key k.

11.3.5 Accessing Elements

For the containers with multiple keys, count has to do more work: If the element is present, it still has to count how many elements have the same key.

When a multimap or multiset has multiple elements of a given key, those elements will be adjacent within the container.

Operations to Find Elements in an Associative Container	Description
c.find(k);	Returns an iterator to the element with key k, or the off-the -end iterator if k is not in the container.
c.count(k);	Return the number of elements with key k.
c.lower_bound(k);	Returns an iterator to the first element with key not less than k.
c.upper_bound(k);	Returns an iterator to the first element with key greater than k.
c.equal_range(k);	Return a pair of iterators denoting the elements with key k.

auto entries = authors.count(search_item);
auto iter = authors.find(search_iter);
while(entries) {
    ++iter;
    --entries;
}

Alternatively, we can solve our problem using lower_bound and upper_bound.

The iterator returned from lower_bound may or may not refer to an element with the given key. If the key is not in the container, then lower_bound refers to the first point at which this key can be inserted while preserving the element order within the container.

The remaining way to solve this problem is the most direct of the three approaches, we can call equal_range :

for (auto pos = authors.equal_range(search_item);
        pos.first != pos.second; ++pos.first)
    cout << pos.first->second << endl;

11.4 The unordered Containers

The new standard defines four unordered associative containers. Rather than using a comparison operation to organise 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.

Aside from operations that manage the hashing, the unordered containers provide the same operations as the ordered containers.

The unordered containers are organised 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 has 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.

Unordered Container Management Operation	Description
c.bucket_count();	Number of buckets in use.
c.ma_bucket_count();	Largest number of buckets this container can hold.
c.bucket_size(n);	Number of elements in the nth bucket.
c.bucket(k);	Bucket in which elements with key k would be found.
local_iterator	iterator type that can access elements in a bucket.
const_local_iterator	const version of the bucket iterator.
c.begin(n), c.end(n);	Iterator to the first, one past the last element in bucket n.
c.cbegin(n), c.cend(n);	Returns const_local_iterator.
c.loca_factor();	Average number of elements per bucket.
c.mas_load_factor();	Average bucket size that c tries to maintain.
c.rehash(n);	Reorganise storage so that bucket_load_factor >= n and bucket_count > size/max_load_factor.
c.reserve(n);

Be default, the unordered containers use the == operator on the key type to compare elements. They also use an object of type hash<key_type> to generator hash code for each element. The library supplies version of the hash template for the built-in types, including pointers.

We cannot directly define an unordered container that uses an our own class type for its key type. Instead of using the default hash, we can use a strategy similar to the one we used to override the default comparison operation on keys for the ordered containers.

size_t hasher(const Sales_data &sd) {
    return hash<string>()(sd.isbn());
}
bool eqOp(const Sales_data &lhs, const Sales_data &rhs) {
    return lhs.isbn() == rhs.isbn();
}
using SD_multiset = unordered_multiset<Sales_data, declytype(hasher)*, decltype(eqOp)*>;