Beginner's Guide
    First Steps
    Input & Output
    Custom Types – Part 1
    Diagnostics
    Standard Library – Part 1
    Function Objects
    Standard Library – Part 2
    Code Organization
    Custom Types – Part 2
    Generic Programming
    Memory Management
    Software Design Basics

    Standard Associative Containers Associative Containers Set/Map

    Quick Overview Overview

    Sets

    #include <set>

    internal structure of std::set

    #include <unordered_set>

    internal structure of std::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 Maps Maps

    #include <map>

    internal structure of std::map

    #include <unordered_map>

    internal structure of std::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::map<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-Based Sets & Maps Are Node-Based Nodes

    usually implemented as balanced binary tree

    internal structure of std::map

    implemented as hash table

    internal structure of std::unordered_map

    Interface: How To How To

    Make New Sets / Maps Make

    Make An Empty Set / Map Empty

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

    This is a function declaration:

    std::set<int> s3 ();

    Make Sets From Key Lists From 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 Ranges From 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: 
    • 2
    • 3
    • 1
    • 4
    s: {1,2,3}

    Insert Keys Into Sets Sets: Insert Keys Set Insert

    Insert Single Keys Single

    • .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-Place Emplace C++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 Keys Ranges

    • .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 Hint With 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 Maps Maps: Insert Keys+Values Map Insert

    Insert Single Key-Value Pairs Single

    • .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-Place Emplace

    • .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 Pairs Ranges

    • .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 Hint With 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 Keys Find/Access/Query/Count Keys Query

    Check If Set/Map Contains Key Containment

    • .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 Position Position

    • .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 Occurrences Count 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 Elements Iterate

    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 Loops Range-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: leightweight 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_elementC++11
    • std::end(container) @one_behind_last_elementC++11

    If you are not familiar with what iterators are, please refer to this article .

    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_elementC++11
    • std::rend(container) @one_before_first_elementC++11

    If you are not familiar with what reverse iterators are, please refer to this article .

    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 Keys Get 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 Positions Get Upper/Lower Key Bounds Get 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 Emptiness Size/Empty

    • container.empty() true, if container has no keys
    • container.size() total number of keys or key-value pairs
    • std::empty(container) true | falseC++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 / Ranges Erase

    Erase A Single Key / Key-Value Pair Single

    • .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 Everything Everything

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

    Extract & (Re-)Insert Nodes Extract/(Re-)Insert Nodes C++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/Maps Transfer

    … 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 It Change 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); m.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/Maps Copy & Assign Copy/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}
    
    • 2
    • 7
    • 3
    • 0
    s: {0,3,7}

    Compare Entire Sets/Maps Compare

    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_unqual_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/Maps Merge Sets/Maps Merge C++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 Table Hash

    (unordered sets & maps only)

    Check & Control Hash Table Size Table

    • .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
    internal structure of std::unordered_map - hash table example 1
    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
    internal structure of std::unordered_map - hash table example 2

    Check & Control Load Factor Load Factor

    • .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};
    cout << s.load_factor();
    cout << s.max_load_factor();
    // set new maximum:
    cout << s.max_load_factor(0.8);
    s.rehash(10);
    cout << s.load_factor();
    
    1.0
    1.0
    
    might trigger rehash
    force rehash
    0.3846

    Access or Iterate Over Hash Buckets Iterate

    • .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 Orderable Order Keys

    if == 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 Hashable Hash 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; …