Home | Projects | Notes > C++ Programming > Associative Container - std::set, std::multiset, std::unordered_set, std::unordered_multiset

Associative Container - std::set, std::multiset, std::unordered_set, std::unordered_multiset

The STL Sets

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 Sets

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

• std::unordered_set

• std::multiset

• std::unordered_multiset

std::set

• Declared in the <set> header file.

• Similar concept to a mathematical set.

• Ordered by key.

• Duplicate elements are NOT allowed.

• Does not allow direct access to the elements. ([] and at() not supported.)

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

Initialization and Assignment

12
1
// Initialization
2
std::set<int> s1{1, 2, 3, 4, 5};
3

4
// Initialization
5
std::set<std::string> s2{
6
    std::string{"Kyungjae"},
7
    "Sunny",    // C-style string will be converted to a std::string.
8
    std::string{"Yena"}
9
};
10

11
// Assignment via initializer list
12
s1 = {2, 4, 6, 8, 10};

Common Methods

Sets have no concept of front and back. Also, they don't allow direct access to the elements using [] or at().

For more information, see cppreference.com.

8
1
std::set<int> s{4, 1, 1, 3, 3, 2, 5};   // 1, 2, 3, 4, 5
2
    // This will not cause an error. The duplicates are simply ignored
3
    // and we end up with a proper set which is also ordered.
4

5
std::cout << s.size();      // 5
6
std::cout << s.max_size();  // A very large number
7

8
s.insert(7);                // 1, 2, 3, 4, 5, 7 - added in order

6
1
person p1{"Kyungjae", 30};
2
person p2{"Sunny", 20};
3
std::set<person> s;
4

5
s.insert(p1);               // adds p1 to the set if it's not present in the set
6
auto result = s.insert(p2); // adds p2 to the set if it's not present in the set

L6: std::set uses an overloaded operator< for ordering, and returns a std::pair<iterator, bool>:

• first is an interator to the inserted element or to the duplicate element already in the set.

• second is a boolean indicating success or failure.

13
1
std::set<int> s{1, 2, 3, 4, 5};
2

3
s.erase(3);         // erase 3 - 1, 2, 4, 5
4

5
auto it = s.find(5);
6
if (it != s.end())
7
{
8
    s.erase(it);    // erase 5 - 1, 2, 4
9
}
10

11
int n = s.count(1); // 1 (0 or 1 based on the presence of the element)
12
s.clear();          // remove all elements
13
s.empty();          // true (true or false depending on the emptiness)

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

std::multiset

• Also declared in the <set> header file.

• Ordered by key.

• Duplicate elements are allowed.

• Does not allow direct access to the elements. ([] and at() not supported.)

• All iterators are available.

std::unordered_set

• Declared in the <unordered_set> header file.

• Elements are unordered.

• Duplicate elements are NOT allowed.

• Elements cannot be modified directly in place and they must be erased and re-inserted. (This is due to the way that std::unordered_set is implemented.)

• Reverse iterators are not supported.

std::unordered_multiset

• Declared in the <unordered_set> header file.

• Elements are unordered.

• Duplicate elements are allowed.

• Reverse iterators are not supported.

Project: Usage of std::set

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

• Overloaded default constructor

• Overloaded operator<

• Overloaded operator==

142
1
#include <iostream>
2
#include <set>
3

4
class person
5
{
6
public:
7
    person() : name{"Unkown"}, age{0} {}    // will be useful when resizing happens
8
    person(std::string name, int age)
9
        : name{name}, age{age}
10
    {}
11
    bool operator<(const person &rhs) const
12
    {
13
        return this->age < rhs.age;
14
    }
15
    bool operator==(const person &rhs) const 
16
    {
17
        return (this->name == rhs.name && this->age == rhs.age);
18
    }
19
    
20
private:
21
    friend std::ostream& operator<<(std::ostream &os, const person &p);
22
    std::string name;
23
    int age;
24
};
25

26
// Overloading the insertion operator as a global function.
27
std::ostream& operator<<(std::ostream &os, const person &p)
28
{
29
    os << p.name << ":" << p.age;
30
    return os;
31
}
32

