🚀 go-pugleaf

Kiedyś myślałem, że odpowiedź na pytanie w tytule jest prosta...

Główną wadą wektora jest to, że usuwanie elementu zachodzi w
pesymistycznym czasie N, a nawet w średnim 0.5*N. Niby wniosek
jest oczywisty: jeśli zajdzie konieczność usuwania elementów ze
środka wektora, to wszelkie prawdziwe lub potencjalne zalety
wektora zostaną pochłonięte przez straty z powolnego usuwania, 
więc należy użyć listy.

Ale ale ale...
Przecież można se na kolanie napisać (albo znaleźć gotowy)
wektor który zamiast typu T, przechowuje strukturę Item:

template<class T>
struct Item {
  int next;
  T t;
};

Pole next to następny wolne element lub wartość -1 gdy element
przechowuje dane. Czyli pole next pełni rolę listy wolnych elementów.

Dodawanie jest tak samo szybkie jak do wektora, a nawet szybsze, bo 
nie alokujemy, tylko kopiujemy na wcześniej prealokowane pozycje. 
Usuwanie jest bardzo szybkie, tylko wpisujemy w next następną
wolną pozycję a usuwaną zapamiętujemy jako głowę listy. Przeiterowanie
takiego wektora będzie też szybsze niż przeiterowanie listy, oczywiście
pod warunkiem, że nie usuniemy więcej niż kilka procent elementów.

Więc odpowiedź na pytanie w tytule już się robi trudna, bo zależy od
tego, ile dodamy elementów maksymalnie, ile średnio usuniemy i jak
często będziemy iterować po całości. A to dopiero rozgrzewka. Dlaczego
to dopiero rozgrzewa? 

A no dlatego, że w wektorze można usuwać poprzez zastąpienie elementu
usuwanego elementem ostatnim. Rozwiązanie takie ma wadę: będzie trzeba
zmienić wszystkie odwołania w całym programie do ostatniego elementu.

Na tym nie koniec. Można zadeklarować zbiór usuniętych elementów. Zbiór
oparty o hash-table szybko testuje, czy wpis spod indexu x jest wolny
czy zajęty, jednak w trakcie iterowania trzeba wykonać N testów - mimo
wszystko może to być wolne. 

Można zamiast hash-table użyć drzewa do zapamiętania zwolnionych pozycji.
Szukamy pierwszej pozycji wolnej w drzewku i iterujemy po elementach 
zajętych aż do napotkania wcześniej znalezionej pozycji wolnej. Potem 
szukamy następnej pozycji wolnej. Czyli test w drzewie będzie 
wykonany tylko tyle razy, ile zostało zwolnionych elementów - wydaje 
się to bardzo szybkim rozwiązaniem.

To ostatnie rozwiązanie wydaje się bardzo dobre dla wektorów z 
których usuwa się czasami mały odsetek elementów. Rozwiązanie na
drzewie (chodzi oczywiście o drzewo poszukiwań binarnych) będzie
wymagało mało testów i będzie miało mały narzut pamięciowy.

Co myślicie o tym wszystkim?

Pozdrawiam