Beginner's Guide

## Quick Overview

### Sets

`#include <set>`

`#include <unordered_set>`

#### `set<Key> / unordered_set<Key>`Unique Keys

unique orderable / hashable keys

``````std::set<int> s {9,2,8};
s.insert(7);
s.erase(8);
if (s.find(7) != end(s)) {…}
if (s.contains(7)) {…} C++20
// find returns an iterator:
auto i = s.find(7);
if (i != end(s))   i = s.erase(i);``````
``````{2, 8, 9}
{2, 7, 8, 9}
{2, 7, 9}
true (7 found)
true (7 found)
{2, 7, 9}
i
{2,9}
i (after)``````

#### `multiset<Key> / unordered_multiset<Key>`Multisets

multiple equivalent keys possible

``````std::multiset<int> s;
s.insert(8);
s.insert(7);
s.insert(2);
s.insert(7);
s.erase(7);``````
``````{}
{8}
{7, 8}
{2, 7, 8}
{2, 7, 7, 8}
{2, 8}``````

### Key→Value MapsMaps

`#include <map>`

`#include <unordered_map>`

##### Maps store `std::pair<Key const,Value>`Maps store `pair<Key const,Value>`pair<K,V>

The standard library associative containers are based on nodes that are linked by pointers. Each node stores a pair of a key and a value.

`std::pair<First,Second>` contains two values of different or same type

``````#include <utility>
std::pair<int,double> p {4, 8.15};
cout << p.first  <<'\n';   // 4
cout << p.second <<'\n';   // 8.15
// C++17 features:
std::pair p2 {4, 8.15};  // std::pair<int,double>
auto [fst,snd] = p2;    // structured binding
cout << fst <<" "<< snd <<'\n';  // 4 8.15``````

#### `map<Key,Value> / unordered_map<Key,Value>`Unique Keys

unique orderable / hashable keys

``````std::map<int,std::string> m;
m.insert({2, "B"});
m.emplace(1, "A");
m[2] = "Y";  // modify
m[3] = "C";  // insert!
auto i = m.find(2);
if (i != end(m))
cout << i->first
<< i->second;
if (m.contains(2)) {…}  C++20
m.erase(2);
auto j = m.find(3);
if (j != end(m))   j = m.erase(j);
// C++17 features:
m.insert_or_assign(4,"D");
m.insert_or_assign(1,"X");
m.try_emplace(4,"Z");
m.try_emplace(5,"E");``````
``````{ }
{2:B}
{1:A,2:B}
{1:A,2:Y}
{1:A,2:Y,3:C}
→ iterator
if found
2  (key)
Y  (value)
true (2 found)
{1:A,3:C}
j
{1:A  }
j (after)
{1:A}
{1:A,4:D}
{1:X,4:D}
{1:X,4:D}
{1:X,4:D,5:E}``````

#### `multimap<Key,Value> / unordered_multimap<Key,Value>`Multimaps

multiple equivalent keys possible

``````std::multimap<int,std::string> m;
m.emplace(1, "A");
m.insert({2, "B"});
m.emplace(1, "C");
m.erase(1);``````
``````{ }
{1:A}
{1:A,2:B}
{1:A,1:C,2:B}
{ 2:B}``````

### Standard Sets & Maps Are Node-BasedSets & Maps Are Node-BasedNodes

usually implemented as balanced binary tree

implemented as hash table

## Interface: How To

### Make New Sets / MapsMake

#### Make An Empty Set / MapEmpty

• ```SetOrMapType variable; ```
• ```SetOrMapType variable {}; ```
``````std::set<int> s1;
std::set<int> s2 {};
std::map<int,float> m1;
std::map<int,float> m2 {};``````

This is a function declaration:

``std::set<int> s3 ();``

#### Make Sets From Key ListsFrom List

• `set<KeyType>{key1,key2,…}`
• `set{key1,key2,…}  C++17`(key type deduced)
``````std::set<int> s1 {12};
std::set<int> s2 {3,2,1,4,5};
std::set s3 {1, 2, 3, 4};        // set<int>    C++17
std::set s4 {1.f, 2.3f, 4.5f};   // set<float>  C++17
std::set s5 {1., 2.3, 4.6};      // set<double> C++17``````

#### Make Sets From Key RangesFrom Range

• `set<Key>(@keys_begin,@keys_end)`
• `set(@keys_begin,@keys_end)  C++17`(key type deduced)
``````std::vector<int> v {2,3,1,4};
std::set<int> s (begin(v),begin(v)+3);``````
``````v: 2314

s: {1,2,3}``````

### Insert Keys Into SetsSets: Insert KeysSet Insert

#### Insert Single KeysSingle

• ```.insert(key) ````pair<@pos,insert_success>`
``````std::set<int> s;
s.insert(3)
auto r1 = s.insert(7);
cout << r1.second;
cout << *r1.first;
auto r2 = s.insert(7);
cout << r2.second;``````
``````{ }
{3}
{3,7}
true (inserted)
7

false (NOT inserted)``````

#### Emplace: Insert & Construct Keys In-PlaceEmplaceC++11

• ```.emplace(keyArg1,keyArg2,…) ````pair<@pos,insert_success>`

Construct key(s) directly inside the set using key constructor arguments (can prevent copying of large key objects).

``````using VS = std::vector<std::string>;
std::set<VS> s;
s.insert( VS{"a","c"} );
s.emplace("v","w","x");``````
``````
{ }
{{"a","c"}}
{{"a","c"},{"v","w","x"}}``````

#### Insert Ranges of KeysRanges

• ```.insert({key1,key2,…}) ```
• ```.insert(@keys_begin,@keys_end) ```
``````std::set<int> s;
s.insert({3,5});
vector<int> v {2,4,1};
s.insert(begin(v),end(v));``````
``````{ }
{3,5}

{1,2,3,4,5}``````

#### Insert/Emplace With Position HintWith Hint

• ```.insert(@hint,key}) ````@insert_pos`
• ```.emplace_hint(@hint,keyArg1,keyArg2,…) ````@insert_pos`

Potentially faster than regular insert: amortized constant cost, if `@hint` is before/after the key's final position in the set.

``````std::set<int> s {1,4};

auto h = s.find(4);
s.insert(h, 3);

h = s.find(1);
s.insert(h, 2);``````
``````
{1, 4}
h
{1, 3, 4}
{1, 3, 4}
h
{1, 2, 3, 4}``````

### Insert Keys+Values Into MapsMaps: Insert Keys+ValuesMap Insert

• ```.insert({key,value}) ````pair<@pos,insert_success>`

Copies/moves key-value pairs into the map. Use `emplace` (see next section) if your key and/or value types are expensive to copy.

``````std::map<int,std::string> m;
auto r1 = m.insert({1,"a"});
cout << r1.second;
cout << *r1.first;
auto r2 = m.insert({1,"b"});
cout << r2.second;
cout << *r2.first;``````
``````{ }
{1:"a"}
true  (inserted)
"a"   (key at position)
{1:"a"}
false (NOT inserted)
"a"   (key at position)``````

#### Emplace: Insert & Construct Key-Value Pairs In-PlaceEmplace

• ```.emplace(key,value) ````pair<@pos,insert_success> C++11`
• ```.try_emplace(key,valArg1,valArg2,…) ````pair<@pos,insert_success> C++17`

Constructs key-value pairs directly inside the map using constructor arguments. (prevents copying of large value or key objects).

``````struct P2 {  // custom value type
P2 (int x_, int y_): x{x_}, y{y_} {}
int x, y;
};``````
``````std::map<char,P2> m;
m.insert( {'a', P2{1,2}} );
m.emplace('c', P2{3,4});
m.try_emplace('b', 5,6);
m.try_emplace('a', 8,9);``````
``````{ }
{'a':{1,2}}
{'a':{1,2},'c':{3,4}}
{'a':{1,2},'b':{5,6},'c':{3,4}}
{'a':{1,2},'b':{5,6},'c':{3,4}}``````

#### Insert / Access / Assign`[key]=v`

• `[key] = value`(inserts key if not found)
• `.at(key) = value`(throws `std::out_of_range` if key not found)
• ```.insert_or_assign(key,value) ````pair<@pos,insert_success> C++17`
``````std::map<int,std::string> m;
m[1] = "a";
m[1] = "x";
m.insert_or_assign(3,"c")
m.insert_or_assign(3,"u")
try {
m.at(1) = "y";
m.at(2) = "z";
} catch(std::out_of_range&) {…}``````
``````{ }
{1:"a"}
{1:"x"}
{1:"y",3:"c"}
{1:"y",3:"u"}