33
// Template function to print elements of any list.
34
template <typename T>
35
void print(const std::set<T> &s)
36
{
37
    std::cout << "[ ";
38
    for (const auto &elem : s)
39
    {
40
        std::cout << elem << " ";
41
    }
42
    std::cout << "]" << std::endl;
43
}
44

45
// insert(), count(), find(), cleear()
46
void test1(void)
47
{
48
    std::cout << "\nTEST1" << std::endl;
49

50
    std::set<int> s{1, 4, 3, 5, 2};
51
    print(s);
52

53
    s = {1, 2, 3, 1, 1, 2, 2, 3, 3, 4, 5};  // duplicates will be ignored
54
    print(s);
55

56
    s.insert(0);
57
    s.insert(10);
58
    print(s);
59

60
    if (s.count(10))
61
    {
62
        std::cout << "10 is in the set." << std::endl;
63
    }
64
    else
65
    {
66
        std::cout << "10 is NOT in the set." << std::endl;
67
    }
68

69
    auto it = s.find(5);    // this is std::set's find(), not the std::find()
70
    if (it != s.end())
71
    {
72
        std::cout << "Found: " << *it << std::endl;
73
    }
74

75
    s.clear();
76
}
77

78
// emplace(), find(), erase(), 
79
void test2(void)
80
{
81
    std::cout << "\nTEST2" << std::endl;
82

83
    std::set<person> s{
84
        {"Kyungjae", 30},
85
        {"Sunny", 20},
86
        {"Yena", 5}
87
    };
88
    print(s);   // the order is determined by the overloaded 'operator<'
89

90
    s.emplace("Nina", 1);
91
    print(s);
92

93
    s.emplace("Theo", 1);    // NO! 1 already exists (uses 'operator<')
94
    print(s);
95

96
    auto it = s.find(person{"Sunny", 20});
97
    if (it != s.end())
98
    {
99
        s.erase(it);
100
    }
101
    print(s);
102

103
    it = s.find(person("XXX", 1)); // will remove Nina (uses 'operator<')
104

105
    if (it != s.end())
106
    {
107
        s.erase(it);
108
    }
109
    print(s);
110
}
111

112
// Shows what happens when an element is inserted into a set.
113
void test3(void)
114
{
115
    std::cout << "\nTEST3" << std::endl;
116

117
    std::set<std::string> s{"A", "B", "C"};
118
    print(s);
119

120
    // Successful insertion
121
    auto result = s.insert("D");    // result - std::pair<iterator, bool>
122
    print(s);
123
    std::cout << std::boolalpha;
124
    std::cout << "first: " << *(result.first) << std::endl;
125
    std::cout << "second: " << result.second << std::endl;
126
    std::cout << std::endl;
127

128
    // Failed insertion
129
    result = s.insert("A");         // result - std::pair<iterator, bool>
130
    print(s);
131
    std::cout << std::boolalpha;
132
    std::cout << "first: " << *(result.first) << std::endl;
133
    std::cout << "second: " << result.second << std::endl;
134
}
135

136
int main(int argc, char *argv[])
137
{
138
    test1();
139
    test2();
140
    test3();
141
    return 0;
142
}

24
1

2
TEST1
3
[ 1 2 3 4 5 ]
4
[ 1 2 3 4 5 ]
5
[ 0 1 2 3 4 5 10 ]
6
10 is in the set.
7
Found: 5
8

9
TEST2
10
[ Yena:5 Sunny:20 Kyungjae:30 ]
11
[ Nina:1 Yena:5 Sunny:20 Kyungjae:30 ]
12
[ Nina:1 Yena:5 Sunny:20 Kyungjae:30 ]
13
[ Nina:1 Yena:5 Kyungjae:30 ]
14
[ Yena:5 Kyungjae:30 ]
15

16
TEST3
17
[ A B C ]
18
[ A B C D ]
19
first: D
20
second: true
21

22
[ A B C D ]
23
first: A
24
second: false