STL Data Structures: set and map in Competitive Programming

In competitive programming, std::set and std::map are standard C++ associative containers that efficiently support operations like insertion, deletion, and search in $O(\log n)$ time. They are usually implemented as balanced binary search trees, so all elements (keys) are kept in sorted order. This makes them very useful when you need to maintain a dynamically changing ordered set of values or key–value pairs.

std::set

A set is a container that stores unique keys in sorted order. Basic properties:

• No duplicates: inserting the same value again has no effect.
• Sorted: iteration goes in increasing order of the keys.
• Typical operations: insert, erase, find, lower_bound, upper_bound.

Typical declaration:

std::map

A map is an ordered dictionary: it stores key–value pairs (key, value), with unique keys and keys sorted by strict weak ordering.

Basic properties:

• Each key appears at most once.
• Access value by key using operator[] or at.
• Insertion, deletion, and search take $O(\log n)$.

Example of a map from strings to integers:

Note: freq[key] creates the key with default value $0$ if it does not exist yet.

Example 1: Counting distinct elements with set

Problem: Given $n$ integers, find how many distinct values there are.

Idea: Insert each element into a set<int>. Since a set keeps only unique elements, the answer is just s.size().

Solution:

Example 2: Maintaining the current minimum greater than or equal to x

Problem: You are given $n$ distinct integers and $q$ queries. Each query gives a value $x$, and you must output the smallest element in the set that is greater than or equal to $x$, or report that it does not exist.

Idea: Store all elements in a set<int>. For each query $x$, use lower\_bound(x) to find the first element not less than $x$.

Solution:

Example 3: Frequency counting with map

Problem: Given $n$ words, output each distinct word and how many times it appears, in lexicographical order.

Idea: Use map<string,int> and increment m[word] for each input word. The map maintains sorted order of keys automatically.

Solution:

Example 4: Coordinate compression using set and map

Coordinate compression is a common technique in competitive programming. We map large or arbitrary values into a smaller range $0 \dots k-1$ while preserving order.

Problem: Given $n$ integers $a_i$, replace each $a_i$ with its rank in the sorted list of distinct values (starting from $0$). Idea:

• Put all values into a set<int> to get distinct sorted values.
• Traverse the set and assign increasing indices into a map<int,int> from value to compressed index.
• Replace each original $a_i$ with its compressed index from the map.

Solution:

#include <bits/stdc++.h>
using namespace std;

int main() {
    set<int> s;          // empty set of ints
    s.insert(5);
    s.insert(1);
    s.insert(3);
    s.insert(3);         // duplicate, ignored

    // s now contains {1, 3, 5}

    if (s.find(3) != s.end()) {
        cout << "3 is in the set\n";
    }

    s.erase(1);          // remove key 1 if present

    for (int x : s) {
        cout << x << " "; // prints: 3 5
    }
    cout << "\n";
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    map<string, int> freq;

    freq["apple"]++;
    freq["banana"] += 2;
    freq["orange"] = 5;

    // Iteration goes in lexicographical order of keys
    for (auto &[word, count] : freq) {
        cout << word << " -> " << count << "\n";
    }

    if (freq.count("apple")) {
        cout << "apple appears " << freq["apple"] << " times\n";
    }

    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    set<int> s;

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        s.insert(x);
    }

    cout << s.size() << "\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    set<int> s;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        s.insert(x);
    }

    while (q--) {
        int x;
        cin >> x;
        auto it = s.lower_bound(x);
        if (it == s.end()) {
            cout << "NO\n";
        } else {
            cout << *it << "\n";
        }
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    map<string, int> freq;
    for (int i = 0; i < n; i++) {
        string w;
        cin >> w;
        freq[w]++; // creates key if not present
    }

    for (auto &[word, count] : freq) {
        cout << word << " " << count << "\n";
    }

    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    set<int> s(a.begin(), a.end()); // distinct sorted values

    map<int, int> comp; // value -> compressed index
    int id = 0;
    for (int x : s) {
        comp[x] = id++;
    }

    for (int i = 0; i < n; i++) {
        a[i] = comp[a[i]];
    }

    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    cout << "\n";

    return 0;
}