Associative Containers: map, set, unordered_map

'std::map' is an ordered associative container that stores key-value pairs sorted by key. It is implemented as a balanced binary search tree (typically red-black tree), giving O(log n) complexity for insertions, deletions, and lookups. The '[]' operator inserts a default-constructed value if the key is absent — use 'find()' or 'count()' when absence should be detectable without side effects. 'std::set' stores unique, sorted keys with no associated value. It is ideal for membership testing, deduplication, and ordered traversal. 'std::multimap' and 'std::multiset' allow duplicate keys. The unordered variants — 'std::unordered_map' and 'std::unordered_set' — use hash tables and deliver average O(1) operations at the cost of ordering and potentially higher memory usage. Iterating over a 'std::map' visits elements in key order, which makes it straightforward to produce sorted output. Structured bindings (C++17) allow destructuring key-value pairs directly in range-for loops: 'for (const auto& [key, val] : m)'. This syntax also works with 'std::pair', tuples, and any type that supports structured binding protocol.

Example

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

int main() {
    // --- std::map ---
    std::map<std::string, int> wordCount;
    for (const std::string& w : {"cat","dog","cat","bird","dog","cat"})
        ++wordCount[w];   // operator[] default-inserts 0

    std::cout << "Word counts (sorted):\n";
    for (const auto& [word, count] : wordCount)   // C++17 structured binding
        std::cout << "  " << word << ": " << count << "\n";

    // Safe lookup without insertion
    if (auto it = wordCount.find("cat"); it != wordCount.end())
        std::cout << "cat found: " << it->second << "\n";

    // --- std::set ---
    std::set<int> primes = {2, 3, 5, 7, 11, 13};
    primes.insert(17);
    primes.insert(7);   // duplicate — silently ignored
    std::cout << "Primes: ";
    for (int p : primes) std::cout << p << " ";
    std::cout << "\n";
    std::cout << "contains 11: " << primes.count(11) << "\n";

    // --- std::unordered_map (O(1) avg) ---
    std::unordered_map<std::string, std::string> capitals;
    capitals["France"]  = "Paris";
    capitals["Germany"] = "Berlin";
    capitals["Japan"]   = "Tokyo";

    std::cout << "Capital of Japan: " << capitals.at("Japan") << "\n";

    return 0;
}

HTML

Full Editor

Related Resources

C++ Reference

Complete tag & property list

C++ How-To Guides

Step-by-step practical guides

C++ Exercises

Practice what you've learned