Cześć!
Potrzebuje struktury która będzie pozwalała na usuwanie elementów oraz opdpowiadała ile elementów jest mniejszych od wartości w złożoności (conajmniej) O(log n), wydaje mi się że multiset
mogłoby spełniać tą funkcję z pomocą equal_range
(lub lower_bound
) tylko wtedy dostaję dwa iteratory. Czy jest możliwę stwierdzić ile elementów znajduję się pomiędzy nimi?
np. Mam takiego mulitseta
{1, 2, 2, 3, 3, 3, 4, 4, 4, 4} i chcę wiedzieć ile elementów jest mniejszych niż 4, więc używam magicznej funkcji
int ile_elementow_jest_mniejszych_niz(int liczba)
która zwraca 6
EDIT:
Funkcja musi działać w O(1)