Podręcznik

Wektor

Wektor jest jednym z najbardziej popularnych kontenerów biblioteki STL - zapewne poprzez fakt, iż bardzo przypomina standardową tablicę. W przypadku wektora elementy mają być przechowywane w jednym spójnym bloku pamięci - podobnie jak standardowa tablica. Rozmiar tej pamięci jest zwiększany w miarę potrzeb - co wiąże się z realokacją (kopiowaniem) całego dotychczas zajmowanego bloku. Dzięki temu wektor ma następujące cechy:

1. Zawartość wektora może być udostępniana bezpośrednio jako wskaźnik. Wystarczy pobrać adres pierwszego elementu - i wektor możemy stosować wszędzie tam, gdzie można było stosować tablice - jest to bardzo przydatne w przypadku konieczności wykorzystywania starych API
2. Wektor praktycznie nie wprowadza narzutu pamięciowego. Rozmiar wektora od rozmiaru sumy jego elementów jest większy jedynie o kilka pól - adres początku, adres pierwszego wolnego miejsca, adres końca obszaru pamięci prealokowanego
3. W wektorze mamy do czynienia z prealokacją pamięci. W praktyce oznacza to, że automatyczne rozszerzanie wektora nie zawsze wiąże się z koniecznością alokacji nowego bloku pamięci i kopiowaniem dotychczasowej zawartości. Zazwyczaj wektor wstępnie rezerwuje miejce na jakąś liczbę elementów, a potem - jak zabraknie miejsca - zwiększa swój rozmiar nie o jeden element, ale np. dwukrotnie. Możemy ręcznie sterować ilością miejsca zarezerwowaną korzystając z metody reserve - tyle że zazwyczaj nie ma takiej potrzeby.
   Wektor oferuje efektywne mechanizmy dostawiania elementów do końca - wydłużania go
4. Operacje wstawiania na początek oraz w środek wektora są czasochłonne. Jeżeli potrzebujecie dostawiać / usuwać elementy na początku i na końcu - stosujcie deque, jesli potrzebujecie częstego wstawiania / usuwania w dowolnym miejscu - lepszym wyborem jest list

Dla wektora (podobnie jak w przypadku wszystkich omawianych kontenerów STL) możemy zdefiniować własny alokator - jednak zazwyczaj nie ma takiej potrzeby. Domyślna wersja alokatora wykorzystuje standardowe new i delete - i w większości zastosowań jest wystarczająca.

Definicja wektora jest podobna do innych zmiennych, przy czym mamy do dyspozycji kilka postaci konstruktora:

// wektor o pięciu elementach inicjowany kolejnymi liczbami całkowitymi
std::vector<int> v1{1, 2, 3, 4, 5};
// wektor na liczby zmiennoprzecinkowe o długości 0
std::vector<double> v2;
// wektor w którym jest 10 pustych napisów
std::vector<std::string> v3{10};
// wektor w którym jest 3 wektory, w których w każdym jest po 4 napisy "aaa"
std::vector<std::vector<std::string>> v4{3, {4, "aaa"}};

W celu uzyskania dostępu do przechowywanych elementów najprościej jest stosować operator []:

for (size_t i=0; i<v1.size(); ++i) {
    std::cout << v1[i] << "\t";
}

Dla tych co wolą jednak być sprawdzani, przewidziano metodę at która kontrolę zakresów przeprowadza. Stosować ją można analogicznie do operatora [] - ponieważ zwraca referencję do przechowywanej wartości:

for (size_t i=0; i<v3.size(); i++) {
    v3.at(i) = std::string("a_")+std::to_string(i+1);
    std::cout << v3.at(i) << "\t";
}

To, że istnieją dwie wersje dostępu indeksowanego do elementów wektora, nie zmienia faktu, iż we współczesnym kodzie zaleca się raczej stosowanie pętli for w wersji zakresowej. Jest to zarówno bezpieczne, jak i efektywne:

for (auto& vi : v4) {
    for (auto& vii : vi) {
        std::cout << vii << "\t";
    }
std::cout << "\n";
}

Lista

Klasa list jest implementacją klasycznej, dwukierunkowej listy. Każdy element takiej listy jest pamiętany w niezależnie alokowanym bloku pamięci, wraz z dwoma adresami - następnego i poprzedniego elementu. Wiąże się z tym zestaw właściwości, które każda lista posiada:

• Przechowywanie tej samej liczby elementów w liście wymaga więcej pamięci, niż przechowywanie ich w wektorze
• Wstawianie i usuwanie elementów w dowolnym miejscu kolekcji jest tak samo efektywne - nie ma problemu z czasem potrzebnym na realokację zasobów.
• Dostęp do elementów jest sekwencyjny. By to podkreślić, twórcy biblioteki standardowej nie zdecydowali się na implementację operatora [] dla listy. Zwyczajowo - listę przeglądamy po kolei. Jeśli do elementów umieszczonych w liście brakuje Wam dostępu swobodnego - zastanówcie się, czy dobrze dobraliście kontener...
• Wstawianie / usuwanie elementów odbywa się przy pomocy iteratorów.

Sposoby inicjacji listy są podobne do sposobów inicjacji wektora. Jeśli chcemy utworzyć listę znaków, i zamieścić na niej 4 litery, to możemy zastosować listę inicjalizatora:

// lista o 4 literach
std::list l1{'a', 'b', 'd', 'e'};

Wydrukowanie zawartości tej listy:

    for (auto li : l1) {
        std::cout << li << "\t";
    }

W przypadku konieczności wstawiania / usuwania elementów z listy - mamy do dyspozycji metody insert oraz erase - tyle że one działają na iteratorach:

    // wyszukanie nieciągłości:
    auto pl = l1.front();
    for (auto it=l1.begin(); it!= l1.end(); it++) {
        if (*it-pl > 1) {
            l1.insert(it, pl+1);
        }
        pl = *it;
    }

insert wstawia element przed elementem wskazywanym przez iterator podany jako argument, erase - usuwa wskazywany element.

Kolejka

Jeśli komuś do końca ani nie odpowiada charakterystyka wektora, ani listy - ma do dyspozycji coś, co jest pomiędzy jednym a drugim rozwiązaniem - deque (ang. double ended queue - kolejka o dwóch końcach). Kolejka - czyli struktura danych gdzie efektywnie można dodawać i usuwać elementy. Przypomina to kolejkę w prawdziwym życiu, w której osoby są usuwane z przodu i dodawane z tyłu. Kolejki dwustronne to szczególny przypadek kolejek, w których operacje wstawiania i usuwania są możliwe na obu końcach.

Dane w deque są pamiętane w wielu ciągłych obszarach (ang. chunk) - ale w każdym obszarze jest więcej niż jeden element. Jak miejsce się kończy - alokowany jest nowy fragment.

Funkcjonalnie te kolejki są podobne do wektorów, ale obsługują wstawianie i usuwanie pierwszego elementu w stałym czasie. Funkcje dla deque są takie same jak w przypadku wektora, z dodatkiem operacji push i pop dla przodu (push_font, pop_front).

Osobiście - często wykorzystuję kolejkę w swoich kodach. Jest wygodniejsza niż wektor, a dodatkowy narzut powodowany przez jej fragmentaryzację zazwyczaj nie jest zauważalny. Jedyne na co trzeba zwracać uwagę - to na brak możliwości stosowania adresu pierwszego elementu tam, gdzie wymagana jest klasyczna tablica C++