(Optional) Introduction to Sets & Maps

C++ contains two versions of sets and maps; one using sorting and the other using hashing.

Sets

A set is a collection of elements that contains no duplicates.

Unordered Sets

In unordered sets, elements are stored in an arbitrary order through hashing. Insertions, deletions, and searches are all $\mathcal{O}(1)$ (with a high constant factor). Unordered sets are implemented by std:unordered_set in the <unordered_set> header.

Some operations on an std::unordered_set named s include:

• s.insert(x), which adds the element x to s if not already present.
• s.erase(x), which removes the element x from s if present.
• s.count(x), which returns 1 if s contains x and 0 if it doesn't.

Unordered sets work with primitive types, but require a custom hash function for structures/classes like vectors and pairs.

Copy
unordered_set<int> s;
s.insert(1);                 // {1}
s.insert(4);                 // {1, 4}
s.insert(2);                 // {1, 4, 2}
s.insert(1);                 // does nothing because 1's already in the set
cout << s.count(1) << endl;  // 1
s.erase(1);                  // {2, 4}
cout << s.count(5) << endl;  // 0
s.erase(0);                  // does nothing because 0 wasn't in the set

Sorted Sets

In sorted sets, the elements are sorted in order of element. Insertions, deletions, and searches are all $\mathcal{O}(\log N)$, where $N$ is the number of elements in the set. Sorted sets are implemented by std:set in the <set> header.

std::set includes all the essential operations that std::unordered_set has (including insertion, deletion, searches, etc.), but also some additional ones. Refer to the More Operations on Sorted Sets module for more detail.

You can iterate through a set in sorted order using a for-each loop.

Copy
set<int> s;
s.insert(1);  // [1]
s.insert(4);  // [1, 4]
s.insert(2);  // [1, 2, 4]

// Outputs 1, 2, and 4 on separate lines
for (int element : s) { cout << element << endl; }

Solution - Distinct Numbers

This problem asks us to calculate the number of distinct values in a given list.

Method 1 - Set

This is probably the easier of the two methods, but requires knowledge of sets. Because sets only store one copy of each value, we can insert all the numbers into a set, and then print out the size of the set.

Copy
#include <bits/stdc++.h>

using namespace std;

int main() {
	int n;
	cin >> n;

	set<int> distinctNumbers;
	for (int i = 0; i < n; i++) {

Method 2 - Sorting

Check out the solution involving sorting.

Maps

A map is a set of entries, each consisting of a key and a value. In a map, all keys are required to be unique, but values can be repeated. Maps have three primary methods:

• one to add a specified key-value pairing
• one to retrieve the value for a given key
• one to remove a key-value pairing from the map

In sorted maps, the pairs are sorted in order of key. Insertions, deletions, and searches are all $\mathcal{O}(\log N)$, where $N$ is the number of pairs in the map. In unordered maps, the pairs aren't kept in sorted order and all insertions, deletions, and searches are all $\mathcal{O}(1)$. Sorted maps are implemented with std::map and unordered maps are implemented with std::unordered_map.

Some operations on an std::map and std::unordered_map named m include:

• m[key], which returns a reference to the value associated with the key key.

  • If key is not present in the map, then the value associated with key is constructed using the default constructor of the value type. For example, if the value type is int, then calling m[key] for a key not within the map sets the value associated with that key to 0. As another example, if the value type is std::string, then calling m[key] for a key not within the map sets the value associated with that key to the empty string. More discussion regarding what happens in this case can be found here.
  • Alternatively, m.at(key) behaves the same as m[key] if key is contained within m but throws an exception otherwise.
  • m[key] = value will assign the value value to the key key.
• m.count(key), which returns the number of times the key is in the map (either one or zero), and therefore checks whether a key exists in the map.
• m.erase(key), which removes the map entry associated with the specified key if the key was present in the map.

Copy
map<int, int> m;
m[1] = 5;                    // [(1, 5)]
m[3] = 14;                   // [(1, 5); (3, 14)]
m[2] = 7;                    // [(1, 5); (2, 7); (3, 14)]
m[0] = -1;                   // [(0, -1); (1, 5); (2, 7); (3, 14)]
m.erase(2);                  // [(0, -1); (1, 5); (3, 14)]
cout << m[1] << endl;        // 5
cout << m.count(7) << endl;  // 0
cout << m.count(1) << endl;  // 1
cout << m[2] << endl;        // 0

Iterating Over Maps

An std::map stores entries as pairs in the form {key, value}. To iterate over maps, you can use a for loop. The auto keyword suffices to iterate over any type of pair (here, auto substitutes for pair<int, int>).

Copy
// Both of these output the same thing
for (const auto &x : m) { cout << x.first << " " << x.second << endl; }
for (auto x : m) { cout << x.first << " " << x.second << endl; }

The first method (iterating over const references) is generally preferred over the second because the second will make a copy of each element that it iterates over. Additionally, you can pass by reference when iterating over a map, allowing you to modify the values (but not the keys) of the pairs stored in the map:

Copy
for (auto &x : m) {
	x.second = 1234;  // Change all values to 1234
}

While you are free to change the values in a map when iterating over it (as demonstrated above), it is generally a bad idea to insert or remove elements of a map while iterating over it.

For example, the following code attempts to remove every entry from a map, but results in a segmentation fault.

Copy
map<int, int> m;

for (int i = 0; i < 10; ++i) m[i] = i;

for (auto &it : m) {
	cout << "Current Key: " << it.first << endl;

	m.erase(it.first);
}

The reason is due to "iterators, pointers and references referring to elements removed by the function [being] invalidated" (as stated in the documentation for erase), though iterators are beyond the scope of this module.

One way to get around this is to just create a new map instead of removing from the old one.

Copy
map<int, int> m, M;

for (int i = 0; i < 10; ++i) m[i] = i;

int current_iteration = 0;

for (const auto &it : m) {
	// only includes every third element
	if (current_iteration % 3 == 0) { M[it.first] = it.second; }

Another is to maintain a list of all the keys you want to erase and erase them after the iteration finishes.

Copy
map<int, int> m;
for (int i = 0; i < 10; ++i) { m[i] = i; }

vector<int> to_erase;
int current_iteration = 0;

for (const auto &it : m) {
	// removes every third element
	if (current_iteration % 3 == 0) { to_erase.push_back(it.first); }

Problems

Some of these problems can be solved by sorting alone, though sets or maps could make their implementation easier.

Check Your Understanding