Set Structures

A set is a data structure that maintains a collection of elements. The basic operations of sets are element insertion, search, and removal.

The C++ standard library contains two set structures:

• set is based on a balanced binary search tree and its operations work in $O(\log n)$.
• unordered_set is based on a hash table and its operations work in $O(1)$ time.

We focus on set structure.

• The function insert adds an element to the set.
• The function count returns the number of occurrences of an element in the set.
• The function erase removes an element from the set.

set<int> s;
s.insert(3);
s.insert(2);
s.insert(5);
cout << s.count(3) << "\n"; // 1
cout << s.count(4) << "\n"; // 0
s.erase(3);
s.insert(4);
cout << s.count(3) << "\n"; // 0
cout << s.count(4) << "\n"; // 1

Important property: all the elements of a set are distinct. The function count always returns either 0 or 1 and the function insert never adds an element to the set if it is already there.

The following code prints the number of elements in a set then iterates through the elements.

cout << s.size() << "\n";
for (auto x : s) {
	cout << x << "\n";
}

The function find(x) returns an iterator that points to an element whose value is $x$. If not found, the iterator will be end(x). This is illustrated below:

auto it = s.find(x); // auto infers the correct iterator type
if (it == s.end()) {
	// since if it returns the end(), which points to a non-valied element, then x is not found
}

set structure is ordered while unordered_set is not.

Finding the smallest and largest element:

auto first = s.begin();
auto last = s.end(); last--;
cout << *first << " " << *last << "\n";

In the code above, note that since end() points to an element after the last element, we have to decrease the iterator by one.

Multiset

A multiset is a set that can have several copies of the same value. It also has structures like multiset and unordered_multiset just like in a set.

Maps

A map is a set that consists of key-value pairs. A map can also be seen as a generalized array. Moreover, the keys in a map can be of any data type and they do not have to be consecutive values. It also has two structures under: map where accessing elements take $O(\log n)$ and unoredered_map where accessing elements take $O(1)$.

The codes below create a map whose keys are strings and values are integers.

map<string,int> m;
m["monkey"] = 4;
m["banana"] = 3;
m["harpsichord"] = 9;
cout << m["banana"] << "\n"; // 3

If the value of a key is requested but the map does not contain it, the key is automatically added to the map with a default value.

The function count checks if a key exists in a map.

if (m.count("aybabtu")) {
	// key exists
}

The following code prints all keys and values in a map:

for (auto x : m) {
	cout << x.first << " " << x.second << "\n";
}

Priority Queues

A priority queue is a multiset that supports element insertion and, depending on the type of the queue, retrieval and removal of either the minimum or maximum element. Insertion takes $O(\log n)$ while retrieval takes $O(1)$ time.

• The advantage of using a priority queue is that it has a smaller constant factors.
• By default, the elements in the priority queue are sorted in decreasing order.

priority_queue<int> q;
q.push(3);
q.push(5);
q.push(7);
q.push(2);
cout << q.top() << "\n"; // 7
q.pop();
cout << q.top() << "\n"; // 5
q.pop();
q.push(6);
cout << q.top() << "\n"; // 6
q.pop();

Priority Queue, Array, Sorting