Map and Multimap — Ordered and Unordered Maps, emplace, try_emplace

DodaTech Updated 2026-06-28 7 min read

In this tutorial, you will learn about Map and Multimap. We cover key concepts, practical examples, and best practices to help you master this topic.

C++ maps are associative containers that store key-value pairs, with std::map providing ordered O(log n) access and std::unordered_map providing average O(1) lookup through hashing.

What You'll Learn

You will use std::map and std::multimap for ordered key-value association, use std::unordered_map for fast hash-based lookup, insert and emplace with try_emplace (C++17) for conditional insertion, understand the pair<const Key, Value> element type, iterate over map elements, and choose between ordered and unordered maps.

Why It Matters

Maps are the most important data structure in computing after arrays. They implement dictionaries, caches, symbol tables, and configuration stores. The C++ standard library provides production-quality implementations of both tree-based and hash-based maps. Understanding when try_emplace avoids unnecessary allocations can significantly improve performance in map-heavy code.

Learning Path

graph LR
    A["32: Set & Multiset"] --> B["33: Map & Multimap"]
    B --> C["34: Stack, Queue, Priority Queue"]
    C --> D["35: String & Span"]
    style A fill:#4a90d9,stroke:#2c5f8a,color:#fff
    style B fill:#4a90d9,stroke:#2c5f8a,color:#fff
    style C fill:#4a90d9,stroke:#2c5f8a,color:#fff
    style D fill:#4a90d9,stroke:#2c5f8a,color:#fff

`std::map`

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

int main() {
    std::map<std::string, int> ages;
    
    // Insert using operator[]
    ages["Alice"] = 30;
    ages["Bob"] = 25;
    ages["Charlie"] = 35;
    
    // Insert using insert (returns pair<iterator, bool>)
    auto [it, inserted] = ages.insert({"David", 28});
    std::cout << "Inserted David: " << inserted << "\n";
    
    // Insert existing key fails
    auto [it2, inserted2] = ages.insert({"Alice", 31});
    std::cout << "Inserted Alice again: " << inserted2 << "\n";
    
    // Access with operator[] (inserts if missing!)
    std::cout << "Alice: " << ages["Alice"] << "\n";
    std::cout << "Eve: " << ages["Eve"] << "\n";  // inserts Eve with default
    
    // Find (does not insert)
    auto it3 = ages.find("Bob");
    if (it3 != ages.end()) {
        std::cout << "Bob: " << it3->second << "\n";
    }
    
    // Iterate (sorted by key)
    for (const auto& [name, age] : ages) {
        std::cout << name << " -> " << age << "\n";
    }
    
    // Count (0 or 1)
    std::cout << "Charlie count: " << ages.count("Charlie") << "\n";
}

`std::multimap`

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

int main() {
    std::multimap<std::string, int> scores;
    
    scores.insert({"Alice", 95});
    scores.insert({"Bob", 82});
    scores.insert({"Alice", 88});  // duplicate key allowed
    scores.insert({"Alice", 91});
    
    // Iterate all
    for (const auto& [name, score] : scores) {
        std::cout << name << ": " << score << "\n";
    }
    
    // Find range for a key
    auto [low, high] = scores.equal_range("Alice");
    int sum = 0, count = 0;
    for (auto it = low; it != high; ++it) {
        sum += it->second;
        ++count;
    }
    std::cout << "Alice average: " << (sum / count) << "\n";
}

`std::unordered_map`

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

int main() {
    std::unordered_map<std::string, int> wordCount;
    
    // Insert and update
    wordCount["the"] = 1;
    wordCount["quick"] = 1;
    wordCount["brown"] = 1;
    wordCount["the"]++;  // increment existing value
    
    // Insert using emplace
    wordCount.emplace("fox", 1);
    
    // Find
    auto it = wordCount.find("brown");
    if (it != wordCount.end()) {
        std::cout << "brown: " << it->second << "\n";
    }
    
    // Check existence without default-inserting
    if (wordCount.count("slow") == 0) {
        std::cout << "slow not found\n";
    }
    
    // Contains (C++20)
    // if (wordCount.contains("quick")) { ... }
    
    // Iterate (no guaranteed order)
    for (const auto& [word, count] : wordCount) {
        std::cout << word << ": " << count << "\n";
    }
    
    // Bucket interface
    std::cout << "Buckets: " << wordCount.bucket_count() << "\n";
    for (size_t i = 0; i < wordCount.bucket_count(); ++i) {
        std::cout << "Bucket " << i << ": " << wordCount.bucket_size(i) << "\n";
    }
}

`try_emplace` and `insert_or_assign` (C++17)

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

struct ExpensiveToCreate {
    std::string data;
    ExpensiveToCreate(const std::string& d) : data(d) {
        std::cout << "Created: " << d << "\n";
    }
};

int main() {
    std::map<int, ExpensiveToCreate> m;
    
    // emplace: always constructs (even if key exists)
    m.emplace(1, "one");     // constructs "one"
    m.emplace(1, "ONE");     // constructs "ONE" (then discards)
    
    m.clear();
    
    // try_emplace: only constructs if key does NOT exist
    m.try_emplace(1, "one");   // constructs "one"
    m.try_emplace(1, "ONE");   // does NOT construct "ONE"
    
    // insert_or_assign: insert or update (returns info)
    auto [it, inserted] = m.insert_or_assign(2, "two");
    std::cout << "Inserted: " << inserted << "\n";
    
    auto [it2, updated] = m.insert_or_assign(2, "TWO");
    std::cout << "Updated: " << !updated << "\n";  // false (updated existing)
}

Heterogeneous Lookup (C++14, C++20)

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

struct StringCompare {
    using is_transparent = void;  // enables heterogeneous lookup
    
    bool operator()(const std::string& a, const std::string& b) const {
        return a < b;
    }
};

int main() {
    std::map<std::string, int, StringCompare> m;
    m["hello"] = 1;
    m["world"] = 2;
    
    // Without is_transparent, finding "hello" creates a std::string temporary
    // With is_transparent, we can use string_view directly (C++20)
    auto it = m.find("hello");  // No temporary string created
    
    if (it != m.end()) {
        std::cout << it->second << "\n";
    }
}

Performance Comparison

Operation	map	unordered_map
Lookup	O(log n)	O(1) average, O(n) worst
Insert	O(log n)	O(1) average, O(n) worst
Delete	O(log n)	O(1) average, O(n) worst
Iteration	O(n) sorted	O(n) unsorted
Memory	~3 pointers per node	Array + linked lists

Common Mistakes

Mistake 1: `operator[]` Default-Constructs Missing Keys

if (m["missing"] == 0) { ... }  // inserts "missing" with default value!

Use find() or contains() (C++20) to check existence without inserting.

Mistake 2: Using `map` When `unordered_map` Is Better

If you do not need sorted iteration, unordered_map is usually faster.

Mistake 3: Modifying Keys

auto it = m.begin();
// it->first = "new";  // Error: key is const

Map keys are const. You must erase and reinsert to change a key.

Mistake 4: Not Using `try_emplace` for Expensive Types

m.emplace(key, expensiveFunction());  // calls expensiveFunction even if key exists
m.try_emplace(key, expensiveFunction());  // only calls if key does not exist

Mistake 5: Using Multimap When a Map of Vectors Would Be Simpler

// Instead of:
std::multimap<Key, Value> mm;
// Consider:
std::map<Key, std::vector<Value>> mv;

Mistake 6: Inserting in Loop with `operator[]`

for (auto& item : items) {
    result[item.key] = item.value;  // lookup + assignment each iteration
}

Use insert or try_emplace which are better optimized.

Practice Questions

What is the difference between map::operator[] and map::find()?
When would you use multimap instead of a map of containers?
How does try_emplace differ from emplace?
What does insert_or_assign return?
Write code to count word frequencies in a text using unordered_map.

Challenge

Implement a simple Database Index using std::map: store records with unique IDs, support insertion by ID, lookup by ID, and range queries (all records with ID between low and high). Measure the time for 100,000 operations.

FAQ

Are map iterators invalidated by insertions?

For ordered maps (std::map), insertions do not invalidate existing iterators (except for the erased element). Unordered maps may invalidate all iterators on rehash.

{{< faq "What happens when I access a map with a missing key using []?" "operator[] default-constructs a value for the key and returns it. This is why m["missing"] inserts an empty string, zero, or nullptr." >}}

Can I use `std::unordered_map` with custom key types?

Yes, but you need to provide a hash function and equality operator. The simplest approach is to specialize std::hash.

What is 'heterogeneous lookup'?

Allows looking up by a type different from the key type. For example, finding std::string keys with std::string_view or const char* without creating a temporary string.

How does `std::map` compare to Python's dict?

Python dict is a hash table (like unordered_map). C++ map is a tree (ordered). C++ unordered_map is closer to Python dict but with explicit control over the hash function.

What is the memory overhead of a map node?

Each node stores key, value, color flag, left/right/parent pointers. For integers, that can be ~40 bytes overhead per entry vs ~4 bytes in a sorted vector.

Mini Project

Build an LRU (Least Recently Used) cache using std::unordered_map and std::list:

#include <iostream>
#include <unordered_map>
#include <list>
#include <string>

class LRUCache {
private:
    using Entry = std::pair<int, int>;
    std::list<Entry> items_;
    std::unordered_map<int, std::list<Entry>::iterator> map_;
    size_t capacity_;
    
public:
    LRUCache(size_t cap) : capacity_(cap) {}
    
    int get(int key) {
        auto it = map_.find(key);
        if (it == map_.end()) return -1;
        
        // Move to front (most recently used)
        items_.splice(items_.begin(), items_, it->second);
        return it->second->second;
    }
    
    void put(int key, int value) {
        auto it = map_.find(key);
        
        if (it != map_.end()) {
            // Update existing
            it->second->second = value;
            items_.splice(items_.begin(), items_, it->second);
            return;
        }
        
        // Evict if full
        if (items_.size() == capacity_) {
            auto last = items_.back();
            map_.erase(last.first);
            items_.pop_back();
        }
        
        // Insert new
        items_.emplace_front(key, value);
        map_[key] = items_.begin();
    }
};

int main() {
    LRUCache cache(3);
    cache.put(1, 100);
    cache.put(2, 200);
    cache.put(3, 300);
    
    std::cout << cache.get(1) << "\n";  // 100 (becomes most recent)
    cache.put(4, 400);  // evicts key 2
    
    std::cout << cache.get(2) << "\n";  // -1 (evicted)
    std::cout << cache.get(3) << "\n";  // 300
    std::cout << cache.get(4) << "\n";  // 400
}

What's Next

Maps are key-value stores. The next lesson covers container adaptors: stack (LIFO), queue (FIFO), and priority_queue (heap), and their underlying container customization.

← Previous Set and Multiset — Ordered and Unordered Sets, Performance Next → Stack, Queue, Priority Queue — Container Adaptors and Underlying Containers

Built by the developers of DodaTech

Doda Browser, DodaZIP & Durga Antivirus Pro

Home Browse Cpp