c++ - razonamiento para std:: lower_bound y std:: upper_bound?
lower bound c++ (9)
STL proporciona funciones de búsqueda binarias std :: lower_bound y std :: upper_bound, pero tiendo a no usarlas porque no he podido recordar lo que hacen, porque sus contratos me parecen completamente desconcertantes.
Solo al mirar los nombres, supongo que "lower_bound" podría ser la abreviatura de "last low bound",
es decir, el último elemento en la lista ordenada que es <= el valor dado (si hay alguno).
Y de manera similar, supongo que "upper_bound" podría ser la abreviatura de "first upper bound",
es decir, el primer elemento en la lista ordenada que es> = el valor dado (si lo hay).
Pero la documentación dice que hacen algo bastante diferente de eso, algo que parece ser una mezcla de retrocesos y aleatorios para mí. Parafraseando el documento:
- lower_bound encuentra el primer elemento que es> = val
- upper_bound encuentra el primer elemento que es> val
Así que lower_bound no encuentra un límite inferior en absoluto; encuentra el primer límite superior ? Y upper_bound encuentra el primer límite superior estricto .
¿¿Tiene esto algún sentido?? ¿Cómo lo recuerdas?
Acepté la respuesta de Brian, pero me di cuenta de que otra forma útil de pensar al respecto me aporta claridad, así que la agrego como referencia.
Piense en el iterador devuelto como apuntando, no en el elemento * iter, sino justo antes de ese elemento, es decir, entre ese elemento y el elemento anterior en la lista, si hay alguno. Al pensarlo de esa manera, los contratos de las dos funciones se vuelven simétricos: lower_bound encuentra la posición de la transición de <val a> = val, y upper_bound encuentra la posición de la transición de <= val a> val. O para decirlo de otra manera, lower_bound es el comienzo del rango de elementos que se comparan con val (es decir, el rango que std :: equal_range devuelve), y upper_bound es el final de ellos.
Deseo que lo hablen así (o cualquiera de las otras buenas respuestas dadas) en los documentos; eso lo haría mucho menos desconcertante!
Ambas funciones son muy similares, ya que encontrarán un punto de inserción en una secuencia ordenada que preservará el género. Si no hay elementos existentes en la secuencia que sean iguales al elemento de búsqueda, devolverán el mismo iterador.
Si intentas encontrar algo en la secuencia, usa lower_bound - apuntará directamente al elemento si se encuentra.
Si está insertando en la secuencia, use upper_bound : conserva el orden original de los duplicados.
Considera la secuencia
1 2 3 4 5 6 6 6 7 8 9
límite inferior para 6 es la posición de los primeros 6.
límite superior para 6 es la posición del 7.
estas posiciones sirven como par común (inicio, final) que designa la ejecución de 6 valores.
Ejemplo:
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
auto main()
-> int
{
vector<int> v = {1, 2, 3, 4, 5, 6, 6, 6, 7, 8, 9};
auto const pos1 = lower_bound( v.begin(), v.end(), 6 );
auto const pos2 = upper_bound( v.begin(), v.end(), 6 );
for( auto it = pos1; it != pos2; ++it )
{
cout << *it;
}
cout << endl;
}
En este caso, creo que una imagen vale más que mil palabras. Supongamos que los usamos para buscar 2 en las siguientes colecciones. Las flechas muestran qué iteradores devolverían los dos:
Entonces, si tiene más de un objeto con ese valor ya presente en la colección, lower_bound le dará un iterador que se refiere al primero de ellos, y upper_bound dará un iterador que se refiere al objeto inmediatamente después del último de ellos.
Esto (entre otras cosas) hace que los iteradores devueltos se puedan utilizar como el parámetro de hint para insert .
Por lo tanto, si los usa como la sugerencia, el elemento que inserte se convertirá en el primer primer elemento con ese valor (si utilizó lower_bound ) o en el último elemento con ese valor (si utilizó upper_bound ). Si la colección no contenía un elemento con ese valor previamente, igual obtendrá un iterador que puede usarse como una hint para insertarlo en la posición correcta en la colección.
Por supuesto, también puede insertar sin una pista, pero con una pista obtiene una garantía de que la inserción se completa con una complejidad constante, siempre que el nuevo elemento a insertar se pueda insertar inmediatamente antes del elemento señalado por el iterador (como lo hará en ambos casos).
Para una matriz o vector:
std :: lower_bound: Devuelve un iterador que apunta al primer elemento en el rango que es
- menor o igual que el valor. (para matriz o vector en orden decreciente)
- mayor o igual que el valor. (para matriz o vector en orden creciente)
std :: upper_bound: devuelve un iterador que apunta al primer elemento en el rango que es
menos que valor. (para matriz o vector en orden decreciente)
mayor que el valor. (para matriz o vector en orden creciente)
Sí. La pregunta tiene absolutamente un punto. Cuando alguien les dio a estas funciones sus nombres, pensaban solo en arreglos ordenados con elementos repetitivos. Si tiene una matriz con elementos únicos, "std :: lower_bound ()" actúa más como una búsqueda de un "límite superior" a menos que encuentre el elemento real.
Entonces esto es lo que recuerdo de estas funciones:
- Si está realizando una búsqueda binaria, considere usar std :: lower_bound () y lea el manual. std :: binary_search () también se basa en él.
- Si desea encontrar el "lugar" de un valor en una matriz ordenada de valores únicos, considere std :: lower_bound () y lea el manual.
- Si tiene una tarea arbitraria de búsqueda en una matriz ordenada, lea el manual para std :: lower_bound () y std :: upper_bound ().
Si no se lee el manual después de uno o dos meses desde la última vez que se usaron estas funciones, es casi seguro que se produzca un error.
Ya hay buenas respuestas sobre qué std::lower_bound y std::upper_bound es.
Me gustaría responder a su pregunta "¿cómo recordarlos ?
Es fácil de entender / recordar si dibujamos una analogía con los métodos STL begin() y end() de cualquier contenedor. begin() devuelve el iterador de inicio al contenedor, mientras que end() devuelve el iterador que está justo fuera del contenedor y todos sabemos cuán útiles son mientras iteran.
Ahora, en un contenedor ordenado y con un valor dado, lower_bound y upper_bound devolverán el rango de iteradores para ese valor fácil de iterar (al igual que begin y end)
Uso práctico ::
Aparte del uso mencionado anteriormente en la lista ordenada para acceder al rango de un valor determinado, una de las mejores aplicaciones de upper_bound es acceder a datos que tienen una relación de varios a uno en un mapa.
Por ejemplo, considere la siguiente relación: 1 -> a, 2 -> a, 3 -> a, 4 -> b, 5 -> c, 6 -> c, 7 -> c, 8 -> c, 9 - > c, 10 -> c
Las 10 asignaciones anteriores se pueden guardar en el mapa de la siguiente manera:
numeric_limits<T>::lowest() : UND
1 : a
4 : b
5 : c
11 : UND
Los valores se pueden acceder mediante la expresión (--map.upper_bound(val))->second .
Para valores de T que van desde el más bajo hasta 0, la expresión devolverá UND . Para valores de T que van de 1 a 3, devolverá ''a'' y así sucesivamente ..
Ahora, imagina que tenemos 100s de mapeo de datos a un valor y 100s de tales mapeos. Este enfoque reduce el tamaño del mapa y lo hace eficiente.
Si tiene varios elementos en el rango [ first , last ) cuyo valor es igual al valor val que está buscando, entonces el rango [ l , u ) donde
l = std::lower_bound(first, last, val)
u = std::upper_bound(first, last, val)
es precisamente el rango de elementos igual a val dentro del rango [ first , last ). Entonces l y l somos el "límite inferior" y el "límite superior" para el rango igual . Tiene sentido si estás acostumbrado a pensar en términos de intervalos medio abiertos.
(Tenga en cuenta que std::equal_range devolverá tanto el límite inferior como el superior en un par, en una sola llamada).
std::lower_bound
Devuelve un iterador que apunta al primer elemento en el rango [primero, último] que no es menor que (es decir, mayor o igual a ) valor.
std::upper_bound
Devuelve un iterador que apunta al primer elemento en el rango [primero, último) que es mayor que el valor.
Entonces, al mezclar tanto el límite inferior como el superior, puedes describir exactamente dónde comienza tu rango y dónde termina.
¿¿Tiene esto algún sentido??
Sí.
Ejemplo:
imaginar vector
std::vector<int> data = { 1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6 };
auto lower = std::lower_bound(data.begin(), data.end(), 4);
1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6
// ^ lower
auto upper = std::upper_bound(data.begin(), data.end(), 4);
1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6
// ^ upper
std::copy(lower, upper, std::ostream_iterator<int>(std::cout, " "));
impresiones: 4 4 4