Home | Projects | Notes > C++ Programming > Associative Container - std::map, std::multimap, std::unordered_map, std::unordered_multimap

Associative Container - std::map, std::multimap, std::unordered_map, std::unordered_multimap

The STL Maps

Associative Containers

• Collections of stored objects that allow fast retrieval using a key.

• The STL provides sets and maps for this purpose.

• Typically implemented as a balanced binary search tree (e.g., red-black tree) or a hash table.

• Most operations are very efficient.

4 Types of Maps

• std::map - By far the most widely used of all types of sets.

• std::unordered_map

• std::multimap

• std::unordered_multimap

std::map

• Declared in the <map> header file.

• Similar concept to a dictionary.

• Elements are stored as Key-Value pairs (std::pair)

• Ordered by key.

• Duplicate elements are NOT allowed. (Keys are unique.)

• Allows direct access to the elements using the key.

• All iterators are available but may become invalid when the corresponding element is deleted.

Initialization

12
1
// Initialization
2
std::map<std::string, int> m1{
3
    {"Kyungjae", 30},
4
    {"Sunny", 20}
5
};
6

7
// Initialization
8
std::map<std::string, std::string> m2{
9
    {"Kyungjae", "Engineer"},
10
    {"Sunny", "Designer"},
11
    {"Yena", "Student"}
12
};

Common Methods

Like sets, maps do not support the concept of front and back.

For more information, see cppreference.com.

31
1
std::map<std::string, std::string> m{
2
    {"Kyungjae", "Engineer"},
3
    {"Sunny", "Designer"},
4
    {"Yena", "Student"}
5
};
6

7
std::cout << m.size();          // 3
8
std::cout << m.max_size();      // A very large number
9

10
std::pair<std::string, std::string> p{"Nina", "Baby"};
11
m.insert(p);
12

13
m.insert(std::make_pair("Jaesoo", "Professor"));
14

15
m["Hyera"] = "Teacher";         // insert
16

17
m["Hyera"] = "Dancer";          // update value
18
m.at("Hyera") = "Cook";         // update value
19

20
m.erase("Sunny");               // erase Sunny
21

22
if (m.find("Yena") != m.end())  // find Yena
23
    std::cout << "Found Yena!";
24

25
auto it = m.find("Kyungjae");
26
if (it != m.end())
27
    m.erase(it);                // erase Kyungjae
28

29
int n = m.count("Nina");        // 1 (0 or 1 based on the presence of the element)
30
m.clear();                      // remove all elements
31
m.empty();                      // true (true or false depending on the emptiness)

L22: Notice that the std::map's find() method is different from the std::find() method in the STL <algorithm> library. You should use std::map's find() because it knows all about the internal implementation of the std::map, and it's going to be much more efficient.

std::multimap

• Also declared in the <map> header file.

• Ordered by key.

• Duplicate elements are allowed.

• Allows direct access to the elements using the key.

• All iterators are available.

std::unordered_map

• Declared in the <unordered_map> header file.

• Elements are unordered.

• Duplicate elements are NOT allowed.

• Reverse iterators are not supported.

std::unordered_multimap

• Declared in the <unordered_map> header file.

• Elements are unordered.

• Duplicate elements are allowed.

• Reverse iterators are not supported.

Project: Usage of std::map

Ensure that your custom classes provide the following three elements to work correctly with the STL:

• Overloaded default constructor

• Overloaded operator<

• Overloaded operator==

102
1
#include <iostream>
2
#include <map>
3
#include <set>
4

5
void print(const std::map<std::string, std::set<int>> &m)
6
{
7
    std::cout << "[ ";
8
    for (const auto &m_elem : m)
9
    {
10
        std::cout << m_elem.first << ": [ ";
11
        for (const auto &s_elem : m_elem.second)
12
        {
13
            std::cout << s_elem << " ";
14
        }
15
        std::cout << "] ";
16
    }
17
    std::cout << "]" << std::endl;
18
}
19

20
template <typename T1, typename T2>
21
void print(const std::map<T1, T2> &m)
22
{
23
    std::cout << "[ ";
24
    for (const auto &elem: m)
25
    {
26
        std::cout << elem.first << ":" << elem.second << " ";
27
    }
28
    std::cout << "]" << std::endl;
29
}
30

31
// insert(), std::make_pair(), [], count(), find(), clear()
32
void test1(void)
33
{
34
    std::cout << "\nTEST1" << std::endl;
35

36
    std::map<std::string, int> m{
37
        {"Kyungjae", 30},
38
        {"Sunny", 20},
39
        {"Yena", 5}
40
        // elements will be ordered by key; std::string in this case
41
    };
42
    print(m);
43

44
    m.insert(std::pair<std::string, int>("Nina",1));
45
    print(m);
46

47
    // make_pair() will figure out the types based on the passed values
48
    m.insert(std::make_pair("Hyera", 50));
49
    print(m);
50

51
    m["Jaesoo"] = 60;
52
    print(m);
53

54
    m["Jaesoo"] += 1;
55
    print(m);
56

57
    m.erase("Jaesoo");
58
    print(m);
59

60
    std::cout << "Count for Hyera: " << m.count("Hyera") << std::endl;
61
    std::cout << "Count for Jaesoo: " << m.count("Jaesoo") << std::endl;
62

63
    auto it = m.find("Nina");
64
    if (it != m.end())
65
    {
66
        std::cout << "Found: " << it->first << ":" << it->second << std::endl;
67
    }
68

69
    m.clear();
70
    print(m);
71
}
72

73
// insert(), find()
74
void test2(void)
75
{
76
    std::cout << "\nTEST2" << std::endl;
77

78
    std::map<std::string, std::set<int>> m{
79
        {"Kyungjae", {60, 90}},
80
        {"Sunny", {80}},
81
        {"Yena", {70, 90, 100}}
82
        // elements will be ordered by key; std::string in this case
83
    };
84
    print(m);
85

86
    m["Kyungjae"].insert(85);   // insert 85 into Kyungjae's set
87
    print(m);
88

89
    auto it = m.find("Yena");
90
    if (it != m.end())
91
    {
92
        it->second.insert(1000);    // insert 1000 into Yena's set
93
    }
94
    print(m);
95
}
96

97
int main(int argc, char *argv[])
98
{
99
    test1();
100
    test2();
101
    return 0;
102
}

1
17
1

2
TEST1
3
[ Kyungjae:30 Sunny:20 Yena:5 ]
4
[ Kyungjae:30 Nina:1 Sunny:20 Yena:5 ]
5
[ Hyera:50 Kyungjae:30 Nina:1 Sunny:20 Yena:5 ]
6
[ Hyera:50 Jaesoo:60 Kyungjae:30 Nina:1 Sunny:20 Yena:5 ]
7
[ Hyera:50 Jaesoo:61 Kyungjae:30 Nina:1 Sunny:20 Yena:5 ]
8
[ Hyera:50 Kyungjae:30 Nina:1 Sunny:20 Yena:5 ]
9
Count for Hyera: 1
10
Count for Jaesoo: 0
11
Found: Nina:1
12
[ ]
13

14
TEST2
15
[ Kyungjae: [ 60 90 ] Sunny: [ 80 ] Yena: [ 70 90 100 ] ]
16
[ Kyungjae: [ 60 85 90 ] Sunny: [ 80 ] Yena: [ 70 90 100 ] ]
17
[ Kyungjae: [ 60 85 90 ] Sunny: [ 80 ] Yena: [ 70 90 100 1000 ] ]