En este artículo, discutiremos la implementación de lower_bound() y upper_bound() en una lista de pares .
- lower_bound(): Devuelve un iterador que apunta al primer elemento del rango [first, last) que tiene un valor mayor o igual al valor dado “val” . Pero en List of Pairs lower_bound() for pair(x, y) devolverá un iterador que apunta a la posición del par cuyo primer valor es mayor o 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 la Lista de pares. - upper_bound(): Devuelve un iterador que apunta al primer elemento del rango [first, last) que tiene un valor mayor que el valor dado “val” . Pero en List of Pairs upper_bound() for pair(x, y) devolverá un iterador que apunta a la posición del par cuyo primer valor es mayor que x y el segundo valor es mayor que y .
Si no se cumplen los criterios mencionados anteriormente, devuelve un iterador al índice que está fuera de la lista de pares.
A continuación se muestra el programa para demostrar lower_bound() y upper_bound() en una lista de pares:
Programa:
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;
}
Producción:
lower_bound() for {2, 5} is at index: {2, 5 }
upper_bound() for {2, 5} is at index: {3, 8 }