{1:"y",3:"u"}
← throws exception``````

#### Insert Ranges of Key-Value PairsRanges

• ```.insert (@kv_pairs_begin,@kv_pairs_end) ```
``````std::vector<pair<int,string>> v;
v.emplace_back(3,"c");
v.emplace_back(1,"a");
v.emplace_back(2,"b");
map<int,string> m;
m.insert(begin(v), end(v));``````
``````// final result
m: {1:"a",2:"b",3:"c"}``````

#### Insert/Emplace With Position HintWith Hint

• ```.insert(@hint,{key,value}) ````@pos`
• ```.emplace_hint(@hint,key,value) ````pair<@pos,insert_success> C++11`

Potentially faster than regular insert: amortized constant cost, if `@hint` is before/after the key's final position in the map.

``````std::map<int,std::string> m;
m.insert({4,"d"});

auto h1 = m.find(4);
m.insert(h1, {1,"a"});

auto h2 = m.find(1);
m.emplace(h2, 3,"c");``````
``````{ }
{4:"d"}
{4:"d"}
h1
{1:"a",4:"d"}
{1:"a",4:"d"}
h2
{1:"a",3:"c",4:"d"}``````

### Find/Access/Count KeysFind/Access/Query/Count KeysQuery

#### Check If Set/Map Contains KeyContainment

• ```.find(key) != @end ```true, if container has 'key'
• ```.contains(key) ```true, if container has 'key' `C++20`
``````std::set<int> s {1,3,5,6};
if (s.find(6) != end(s)) {…}
if (s.find(7) != end(s)) {…}
if (s.contains(6)) {…}
if (s.contains(7)) {…}``````
``````
true
false
true
false``````

#### Find/Get Key PositionPosition

• ```.find(key) ````@position`, if '`key`' found or `@end` otherwise
``````std::set<int> s {1,3,5,6};
auto i = s.find(3);
if (i != end(s)) {
cout << *i;
i = s.erase(i);
}

auto j = s.find(4);
if (j != end(s)) {…}``````
``````{1, 3, 5, 6 }
i
true
3
{1, 5, 6 }
i (after)
{1, 5, 6 }
j
false``````

#### Access / Assign (maps only)`[key]→value`

• `[key] = value`(inserts key if not found)
• `.at(key) = value`(throws `std::out_of_range` if key not found)
``````std::map<int,std::string> m;
m[1] = "a";
m[2] = "b";
m[1] = "x";
try {
m.at(2) = "y";
m.at(3) = "z";
} catch(std::out_of_range&) {…}``````
``````{ }
{1:"a"}
{1:"a",2:"b"}
{1:"x",2:"b"}

{1:"x",2:"y"}
← throws exception``````

#### Count Key OccurrencesCount Key

• ```.count(key) ```→ number of occurrences of '`key`'

This makes most sense for containers that allow multiple equivalent keys, like e.g., `multiset` since for the non-multi associative containers the result will be either 0 or 1.

``````std::multiset<int> s {1,3,3,6,9};
cout << s.count(1);
cout << s.count(2);
cout << s.count(3);
std::map<int,std::string> m {{1,"a"},{3,"b"}};
cout << m.count(1);
cout << m.count(2);``````
``````
1
0
2

1
0``````

### Iterate Over ElementsIterate

It is not possible to modify keys through iterators or in range based for loops, because this could break the container invariant (key ordering or position in the hash table).

#### Range-Based `for` LoopsRange-for

