6.2 Associative Containers (Map vs Unordered Map)

Associative containers store data as key value pairs, allowing you to lookup elements using a custom key instead of a numerical index. C++ provides two main associative containers with completely different underlying structures and performance profiles: std::map and std::unordered_map.

Let's look at trees, hash tables, and search complexities.

The std::map is implemented under the hood as a self balancing Red Black Tree. When you insert a key value pair, the tree restructures itself to maintain a sorted order based on the keys.

* Search Complexity: Searching, inserting, and deleting in a map runs in logarithmic time O(log n) because the CPU traverses the tree branches.

* Iterators: Because the tree is sorted, iterating over a map visits the elements in sorted order of the keys.

* The Index Catalog Metaphor: A map is like an alphabetical catalog index card file. Every card is sorted alphabetically. If you want to insert a card or find one, you flip through the cards, halving your search space at each step. It is highly organized and sorted, but takes a few steps to locate the target card.

The std::unordered_map is implemented as a Hash Table. It uses a mathematical function (a hash function) to convert your key into a numerical index, mapping the element directly to a slot in an array called a bucket.

* Search Complexity: Under normal conditions, lookups, insertions, and deletions run in constant time O(1) because the hash function points directly to the memory slot.

* Iterators: Elements are stored in arbitrary order; iterating over the container returns keys in random order.

* The Labeled Bucket Metaphor: An unordered map is like dropping your keys into labeled buckets based on a mathematical calculation on the key name. You look at the name, calculate the bucket index, and reach straight into that bucket to pull out the item. Finding the item is instant.

What happens if two different keys produce the same hash index? This is a hash collision. The container handles this by chaining multiple elements in the same bucket (usually as a linked list). If many keys collide, lookup speed degrades from O(1) to O(n) linear search. Writing efficient hash functions is critical to high performance lookup structures.

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

int main() {
    // Ordered Map (Sorted Red Black Tree, O(log n))
    std::map<int, std::string> orderedMap;
    orderedMap[2] = "Two";
    orderedMap[1] = "One"; // Will be sorted: Key 1 will precede Key 2!

    // Unordered Map (Hash Table, O(1))
    std::unordered_map<int, std::string> hashtable;
    hashtable[10] = "Ten";
    hashtable[20] = "Twenty";

    return 0;
}