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 keeps keys sorted. Most standard-library implementations use a balanced binary search tree (often a red-black tree), but the C++ standard does not require a particular data structure, only the observable complexity and ordering guarantees.

• 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 unspecified order; iterating over the container visits keys in an implementation-dependent sequence (not sorted).

• 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. std::unordered_map exposes buckets, but its collision strategy and node layout are implementation details; do not assume a particular linked-list representation from the C++ standard.

Flat or Robin Hood-style hash tables can improve locality for some workloads, but they bring their own load-factor, erase, reference-stability, and implementation trade-offs. Benchmark a suitable container with realistic keys and access patterns rather than assuming it always beats std::unordered_map.

std::map is typically implemented as a node-based balanced tree, but C++ does not require a specific tree algorithm or allocation strategy. Node-oriented storage can have poorer locality and more allocation work than a flat container, yet sorted traversal, stable iterators, and ordered queries can make it the correct design.

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

int main() {
    // Ordered map (sorted keys, O(log n) operations)
    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;
}