Associative Containers
Associative Container: A container that stores and retrieves elements by key rather than by position.
Key: A value used to identify or locate an element.
The standard library provides eight associative containers.
| Container | Meaning |
|---|---|
map | Ordered key-value pairs with unique keys |
set | Ordered unique keys |
multimap | Ordered key-value pairs allowing duplicate keys |
multiset | Ordered keys allowing duplicates |
unordered_map | Hashed key-value pairs with unique keys |
unordered_set | Hashed unique keys |
unordered_multimap | Hashed key-value pairs allowing duplicate keys |
unordered_multiset | Hashed keys allowing duplicates |
Ordered containers are declared in:
#include <map>
#include <set>
Unordered containers are declared in:
#include <unordered_map>
#include <unordered_set>
11.1 Using an Associative Container
A map stores key-value pairs.
A set stores keys only.
Using a map
map: An associative array whose elements are accessed by key.
#include <map>
#include <string>
std::map<std::string, std::size_t>
word_count;
Here:
key type = std::string
mapped type = std::size_t
A classic word-counting program is:
std::string word;
while (std::cin >> word)
{
++word_count[word];
}
If word is not already present, the subscript operation creates a new element whose mapped value is value-initialized.
For std::size_t, that initial value is:
0
Then the value is incremented.
Iterating through a map
A map element is a pair.
for (const auto& entry : word_count)
{
std::cout
<< entry.first
<< " occurs "
<< entry.second
<< " times\n";
}
For each map element:
first = key
second = mapped value
Ordered maps are traversed in key order.
Using a set
set: An associative container that stores unique keys.
A set is useful when the main question is:
Does this value exist?
Example:
std::set<std::string> excluded{
"the",
"but",
"and",
"or"
};
Check whether a word should be ignored:
if (excluded.find(word)
== excluded.end())
{
++word_count[word];
}
If find() returns end(), the key is not present.
11.2 Overview of the Associative Containers
Associative containers organize their elements according to keys rather than insertion position.
They do not provide positional operations such as:
push_front()
push_back()
Ordered associative containers provide bidirectional iterators.
1) Defining an Associative Container
Default Construction
std::map<std::string, int>
scores;
std::set<int>
values;
Both containers are initially empty.
List Initialization
std::set<int> values{
1,
2,
3,
4
};
A map initializer contains key-value pairs.
std::map<std::string, int> scores{
{"Alice", 95},
{"Bob", 88},
{"Carol", 91}
};
Range Initialization
std::vector<int> source{
1,
2,
2,
3,
3
};
std::set<int> values(
source.begin(),
source.end()
);
The set contains:
1 2 3
Duplicate values are ignored because set requires unique keys.
Unique-Key Containers
These containers permit at most one element for each key:
map
set
unordered_map
unordered_set
Example:
std::set<int> values{
1,
1,
2,
2,
3
};
The resulting set contains:
1 2 3
Multiple-Key Containers
These containers allow equivalent keys to occur multiple times:
multimap
multiset
unordered_multimap
unordered_multiset
Example:
std::multiset<int> values{
1,
1,
2,
2,
3
};
The container keeps all five elements.
2) Requirements on Key Type
Ordered associative containers need a way to order their keys.
By default they use:
operator<
The comparison must establish a strict weak ordering.
Key Equivalence
Two keys are considered equivalent when neither is less than the other.
Conceptually:
!compare(a, b)
&&
!compare(b, a)
For a unique-key ordered container, equivalent keys represent the same key.
Custom Comparison Function
A custom comparator can replace the default < operation.
Suppose:
struct Record
{
int id;
std::string name;
};
Comparator:
bool compare_record(
const Record& lhs,
const Record& rhs)
{
return lhs.id < rhs.id;
}
Define a set using the function pointer type:
using Compare =
bool (*)(
const Record&,
const Record&
);
std::set<
Record,
Compare
> records(compare_record);
The comparator type is part of the container type.
The comparator object is supplied when the container object is created.
Lambda Comparator
A callable object can also provide ordering.
auto compare =
[](const Record& lhs,
const Record& rhs)
{
return lhs.id < rhs.id;
};
std::set<
Record,
decltype(compare)
> records(compare);
The comparison must remain consistent while elements are stored in the container.
3) The pair Type
pair: A library template that stores two public members.
Required header:
#include <utility>
Example:
std::pair<std::string, int>
item{
"Alice",
95
};
Access the members:
std::cout << item.first;
std::cout << item.second;
Constructing a pair
std::pair<std::string, int>
p1;
std::pair<std::string, int>
p2("Alice", 95);
std::pair<std::string, int>
p3{"Bob", 88};
Using make_pair():
auto p4 =
std::make_pair(
std::string("Carol"),
91
);
The member types are inferred.
Returning a pair
A function may return a pair directly.
std::pair<std::string, int>
make_score()
{
return {
"Alice",
95
};
}
Usage:
auto result =
make_score();
std::cout
<< result.first
<< ' '
<< result.second;
11.3 Operations on Associative Containers
Associative containers define type aliases specific to key-based storage.
| Type | Meaning |
|---|---|
key_type | Key type |
mapped_type | Mapped value type; map types only |
value_type | Stored element type |
For:
std::map<std::string, int>
the types are conceptually:
key_type
std::string
mapped_type
int
value_type
std::pair<const std::string, int>
The map key is const because changing it in place would break the container's ordering.
1) Associative Container Iterators
Dereferencing a map iterator gives a reference to its value_type.
std::map<std::string, int>
scores{
{"Alice", 95},
{"Bob", 88}
};
auto iter =
scores.begin();
Access the key:
std::cout
<< iter->first;
Access the mapped value:
std::cout
<< iter->second;
Map Keys Cannot Be Modified
This is invalid:
// Error:
// iter->first = "Carol";
The key is const.
The mapped value can be changed:
iter->second = 100;
Set Iterators Are Read-Only
For a set:
std::set<int> values{
1,
2,
3
};
auto iter =
values.begin();
The element may be read:
std::cout << *iter;
but not changed:
// Error:
// *iter = 10;
Changing a key directly could violate the ordering of the container.
Ordered Traversal
Ordered associative containers iterate in key order.
std::map<std::string, int> scores{
{"Carol", 91},
{"Alice", 95},
{"Bob", 88}
};
for (const auto& entry : scores)
{
std::cout
<< entry.first
<< '\n';
}
Output:
Alice
Bob
Carol
Associative Containers and Generic Algorithms
Read-only algorithms can work with associative-container iterators.
However, algorithms that modify keys or reorder elements are generally inappropriate.
For lookup, prefer the container member:
scores.find("Alice");
rather than a generic linear search.
The member operation can use the container's internal search structure.
2) Adding Elements
Important operations include:
insert()
emplace()
Inserting into a set
std::set<int> values;
values.insert(10);
values.insert(20);
values.insert(10);
The second insertion of 10 has no effect because a set has unique keys.
Inserting into a map
A map element is a key-value pair.
std::map<std::string, int>
scores;
scores.insert(
{"Alice", 95}
);
Other forms include:
scores.insert(
std::make_pair(
"Bob",
88
)
);
or:
scores.insert(
std::pair<
std::string,
int
>{
"Carol",
91
}
);
Return Value from Unique-Key insert()
For map and set, inserting one element returns:
std::pair<iterator, bool>
Example:
auto result =
scores.insert(
{"Alice", 95}
);
Check whether insertion occurred:
if (result.second)
{
std::cout
<< "inserted\n";
}
else
{
std::cout
<< "key already exists\n";
}
The iterator:
result.first
refers to the element with that key.
Word Counting with insert()
Instead of subscripting:
++word_count[word];
the insertion return value can be used:
auto result =
word_count.insert(
{word, 1}
);
if (!result.second)
{
++result.first->second;
}
If the key did not exist, {word, 1} is inserted.
If it already existed, the existing counter is incremented.
Inserting into a Multi Container
A multimap or multiset allows duplicate keys.
std::multimap<
std::string,
std::string
> authors;
authors.insert(
{"Barth", "Sot-Weed Factor"}
);
authors.insert(
{"Barth", "Lost in the Funhouse"}
);
Both elements are stored.
Single-element insertion into a multi container returns an iterator to the inserted element.
emplace()
emplace() constructs an element directly inside the container.
std::map<std::string, int>
scores;
scores.emplace(
"Alice",
95
);
The arguments are used to construct the stored pair.
3) Erasing Elements
Associative containers support several forms of erase().
Erase by Key
std::set<int> values{
1,
2,
3
};
auto removed =
values.erase(2);
Result:
removed = 1
For a unique-key container, the result is normally:
0 or 1
Erase from a Multi Container
std::multiset<int> values{
1,
2,
2,
2,
3
};
auto removed =
values.erase(2);
Result:
removed = 3
Every equivalent key is erased.
Erase by Iterator
auto iter =
values.find(3);
if (iter != values.end())
{
values.erase(iter);
}
Only the element denoted by the iterator is removed.
Erase a Range
values.erase(
values.begin(),
values.end()
);
This removes the specified iterator range.
4) Subscripting a map
Only:
map
unordered_map
support subscripting.
set, multimap, and multiset do not.
Map Subscript
std::map<std::string, int>
scores;
scores["Alice"] = 95;
The expression:
scores["Alice"]
returns the mapped value associated with "Alice".
Missing-Key Insertion
If the key does not exist:
int score =
scores["Bob"];
a new element is inserted.
Conceptually:
key = "Bob"
value = 0
because int is value-initialized.
This side effect is important.
Why Word Counting Is Concise
++word_count[word];
works because a missing key automatically creates a counter initialized to zero.
Conceptually:
missing word
↓
insert {word, 0}
↓
increment
↓
{word, 1}
at()
at() accesses an existing mapped value without inserting a new element.
int score =
scores.at("Alice");
If the key does not exist, at() throws:
std::out_of_range
Example:
try
{
std::cout
<< scores.at("Unknown");
}
catch (
const std::out_of_range&)
{
std::cout
<< "key not found\n";
}
Subscript Return Type
For:
std::map<std::string, int>
scores;
this:
scores["Alice"]
has the mapped type:
int
as an lvalue.
Therefore it can be modified:
++scores["Alice"];
By contrast, dereferencing a map iterator yields:
pair<const string, int>
5) Accessing Elements
Important lookup operations include:
| Operation | Meaning |
|---|---|
find(k) | Find first element with key k |
count(k) | Count elements with key k |
lower_bound(k) | First key not less than k |
upper_bound(k) | First key greater than k |
equal_range(k) | Range of elements equivalent to k |
find()
auto iter =
scores.find("Alice");
if (iter != scores.end())
{
std::cout
<< iter->second;
}
If the key does not exist:
iter == scores.end()
Use find() for Noninserting Lookup
Do not use:
scores["Unknown"];
when the intention is only to check whether the key exists.
That expression can insert a new element.
Prefer:
if (scores.find("Unknown")
!= scores.end())
{
// key exists
}
count()
For unique-key containers:
scores.count("Alice");
returns:
0 or 1
For multi containers it can return larger values.
authors.count("Barth");
might return:
2
Finding All Elements in a multimap
Because equal keys are adjacent in an ordered multi container, one approach is:
auto count =
authors.count("Barth");
auto iter =
authors.find("Barth");
while (count)
{
std::cout
<< iter->second
<< '\n';
++iter;
--count;
}
lower_bound() and upper_bound()
For an ordered associative container:
auto begin =
authors.lower_bound("Barth");
auto end =
authors.upper_bound("Barth");
The range:
[begin, end)
contains all elements whose key is equivalent to "Barth".
Traversal:
for (auto iter = begin;
iter != end;
++iter)
{
std::cout
<< iter->second
<< '\n';
}
If there are no matching keys:
begin == end
equal_range()
equal_range() returns both iterators together.
auto range =
authors.equal_range("Barth");
Equivalent range:
[range.first, range.second)
Traversal:
for (auto iter = range.first;
iter != range.second;
++iter)
{
std::cout
<< iter->second
<< '\n';
}
This is often the clearest way to process all elements with an equivalent key.
6) A Word Transformation Map
A useful associative-container example is a word transformation program.
A map stores:
original word -> replacement text
Example:
std::map<
std::string,
std::string
> transformations{
{"brb", "be right back"},
{"k", "okay"},
{"u", "you"}
};
Building the Transformation Map
Suppose each rule contains:
key replacement text
Using subscript assignment:
transformations[key] =
replacement;
If the key is new, a new element is inserted.
If the key already exists, its mapped value is replaced.
Nonmodifying Transformation Lookup
Use find() because looking up a word should not add a new rule.
const std::string&
transform(
const std::string& word,
const std::map<
std::string,
std::string
>& rules)
{
auto iter =
rules.find(word);
if (iter != rules.cend())
{
return iter->second;
}
return word;
}
If the word exists:
return replacement
Otherwise:
return original word
Why Not Use operator[]?
Using:
rules[word]
would be inappropriate for a const map and, on a non-const map, could insert missing words.
Lookup should not modify the transformation table.
11.4 The Unordered Containers
Unordered Associative Container: An associative container organized by hashing rather than key ordering.
Examples:
std::unordered_map<
std::string,
int
> scores;
std::unordered_set<
std::string
> words;
Ordered vs. Unordered
Ordered containers use a comparison operation.
map / set
↓
key comparison
↓
ordered traversal
Unordered containers use:
hash function
+
key equality
```
and do not maintain sorted key order.
---
### Hash-Based Lookup
Conceptually:
~~~text
key
↓
hash function
↓
hash value
↓
bucket
↓
compare keys inside bucket
The hash function determines which bucket should contain the element.
The equality operation distinguishes equivalent keys within that bucket.
Basic Use
std::unordered_map<
std::string,
std::size_t
> word_count;
std::string word;
while (std::cin >> word)
{
++word_count[word];
}
The interface is very similar to map.
Operations such as:
find()
insert()
erase()
count()
operator[]
```
are also available where applicable.
---
### Traversal Order
Do not rely on iteration order in an unordered container.
~~~cpp
for (const auto& entry
: word_count)
{
std::cout
<< entry.first
<< '\n';
}
The output is not guaranteed to be alphabetically ordered.
When to Use Unordered Containers
Unordered containers are useful when:
- key ordering is not needed
- hashing is available for the key type
- average-case hash lookup is desirable
Ordered containers are often simpler when:
- sorted traversal is useful
- range operations such as
lower_bound()are needed - a natural key ordering already exists
Buckets
An unordered container stores elements in buckets.
Different keys may hash to the same bucket.
This is a collision.
The container resolves collisions by comparing keys inside the selected bucket.
Bucket Operations
| Operation | Meaning |
|---|---|
bucket_count() | Current number of buckets |
max_bucket_count() | Maximum possible bucket count |
bucket_size(n) | Number of elements in bucket n |
bucket(k) | Bucket containing key k |
load_factor() | Average elements per bucket |
max_load_factor() | Maximum target load factor |
rehash(n) | Reorganize using an appropriate bucket count |
reserve(n) | Prepare for at least n elements |
bucket_count()
auto count =
word_count.bucket_count();
This reports the current number of buckets.
bucket_size()
for (std::size_t i = 0;
i != word_count.bucket_count();
++i)
{
std::cout
<< "bucket "
<< i
<< ": "
<< word_count.bucket_size(i)
<< '\n';
}
This can be used to inspect the hash distribution.
bucket()
auto index =
word_count.bucket("hello");
index identifies the bucket associated with the key.
Load Factor
Load Factor: The average number of elements per bucket.
Conceptually:
load factor
=
number of elements
------------------
number of buckets
Retrieve it with:
auto load =
word_count.load_factor();
A high load factor can increase the number of keys that must be examined inside a bucket.
rehash()
word_count.rehash(100);
requests that the container reorganize its elements using enough buckets to satisfy the requested bucket count and load-factor requirements.
Rehashing can invalidate iterators.
reserve()
word_count.reserve(1000);
prepares the container to hold approximately the requested number of elements without needing an immediate rehash, subject to the container's load-factor rules.
Use it when the expected number of elements is known in advance.
Requirements on Key Types
For an unordered container, the key type needs:
- a hash operation
- an equality operation
The standard library provides:
std::hash<T>
for many built-in and standard-library types.
Example:
std::unordered_set<std::string>
names;
std::hash<std::string> supplies the default hash function.
Key Equality
By default, equivalent keys are compared using equality.
Conceptually:
lhs == rhs
Equal keys must produce equal hash values.
Custom Hash Function
Suppose:
struct Point
{
int x;
int y;
};
Equality:
bool operator==(
const Point& lhs,
const Point& rhs)
{
return
lhs.x == rhs.x
&&
lhs.y == rhs.y;
}
Hasher:
struct PointHash
{
std::size_t operator()(
const Point& point) const
{
auto h1 =
std::hash<int>{}(
point.x
);
auto h2 =
std::hash<int>{}(
point.y
);
return h1 ^ (h2 << 1);
}
};
Use it as:
std::unordered_set<
Point,
PointHash
> points;
The unordered container uses:
PointHash
to choose a bucket
operator==
to test key equality
Custom Equality Operation
A separate equality callable can also be supplied.
struct PointEqual
{
bool operator()(
const Point& lhs,
const Point& rhs) const
{
return
lhs.x == rhs.x
&&
lhs.y == rhs.y;
}
};
Container:
std::unordered_set<
Point,
PointHash,
PointEqual
> points;
The hash and equality functions must agree:
if a == b
then hash(a) == hash(b)
Essential Study Checklist
- Associative containers store and retrieve elements by key.
mapstores key-value pairs.setstores keys.mapandsetrequire unique keys.multimapandmultisetallow duplicate keys.- Containers beginning with
unordered_use hashing instead of key ordering. mapis often called an associative array.- Map subscripts use keys rather than numeric positions.
- A map element is a
pairwhosefirstmember is the key andsecondis the mapped value. - Subscripting a missing map key inserts a value-initialized mapped value.
setis useful for membership tests.- Ordered associative containers iterate in key order.
- Ordered associative containers use a comparison operation on keys.
- The default ordered comparison is normally
<. - Ordered key comparison must establish a strict weak ordering.
- Equivalent ordered keys satisfy neither
a < bnorb < aunder the comparator. - A custom comparator type becomes part of the container type.
pairstores two public members namedfirstandsecond.make_pair()creates a pair while deducing its member types.key_typeis the associative container's key type.mapped_typeis the associated value type for map containers.- A map's
value_typeispair<const key_type, mapped_type>. - Map keys cannot be changed through iterators.
- A map's mapped value can be modified through a non-const iterator.
- Set iterators provide read-only access to keys.
- Prefer associative-container member lookup operations over generic linear search.
insert()adds elements to associative containers.- A map insertion value is a key-value pair.
- Inserting an existing key into
maporsetdoes not add another element. - Single-element insertion into a unique-key container returns
pair<iterator, bool>. - The returned
boolindicates whether insertion occurred. multimapandmultisetallow repeated equivalent keys.erase(k)removes every element whose key is equivalent tok.- In a unique-key container,
erase(k)returns0or1. - In a multi container,
erase(k)may return a larger count. - Only
mapandunordered_mapsupport subscripting. operator[]can insert a missing key.- Use
find()when lookup must not insert a new element. at()accesses an existing mapped value and throws if the key is absent.find(k)returns an iterator to a matching element orend().count(k)returns the number of elements with keyk.lower_bound(k)returns the first key not less thank.upper_bound(k)returns the first key greater thank.[lower_bound(k), upper_bound(k))contains all equivalent ordered keys.equal_range(k)returns the same equivalent-key range as a pair of iterators.- A word-transformation map naturally represents
word -> replacementrules. - Use
find()in nonmodifying transformation lookup. - Unordered containers use a hash function and key equality.
- Unordered containers do not maintain sorted traversal order.
- A hash function maps keys to integral hash values.
- Hash values are used to select buckets.
- Keys that hash to the same bucket cause collisions.
bucket_count()reports the number of buckets.bucket_size(n)reports the number of elements in a bucket.load_factor()is the average number of elements per bucket.rehash()reorganizes the bucket structure.reserve()prepares an unordered container for an expected number of elements.std::hash<T>supplies default hashing for supported key types.- Custom key types may require custom hashing and equality operations.
- Equal keys must always produce equal hash values.