set, map, multiset, and multimap

Ordered unique keys, frequency maps, coordinate compression, and when ordering buys you binary search for free.

set and map — sorted unique keys

set<K> stores unique keys in sorted order. map<K,V> stores key→value pairs ordered by K.

Operations: insert, erase, find, count (0 or 1 for set/map), lower_bound, upper_bound — all O(log n).

Iteration visits keys in sorted order — useful for sweeping line algorithms or merging sorted streams.

[] on map: inserts default if missing — convenient but hides O(log n) inserts; in tight loops prefer find when key might be absent to avoid accidental size growth.

Example — set: distinct values, ordered walk:

set<int> s;
s.insert(5); s.insert(2); s.insert(5);
for (int x : s) cout << x << " ";  // 2 5
if (s.count(3)) { /* 3 present */ }
auto it = s.lower_bound(4);  // first element >= 4

Example — map as frequency counter:

map<string, int> freq;
string w;
while (cin >> w) freq[w]++;
for (auto const& [k, v] : freq)
    cout << k << " " << v << "\n";

Example — avoid accidental insert with find:

map<int, long long> dp;
int k = 7;
auto it = dp.find(k);
if (it == dp.end()) {
    // not computed yet
} else {
    long long val = it->second;
}

Example — map + coordinate as key:

map<pair<int,int>, int> cell;  // grid cell -> id
cell[{r, c}] = id;

multiset and multimap — duplicates

multiset allows repeated keys; equal_range returns the span of one value.

Erase nuance: erase(iterator) removes one instance; erase(value) removes all copies with that value.

Frequency counting: map<T,int> or unordered_map is often clearer than multiset unless you need sorted multiset behavior (k-th smallest with order-statistics needs extra structure).

Example — multiset with duplicates:

multiset<int> ms;
ms.insert(3); ms.insert(3); ms.insert(1);
// ordered: 1 3 3
auto it = ms.lower_bound(3);  // first 3
auto [lo, hi] = ms.equal_range(3);
int cnt = int(distance(lo, hi));  // or loop hi - lo with random-access only; for multiset use loop

Example — erase one vs erase all:

multiset<int> ms = {1,2,2,2,3};
ms.erase(ms.find(2));       // removes ONE 2
// ms.erase(2);             // would remove ALL 2's

Example — multimap (same key, many values):

multimap<int, int> edges;  // adjacency with parallel storage
edges.insert({1, 2});
edges.insert({1, 3});
for (auto [u, v] : edges) { /* ... */ }
auto r = edges.equal_range(1);  // all neighbors of 1
for (auto it = r.first; it != r.second; ++it) {
    int v = it->second;
}

Coordinate compression

When values are huge but count is small, map them to 0..m-1:

Copy unique values to vector, sort, erase(unique).
For each original x, idx = lower_bound(comp.begin(), comp.end(), x) - comp.begin().

Alternatively build set of all coordinates, then index — same idea.

Feeds into Fenwick trees / segment trees on compressed indices.

Example — compress array values:

vector<long long> a = {1000000000LL, -5, 1000000000LL, 0};
vector<long long> co = a;
sort(co.begin(), co.end());
co.erase(unique(co.begin(), co.end()), co.end());
// co is sorted unique; index of x is:
for (long long& x : a) {
    x = lower_bound(co.begin(), co.end(), x) - co.begin();
}
// now a[i] in [0, co.size())

Example — compress using set:

set<long long> s(a.begin(), a.end());
vector<long long> co(s.begin(), s.end());
// same lower_bound indexing as above

When ordered beats unordered

Choose set/map when you need sorted traversal, lower_bound on keys, or deterministic iterator order.

Choose unordered_* when you only need membership / frequency with no order — usually faster average case, but watch hacking / worst-case (see unordered topic).

Example — need smallest key ≥ x (ordered only):

set<long long> s;  // ... insert values
auto it = s.lower_bound(x);
if (it == s.end()) { /* none */ }
else { long long y = *it; }

Example — same with map keys:

map<int, string> mp;
auto it = mp.lower_bound(42);

Complexity

Balanced BST implementations (typically red-black): O(log n) per operation, O(n) memory.

Iterator invalidation: safer than vector for insert/erase of other elements — iterators to other elements generally stay valid (except for erased element).

Complexity Analysis

Time Complexity

O(log n) per find/insert/erase on average trees

Space Complexity

O(n) keys (plus values in map)

map::operator[] inserts default — use carefully in competitive code

Growth Rate Comparison