Multimap find(), lower_bound(), upper_bound() in C++ STL

C++ STL | Multimap find(), lower_bound(), upper_bound(): In this tutorial, we are going to see some useful functions in multimap C++ STL along with its application and use cases.
Submitted by Radib Kar, on June 18, 2020

C++ multimap::find(), multimap::lower_bound(), and multimap::upper_bound() functions

Multimap is used when you need to store the same keys with distinct values where the map fails to do the same.

In this article, we are going to see some useful functions in multimap.

multimap::find() in C++ STL

Similarly, as in the map, multimap provides us a way to search a key.

The syntax of the find function is like below,

iterator find(key);

Find simply returns the iterator to the first occurrence of the key if the key occurs. If the key doesn't occur at all then it returns iterator multimap::end().

In case of multiple occurrences of the same key, it would return an iterator to the first occurrence only.

An example is the following.

Say the multimap mymap already constructed is,

Key	Value
2	8
2	14
3	12
5	10
5	6

Now mymap.find(2) will return iterator mymap.begin() (as to the first element). Where, mymap.find(7) will return mymap.end() as key is not found().

multimap::lower_bound() in C++ STL

Similarly, as in the map, multimap provides us a way to search a key.

The syntax of the find function is like below,

iterator lower_bound(key);

Find simply returns the iterator to the first occurrence of the key if the key occurs. If the key doesn’t occur at all then it returns an iterator to the next greater element. If the key is greater than the maximum key in the multimap it will return an iterator to pair <search_key,0>.

In case of multiple occurrences of the same key, it would return an iterator to the first occurrence only .

An example is the following.

Say the multimap mymap already constructed is,

Key	Value
2	8
2	14
3	12
5	10
5	6

Now mymap.lower_bound(2) will return iterator mymap.begin() (as to the first element). Where mymap.lower_bound(4) will return an iterator to the entry <5,10> as the key is not found and 5 is the next greater key.

multimap::upper_bound() in C++ STL

Similarly, as in the map, multimap provides us a way to search a key.

The syntax of the find function is like below:

iterator upper_bound(key);

Find simply returns the iterator to the next greater key of the searched key. If the searched key is greater than or equals to max key present in the multimap then it returns an iterator to pair <search_key,0>.

An example is the following.

Say the multimap mymap already constructed is

Key	Value
2	8
2	14
3	12
5	10
5	6

Now mymap.upper_bound(2) will return iterator to pair <3,12> (3 is next greater key of 2). Where, mymap.lower_bound(5) will return iterator to the entry <5,0> as next greater key doesn’t exist for 5.

Also some other trivial functions are: size() and count() whose uses are exactly same as map.

C++ implementation of multimap find(), lower_bound(), upper_bound()

#include <bits/stdc++.h>
using namespace std;

int main()
{
    multimap<int, int> mymultimap;
    
    // insertion in multimap
    cout << "Inserting like above example\n";
    mymultimap.insert(make_pair(5, 10));
    mymultimap.insert(make_pair(2, 8));
    mymultimap.insert(make_pair(3, 12));
    mymultimap.insert(make_pair(2, 14));
    mymultimap.insert(make_pair(5, 6));

    cout << "Printing the multimap\n";
    multimap<int, int>::iterator ij;
    for (ij = mymultimap.begin(); ij != mymultimap.end(); ij++) {
        cout << "key: " << ij->first << " ,value: " << ij->second << endl;
    }

    cout << "finding key 3\n";
    ij = mymultimap.find(3);
    cout << "key: " << ij->first << " ,value: " << ij->second << endl;

    cout << "finding lower bound for 1\n";
    ij = mymultimap.lower_bound(1);
    cout << "key: " << ij->first << " ,value: " << ij->second << endl;

    cout << "finding lower bound for 2\n";
    ij = mymultimap.lower_bound(2);
    cout << "key: " << ij->first << " ,value: " << ij->second << endl;

    cout << "finding lower bound for 5\n";
    ij = mymultimap.lower_bound(5);
    cout << "key: " << ij->first << " ,value: " << ij->second << endl;
    cout << "finding lower bound for 6\n";
    ij = mymultimap.lower_bound(6);
    cout << "key: " << ij->first << " ,value: " << ij->second << endl;

    cout << "finding upper bound for 1\n";
    ij = mymultimap.upper_bound(1);
    cout << "key: " << ij->first << " ,value: " << ij->second << endl;

    cout << "finding upper bound for 2\n";
    ij = mymultimap.upper_bound(2);
    cout << "key: " << ij->first << " ,value: " << ij->second << endl;

    cout << "finding upper bound for 5\n";
    ij = mymultimap.upper_bound(5);
    cout << "key: " << ij->first << " ,value: " << ij->second << endl;
    
    cout << "finding upper bound for 6\n";
    ij = mymultimap.upper_bound(6);
    cout << "key: " << ij->first << " ,value: " << ij->second << endl;

    return 0;
}

Output:

Inserting like above example
Printing the multimap
key: 2 ,value: 8
key: 2 ,value: 14
key: 3 ,value: 12
key: 5 ,value: 10
key: 5 ,value: 6
finding key 3
key: 3 ,value: 12
finding lower bound for 1
key: 2 ,value: 8
finding lower bound for 2
key: 2 ,value: 8
finding lower bound for 5
key: 5 ,value: 10
finding lower bound for 6
key: 5 ,value: 0
finding upper bound for 1
key: 2 ,value: 8
finding upper bound for 2
key: 3 ,value: 12
finding upper bound for 5
key: 5 ,value: 0
finding upper bound for 6
key: 5 ,value: 0