``for (auto lightKey : mySet) {…}``
``for (auto const& heavyKey : mySet) {…}``
``for (auto const& keyValuePair : myMap) {…}``
``for (auto const& [key,value] : myMap) {…}  C++17``
``````// keys that are cheap to copy:
std::set<int> s1 { … };
for (auto key : s1) { … }
// keys that are expensive to copy:
std::set<std::string> s2 { … };
for (auto const& key : s2) { … }
// C++17: lightweight key-value pairs
std::map<int,std::string> m2 { … };
for (auto [key,value] : m2) {
cout << key <<":"<< value <<" "; }
// C++17: expensive-to-copy key-value pairs
std::map<int,std::string> m2 { … };
for (auto const& [key,value] : m2) {
cout << key <<":"<< value <<" "; }
// C++11: lightweight key-value pairs
std::map<int,std::string> m1 { … };
for (auto kv : m1) {
cout << kv.first <<":"<< kv.second <<" "; }
// C++11: expensive-to-copy key-value pairs
std::map<int,std::string> m1 { … };
for (auto const& kv : m1) {
cout << kv.first <<":"<< kv.second <<" "; }``````

#### Obtain Iterators (Forward Direction)Iterator

• ```container.begin() ````@first_element`
• ```container.end() ````@one_behind_last_element`
• ```std::begin(container) ````@first_element``C++11`
• ```std::end(container) ````@one_behind_last_element``C++11`

``````std::set<int> s {1,3,9};
auto i = begin(s);
const auto e = end(s);
cout << *i;
// go to next
++i;
cout << *i;``````
``````{1,3,9 }

i     e
1
{1,3,9 }

3``````
``````std::map<int,std::string> m {
{1,"a"}, {2,"b"}};
auto i = begin(m);
const auto e = end(m);
cout << i->first
<< i->second;
++i;
auto kvpair = *i;
cout << kvpair.first
<< kvpair.second;
auto [k,v] = *i;
cout << k <<" "<< v;``````
``````
{1:"a", 2:"b" }

i            e
1
"a"
{1:"a", 2:"b" }

2
"b"
C++17
2 "b"``````

#### Obtain Iterators (Reverse Direction)Reverse Dir.

Only available for ordered containers.

• ```container.rbegin() ````@last_element`
• ```container.rend() ````@one_before_first_element`
• ```std::rbegin(container) ````@last_element``C++11`
• ```std::rend(container) ````@one_before_first_element``C++11`

``````std::set<int> s {1,3,9};
auto i = rbegin(s);
const auto e = rend(s);
cout << *i;
// go to next
++i;
cout << *i;``````
``````{ 1,3,9}

e     i
9
{1,3,9 }

3``````
``````std::map<int,std::string> m {
{1,"a"}, {2,"b"}};
auto i = rbegin(m);
const auto e = rend(m);
cout << i->first
<< i->second;
++i;
auto kvpair = *i;
cout << kvpair.first
<< kvpair.second;
auto [k,v] = *i;
cout << k <<" "<< v;``````
``````
{ 1:"a", 2:"b"}

e        i
2
"b"
{ 1:"a", 2:"b"}

1
"a"
C++17
1 "a"``````

### Get Range of Equivalent KeysGet Ranges

• ```.equal_range(key) ````pair<@range_begin,@range_end>`

This follows the usual iterator range convention, so `@range_end` points to one behind the last element in the range.

``````std::multiset<int> s {2,4,4,4,6};
// 4 is a non-unique key:
auto e4 = s.equal_range(4);
cout << *(e4.first)
<< *(e4.second);
auto n = distance(e4.first,
e4.second);
// 1 is smaller than all:
auto e1 = s.equal_range(1);
// → empty range
// 2 is the smallest key:
auto e2 = s.equal_range(2);
// → range with 1 element
// 3 is in between keys:
auto e3 = s.equal_range(3);
// → empty range
// 6 is the largest key:
auto e6 = s.equal_range(6);
// → range with 1 element
// 7 is larger than all:
auto e7 = s.equal_range(7);
// → empty range``````
``````
{2,4,4,4,6 }

4  (first in range)
6  (1 behind last)
n: 3  (range size)

{2,4,4,4,6 }

{2,4,4,4,6 }

{2,4,4,4,6 }

{2,4,4,4,6 }

{2,4,4,4,6 }
``````

### Get Upper/Lower Key Bound PositionsGet Upper/Lower Key BoundsGet Bounds

• ```.lower_bound(key) ````@first_not_less_than_key`
• ```.upper_bound(key) ````@first_greater_than_key`
``````std::multiset<int> s {2,4,4,4,6};
// 1 is smaller than all:
auto l1 = s.lower_bound(1);
auto u1 = s.upper_bound(1);
if (l1 != end(s)) cout << *l1;
if (u1 != end(s)) cout << *u1;
// 2 is the smallest key:
auto l2 = s.lower_bound(2);
auto u2 = s.upper_bound(2);
if (l2 != end(s)) cout << *l2;
if (u2 != end(s)) cout << *u2;
// 3 is in between keys:
auto l3 = s.lower_bound(3);
auto u3 = s.upper_bound(3);
if (l3 != end(s)) cout << *l3;
if (u3 != end(s)) cout << *u3;
// 4 is a non-unique key:
auto l4 = s.lower_bound(4);
auto u4 = s.upper_bound(4);
if (l4 != end(s)) cout << *l4;
if (u4 != end(s)) cout << *u4;
// 6 is the largest key:
auto l6 = s.lower_bound(6);
auto u6 = s.upper_bound(6);
if (l6 != end(s)) cout << *l6;
if (u6 != end(s)) cout << *u6;
// 7 is larger than all:
auto l7 = s.lower_bound(7);
auto u7 = s.upper_bound(7);
if (l7 != end(s)) cout << *l7;
if (u7 != end(s)) cout << *u7;``````
``````
{2,4,4,4,6 }

true  → 2
true  → 2
{2,4,4,4,6 }

true  → 2
true  → 4
{2,4,4,4,6 }

true  → 4
true  → 4
{2,4,4,4,6 }

true  → 4
true  → 6
{2,4,4,4,6 }

true  → 6
false @end
{2,4,4,4,6 }

false @end
false @end``````

### Get Size / Query EmptinessSize/Empty

• ```container.empty() ```true, if container has no keys
• ```container.size() ```total number of keys or key-value pairs
• ```std::empty(container) ```true | false`C++17`
• ```std::size(container) ```→ #(keys/key-value pairs) `C++17`
``````std::map<int;std::string> m;
cout << m.empty();
cout << m.size();
m.insert(3,"x");
cout << m.empty();
cout << m.size();
m.insert(1,"y");
cout << m.size();``````
``````{ }
true
0
{3:"x"}
false
1
{1:"y",3:"x"}
2``````

### Erase Elements / RangesErase

#### Erase A Single Key / Key-Value PairSingle

• ```.erase(key) ```number of deleted keys/key-value pairs
``````std::multiset<int> s {1,3,3,7,9};
auto n = s.erase(3)
cout << n;
s.erase(7)``````
``````{1,3,3,7,9}
{1,7,9}
2
{1,9}``````

#### Erase With Iterator (Ranges)Iterator(Range)

• ```.erase(@position) ````@behind_deleted`
• ```.erase(@range_begin,@range_end) ````@behind_last_deleted`
``````std::set<int> s {1,3,6,8,9};
auto i = s.find(3);
i = s.erase(i);

auto j = s.erase(begin(s), s.find(8));``````
``````{1,3,6,8,9}
i
{1,6,8,9}
i (after)
{1,6,8,9}

{8,9}
j``````

#### Erase EverythingEverything

• ```.clear() ```
``````std::set<int> s {1,2,5,8};
s.clear();
s.empty();``````
``````{1,2,5,8}
{ }
true``````

### Extract & (Re-)Insert NodesExtract/(Re-)InsertNodesC++17

• ```.extract(key) ````node`
• ```.extract(@position) ````node`
• ```.insert(node) ````@insert_position`

Important Member Functions:

• `.key() ``key_type&`
• `.mapped()``mapped_type&`

#### Transfer Key(-Value Pair) Between Sets/MapsTransfer

… without copying or moving key/value objects

``````set<string> s {"a","b","e"};
set<string> t {"x","z"};
t.insert(s.extract("a"));``````
``````s: {"a","b","e"}
t: {"x","z"}
s: { "b","e"}
t: {"a","x","z"}``````

#### Change Keys Without Copying ItChange Key

``````set<string> s {"a","c","e"};
auto na = s.extract("a");
na.key() = "z";
// move node back in
s.insert(std::move(na));
map<int,string> m {  {2,"a"},{3,"x"}};
auto n2 = m.extract(2);
n2.key() = 5;
// move node back in
m.insert(std::move(n2));``````
``````{"a","c","e"}
get node
change key

