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: