Imagine you create a program that tracks unique IP addresses accessing some website or a gaming inventory to prevent collecting duplicate quest items. Using a vector means that you will need to perform a sequential search to find an element in the list, which gets more time consuming as the number of elements increases. As a result, your search time complexity is linear, meaning that a million of items will take a million of comparisons. In order to solve this problem, the C++ Standard Library offers ordered and unordered sets, which store only unique elements and allow for extremely efficient search.
An ordered set container template guarantees the uniqueness of elements and automatically keeps them sorted. If you try to insert an element which is already contained in the set, the container silently ignores the insertion attempt. Take a look at an example of using an ordered set to organize usernames:
#include <iostream>
#include <set>
int main() {
std::set<std::string> unique_usernames;
// Insert elements
unique_usernames.insert("charlie");
unique_usernames.insert("alice");
unique_usernames.insert("bob");
unique_usernames.insert("alice"); // Duplicate, will be ignored
// Elements are automatically sorted alphabetically
for (const auto& name : unique_usernames) {
std::cout << name << " ";
}
std::cout << "\n";
return 0;
}An ordered set contains unique keys in comparator order and normally provides logarithmic lookup. An unordered set hashes keys to buckets using a hash function and normally provides average constant-time lookup. The unordered variant makes no iteration-order promise, and may move elements around on rehash.
Inside, the ordered set is typically implemented as a balanced binary search tree (usually red-black). This gives it logarithmic times of searching, inserting and removing elements. With one million of elements, you will perform only about twenty comparisons to find an element, which makes ordered sets much more suitable for searches compared to vectors.
At some cases, you will need unique keys and fast lookups provided by a set, but you will not care about the ordering of the elements. Maintenance of the sorted tree structure introduces unnecessary performance overheads on every insertion and removal. For this reason, the C++ Standard Library offers an unordered set. Instead of a tree, an unordered set stores its elements in the hash table. Using a hash value of an element, it finds its storage location, thus achieving average constant time complexity of all operations, including lookups, inserts and removals.
The example below demonstrates how to perform searching for elements and existence checks in unordered sets using the traditional search member function and modern membership-checking member function:
Both containers define their keys identity using supplied policies. A set considers two keys identical if none of them compares less than another. An unordered set demands equal keys to produce identical hash values. A user-defined equality comparison and a hasher must describe the same notion of identity or else the search might fail to locate a seemingly equal element.
#include <iostream>
#include <unordered_set>
int main() {
std::unordered_set<int> prime_numbers{ 2, 3, 5, 7, 11 };
// Check if an element exists using find()
int search_value = 5;
auto it = prime_numbers.find(search_value);
if (it != prime_numbers.end()) {
std::cout << search_value << " is in the set.\n";
} else {
std::cout << search_value << " is not in the set.\n";
}
// C++20 contains() returns a simple boolean
if (prime_numbers.contains(13)) {
std::cout << "13 is in the set.\n";
} else {
std::cout << "13 is not in the set.\n";
}
return 0;
}While inserting an element into a set or an unordered set, you may need to learn whether an insertion has been successful or the value was simply ignored due to existence. The insert operation provides this information by returning a pair. The first element of this pair is an iterator to either the newly inserted or the pre-existing element. The second element is a boolean that is true in case of the success of insertion, and false otherwise.
#include <iostream>
#include <set>
int main() {
std::set<int> scores;
auto result1 = scores.insert(100);
std::cout << "Inserted 100: " << std::boolalpha << result1.second << "\n";
auto result2 = scores.insert(100);
std::cout << "Inserted 100 again: " << result2.second << "\n";
return 0;
}Technical rules which should be kept in mind while working with sets are identical in both ordered and unordered variants: the elements of the containers are read-only. The container uses the exact value of every element to keep either a sorted tree or hash buckets. Modifying an element in place will corrupt the internal state of the container, therefore, dereferencing a set iterator always gives a constant reference. In case you need to update an existing element, you will need to erase it using the erasure member function, update the value and insert it into the container.
Exercise: std::set and std::unordered_setStarter code, hints and solutionOpenClose
Practice: std::set and std::unordered_set
Work through the mission, reveal hints only when needed, and compare your result with the model solution.
Your challenge
Insert 13 before the membership checks and print the set size. Predict both lookup results without assuming an iteration order.
Mission checklist
- Run the starter as a baseline, then predict the change requested in Your challenge.
- Make that change in your editor; use the lesson-specific hints if you need help.
- Compile and run your answer, then compare with the worked solution and explain the result.
Starter program
This is the working baseline, not the completed answer. Compile as C++20, then make the change described above.
#include <iostream>
#include <unordered_set>
int main() {
std::unordered_set<int> prime_numbers{ 2, 3, 5, 7, 11 };
// Check if an element exists using find()
int search_value = 5;
auto it = prime_numbers.find(search_value);
if (it != prime_numbers.end()) {
std::cout << search_value << " is in the set.\n";
} else {
std::cout << search_value << " is not in the set.\n";
}
// C++20 contains() returns a simple boolean
if (prime_numbers.contains(13)) {
std::cout << "13 is in the set.\n";
} else {
std::cout << "13 is not in the set.\n";
}
return 0;
}Hints
find returns end() when a key is absent; contains directly returns a Boolean. Both checks examine membership, not a sorted position.
Insert 13 before its contains check and compare the branch. Inserting a duplicate such as 5 does not add another element to a set, and unordered_set iteration order is not promised.
Worked solution
Inserting 13 before the lookups adds one unique element and makes the contains(13) branch succeed. The added size is 6; no iteration order is assumed for unordered_set.
#include <iostream>
#include <unordered_set>
int main() {
std::unordered_set<int> prime_numbers{ 2, 3, 5, 7, 11 };
// Check if an element exists using find()
prime_numbers.insert(13);
int search_value = 5;
auto it = prime_numbers.find(search_value);
if (it != prime_numbers.end()) {
std::cout << search_value << " is in the set.\n";
} else {
std::cout << search_value << " is not in the set.\n";
}
// C++20 contains() returns a simple boolean
if (prime_numbers.contains(13)) {
std::cout << "13 is in the set.\n";
} else {
std::cout << "13 is not in the set.\n";
}
std::cout << "Set size: " << prime_numbers.size() << '\n';
return 0;
}
Example output
5 is in the set.
13 is in the set.
Set size: 6
0 comments
No comments yet. Be the first.