Associative Containers

Overview

Associative containers automatically SORT their data. They are implemented as Red-Black Trees (Self-Balancing BSTs). Insertions, deletions, and lookups take O(log N) time.

Syntax

cpp

#include <set>
#include <map>

// Set (Unique, sorted elements)
std::set<int> s = {5, 1, 3, 3}; // Contains {1, 3, 5}
s.insert(4); 

// Map (Key-Value pairs, sorted by key)
std::map<std::string, int> ages;
ages["Alice"] = 25;
ages["Bob"] = 30;

// multiset/multimap allow duplicate keys!

Common Pitfalls

Accessing `map["key"]` inserts the key with a default value (e.g., 0) if it doesn't exist. Use `map.count("key")` or `map.find("key")` to check for existence safely.

Interview Tips

A `std::map` and `std::set` guarantee O(log N) operations and keep elements strictly sorted. If you don't need elements sorted, use `unordered_map` for O(1) performance.

Real-World Example

Using a map to count word frequencies automatically sorted alphabetically.

example

cpp

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

int main() {
    map<string, int> freq;
    
    // Increment counts
    freq["apple"]++;
    freq["banana"]++;
    freq["apple"]++;
    
    // Iterates in alphabetical order automatically!
    for (auto const& [word, count] : freq) {
        cout << word << ": " << count << endl;
    }
    return 0;
}

Take C++ Quiz