Praca z std :: map <t1, t2> :: erase (pozycja iteratora)?

Question

Przeczytałem na cplusplus.com, że operacja usunięcia elementu w std::map przez podanie iteratora jako argumentu jest stała.

Jeśli się nie mylę (i proszę, popraw mnie jeśli tak) to iteratory są w zasadzie wskaźnikami do elementów na mapie z operatorem ++, który właśnie zwraca następcę w kolejności obecnego elementu. Zgaduję, że to jest posortowany wynik zostaje osiągnięty po przejściu std::map.

Teraz, jeśli mapa jest czerwonym, czarnym drzewem, czy usunięcie elementu (przy użyciu jego adresu) nie powinno być logarytmiczną operacją czasu, ciekawe, jak robią to w stałym czasie (chyba, że ​​istnieje wysoce nieekonomiczna alternatywa pamięci; aby to zrobić).

Answer 1

Na wstępie, bym nieufnie podchodził do jakichkolwiek informacji, które otrzymałeś od cplusplus.com; strona jest znana z pewnych błędów.

Zwiedzając cppreference.com, otrzymujemy, że złożoność jest amortyzowana stała czas. Oznacza to, że każda sekwencja operacji n erase powinna zająć czas O (n), nawet jeśli pojedyncza operacja kasowania zajmuje czas większy niż O (1).

Okazuje się, że czas potrzebny do wstawienia lub usunięcia z czerwonego/czarnego drzewa kończy się obliczany w następujący sposób: każde wstawienie lub usunięcie zajmuje czas O (log n), aby znaleźć pozycję dla węzła, ale następnie nie tylko amortyzowana praca O (1) w celu wstawienia lub usunięcia elementu. Oznacza to, że praca polegająca na wstawianiu lub usuwaniu węzła z drzewa czerwonego/czarnego jest zdominowana przez pracę wymaganą do ustalenia, gdzie ten węzeł się znajduje, a nie pracę wymaganą do ponownego zrównoważenia drzewa. W rezultacie, jeśli masz już wskaźnik do czerwonego/czarnego drzewa i chcesz usunąć ten element, musisz tylko dokonać amortyzacji O (1), aby usunąć element. Każde pojedyncze usunięcie może zająć trochę czasu (co najwyżej O (log n)), ale w przypadku strumienia n operacji całkowita praca wynosi co najwyżej O (n).

Należy zauważyć, że standard nie wymaga, aby std::map używać czerwonego/czarnego drzewa. Może wykorzystywać inny typ struktury danych (np. splay tree, scapegoat tree lub deterministyczny skiplist), który gwarantuje również złożoność tego czasu. Co ciekawe, nie wszystkie zrównoważone struktury drzewa wyszukiwania binarnego mogą obsługiwać skasowane usuwanie O (1). Na przykład AVL tree nie ma tej gwarancji.

Mam nadzieję, że to pomoże!

Answer 2

Po przekazaniu iteratora do odwzorowania w celu usunięcia elementu, amortyzowany jest stały czas zgodnie z http://www.cplusplus.com/reference/map/map/erase/.

Amortyzowany stały czas oznacza, że ​​"średni czas na operację, jeśli wykonujesz wiele operacji". Dlatego może zaistnieć pewna operacja, która trwa dłużej niż stały czas, ale jeśli wykonujesz tę samą operację wiele razy, jest ona amortyzowana stała.