Implementation of lower_bound() and upper_bound() in List of Pairs in C++
In this article, we will discuss the implementation of the lower_bound() and upper_bound() in a list of pairs.
- lower_bound(): It returns an iterator pointing to the first element in the range [first, last) which has a value greater than or equals to the given value “val”. But in List of Pairs lower_bound() for pair(x, y) will return an iterator pointing to the position of pair whose the first value is greater than or equals x and the second value is greater than equals to y.
If the above-mentioned criteria are not met, then it returns an iterator to the index which out of the List of pairs. - upper_bound(): It returns an iterator pointing to the first element in the range [first, last) which has a value greater than the given value “val”. But in List of Pairs upper_bound() for pair(x, y) will return an iterator pointing to the position of pair whose the first value is greater than x and the second value is greater than y.
If the above-mentioned criteria are not met, then it returns an iterator to the index which out of the list of pairs.
Below is the program to demonstrate lower_bound() and upper_bound() in a list of pairs:
Program:
C++
// C++ program to demonstrate lower_bound() // and upper_bound() in List of Pairs #include <bits/stdc++.h> using namespace std; // Function to implement lower_bound() void findLowerBound( list<pair< int , int > >& list, pair< int , int >& p) { // Given iterator points to the // lower_bound() of given pair auto low = lower_bound(list.begin(), list.end(), p); cout << "lower_bound() for {2, 5}" << " is at index: {" << (*low).first << ", " << (*low).second << " }" << endl; } // Function to implement upper_bound() void findUpperBound( list<pair< int , int > >& list, pair< int , int >& p) { // Given iterator points to the // upper_bound() of given pair auto up = upper_bound(list.begin(), list.end(), p); cout << "upper_bound() for {2, 5}" << " is at index: {" << (*up).first << ", " << (*up).second << " }" << endl; } // Driver Code int main() { list<pair< int , int > > list; // Given sorted List of Pairs list.push_back(make_pair(1, 3)); list.push_back(make_pair(1, 7)); list.push_back(make_pair(2, 4)); list.push_back(make_pair(2, 5)); list.push_back(make_pair(3, 8)); list.push_back(make_pair(8, 6)); // Given pair {2, 5} pair< int , int > p = { 2, 5 }; // Function Call to find lower_bound // of pair p in arr findLowerBound(list, p); // Function Call to find upper_bound // of pair p in arr findUpperBound(list, p); return 0; } |
Output:
lower_bound() for {2, 5} is at index: {2, 5 } upper_bound() for {2, 5} is at index: {3, 8 }