.upper_bound()

The .upper_bound() method is a built-in function in C++ STL (Standard Template Library) maps that returns an iterator pointing to the first element in the container whose key is considered to go after the specified key. In simpler terms, it finds the first element that is greater than the given key.

Maps in C++ are associative containers that store elements formed by a key-value pair in a specific order. The .upper_bound() method is particularly useful for tasks such as finding insertion points, range queries, and implementing algorithms that require identifying the next element in a sorted sequence. This method leverages the fact that maps maintain their elements in a sorted order based on keys, making it an efficient operation with logarithmic complexity.

Syntax

map_name.upper_bound(key& k);

Parameters:

• map_name: The name of the map container on which the operation is performed.
• k: The key value to search for. This parameter specifies the key for which the function will find the upper bound.

Return value:

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

Example 1: Finding the Next Element

This example demonstrates how to use the .upper_bound() method to find the next element in a map after a given 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 upper bound of 'b'
  auto it = charMap.upper_bound('b');

  // Displaying the result
  cout << "\nUpper bound of 'b' is: " << it->first << " : " << it->second << endl;

  return 0;
}

to clipboard
Copy to clipboard

The output generated by this code is:

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

Upper bound of 'b' is: c : 3

to clipboard
Copy to clipboard

In this example, a map is created with character keys and integer values. After inserting elements, the .upper_bound() method is called with the key 'b'. The method returns an iterator to the element with key 'c', which is the first element that comes after 'b' in the map.

Example 2: Range-Based Queries

This example demonstrates how to use .upper_bound() for implementing range-based queries in a map:

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

int main() {
  // Creating a map of student scores
  map<string, int> studentScores;

  // Adding student scores
  studentScores["Alice"] = 85;
  studentScores["Bob"] = 72;
  studentScores["Carol"] = 93;
  studentScores["David"] = 64;
  studentScores["Eve"] = 91;

  // Define the range: students from "B" to "E"
  string startName = "B";
  string endName = "E";

  // Finding students within the range using upper_bound
  auto startIter = studentScores.lower_bound(startName); // Starting from "B"
  auto endIter = studentScores.upper_bound(endName);     // Up to but not including "E" and beyond

  // Displaying students in the specified range
  cout << "Students in range [" << startName << " to " << endName << "):" << endl;
  for (auto it = startIter; it != endIter; ++it) {
    cout << it->first << ": " << it->second << endl;
  }

  return 0;
}

to clipboard
Copy to clipboard

The output of this code will be as follows:

Students in range [B to E):
Bob: 72
Carol: 93
David: 64

to clipboard
Copy to clipboard

This example demonstrates how .upper_bound() can be used with .lower_bound() to perform a range query. A map of student names and their corresponding scores is created. Calling .upper_bound("E") returns an iterator to the first student name that comes after ‘E’ alphabetically, defining a range that includes names from ‘B’ to just before ‘E’.

Codebyte Example: Finding Insertion Points

This example demonstrates using .upper_bound() to find the correct position for inserting new elements while maintaining order:

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

void displayInventory(const map<int, string>& inventory) {
  cout << "Current Inventory:" << endl;
  for (const auto& item : inventory) {
    cout << "ID: " << item.first << " - " << item.second << endl;
  }
  cout << endl;
}

int main() {
  // Creating an inventory management system using a map
  map<int, string> inventory;

  // Adding initial items
  inventory[1001] = "Laptop";
  inventory[1003] = "Smartphone";
  inventory[1005] = "Tablet";
  inventory[1007] = "Headphones";

  displayInventory(inventory);

  // Need to insert a new item with ID 1004
  int newItemId = 1004;
  string newItemName = "Smartwatch";

  // Find the correct position to insert using upper_bound
  auto insertPosition = inventory.upper_bound(newItemId);

  cout << "The new item should be inserted before ID: "
       << (insertPosition != inventory.end() ? to_string(insertPosition->first) : "end") << endl;

  // Insert the new item
  inventory[newItemId] = newItemName;

  // Display updated inventory
  displayInventory(inventory);

  return 0;
}

to clipboard
Copy to clipboard

In this example, an inventory system is managed using a map where item IDs are the keys and item names are the values. The .upper_bound() is used to find the position where a new item with ID 1004 should be inserted to maintain the sorted order of the map. This showcases a practical use of .upper_bound() in a real-world scenario.

Frequently Asked Questions

1. What is the difference between .upper_bound() and .lower_bound() in C++ maps?

.upper_bound(k) returns an iterator to the first element whose key is greater than k, while .lower_bound(k) returns an iterator to the first element whose key is not less than k (i.e., greater than or equal to k).

2. What is the time complexity of the .upper_bound() method?

The time complexity is O(log n), where n is the number of elements in the map. This efficiency is possible because maps in C++ are typically implemented as balanced binary search trees.

3. Can .upper_bound() be used on other container types besides maps?

Yes, .upper_bound() is available for other associative containers in the STL like set, multiset, multimap, and also as a standalone algorithm that can be used on any sorted range with std::upper_bound().