Set Structures

Programming

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