C++ Programming 9. C++ Standard Template Library (STL) 7 mins read 16,637 views

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

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 re...
Published: Nov 1, 2026Last Updated: Nov 21, 2026Curriculum: Class 12 / AP Physics / JEE-NEETReviewed by: OperateTools Editorial Board
Quick Summary & Direct Answer (AEO / GEO Extraction)

What is std::multimap in C++: Multiple Values for the Same Key? 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 re...

Audience & Scope: Students, educators, and candidates preparing for academic examinations and technical assessments in C++ Programming.
What is std::multimap, how does it store duplicate keys, and how do you retrieve all values associated with a key?
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).

Explanation & In-Depth Details

1. Duplicate Key Organization:
```text
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<iterator, iterator>` bounding all matching keys in $O(\log N)$.
- `count(k)`: Returns the number of occurrences of key `k`.

Code Example

#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;
}

Interview Question & Tips

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.

Best Practices

• 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.
Academic Standards & Verified Citations

This study reference for std::multimap in C++: Multiple Values for the Same Key is curated and verified against recognized curriculum benchmarks, peer-reviewed textbooks, and official technical documentation:

C++ Programming