¿Por qué std :: set :: lower_bound (x) (efectivamente) se define como el número más pequeño> = x en lugar del número más grande <= x?

Question

Tal vez estoy malinterpretando la definición técnica de lower bound, pero esperaría que si tuviera un conjunto a = { 0, 3, 4 } y calculé el a.lower_bound(2) que el resultado sería 0. Es decir. Yo esperaría std::set::lower_bound a estar cerca del concepto matemático de infimum

Y sin embargo, la biblioteca estándar define como el número más grande de no menos de (>= efectiva) x.

¿Cuál es el razonamiento detrás de esto?

Answer 1

Las funciones "[lower|upper]_bound" están destinadas a devolver un lugar en un conjunto donde podría insertar una clave que no infringiría el orden del conjunto. Debido a que un iterador de un conjunto de STL señala antes del siguiente elemento, si lower_bound(2) devolvió un iterador a 0, insertar 2 violaría el orden de su conjunto, ahora sería {2, 0, 3, 4}. El límite superior sirve para mostrar el último lugar donde podría insertar sin violar el orden establecido.

Esto es más útil si su conjunto puede tener entradas duplicadas. Considere {0, 3, 3, 4}. lower_bound(3) devolvería un iterador aquí: {0, *, 3, 3, 4}, mientras que upper_bound(3) lo devolvería aquí: {0, 3, 3, *, 4}.

Answer 2

Puede ser útil considerar el comportamiento de lower_bound y upper_bound juntos.

En el STL, los rangos son siempre intervalos de apertura cerrada. El rango delimitado por dos iteradores, first y last, incluye todos los elementos entre first y last, incluidos first y excluyendo last. Usando la notación de intervalo, representaríamos esto como [first, last).

lower_bound y upper_bound están definidos de tal manera que se encuentran con la gama de elementos que comparan igual al valor especificado. Si itera entre lower_bound(x) y upper_bound(x), iterará sobre todos los elementos que se comparen igual a x. Si ningún elemento es igual a x, entonces se garantiza que lower_bound(x) == upper_bound(x).

Esta característica es menos importante para std::map, que tiene a lo sumo un elemento para cada clave, pero es una característica muy útil para contenedores asociativos no únicos y para el que no es miembro std::lower_bound que puede utilizarse con secuencias arbitrarias de elementos ordenados.

[Tenga en cuenta que si desea obtener tanto el límite inferior y superior, debe llamar equal_range lugar, que devuelve ambos.]