Associative Containers: Key-Based Lookup

Associative containers organize elements by key for fast lookup. Two families: ordered (red-black trees) and unordered (hash tables).

std::set: Unique Sorted Keys

Stores unique elements in sorted order:

std::set<int> s = {5, 2, 8, 2, 1};  // {1, 2, 5, 8} - duplicates removed

s.insert(3);  // O(log n)
s.erase(2);   // O(log n)

if (s.count(5)) {  // O(log n), returns 0 or 1
    std::cout << "Found 5\\n";
}

auto it = s.find(8);  // O(log n), returns iterator
if (it != s.end()) {
    std::cout << *it << '\\n';
}

Iteration Order

Elements are always sorted:

std::set<int> s = {5, 1, 3, 2, 4};
for (auto x : s) {
    std::cout << x << ' ';  // Outputs: 1 2 3 4 5
}

Custom Comparison

struct Person {
    std::string name;
    int age;
};

struct CompareByAge {
    bool operator()(const Person& a, const Person& b) const {
        return a.age < b.age;
    }
};

std::set<Person, CompareByAge> people;

std::map: Key-Value Pairs

Associates keys with values, sorted by key:

std::map<std::string, int> ages;
ages["Alice"] = 30;
ages["Bob"] = 25;
ages.insert({"Charlie", 35});
ages.emplace("David", 28);

std::cout << ages["Alice"];  // 30

// operator[] creates element if missing!
std::cout << ages["Unknown"];  // Creates entry with value 0

// Use find to avoid creation:
if (auto it = ages.find("Eve"); it != ages.end()) {
    std::cout << it->second;
} else {
    std::cout << "Not found\\n";
}

Structured Bindings (C++17)

for (const auto& [name, age] : ages) {
    std::cout << name << ": " << age << '\\n';
}

std::multiset and std::multimap

Allow duplicate keys:

std::multiset<int> ms = {1, 2, 2, 3, 3, 3};
std::cout << ms.count(3);  // 3

std::multimap<std::string, int> mm;
mm.insert({"Alice", 90});
mm.insert({"Alice", 85});  // Same key, different value

auto range = mm.equal_range("Alice");
for (auto it = range.first; it != range.second; ++it) {
    std::cout << it->second << ' ';  // 90 85
}

Unordered Associative Containers (C++11)

Hash table based: O(1) average, no ordering:

std::unordered_set<int> us = {5, 2, 8, 1};
us.insert(3);  // O(1) average

// Iteration order is arbitrary
for (auto x : us) {
    std::cout << x << ' ';  // Unpredictable order
}

std::unordered_map<std::string, int> um;
um["key"] = 42;  // O(1) average

Custom Hash Function

struct Person {
    std::string name;
    int age;
};

struct PersonHash {
    size_t operator()(const Person& p) const {
        return std::hash<std::string>{}(p.name) ^ std::hash<int>{}(p.age);
    }
};

struct PersonEqual {
    bool operator()(const Person& a, const Person& b) const {
        return a.name == b.name && a.age == b.age;
    }
};

std::unordered_set<Person, PersonHash, PersonEqual> people;

Ordered vs Unordered: When to Use

Default choice: unordered_map/unordered_set unless you need ordering.

Range-Based Operations

Ordered containers support efficient range queries:

std::set<int> s = {1, 2, 3, 4, 5, 6, 7, 8, 9};

auto lower = s.lower_bound(3);  // First element >= 3
auto upper = s.upper_bound(7);  // First element > 7

for (auto it = lower; it != upper; ++it) {
    std::cout << *it << ' ';  // 3 4 5 6 7
}

Transparent Comparators (C++14)

Avoid creating temporary objects for lookup:

std::set<std::string, std::less<>> s;  // Note: std::less<> not std::less<std::string>

s.find("hello");  // Doesn't create std::string temporary