Sets and Maps: set, multiset, map

Lesson 7 of 11 · Data structures

The containers set and map keep their elements ordered and allow adding, removing and finding in O(log n) time. In competitions they are used for counting occurrences, removing duplicates, tracking the smallest and the largest element and finding the nearest element while the set is changing.

Before you start: prerequisites – maps in C++, lower_bound (SR).
How to learn: type in and run every example, and solve the tasks at the end on your own first; open the hint and the solution only after that. All programs are in C++.

set: a set of different elements

set keeps every element at most once, always sorted. Adding an existing element changes nothing.

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s;
    s.insert(5);
    s.insert(1);
    s.insert(9);
    s.insert(5);                           // 5 already exists – nothing changes
    cout << "size: " << s.size() << endl;

    for (int x : s) cout << x << " ";      // always increasing
    cout << endl;

    cout << "is 9 there? " << s.count(9) << endl;   // 1 or 0
    s.erase(9);
    cout << "is 9 there? " << s.count(9) << endl;

    cout << "smallest: " << *s.begin() << endl;
    cout << "largest: " << *s.rbegin() << endl;
    return 0;
}
OperationMeaningComplexity
s.insert(x)adds xO(log n)
s.erase(x)removes xO(log n)
s.count(x)1 if x exists, otherwise 0O(log n)
*s.begin(), *s.rbegin()the smallest and the largest elementO(1)
s.lower_bound(x)an iterator to the first element >= xO(log n)
s.size(), s.empty()the number of elements, whether it is emptyO(1)

Finding the nearest element in a changing set

A sorted array and lower_bound (SR) work as long as the array does not change. If elements are added between the queries, we use the set's method s.lower_bound(x). Example: parking spots are taken one by one, and for every new car we look for the first free spot with a number >= x.

#include <iostream>
#include <set>
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;                      // spots 1..n, q cars
    set<int> freeSpots;
    for (int i = 1; i <= n; i++) freeSpots.insert(i);

    while (q--) {
        int x;
        cin >> x;                       // the driver wants spot x or the first larger one
        auto it = freeSpots.lower_bound(x);
        if (it == freeSpots.end()) {
            cout << "none" << endl;
        } else {
            cout << *it << endl;
            freeSpots.erase(it);        // the spot is now taken
        }
    }
    return 0;
}

multiset: a set with repetitions

multiset allows several equal elements, and it is still sorted. Watch out: ms.erase(x) removes all copies of the number x; one copy is removed through an iterator: ms.erase(ms.find(x)).

#include <iostream>
#include <set>
using namespace std;

int main() {
    multiset<int> ms = {4, 1, 4, 7, 4};
    cout << "fours: " << ms.count(4) << endl;
    ms.erase(ms.find(4));                // removes only one four
    cout << "fours: " << ms.count(4) << endl;
    for (int x : ms) cout << x << " ";
    cout << endl;
    return 0;
}

A multiset is handy when you constantly need to know the smallest and the largest of the current elements, while elements are both added and removed (for example, prices in a shop that change).

map: key – value pairs

map<K, V> assigns a value to every key. The basics are described in the lesson Data dictionary – maps in C++; here the most important use is counting occurrences when the values are too large for an ordinary array of counters (up to 109, negative, or words).

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    int n;
    cin >> n;
    map<string, int> count;             // word -> number of occurrences
    for (int i = 0; i < n; i++) {
        string word;
        cin >> word;
        count[word]++;                  // a new word automatically gets 0, and then it is increased
    }
    for (auto &entry : count)           // the keys are sorted alphabetically
        cout << entry.first << " " << entry.second << endl;
    return 0;
}
A trap: just reading count[x] for a key that does not exist adds it with the value 0. To check whether a key exists, use count.count(x).

unordered_set and unordered_map

The versions without ordering use a hash table: adding and finding are O(1) on average, but the elements are not sorted and there is no lower_bound. They are used when the order does not matter and there are many operations.

set / mapunordered_set / unordered_mapvector + sort
FindingO(log n)O(1) on averageO(log n) (binary search)
Adding while workingO(log n)O(1) on averageslow (O(n))
Sorted orderyesnoyes
The nearest elementyes (lower_bound)noyes
Whena dynamic set, orderingonly counting / existencethe data do not change

Practice tasks

Every task has an example, a hint and a solution. The solutions have been checked on the examples from the text.

TASK 01Difficulty: easy

The number of different values

n integers are given (up to 109 in absolute value, n ≤ 2·105). Print how many of them are different.

Example

Input

6
5 -2 5 1000000000 -2 7

Output

4
TASK 02Difficulty: easy

The most frequent word

n words are given. Print the word that appears the most times and the number of its occurrences; if there are several, print the alphabetically first one.

Example 1

Input

7
cat dog cat bird dog cat fish

Output

cat 3

Example 2

Input

4
b a b a

Output

a 2
TASK 03Difficulty: medium

The cheapest and the most expensive

Changes happen in a shop. The query + x adds a product with the price x, the query - x removes one product with the price x (it certainly exists), and the query ? asks to print the lowest and the highest current price (or empty).

Example

Input

7
+ 5
+ 3
+ 5
?
- 3
- 5
?

Output

3 5
5 5
Common mistakes and tips
  • set does not keep duplicates; if you need them, use multiset.
  • ms.erase(x) removes all copies, ms.erase(ms.find(x)) only one.
  • Do not call lower_bound(s.begin(), s.end(), x) on a set – that is O(n). The correct form is s.lower_bound(x).
  • Before dereferencing an iterator (*it) check that it is not end().

Check your knowledge

Open the quiz

Sets and maps

1. How many elements does a set have after insert(3), insert(3), insert(5)?




2. What is the complexity of adding to a set?




3. What happens when you read count["x"] for a key that does not exist in the map count?




4. How do you remove only one copy of the number x from a multiset?