Aquí discutiremos la implementación de lower_bound() y upper_bound() en vector de pares .
límite inferior():
Devuelve un iterador que apunta al primer elemento del rango [primero, último] que tiene un valor mayor o igual que el valor dado «val» . Pero en Vector of Pairs lower_bound() for pair(x, y) devolverá un iterador que apunta a la posición del par cuyo
- el primer valor es mayor que x
- el primer valor es igual a x y el segundo valor es mayor que igual a y .
Si no se cumplen los criterios mencionados anteriormente, devuelve un iterador al índice que está fuera de los vectores de pares.
límite_superior():
Devuelve un iterador que apunta al primer elemento del rango [primero, último] que tiene un valor mayor que el valor dado «val» . Pero en Vector of Pairs upper_bound() for pair(x, y) devolverá un iterador que apunta a la posición del par cuyo
- El primer valor es igual a x y el segundo valor es mayor que y, o
- cuyo primer valor es mayor que x.
A continuación se muestra el programa para demostrar lower_bound() y upper_bound() en vectores de pares:
Programa 1:
CPP
// C++ program to demonstrate lower_bound()
// and upper_bound() in Vectors of Pairs
#include <bits/stdc++.h>
using namespace std;
// Function to implement lower_bound()
void findLowerBound(vector<pair<int, int> >& arr,
pair<int, int>& p)
{
// Given iterator points to the
// lower_bound() of given pair
auto low = lower_bound(arr.begin(), arr.end(), p);
cout << "lower_bound() for {2, 5}"
<< " is at index: " << low - arr.begin() << endl;
}
// Function to implement upper_bound()
void findUpperBound(vector<pair<int, int> >& arr,
pair<int, int>& p)
{
// Given iterator points to the
// upper_bound() of given pair
auto up = upper_bound(arr.begin(), arr.end(), p);
cout << "upper_bound() for {2, 5}"
<< " is at index: " << up - arr.begin() << endl;
}
// Driver Code
int main()
{
// Given sorted vector of Pairs
vector<pair<int, int> > arr;
arr = { { 1, 3 }, { 1, 7 }, { 2, 4 },
{ 2, 5 }, { 3, 8 }, { 8, 6 } };
// Given pair {2, 5}
pair<int, int> p = { 2, 5 };
// Function Call to find lower_bound
// of pair p in arr
findLowerBound(arr, p);
// Function Call to find upper_bound
// of pair p in arr
findUpperBound(arr, p);
return 0;
}
lower_bound() for {2, 5} is at index: 3
upper_bound() for {2, 5} is at index: 4