Chapter 10: Associative Containers—Maps and Sets

In the previous chapters, we focused on **Sequential Containers** (std::vector, std::string) where elements are ordered by their physical position, and you access them using a numerical index (0, 1, 2, ...).

This chapter introduces **Associative Containers**, which are ordered by a user-defined **key**. Instead of asking "What is at position 3?", you ask, "What is associated with the key 'username'?" These containers are optimized for extremely fast lookups, insertions, and deletions based on the key.

Section 1: The Unique Collection: `std::set`

An std::set is a container that stores unique elements in a specific, sorted order. It is perfect for membership checking (checking if an element exists) and ensuring a collection has no duplicates.

Key Characteristics of `std::set`:

**Uniqueness:** Every element must be unique. If you try to insert an element that already exists, the operation is ignored.
**Ordering:** Elements are automatically stored in a sorted order based on their value (e.g., lexicographically for strings, numerically for integers).
**Key-Only:** The set only stores the key itself; there is no associated "value."
**Performance:** Lookup, insertion, and deletion operations take **logarithmic time** (O(log N)).

The excellent performance of std::set is because it is typically implemented using a **Self-Balancing Binary Search Tree**, like a Red-Black Tree. This structure ensures that no matter how many elements are added or removed, the tree remains balanced, guaranteeing fast lookups.


#include <set>
#include <iostream>

void demonstrate_set() {
    std::set<std::string> unique_words;

    // Insertion
    unique_words.insert("apple");
    unique_words.insert("banana");
    unique_words.insert("apple"); // Ignored, already exists

    // Membership Checking (using count)
    // count() returns 1 if the element is present, 0 otherwise.
    if (unique_words.count("banana")) {
        std::cout << "The set contains 'banana'." << std::endl;
    }

    // Iteration (elements are always traversed in sorted order)
    std::cout << "Sorted words: ";
    for (const auto& word : unique_words) {
        std::cout << word << " "; // Output: apple banana 
    }
    std::cout << std::endl;
}

Section 2: The Key-Value Store: `std::map`

The std::map is one of the most powerful containers in the STL. It stores elements as a combination of a **Key** and an associated **Value** (a key-value pair). It is essentially C++'s version of a dictionary or associative array.

Key Characteristics of `std::map`:

**Key-Value Pair:** Each element consists of a unique Key (used for lookup) and a Value (the associated data).
**Uniqueness:** Keys must be unique (just like a set).
**Ordering:** Elements are sorted by their **Key** (not by their value).
**Performance:** Lookup, insertion, and deletion are all O(log N), guaranteed by the underlying tree structure.


#include <map>
#include <string>
#include <iostream>

void demonstrate_map() {
    // Key is string (city name), Value is int (population in thousands)
    std::map<std::string, int> city_population;

    // 1. Insertion using the subscript operator ([]), the easiest way
    city_population["New York"] = 8419;
    city_population["Los Angeles"] = 3980;
    
    // If the key exists, the value is updated.
    city_population["New York"] = 8468; 

    // 2. Accessing Values
    std::cout << "Population of Los Angeles (in thousands): " 
              << city_population["Los Angeles"] << std::endl;

    // 3. Safe Access with .at() (throws exception if key not found)
    try {
        std::cout << "NY Population: " << city_population.at("New York") << std::endl;
    } catch (const std::out_of_range& e) {
        std::cout << "Key not found!" << std::endl;
    }

    // 4. Iteration (always by sorted key)
    std::cout << "Cities by sorted key:" << std::endl;
    for (const auto& pair : city_population) {
        // 'pair' is a std::pair
        std::cout << "  " << pair.first << ": " << pair.second << std::endl;
    }
}

Important Difference: Using map[key] to access an element will **insert** the key with a default-constructed value (e.g., 0 for an int, empty for a string) if the key is not found. Using map.at(key) will **throw an exception** if the key is not found. Use .at() for safe lookups, and [] for insertion/modification.

Section 3: Hash Tables and Unordered Containers

While std::map and std::set offer strong guarantees about sorted order and O(log N) performance, sometimes you don't need the sorted feature and you need even faster performance.

This is where the **Unordered Associative Containers** come in: std::unordered_map and std::unordered_set.

Hash Table Implementation

Unordered containers are implemented using a **Hash Table**. Instead of organizing data into a tree structure, they use a hash function to map a key directly to a storage location (a "bucket").

**Key Characteristic:** They provide **Average Constant Time** (O(1)) performance for insertion, deletion, and lookup. This is incredibly fast—the time complexity doesn't increase with the size of the container on average.
**Trade-off:** They **do not maintain any sorted order**. The elements are stored in the order determined by the hash function, which is essentially random.


#include <unordered_map>
#include <iostream>

void demonstrate_unordered_map() {
    // Fast key-value storage without ordering guarantees
    std::unordered_map<std::string, double> student_grades;

    student_grades["Alice"] = 95.5;
    student_grades["Bob"] = 88.0;
    student_grades["Charlie"] = 92.1;

    // O(1) average lookup
    std::cout << "Bob's Grade: " << student_grades["Bob"] << std::endl;

    // Iteration order is unpredictable
    std::cout << "Grades (Unordered):" << std::endl;
    for (const auto& pair : student_grades) {
        std::cout << "  " << pair.first << ": " << pair.second << std::endl;
    }
}

Choosing the Right Container

Final Thoughts on Associative Containers

The ability to model data structures like dictionaries and unique-item lists using `std::map` and `std::set` frees you from having to invent complex search and storage logic. You rely on the optimized, battle-tested structure of the STL, making your code safer, cleaner, and faster.

You now have a complete toolkit for handling any collection of data: sequential access with `vector`, and key-based access with `map` and `set`.

In **Chapter 11**, we will wrap up our discussion of containers by looking at **Adaptors**—specifically **std::stack** and **std::queue**—which enforce specific access rules on underlying containers, preparing us for deeper concepts in object-oriented programming.

Chapter 10: Associative Containers—Maps and Sets

Section 1: The Unique Collection: std::set

Key Characteristics of std::set:

Section 2: The Key-Value Store: std::map

Key Characteristics of std::map: