Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?
Autor: pekfos
Kurs C++

Kontener std::vector<>

[lekcja] Rozdział 48. Omówienie funkcjonalności kontenera std::vector<>

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<>

C/C++
#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.
C/C++
#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():
C/C++
std::vector < int > wektor;
wektor.reserve( 10 );
std::cout << "Rozmiar: " << wektor.size() << " Pojemnosc: " << wektor.capacity() << '\n';
Rozmiar: 0 Pojemnosc: 10
C/C++
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:
C/C++
#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:
C/C++
std::vector < int >::iterator iter = wektor.begin();
auto iter2 = wektor.begin(); // C++11 pozwala oszczędzić pisania tej długiej nazwy typu
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.
C/C++
#include <vector>
#include <iostream>

int main()
{
    std::vector < int > wektor( 10, 0 ); // 10 elementów 0, analogicznie jak resize(10, 0)
    wektor.insert( wektor.begin(), 1 ); // Przed pierwszym, więc na początek
    wektor.insert( wektor.end(), 3, 2 ); // Przed za-ostatnim, więc na koniec; 3 elementy o wartości 2
    wektor.insert( wektor.begin() + 3, 3 ); // Przed elementem o indeksie 3, więc w miejsce o indeksie 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.
C/C++
#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() ); // Usuń pierwszy element
    wektor.erase( wektor.begin() + 2, wektor.begin() + 4 ); // Usuń indeksy 2, 3
    wektor.erase( wektor.begin() + 4, wektor.end() ); // Usuń od indeksu 4 do końca.
   
    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:
  • Realokacja unieważnia wszystkie iteratory,
  • Usunięcie elementu unieważnia iterator na niego,
  • Usunięcie/wstawienie elementu unieważnia iteratory na wszyskie elementy po wstawionej/usuniętej sekwencji, wliczając w to end().
Poprzedni dokument Następny dokument
Rekurencja Wprowadzenie do standardowych algorytmów