Jakiś czas temu potrzebowałem napisać kontener coś w ten deseń.
vector jest fajną rzeczą, ale jego natura powoduje pewien problem, oto on:
std::vector<OBIEKT> obiekty; // tytułowy bohater
// dodajmy 3 obiekty
obiekty.push_back(OBIEKT(...));
obiekty.push_back(OBIEKT(...));
obiekty.push_back(OBIEKT(...));
// teraz załóżmy, że trzeba gdzieś na zewnątrz zwrócić wskaźniki do tych obiektów
OBIEKT* ptr0 = &obiekty[0];
OBIEKT* ptr1 = &obiekty[1];
OBIEKT* ptr2 = &obiekty[2];
// i wszystko jest ok dopóki nie usuwamy naszych obiektów
obiekty.erase(obiekty.begin()); // usuwamy pierwszy obiekt
I po erasie następuje przesunięcie wszystkich obiektów, a więc rzecz która powoduje, że nasze wskaźniki nie pokazują już na te prawidłowe obiekty.
W takim przypadku trzeba zrezygnować z vectora i trzeba użyć czegoś jak lista, w której nie ma przesunięć obiektów. Ale znowu lista z definicji nie mówi nic o miejscu w którym alokowane są obiekty i tak - jeśli zrobimy sobie listę w której, alokujemy kolejne elementy operatorem new, może się zdarzyć, że te elementy będą fizycznie znajdować się daleko od siebie, a to powoduje zwiększenie wymiany pamięci cache, więc znacznie zwalnia wykonanie programu (w grach ma to spore znaczenie).
Oczywiście w jakimś tam testowym programie gdzie wykonamy kilka new'ów obok siebie w praktyce new najpewniej zwróci fragmenty sterty obok siebie, ale załóżmy, że jednak nasz program działa trochę dłużej, obiekty dodajemy w różnych etapach czasowych działania naszego programu, a w między czasie new wywoływany jest jest wielokrotnie do innych celów (dane na stercie są wymieszane), wtedy faktycznie nasza lista najpewniej będzie zawierała obiekty przydzielone na zupełnie innych fragmentach sterty - co jest niepożądane wydajnościowo.
W takim wypadku właśnie trzeba zrobić sobie taką listę, ale działającą jako tablica. Czyli implementujesz faktycznie listą, w której zapamiętujesz adresy kolejnych obiektów, ale wszystkie te obiekty fizycznie alokujesz na tablicy/wektorze/liniowej przestrzeni pamięci.
Czyli technicznie rzecz biorąc robisz tablicę, w której mogą występować puste miejsca (w sensie że logicznie nie istnieje tam obiekt, bo pamięć wiadomo istnieje/jest przydzielona :>), oraz kolejność logiczna elementów nie jest zgodna z kolejnością w tablicy, np. element pierwszy może zawierać adres, który mówi, że następny element jest tym piątym w tablicy :> a następny tym trzecim, a na indeksach drugim i czwartym nie ma "zaalokowanych/utworzonych" obiektów.
Uproszczony schemat:
struct ListItem {
OBIEKT object; // zaalokowane dane obiektu
LitsItem* next; // tylko jedno kierunkowa..
ListItem* prev; // ...albo i dwu :>
};
ListItem list[5]; // wektor/tablica 5 elementów
list[0].next = &list[4]; // pierwszy mówi, że następnym jest ten piąty
list[4].next = &list[2]; // piąty w tablicy, a loigicznie(według listy) drugi, mówi, że trzecim w liście(logicznie), jest ten trzeci w tablicy
list[2].next = NULL; // a ten trzeci jest już ostatnim, więc logicznie na indeksie 1(drugim w tablicy), oraz 3(czwartym binarnie) nie istnieją obiekty, oczywiście logicznie w liście