Wstęp
Dynamicznie alokowane tablice są bardzo użyteczne. Dynamicznie
rozszerzalne tablice są jeszcze bardziej użyteczne. To nie powinno być dla Ciebie nic nowego - było to zaimplementowane w przykładzie w lekcji o alokacji. O ile sztuczka nie jest skomplikowana, fajnie by było nie implementować tego osobno dla tablicy
int,
double, jakiejś struktury
T itd.. Najlepiej by było nie implementować tego w ogóle, w skrócie dobrze by było mieć jakiś
pojemnik na dane ustalonego typu i niech ten
pojemnik zajmuje się zarządzaniem pamięcią. W niektórych językach programowania nazywa się to kolekcją, w C++ natomiast przyjęło się używać terminu kontenera.
std::vector<> to najprostszy i najbardziej uniwersalny kontener - zwykła rozszerzająca się tablica.
Kontener tablicy std::vector<>
#include <vector>
std::vector < int > mojWektor;
Korzystanie z tego kontenera wymaga dołączenia nagłówka
<vector>. W ostrych nawiasach podajemy typ przechowywanego elementu. Tak utworzona zmienna reprezentuje sobą pustą tablicę liczb typu
int. Do kontenera możemy dodawać nowe elementy, na przykład metodą
push_back(), która dodaje element na koniec.
#include <vector>
#include <iostream>
int main()
{
std::vector < int > wektor;
for( int i = 0; i < 10; ++i )
{
std::cout << "Rozmiar: " << wektor.size() << " Pojemnosc: " << wektor.capacity() << '\n';
wektor.push_back( i );
}
}
Rozmiar: 0 Pojemnosc: 0
Rozmiar: 1 Pojemnosc: 1
Rozmiar: 2 Pojemnosc: 2
Rozmiar: 3 Pojemnosc: 4
Rozmiar: 4 Pojemnosc: 4
Rozmiar: 5 Pojemnosc: 8
Rozmiar: 6 Pojemnosc: 8
Rozmiar: 7 Pojemnosc: 8
Rozmiar: 8 Pojemnosc: 8
Rozmiar: 9 Pojemnosc: 16
size() zwraca rozmiar wektora, licząc w
przechowywanych elementach.
capacity() zwraca rozmiar wektora w
zarezerwowanej pamięci. Jak widać, vector dba o to, by nie alokować pamięci za często. Gdy jest potrzebna realokacja, wszystkie elementy są przenoszone do nowej lokalizacji. Jeśli z góry wiemy, ile potrzeba nam pamięci (lub ile maksymalnie potrzeba nam pamięci), możemy wpływać na oba te rozmiary metodami
resize() i
reserve():
std::vector < int > wektor;
wektor.reserve( 10 );
std::cout << "Rozmiar: " << wektor.size() << " Pojemnosc: " << wektor.capacity() << '\n';
Rozmiar: 0 Pojemnosc: 10
std::vector < int > wektor;
wektor.resize( 10 );
std::cout << "Rozmiar: " << wektor.size() << " Pojemnosc: " << wektor.capacity() << '\n';
Rozmiar: 10 Pojemnosc: 10
Podbicie pojemności pozwala szybciej dodawać elementy, a podbicie rozmiaru
tworzy nowe elementy. Jako drugi argument
resize() można podać wartość, jaką przyjmą ewentualne dodane elementy (ta metoda ustawia rozmiar tablicy, a więc ją powiększa, lub zmniejsza). Dostęp do elementu po indeksie odbywa się tak jak w przypadku tablicy, czy wskaźnika na nią - z użyciem kwadratowych nawiasów:
#include <vector>
#include <iostream>
int main()
{
std::vector < int > wektor;
for( int i = 1; i <= 16; i *= 2 )
wektor.resize( i, i );
for( int i = 0; i < wektor.size(); ++i )
std::cout << wektor[ i ] << ' ';
}
1 2 4 4 8 8 8 8 16 16 16 16 16 16 16 16
| Pomimo tego, że mamy zarezerwowaną pamięć na 100 elementów, z czego przechowywanych jest tylko 10, wyjście poza tablicę tych 10 elementów dalej jest niepoprawne, bo pozostałe 90 elementów to niezainicjalizowana pamięć. Jest to więc coś innego niż rozszerzalna tablica, którą realizowaliśmy wcześniej. Jeśli zaalokujesz tablicę stu zmiennych std::string, wszystkie będą zainicjalizowane do domyślnego stanu. W std::vector<std::string> o rozmiarze zero i zarezerwowanym miejscem na 100 zmiennych, żaden string nie będzie zainicjalizowany. |
Inne sposoby dodawania elementów
Do tej pory było omówione dodawanie elementów na koniec wektora,
push_back(), bo to jest w pewnym sensie specjalność tego kontenera. Jeśli jest wolne miejsce, to jest ono na końcu, więc dodawanie na koniec jest najszybsze. Dostępne jest też opcja wstawiania w dowolne miejsce. W szczególności - na początek. Miej jednak na względzie, że przez to że
std::vector przechowuje dane w ciągłym bloku pamięci, dodawanie elementów w inne miejsce niż na koniec będzie wymagało przemieszczania innych elementów. Wszystkich, jeśli dodajesz na początek.
Dodawaniem elementów, w miejsca inne niż koniec, zajmuje się metoda
insert(). Jedno wywołanie może być użyte do wstawienia więcej niż jednego elementu. Niezależnie od tego co chcemy osiągnąć, pierwszy argument określa 'element', który ma się stać pierwszym 'elementem' po wstawionych elementach. Innymi słowy wstawione elementy będą poprzedzać ten określony w argumencie
insert().
Metoda
insert() nie określa miejsca wstawienia na podstawie indeksu, lecz
iteratora. Iterator to jest coś, co potrafi iterować, na przykład po elementach kontenera, niezależnie od tego, jak są zorganizowane dane w tym kontenerze. Iteratory różnych rodzajów kontenerów mogą dawać różne stopnie swobody w poruszaniu się po elementach.
std::vector to tablica, więc jego iterator zachowuje się jak wskaźnik. Iteratory można dostać wywołując metody
begin(),
end().
begin() zwraca iterator na pierwszy element kontenera, który to element niekoniecznie musi istnieć.
end() zwraca iterator "zakońcowy" (
past-the-end iterator), wskazujący na element za ostatnim, który oczywiście nie istnieje i niekoniecznie musi wskazywać na zarezerwowaną pamięć.
Iteratory wektora są typu std::vector<T>::iterator, bądź std::vector<T>::const_iterator, jeśli wektor jest stałą. Możesz użyć tego typu do tworzenia zmiennych na iteratory:
std::vector < int >::iterator iter = wektor.begin();
auto iter2 = wektor.begin();
|
Iteratory to bardziej wskaźniki niż indeksy, chociaż nie są żadnym z nich. Nie możesz więc mieszać iteratorów z różnych kontenerów.
|
#include <vector>
#include <iostream>
int main()
{
std::vector < int > wektor( 10, 0 );
wektor.insert( wektor.begin(), 1 );
wektor.insert( wektor.end(), 3, 2 );
wektor.insert( wektor.begin() + 3, 3 );
for( int i = 0; i < wektor.size(); ++i )
std::cout << wektor[ i ] << ' ';
}
1 0 0 3 0 0 0 0 0 0 0 0 2 2 2
Usuwanie elementów
Metoda
pop_back() usuwa z wektora ostatni element, metoda
clear() usuwa wszystkie. Oprócz tego jest również metoda
erase(), która pozwala usunąć zakres elementów z dowolnego miejsca w wektorze, na podstawie iteratora, lub pary iteratorów. W przypadku pary, pierwszy iterator wskazuje na pierwszy element do usunięcia, a drugi wskazuje na pierwszy element do zostawienia. Jeśli oba iteratory z pary są sobie równe, żaden element nie zostanie usunięty.
#include <vector>
#include <iostream>
int main()
{
std::vector < int > wektor;
for( int i = 0; i < 10; ++i )
wektor.push_back( i );
wektor.erase( wektor.begin() );
wektor.erase( wektor.begin() + 2, wektor.begin() + 4 );
wektor.erase( wektor.begin() + 4, wektor.end() );
for( int i = 0; i < wektor.size(); ++i )
std::cout << wektor[ i ] << ' ';
}
1 2 5 6
Ważność iteratorów
Jeśli zdarzy Ci się potrzeba przechowywania iteratorów, pamiętaj że nie mają one nieograniczonej ważności. Operacje na kontenerze mogą unieważniać wszystkie, lub tylko niektóre iteratory. To zależy już od rodzaju operacji i rodzaju kontenera. Nie ma obawy, jeśli pobierasz iteratory tylko dla wykonania jakiejś jednej operacji. W przeciwnym razie powinieneś upewnić się w dokumentacji, czy używane operacje nie powodują unieważnienia twoich iteratorów. W przypadku wektora, reguła jest prosta -
jeśli element został usunięty, lub zmienił lokalizację, to iterator na niego jest nieważny. A więc: