.lower_bound()

arisdelaCruz1413618857's avatar
arisdelaCruz1413618857's avatar
arisdelaCruz1413618857
Published May 11, 2025
Contribute to Docs

The .lower_bound() method in C++ is a member function of the std::map and std::multimap containers. It is used to find the first element whose key is not less than a specified key (i.e., greater than or equal to the given key). This method returns an iterator pointing to that element. If no such element exists—meaning all keys are less than the specified key—it returns an iterator to the container’s end().

Since std::map and std::multimap store elements in sorted order based on their keys, .lower_bound() efficiently utilizes this ordering to perform fast lookups. It is particularly useful in range queries, binary search-like operations, and algorithms that require locating boundary elements. The time complexity of .lower_bound() is O(log n) due to the underlying Red-Black Tree structure.

Syntax

map_name.lower_bound(const Key& k);

Parameters:

  • map_name: The name of the std::map or std::multimap container on which the method is called.
  • k: A constant reference to the key value. This specifies the key for which the function will find the lower bound.

Return value:

  • Returns an iterator pointing to the first element in the map whose key is greater than or equal to k.
  • If no element is found (all keys are less than k), it returns map_name.end().
  • If the map is const-qualified, it returns a const_iterator; otherwise, it returns an iterator.

Example 1: Finding the First Element Greater Than or Equal to a Key

This example demonstrates how to use the .lower_bound() method to find the first element in a map that is greater than or equal to a specified key:

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


int main() {
  // Creating a map with character keys and integer values
  map<char, int> charMap;


  // Inserting elements into the map
  charMap['a'] = 1;
  charMap['b'] = 2;
  charMap['c'] = 3;
  charMap['e'] = 5;


  // Displaying the original map
  cout << "Map contents:" << endl;
  for (auto& pair : charMap) {
    cout << pair.first << " : " << pair.second << endl;
  }


  // Finding the lower bound for key 'c'
  auto it = charMap.lower_bound('c');


  if (it != charMap.end()) {
    cout << "Lower bound for 'c': " << it->first << " : " << it->second << endl;
  } else {
    cout << "'c' not found in the map." << endl;
  }


  return 0;
}

The output generated by this code is:

Map contents:
a : 1
b : 2
c : 3
e : 5


Lower bound for 'c': c : 3

In this example, the .lower_bound() method is used to find the first element in the map that is greater than or equal to the key 'c'. The iterator it points to the element with key 'c', and its value is displayed. If the key 'c' were not present in the map, the program would indicate that the key was not found.

Example 2: Finding the Lower Bound for a Non-Existent Key

This example demonstrates how to use .lower_bound() to find the lower bound for a non-existent key:

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


int main() {
  // Creating a map with character keys and integer values
  map<char, int> charMap;


  // Inserting elements into the map
  charMap['a'] = 1;
  charMap['b'] = 2;
  charMap['c'] = 3;
  charMap['e'] = 5;


  // Displaying the original map
  cout << "Map contents:" << endl;
  for (auto& pair : charMap) {
    cout << pair.first << " : " << pair.second << endl;
  }


  // Finding the lower bound for key 'd'
  auto it = charMap.lower_bound('d');


  if (it != charMap.end()) {
    cout << "Lower bound for 'd': " << it->first << " : " << it->second << endl;
  } else {
    cout << "'d' not found in the map." << endl;
  }


  return 0;
}

The output generated by this code is:

Map contents:
a : 1
b : 2
c : 3
e : 5
Lower bound for 'd': e : 5

In this example, the .lower_bound() method is used to find the first element in the map that is greater than or equal to the key 'd'. Since 'd' is not present, the method returns an iterator to 'e', the first key greater than 'd'.

Codebyte Example: Using .lower_bound() with a Custom Comparator

This example demonstrates how to use .lower_bound() with a custom comparator to find the lower bound for a key in a map with a custom sorting order:

Code
Output
Loading...


All contributors
Contribute to Docs
Learn C++ on Codecademy