{"c","e","z"}
{2:"a",3:"x"}
get node
change key

{3:"x",5:"a"}``````

### Copy & Assign Entire Sets/MapsCopy & AssignCopy/Assign

creates a new container object and copies all contained keys & values
all contained objects are copied from source to assignment target

Copying / copy-assigning sets or maps might be expensive, if they contain a large number of elements!

``````std::set<int> a {4,7,1,9};
std::set<int> b {1,2,3};
bool equal1 = (a == b);
// copy assignment:
a = b;
bool equal2 = (a == b);
b.clear();
bool equal3 = (a == b);
// ways of making copies:
std::set<int> a2 {a};
std::set<int> a3 (a);
std::set<int> a4 = a;
auto a5 {a};
auto a6 (a);
auto a7 = a;``````
``````a: {4,7,1,9}
b: {1,2,3}
false

a: {1,2,3}
true
b: {}  a: {1,2,3}
false

a2: {1,2,3}
a3: {1,2,3}
a4: {1,2,3}
a5: {1,2,3}
a6: {1,2,3}
a7: {1,2,3}``````
• ```assign(@keys_begin, @keys_end) ```
``````std::set<int> s {1,6};
vector<int> keys {2,7,3,0};
s.assign(begin(keys)+1,
end(keys));``````
``````s: {1,6}
2730

s: {0,3,7}``````

### Compare Entire Sets/Maps

comparing two associative containers compares the contained keys / key-value pairs

two associative containers are equal, if their key(-value) content is equal

``````std::set<int> s1 {1,2,7,8,9};
std::set<int> s2 {1,4,5};
bool s1_equals_s2  = (s1 == s2);  // false
bool s1_uenqual_s2 = (s1 != s2);  // true
bool s1_smaller_s2 = (s1 <  s2);  // true
bool s1_greater_s2 = (s1 >  s2);  // false
std::map<int,std::string> m1 {{1,"z"},{2,"f"},{7,"b"}};
std::map<int,std::string> m2 {{1,"a"},{3,"x"}};
bool m1_equals_m2  = (m1 == m2);  // false
bool m1_unequal_m2 = (m1 != m2);  // true
bool m1_smaller_m2 = (m1 <  m2);  // true
bool m1_greater_m2 = (m1 >  m2);  // false``````

### Merge Entire Sets/MapsC++17

Integrate nodes from source into target without copying keys or values:

• ```target.merge(source) ```

Runtime complexity:  source.size() ⋅ log(target.size() + source.size()))

``````set<string> s {2,7};
set<string> t {1,5,8,9};
t.merge(s);``````
``````s: {2,7}
t: {1,5,8,9}
s: { }
t: {1,2,5,7,8,9}``````

### Inspect/Control Hash TableHash

#### (unordered sets & maps only)

Note that the exact number of hash buckets as a function of the number of inserted elements is not standardized and depends on the standard library implementation.

#### Check & Control Hash Table SizeTable

• ```.size() ```→ #elements  (#keys/key-value pairs)
• `.reserve(#elements)`   make space for at least '#elements' (might trigger rehash)
• ```.bucket_count() ```→ #hash_table_buckets
• ```.bucket_size(bucket_index) ```→ #elements_in_bucket
• ```.load_factor() ```→ #non_empty_buckets / #bucket_count
• `.rehash(new_min_bucket_count)`(also takes max_load_factor into account)
``````unordered_map<int,string> m { {6,"x"},{4,"a"},{7,"n"},{2,"z"} };
cout
<< m.size()         // 4
<< m.bucket_count() // 5
<< m.bucket_size(1) // 1
<< m.bucket_size(2) // 0
<< m.bucket_size(3) // 2
<< m.load_factor(); // 0.6 = 3/5``````
``````unordered_map<int,string> m { {6,"x"},{4,"a"},{7,"n"},{2,"z"} };
// set to at least 7 buckets:
m.rehash(7);
cout
<< m.size()         // 4
<< m.bucket_count() // 7
<< m.bucket_size(1) // 1
<< m.bucket_size(2) // 0
<< m.load_factor(); // 0.57 = 4/7``````

