Dlaczego std :: set :: lower_bound (x) (efektywnie) jest zdefiniowany jako najmniejsza liczba = = x zamiast największej liczby <= x?

Question

Być może nie rozumiem techniczną definicję lower bound, ale oczekiwałbym, gdybym miał zestaw a = { 0, 3, 4 } i obliczył a.lower_bound(2), że wynik będzie 0. To znaczy. Spodziewam się std::set::lower_bound być blisko pojęciem matematycznym infimum

A jednak średnia biblioteka definiuje ją jako największą liczbą nie mniej niż (w praktyce >=) X.

Jaki jest tego powód?

Answer 1

Funkcje "[lower|upper]_bound" mają na celu zwrócenie miejsca w zestawie, w którym można wstawić klucz, który nie narusza porządku zestawu. Ponieważ iterator zbioru STL wskazuje przed następnym elementem, jeśli lower_bound(2) zwrócił iterator na 0, wstawienie 2 naruszyłoby kolejność zestawu, teraz będzie to {2, 0, 3, 4}. Górna granica służy do pokazania ostatniego miejsca, które można wstawić bez naruszania kolejności zestawów.

Jest to najbardziej przydatne, jeśli zestaw może mieć zduplikowane wpisy kluczowe. Rozważ {0, 3, 3, 4}. lower_bound(3) zwróci iterator tutaj: {0, *, 3, 3, 4}, a upper_bound(3) zwróci go tutaj: {0, 3, 3, *, 4}.

Answer 2

Może pomóc rozważyć zachowanie się lower_bound i upper_bound łącznie.

W STL zakresy są zawsze przerwami otwartymi. Zakres ograniczony przez dwa iteratory, first i last, obejmuje wszystkie elementy między first i last, w tym first i wyłączając last. Używając notacji przedziałowej, będziemy to reprezentować jako [first, last).

są zdefiniowane w taki sposób, że znajdują zakres od elementów, które są równe podanej wartości. Jeśli wykonasz iterację między lower_bound(x) a upper_bound(x), powtórzysz wszystkie elementy porównywane z wartościami x. Jeśli żaden element nie jest równy x, wówczas jest zagwarantowane, że lower_bound(x) == upper_bound(x).

Ta funkcja jest mniej ważna dla std::map, która ma co najwyżej jeden element dla każdego klucza, ale jest bardzo przydatną funkcją dla nieunikalnych pojemników asocjacyjnych i dla niezgłoszenia std::lower_bound, które mogą być używane z dowolnymi sekwencjami posortowanych elementów.

[Zauważ, że jeśli chcą uzyskać zarówno dolną i górną granicę, należy zadzwonić equal_range zamiast, który powraca zarówno.]