Este enunciado ha sido probado por nuestros expertos para asegurar la exactitud de nuestro tutorial.
Solución:
-
Límite inferior: primer elemento que es mayor o igual.
-
Cota superior: primer elemento que es estrictamente mayor.
Ejemplo:
+- lb(2) == ub(2) +- lb(6) +- lb(8)
| == begin() | == ub(6) | +- ub(8) == end()
V V V V
+---+---+---+---+---+---+---+---+---+---+---+
| 3 | 4 | 4 | 4 | 4 | 5 | 7 | 7 | 7 | 7 | 8 |
+---+---+---+---+---+---+---+---+---+---+---+
^ ^ ^
| | |
+- lb(4) +- ub(4) +- lb(9) == ub(9) == end()
|- eq-range(4) -|
Como puede ver, el rango igual semiabierto para norte es [lb(n), ub(n)).
Note that both bounds give you meaningful insertion locations for an element of the desired value so that the ordering is maintained, but lower_bound has the distinguishing feature that if the element already exists, then you get an iterator which actually points to that element. Thus you can use lower_bound on an ordered range to implement your own unique-membership or multiple-membership container.
void insert(Container & c, T const & t)
auto it = std::lower_bound(c.begin(), c.end(), t);
// if unique container:
if (it != c.end() && *it == t) /* error, element exists! */ return;
c.insert(it, t);
It returns the iterator one past the last element that is less than the value asked for. This is useful as an insertion position (and that’s why the function returns that iterator). It’s also useful that the half-open range first, lower_bound(first, last, value) specifies all values less than value.
upper_bound returns the iterator one past the last element [less than or equal to / not greater than] el valor solicitado. O estrictamente: el último elemento cuyo valor no es menor que, ya que ambos algoritmos tratan exclusivamente con comparadores menores que.
Si desea que el iterador anterior al iterador sea devuelto por lower_boundpuede restar 1 (para un iterador de acceso aleatorio), disminuir (para un iterador bidireccional) o realizar una búsqueda lineal en lugar de usar lower_bound (para un iterador directo que no es ninguno de esos).
Tenga cuidado con el caso extremo de que no hay ningún elemento menor que el valor solicitado, en cuyo caso no puede tener lo que desea, porque no existe. lower_bound por supuesto, devuelve el comienzo del rango en ese caso, por lo que no necesita un valor de retorno de caso especial.
Dado que esto ha sido reabierto, intentaré que mi comentario sea una respuesta.
El nombre lower_bound es matemáticamente incorrecto. Un mejor nombre podría ser least_upper_bound, pero eso probablemente confundiría a la mayoría de las personas sin mentalidad matemática. (Y entonces como se llama upper_bound? almost_least_upper_bound? ¡Sí!)
Mi consejo: supere el hecho de que los nombres lower_bound y upper_bound son técnicamente incorrectos. Las dos funciones definidas son bastante útiles. Piense en esas funciones como un abuso útil de la notación.
Para hacer matemáticamente correcto lower_bound función que se ajusta al concepto de C++ de un iterador, la función tendría que devolver un iterador inverso en lugar de un iterador directo. Devolver un iterador inverso no es tan útil como el enfoque adoptado por el quizás mal llamado lower_bound y upper_boundy el concepto de devolver un iterador inverso choca con el hecho de que no todos los contenedores son reversibles.
¿Por qué un iterador inverso? Así como no hay garantía de que exista un límite superior en el contenedor, tampoco hay garantía de que exista un límite inferior. La existencia lower_bound y upper_bound regreso end() para indicar que el valor buscado está fuera de escala alto. A true el límite inferior tendría que volver rend() para indicar que el valor buscado está fuera de escala bajo.
Hay una manera de implementar un true límite inferior en forma de un iterador directo, pero tiene el precio de abusar del significado de end() para significar “no hay límite inferior”. El problema con este abuso de notación es que algún usuario de la función podría hacer algo equivalente a true_lower_bound(off_scale_low_search_value)-1 ¡y voilá! uno tiene un puntero al elemento más grande del conjunto.
Dicho esto, aquí está cómo hacerlo. Tener el true devolución de función de límite inferior end() si el contenedor está vacío o si el valor buscado es menor que el primer valor del contenedor. De lo contrario volver upper_bound()-1.
Si entiendes que te ha sido de ayuda nuestro artículo, sería de mucha ayuda si lo compartieras con otros entusiastas de la programación y nos ayudes a dar difusión a este contenido.