Problem z teorią zmiany rozmiaru wektora.

Cześć. Przez jakiś czas męczę się ze zrozumieniem działania wektora. Problem leży w teorii.

W książce autor napisał że wektor zawiera 3 prywatne zmienne składowe:

class vector{
   int sz; //size
   double* elem; //wskaźnik na pierwszy element
   int space; //tu mam problemy, ale z tego co zrozumiałem to jest to ilość miejsca którą wektor może zajmować bez relokacji.
public:
//...
};

W książce jest obrazek który wprowadza w duże zakłopotanie. Pokazuje on że zmienna space "wskazuje" na miejsce daleko za ostatnim elementem wektora( lub że space obejmuję znacznie większą ilość miejsca niż jeden rozmiar jednego elementu typu double.

No i teraz skoro wektor jest pewny że ma space-sz miejsca na przyszłe alokacje elementów, to co się stanie jeśli coś innego zaalokuje miejsce zaraz za wektorem? Nie ma żadnych funkcji sprawdzających, a jednak wszystko działa.

Chodzi ci o to co się stanie jak w pamięci zaraz za obszarem zaalokowanym będzie już coś a my spróbujemy zwiększyć obszar wektora?
Lekcja na dziś: funkcja realloc http://www.cplusplus.com/reference/clibrary/cstdlib/realloc/
W skrócie: na przykład odszukany zostanie spójny kawałek pamięci o odpowiednim rozmiarze i dane zostaną do niego skopiowane (dlatego vector jest dość kosztowną strukturą danych w sytuacji pesymistycznej ;])

Skoro zaalokował pamięć, to już nie można drugi raz zaalokować w tym samym miejscu, bo jest zajęta.

Ale skoro wektor ma zajmować jak najmniej miejsca, to po co alokuje masę nieużywanej pamięci na przyszłe elementy skora wcale nie musi takich być?

@MakeMeHappy bo dzięki temu rzadziej musi wykonywać realokację? o_O Zwykle interesuje nas niska złożoność obliczeniowa, nawet kosztem większego zużycia pamięci.
Wyobraź sobie że wektor alokuje dokładnie tyle ile potrzebuje. Wtedy każda operacja push_back wymaga realokacji i w sytuacji pesymistycznej przepisania całego tego wektora w nowe miejsce...

Skoro zaalokował pamięć, to już nie można drugi raz zaalokować w tym samym miejscu, bo jest zajęta.

To już jest w gestii menedżera pamięci i systemu operacyjnego, czy możliwa jest realokacja w miejscu.

Teoretycznie, jeśli za obecnie zaalokowanym obszarem jest wolne miejsce, to możliwa jest realokacja w tym sensie, że powiększa się zaalokowany obszar, i ewentualnie zeruje tak „dodaną” pamięć, a oryginalne dane nie muszą być wcale przesuwane.

Wątpie, żeby implementacja std:vector uwzględniała realokację. Jeżeli zależy Ci na braku kopiowania (bo np. jest bardzo kosztowne), a małe wydłużenie czasu dostępu do elementu nie ma dużego znaczenia to możesz użyć std:deque.

Nawet jeśli zachodzi kopiowanie, to vector alokuje pamięć z zapasem, więc nie ma kopiowania wszystkiego przy każdym dodaniu elementu.

Okej im dalej czytam tym wszystko dziwniejsze.

 
void vector::reserve(int newalloc){
   if(newalloc<=space) return; //Jeśli ilość pamięci dla przyszłych rozszerzeń jest mniejsza od aktualnej przerwij? 
   double* p= new double[newalloc];//deklarujemy pamięć dla przyszłych rozszerzeń
   for(int i=0;i<sz;++i) 
      p[i]=elem[i];//Po co wypełnia pamięć dla przyszłych rezerwacji zawartością wektora?
   delete elem[]; //A teraz wywala zawartość wektora
   elem = p; //i wskazuje na pamięć dla rozszerzeń?
   space = newalloc;
}

void vector::push_back(double d){
   if (space==0) reserve(8);//jeśli nie ma miejsca dla tego rozszerzenia zarezerwuj 8b. Wszytko ok.
   else if (sz==space) reserve(2*space);// na początku było powiedziane ze space to rozmiar calego wektora razem z miejscem dla rozszerzen. W takim wypadku ta instukcja to to samo co w poprzedniej linijce.
   elem[sz] = d;//ok
   ++sz;//ok
}
:O

void vector::reserve(int newalloc){
   if(newalloc<=space) return; // jeśli już jest zaalokowane miejsce na tyle elementów ile zgłaszamy, lub nawet więcej, przerwij.
   double* p= new double[newalloc]; // alokacja pamięci na CAŁY wektor w potrzebnym rozmiarze
   for(int i=0;i<sz;++i) 
      p[i]=elem[i]; // kopiowanie całej obecnej zawartości do nowego obszaru
   delete elem[]; // zwolnienie starego obszaru
   elem = p; // od tej pory nowy obszar staje się „obowiązujący”
   space = newalloc; // tak samo nowy rozmiar
}

void vector::push_back(double d){
   if (space==0) reserve(8); // jeśli wektor jest pusty, to na początek zarezerwuj miejsca na 8 ELEMENTÓW (nie bajtów)
   else if (sz==space) reserve(2*space); // jeśli jesteśmy „na styk” z wolnym miejscem (nie zostałoby nic), powiększamy rozmiar obszaru dwukrotnie.
   elem[sz] = d;//ok
   ++sz;//ok
}

A więc to tak! Dzięki za pomoc!