• ```.load_factor() ```→ #occupied_slots / #all_slots
• ```.max_load_factor() ```→ max_allowed_load_factor
• `.max_load_factor(new_maximum)` (might trigger rehash)
``````unordered_set<int> s {1,3,5,8,9};
// set new maximum:
s.rehash(10);
``````
1.0
1.0

might trigger rehash
force rehash
0.3846``````

#### Access or Iterate Over Hash BucketsIterate

• ```.bucket(key) ```index_of_bucket_with_key
• ```.bucket_size(bucket_index) ```→ number_of_nodes_in_bucket
• ```.begin(bucket_index) ````@bucket_begin`
• ```.end(bucket_index) ````@bucket_end`
• ```.cbegin(bucket_index) ````const@bucket_begin`
• ```.cend(bucket_index) ````const@bucket_end`
``````unordered_set<int> s {1,3,5,8,9};
// get bucket with key 3
const auto b = s.bucket(3);
// iterate over keys in bucket
for (auto i = s.begin(b); i != s.end(b); ++i) {
cout << *i;
}``````

### Get Types: Key / Value/…Types

``````using set_t = std::map<double>;
set_t::size_type i = 0;  // std::size_t
set_t::key_type{0} k = 0;   // double
set_t::value_type{0} v = 0; // double
using map_t = std::map<int,std::string>;
map_t::key_type{0} k = 0;    // int
map_t::mapped_type{0} m = 0; // string
map_t::value_type{0,"a"} v {1,"a"}; // pair<const int,string>``````

### Make Keys OrderableOrder Keys

if `a == b` is true,  i.e., their values are the same

if `!(a < b) && !(b < a)` is true,  i.e., neither one is ordered before the other

The C++ standard library uses equivalence based on less than for ordering objects (according to a strict weak ordering).

• `set<Key,KeyComp>,`
• `map<Key,Mapped,KeyComp>, …`

The type `KeyComp` needs to provide a public member function

``bool operator() (Key const&, Key const&) const``

which returns `true`, if the first argument should be ordered before the second. The default is `std::less<Key>`.

``````std::set<int,std::greater<>> s;
s.insert({1,5,3,2});
s.insert(4);
// get comparator copy
auto kc = s.key_comp();
cout << kc(4,2);``````
``````C++98-11: std::greater<int>
s: {5,3,2,1}
s: {5,4,3,2,1}

true``````
``````// custom key type
struct P2 {
P2(int x_, int y_): x{x_}, y{y_} {}
int x, y;
};
// comparator function object
struct P2_less {
constexpr bool operator ()
(P2 const& l, P2 const& r) const noexcept {
if (l.x < r.x) return true;
return (l.y < r.y);
}
};``````
``````std::set<P2,P2_less> s;
s.insert( P2{1,2} );
s.emplace(3,4);``````
``````s: { }
s: {{1,2}}
s: {{1,2},{3,4}}``````

You should only do that

• if objects of your type can be ordered in a way that is natural & unambiguous
• if you can at least provide a strict weak ordering

### Make Keys HashableHash Keys

• `set<Key,Hasher>,`
• `map<Key,Mapped,Hasher>, …`

The type `Hasher` needs to provide a public member function

``std::size_t operator() (Key const&) const``

which returns the hash value (= an unsigned index) for a given key. The default is `std::hash<Key>`.

``````struct TM_hash {
// 32bit integer hash by T. Mueller
constexpr std::size_t
operator () (std::uint32_t k) const noexcept {
k = ((k >> 16) ^ k) * 0x45d9f3b;
k = ((k >> 16) ^ k) * 0x45d9f3b;
k = ((k >> 16) ^ k);
return k;
}
};
// make set with custom hasher
std::unordered_set<std::uint32_t,TM_hash> s;
…
// get copy of hasher from set
auto h = s.hasher();``````
``````// custom key type
class A { … };
// hasher function class
struct A_hash {
std::size_t operator () (A const& k) const noexcept {
… // suitable hash function
}
};
// make set with custom hasher
std::unordered_set<A,A_hash> s;
…``````

## Cheat Sheets

(click for fullscreen view)

(click for fullscreen view)

(click for fullscreen view)

(click for fullscreen view)

(click for fullscreen view)