Topic 63 of 91 9. C++ Standard Template Library (STL) Interactive Tutorial

std::multimap in C++: Multiple Values for the Same Key

7 mins read Last updated: 26 Sep 2026 16,631 views

On This Page0 sectionsQuick jump to subtopic

Direct Answer & Core Concept

std::multimap is an associative container that allows multiple key-value pairs to have identical keys, stored in sorted key order using a Red-Black Tree. You retrieve all values for a specific key using equal_range(key), which returns a pair of iterators [lower_bound, upper_bound).

Detailed Explanation & Mechanics

1. Duplicate Key Organization:

Architecture Diagram

MULTIMAP TREE NODES:
Key: "error"  ──► "Disk full"
Key: "error"  ──► "Connection timed out"
Key: "info"   ──► "System started"
Key: "warn"   ──► "High memory usage"

2. Querying Duplicate Keys:

equal_range(k): Returns std::pair bounding all matching keys in $O(\log N)$.
count(k): Returns the number of occurrences of key k.

Runnable Code Example: std::multimap in C++: Multiple Values fo

C++20 / C++23

main.cpp

Run Online

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

int main() {
    std::multimap<std::string, std::string> phoneBook;

    phoneBook.insert({"Alice", "+1-555-0101"});
    phoneBook.insert({"Alice", "+1-555-0999"}); // Second number for Alice
    phoneBook.insert({"Bob",   "+1-555-0202"});
    phoneBook.insert({"Alice", "+1-555-1234"}); // Third number

    std::cout << "All Numbers for Alice (using equal_range):\n";
    auto [start, end] = phoneBook.equal_range("Alice");
    for (auto it = start; it != end; ++it) {
        std::cout << "  - " << it->first << ": " << it->second << "\n";
    }

    std::cout << "Total numbers registered for Alice: " << phoneBook.count("Alice") << "\n";
    return 0;
}

Common C++ Technical Interview Questions & Answers

Interview Prep

Q: Does `std::multimap` support `operator[]`?

A: No. `operator[]` cannot be supported because a single key may correspond to multiple different values, making unambiguous single-value retrieval impossible.

Q: What is the complexity of finding the range of identical keys in `std::multimap`?

A: $O(\log N)$ using `.equal_range(k)`. Traversing the matching elements within that range takes $O(K)$, where $K$ is the number of matching elements.

Key Takeaways, Modern Best Practices & Idioms

C++ Best Practices & Production Rules

• Use .equal_range() rather than separate .lower_bound() and .upper_bound() calls to avoid redundant tree traversals.
• Use std::multimap for one-to-many relationship modeling (e.g. tag-to-articles, category-to-products).
• Insert elements with .insert() or .emplace() since operator[] is not provided.

Previous Topicstd::set in C++: Unique Sorted Elements and Set Operations

Next Topicstd::multiset in C++: Sorted Collections That Allow Duplicates