Szukam klasy kontenera C++, która jest indeksowana jak std::vector, ale ma szybkie wstawianie, usuwanie i indeksowanie. Na przykład interfejs vector zaimplementowany z podstawowym drzewem równoważenia będzie miał również wstawienia/usunięcie O (logN) i indeksowanie O (logN).Kontener z szybkimi wkładkami i indeksem?
Aby było jasne: nie szukam std::map<int, T>. Wstawienie elementu o indeksie N powinno zwiększyć indeksy wszystkich kolejnych elementów w tablicy, co nie byłoby możliwe w przypadku std::map<int, T>.
Znalazłem AVL Array, który robi dokładnie to, czego szukam. Ma odpowiedni interfejs, ale chciałbym zobaczyć, czy są inne opcje.
Czy znasz jakieś inne wdrożenia (jakości produkcji)? Może coś bardziej popularnego (czy boost ma coś w tym stylu?). Coś o mniejszym śladzie pamięci? (Węzeł trzymający wskaźnik w macierzy AVL ma 64 bajty na moim komputerze.)
można rozwinąć dlaczego wymaga losowego dostępu? – BeyelerStudios
Wygląda na to, że nie dotyczy tematu - szuka zaleceń dotyczących oprogramowania/biblioteki. –
Nie sądzę, że istnieje prostsza (pod względem struktury danych) rzecz, która robi to, co chcesz, więc wymaga 2 ptr dla następnej/poprzedniej i 3 ptr dla rodzica/lewej/prawej plus oryginalny wskaźnik. Łącznie 6 wskaźników = 48 bajtów dla środowisk 64-bitowych. To najmniej można osiągnąć, jeśli chodzi o ślad pamięci (chyba). – mostruash