Sets and Maps

A set answers membership questions for distinct keys. A map associates each distinct key with a stored value, such as a frequency, best score, or vertex ID. Ordered set/map keep keys sorted and guarantee logarithmic lookup and modification. Unordered variants organize keys by hashing and usually provide constant expected lookup, but do not preserve order and can have linear worst-case operations. This lesson builds a small inventory with both an ordered set of active values and a map of frequencies, then explains when hashing is worth the different guarantees.

Prerequisites: Arrays and Vectors, comparison operators, iterators at a basic level.

Build the idea

1. 1. Choose membership or association. set<int> present; records whether a value exists. Inserting 5 twice still stores one key. map<int,int> count; records an integer count for each value. A map also has unique keys; repeated occurrences belong in its mapped frequency, not as duplicate keys. multiset is a separate container that allows repeated equal keys. Be careful: multiset.erase(value) removes every equal occurrence; erasing one iterator removes one occurrence.
2. 2. Distinguish reading from insertion. freq[x] returns the mapped value, creating x with value zero if missing. This is convenient for ++freq[x], but a supposed read can change the map. find(x) returns an iterator or end without inserting. The inventory uses find for queries and deletion. When a frequency falls to zero, erase its map entry and erase x from the ordered active set. The invariant is: x belongs to active if and only if freq contains x with positive count.
3. 3. Use order for questions beyond equality. active.lower_bound(x) finds the smallest stored key at least x, or end if none exists. For active values {2,8}, lower_bound(3) yields 8. upper_bound(x) returns the first key strictly greater than x. A predecessor requires decrementing an iterator only after checking it is not begin. Use the container's lower_bound member on a set/map: it navigates its search structure in logarithmic time. Generic std::lower_bound over non-random-access iterators may use linear iterator movement.
4. 4. Trace duplicates and deletion. Add 5 twice, then 2. The frequencies are 5→2 and 2→1 while the active set is {2,5}. Removing one 5 changes only its frequency to 1. Removing the second deletes 5 from both containers. Removing an absent value is ignored. A frequency query must print zero without recreating an absent map entry. The implementation prints the number of distinct active values after every update, while Q asks a count and N asks a successor. Different questions justify the two related structures.
5. 5. Ordered guarantees versus hashing. std::set and std::map support O(log d) search, insertion, and deletion for d distinct keys. std::unordered_set and std::unordered_map provide expected average O(1) for common operations with a suitable hash and load factor, but worst-case O(d) when many keys collide. Reserving anticipated entries reduces rehashing; it does not remove adversarial-collision worst cases. Iteration order is unspecified and may change after rehash. An unordered container has no ordered lower_bound. If output must be sorted, either use an ordered container or explicitly sort extracted keys.
6. 6. Read the implementation and its numeric limits. Keys use long long to allow values beyond int. Counts also use long long, though the number of updates is bounded by q. The two containers deliberately duplicate the key set to teach both roles. A leaner solution could use only the ordered map: its lower_bound can find the same successor, and its size already counts distinct keys. Keep both only when the separation clarifies the problem or different structures are necessary. For name-to-ID mapping, map<string,int> or unordered_map<string,int> replaces numeric keys while vectors store the actual graph data.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<map>
#include<set>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    if(!(cin>>q)||q<0){
        return 0;
    }
    map<long long,long long>freq;
    set<long long>active;
    while(q--){
        char op;
        long long x;
        cin>>op>>x;
        if(op=='+'){
            ++freq[x]; // Missing key starts with count zero.
            active.insert(x);
            cout<<active.size()<<'\n';
        }
        else if(op=='-'){
            auto it=freq.find(x);
            if(it!=freq.end()){
                --it->second;
                // A key is active exactly while its stored frequency is positive.
                if(it->second==0){
                    freq.erase(it);
                    active.erase(x);
                }
            }
            cout<<active.size()<<'\n';
        }
        else if(op=='Q'){
            auto it=freq.find(x); // Reading does not insert a key.
            cout<<(it==freq.end()?0:it->second)<<'\n';
        }
        else if(op=='N'){
            // Ordered lookup finds the first active value at least x.
            auto it=active.lower_bound(x);
            if(it==active.end()){
                cout<<"NONE\n";
            }
            else{
                cout<<*it<<'\n';
            }
        }
    }
}

Complexity analysis

With d active distinct values, every update, Q query, and N successor query takes O(log(d+1)); q commands take O(q log(q+1)) worst-case time and O(d) storage. Ordered-container size is constant time. Hash-based membership/frequency operations are expected O(1) but worst-case O(d) each, and rehashing can invalidate iterators. Hashing cannot replace the ordered successor query directly.

Example input and output

Read q ≥ 0 commands. + x inserts one occurrence; - x removes one if present; both print the distinct count. Q x prints frequency. N x prints the smallest active key ≥ x, or NONE. Keys fit in signed 64 bits.

Input

10
+ 5
+ 5
+ 2
Q 5
N 3
- 5
Q 5
- 5
N 3
Q 9

Output

1
1
2
2
5
2
1
1
NONE
0

Repeated 5 increases its count without adding a distinct key. Removing its final occurrence leaves only 2, so no active key is at least 3. Querying absent 9 prints zero and keeps the containers unchanged.

Practical applications

Use sets for active coordinates and ordered successors, maps for sparse frequencies and name-to-ID mapping, unordered maps for average-fast dictionary lookup, and multisets for duplicate priorities with deletion. For k-th smallest queries, an ordinary set has no constant- or logarithmic-time rank operation; use a Fenwick tree with compressed coordinates or an order statistic structure.

Check your understanding

Which statement about unordered_map is correct?

Put it into practice

Rewrite the inventory using only one ordered map and preserve every output.