c-plus-plus
  1. c-plus-plus-multimap
PreviousNext

C++ STL Tutorial: Multimap

Multimap in C++ STL is an associative container that stores elements in key-value pairs, but allows multiple elements to have the same key. This makes it different from other associative containers like map, which allows only one value to be stored for each key.

Syntax

multimap<key_type, value_type> m;

Example

#include <iostream>
#include <map>
using namespace std;

int main() {
    multimap<int, string> m;
    m.insert(make_pair(1, "John"));
    m.insert(make_pair(2, "Jack"));
    m.insert(make_pair(3, "Jill"));
    m.insert(make_pair(1, "Jane"));
    
    cout << "Multimap elements: " << endl;
    for(auto it=m.begin(); it!=m.end(); ++it) {
        cout << it->first << " " << it->second << endl;
    }
    
    return 0;
}

Output

Multimap elements:
1 John
1 Jane
2 Jack
3 Jill

Explanation

In the above example, we create a multimap m with key type int and value type string. We insert four key-value pairs into the multimap, with key values of 1, 2, 3, and 1, respectively. This demonstrates that a multimap can have multiple elements with the same key.

We then iterate over the multimap using an iterator it, and print out the key and value for each element in the multimap.

Use

Multimap is useful when we need to store multiple elements with the same key. This is common in scenarios where we need to associate a key with more than one value. For example, in a dictionary, we might have multiple definitions for the same word.

Another common use case is in graph algorithms, where we might want to store multiple edges with the same source and destination vertices.

Important Points

  • Multimap is an associative container that stores elements in key-value pairs.
  • Multimap allows multiple elements to have the same key.
  • Multimap is implemented as a balanced tree.
  • Multimap operations like inserting and accessing elements have logarithmic complexity O(log n).
  • Multimap provides iterators, allowing us to iterate over the elements in the container.

Summary

Multimap is a useful associative container in the C++ STL, allowing us to store multiple elements with the same key. It is implemented as a balanced tree, and provides operations with logarithmic complexity. Multimap is often used in applications where we need to associate multiple values with a single key, such as in dictionaries or graph algorithms.

MapBitset
Published on: