16.2 — Wprowadzenie do std::vector i listy konstruktory

W poprzednim lekcja 16.1 — Wprowadzenie do kontenerów i tablic, wprowadziliśmy zarówno kontenery, jak i tablice. W tej lekcji przedstawimy typ tablicy, na którym będziemy się skupiać przez resztę rozdziału: std::vector. Rozwiążemy także jedną część wyzwania związanego ze skalowalnością, które przedstawiliśmy w ostatniej lekcji.

Wprowadzenie do std::vector

std::vector jest jedną z klas kontenerów w standardowej bibliotece kontenerów C++, która implementuje tablicę. std::vector jest zdefiniowana w nagłówku <vector> jako szablon klasy z parametrem typu szablonu, który definiuje typ elementów. Zatem std::vector<int> deklaruje std::vector którego elementy są typu int.

Tworzenia std::vector obiektu jest proste:

#include <vector>

int main()
{
	// Value initialization (uses default constructor)
	std::vector<int> empty{}; // vector containing 0 int elements

	return 0;
}

Zmienna empty jest zdefiniowane jako std::vector którego elementy mają typ int. Ponieważ użyliśmy tutaj inicjalizacji wartości, nasz wektor zacznie się pusty (to znaczy bez elementów).

Wektor bez elementów może teraz nie wydawać się przydatny, ale spotkamy się z tym ponownie w przyszłych lekcjach (szczególnie 16.11 — std::vector i zachowanie stosu).

Inicjowanie std::vector z listą wartości

Ponieważ celem kontenera jest zarządzanie zbiorem powiązanych wartości, najczęściej będziemy chcieli zainicjować nasz kontener tymi wartościami. Możemy to zrobić za pomocą inicjalizacji listy z określonymi wartościami inicjującymi, które chcemy. Na przykład:

#include <vector>

int main()
{
	// List construction (uses list constructor)
	std::vector<int> primes{ 2, 3, 5, 7 };          // vector containing 4 int elements with values 2, 3, 5, and 7
	std::vector vowels { 'a', 'e', 'i', 'o', 'u' }; // vector containing 5 char elements with values 'a', 'e', 'i', 'o', and 'u'.  Uses CTAD (C++17) to deduce element type char (preferred).

	return 0;
}

Przy primes, wyraźnie określamy, że chcemy std::vector którego elementy mają typ int. Ponieważ dostarczyliśmy 4 wartości inicjujące, primes będzie zawierać 4 elementy, których wartości are 2, 3, 5, I 7.

Przy vowels, nie określiliśmy jawnie typu elementu. Zamiast tego używamy CTAD z C++ 17 (dedukcja argumentów szablonu klasy), aby kompilator wywnioskował typ elementu z inicjatorów. Ponieważ dostarczyliśmy 5 wartości inicjujących, vowels będzie zawierać 5 elementów, których wartościami są 'a', 'e', 'i', 'o', I 'u'.

konstruktorzy list i inicjator. lists

Porozmawiajmy o tym, jak powyższe działa nieco bardziej szczegółowo.

W lekcji 13.8 -- Inicjowanie agregatu Struct, zdefiniowaliśmy listę inicjatorów jako listę wartości oddzielonych przecinkami w nawiasach klamrowych (np. { 1, 2, 3 }).

Kontenery zazwyczaj mają specjalny konstruktor zwany konstruktorem listy która pozwala nam skonstruować instancję kontenera przy użyciu listy inicjalizatorów. Konstruktor listy robi trzy rzeczy:

• Zapewnia, że kontener ma wystarczającą ilość miejsca do przechowywania całej inicjalizacji wartości (jeśli to konieczne).
• Ustawia długość kontenera na liczbę elementów na liście inicjatorów (jeśli to konieczne).
• Inicjuje elementy na wartości na liście inicjatorów (w kolejności).

Tak więc, gdy udostępniamy kontener z listą inicjatorów wartości, wywoływany jest konstruktor listy, a kontener jest tworzony przy użyciu tej listy wartości!

Dostęp do elementów tablicy za pomocą operatora indeksu dolnego (operator[])

A teraz, gdy stworzyliśmy tablicę elementów… jak uzyskać dostęp je?

Posłużmy się przez chwilę analogią. Rozważmy zestaw identycznych skrzynek pocztowych, ustawionych obok siebie. Aby ułatwić identyfikację skrzynek pocztowych, każda skrzynka pocztowa ma namalowany numer z przodu. Pierwsza skrzynka ma numer 0, druga ma numer 1 itd. Jeśli więc ktoś kazałby Ci wrzucić coś do skrzynki pocztowej o numerze 0, wiedziałbyś, że chodzi o pierwszą skrzynkę pocztową.

W C++ najczęstszym sposobem uzyskiwania dostępu do elementów tablicy jest użycie nazwy tablicy wraz z operatorem indeksu dolnego (operator[]). Aby wybrać konkretny element, w nawiasach kwadratowych operatora indeksu dolnego podajemy wartość całkowitą, która określa, który element chcemy wybrać. Ta wartość całkowa nazywana jest indeksem dolnym (lub nieformalnie indeksem skrzynek pocztowych, dostęp do pierwszego elementu odbywa się przy użyciu indeksu 0, dostęp do drugiego przy użyciu indeksu 1 itd.

Dla przykład primes[0] zwróci element z indeksem 0 (pierwszy element) z tablicy prime . Operator indeksu dolnego zwraca referencję do rzeczywistego elementu, a nie kopię. it, itp…)

Ponieważ indeksowanie zaczyna się od 0, a nie od 1, mówimy, że tablice w C++ to liczą się zerami. Może to być mylące, ponieważ jesteśmy przyzwyczajeni do liczenia obiektów zaczynając od 1.

To również może powodować pewną dwuznaczność językową, ponieważ gdy mówimy o elemencie tablicy 1, może nie być jasne, czy mówimy o pierwszym elemencie tablicy (z indeksem 0), czy o drugim elemencie tablicy (z indeksem 1). Ogólnie rzecz biorąc, będziemy mówić o elementach tablicy w kategoriach pozycji, a nie indeksu (więc „pierwszym elementem” jest ten z indeksem 0).

Oto przykład:

#include <iostream>
#include <vector>

int main()
{
    std::vector primes { 2, 3, 5, 7, 11 }; // hold the first 5 prime numbers (as int)

    std::cout << "The first prime number is: " << primes[0] << '\n';
    std::cout << "The second prime number is: " << primes[1] << '\n';
    std::cout << "The sum of the first 5 primes is: " << primes[0] + primes[1] + primes[2] + primes[3] + primes[4] << '\n';

    return 0;
}

Wypisuje:

The first prime number is: 2
The second prime number is: 3
The sum of the first 5 primes is: 28

Dzięki tablicom nie musimy już definiować 5 zmiennych o różnych nazwach, które przechowują nasze 5 wartości pierwszych. Zamiast tego możemy zdefiniować pojedynczą tablicę (primes) z 5 elementami i po prostu zmienić wartość indeksu, aby uzyskać dostęp do różnych elementów!

Porozmawiamy więcej o operator[] oraz innych metodach dostępu do elementów tablicy w następnej lekcji 16.3 -- std::vector oraz problemu długości bez znaku i indeksu dolnego.

Indeks dolny poza granicami

Podczas indeksowania tablicy podany indeks musi wybierać prawidłowy element tablicy. Oznacza to, że dla tablicy o długości N indeks dolny musi mieć wartość z zakresu od 0 do N-1 (włącznie).

operator[] nie wykonują żadnego sprawdzania granic, co oznacza, że nie sprawdzają, czy indeks mieści się w granicach od 0 do N-1 (włącznie). Przekazanie nieprawidłowego indeksu do operator[] zwróci nieokreślone zachowanie.

Dość łatwo jest pamiętać, aby nie używać ujemnych indeksów dolnych. Trudniej jest zapamiętać, że nie ma elementu o indeksie N! Ostatni element tablicy ma indeks N-1, więc użycie indeksu N spowoduje, że kompilator spróbuje uzyskać dostęp do elementu znajdującego się o jeden koniec tablicy.

Tablice sąsiadują ze sobą w pamięci

Jedną z cech charakterystycznych tablic jest to, że elementy są zawsze alokowane w pamięci w sposób ciągły, co oznacza, że wszystkie elementy sąsiadują ze sobą w pamięci (bez przerw między nimi).

Ilustracja tego:

#include <iostream>
#include <vector>

int main()
{
    std::vector primes { 2, 3, 5, 7, 11 }; // hold the first 5 prime numbers (as int)

    std::cout << "An int is " << sizeof(int) << " bytes\n";
    std::cout << &(primes[0]) << '\n';
    std::cout << &(primes[1]) << '\n';
    std::cout << &(primes[2]) << '\n';

    return 0;
}

Na komputerze autora jedno uruchomienie powyższego programu dał następujący wynik:

An int is 4 bytes
00DBF720
00DBF724
00DBF728

Zauważ, że adresy pamięci dla tych elementów int są od siebie oddalone o 4 bajty, tyle samo, co rozmiar int na maszynie autora.

Oznacza to, że tablice nie mają żadnego narzutu na element. Pozwala także kompilatorowi na szybkie obliczenie adresu dowolnego elementu tablicy.

Tablice to jeden z niewielu typów kontenerów, które pozwalają na losowy dostęp, co oznacza, że ​​dostęp do dowolnego elementu kontenera można uzyskać bezpośrednio (w przeciwieństwie do dostępu sekwencyjnego, gdzie dostęp do elementów musi być uzyskiwany w określonej kolejności). Losowy dostęp do elementów tablicy jest zazwyczaj wydajny i sprawia, że ​​tablice są bardzo łatwe w użyciu. Jest to główny powód, dla którego tablice są często preferowane w stosunku do innych kontenerów.

Konstruowanie std::vector o określonej długości

Rozważmy przypadek, w którym chcemy, aby użytkownik wprowadził 10 wartości, które będziemy przechowywać w std::vector. W tym przypadku potrzebujemy std::vector o długości 10, zanim będziemy mieli jakiekolwiek wartości do umieszczenia w std::vector. Jak sobie z tym poradzić?

Możemy utworzyć std::vector i zainicjować go listą inicjującą zawierającą 10 wartości zastępczych:

	std::vector<int> data { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; // vector containing 10 int values

Ale to jest złe z wielu powodów. Wymaga dużo pisania. Nie jest łatwo sprawdzić, ile jest inicjatorów. A aktualizacja nie jest łatwa, jeśli zdecydujemy, że później chcemy mieć inną liczbę wartości.

Na szczęście std::vector posiada jawny konstruktor (explicit std::vector<T>(std::size_t)), który przyjmuje pojedynczą std::size_t wartość określającą długość std::vector do skonstruowania:

	std::vector<int> data( 10 ); // vector containing 10 int elements, value-initialized to 0

Każdy z utworzonych elementów jest inicjalizowany wartością, co for int wykonuje inicjalizację zerową (a dla typów klas wywołuje konstruktor domyślny).

Jednak jest jedna nieoczywista rzecz w używaniu tego konstruktora: należy go wywołać przy użyciu bezpośredniej inicjalizacji.

Niepuste listy inicjatorów preferują konstruktory list

Aby zrozumieć, dlaczego poprzedni konstruktor musi zostać wywołany przy użyciu bezpośredniej inicjalizacji, rozważ to definicja:

	std::vector<int> data{ 10 }; // what does this do?

Istnieją dwa różne konstruktory pasujące do tej inicjalizacji:

• { 10 } można zinterpretować jako listę inicjatorów i dopasować do konstruktora listy w celu skonstruowania wektora o długości 1 o wartości 10.
• { 10 } można zinterpretować jako pojedynczą wartość inicjującą w nawiasach klamrowych i dopasować za pomocą konstruktora std::vector<T>(std::size_t) w celu skonstruowania wektora o długości 10 z elementami wartość-inicjowana na 0.

Zwykle, gdy definicja typu klasy pasuje do więcej niż jednego konstruktora, dopasowanie jest uważane za niejednoznaczne i skutkuje błędem kompilacji. Jednakże w C++ obowiązuje w tym przypadku specjalna zasada: gdy lista inicjatorów nie jest pusta, zamiast innych pasujących konstruktorów zostanie wybrany pasujący konstruktor listy. Bez tej reguły konstruktor listy powodowałby niejednoznaczne dopasowanie z dowolnym konstruktorem, który przyjął argumenty jednego typu.

Ponieważ { 10 } można interpretować jako listę inicjalizującą i std::vector posiada konstruktor listowy, w tym przypadku konstruktor listy ma pierwszeństwo.

Aby lepiej wyjaśnić, co dzieje się w różnych przypadkach inicjalizacji, przyjrzyjmy się podobnym przypadkom z użyciem kopiowania, inicjalizacji bezpośredniej i listy:

	// Copy init
	std::vector<int> v1 = 10;     // 10 not an initializer list, copy init won't match explicit constructor: compilation error

	// Direct init
	std::vector<int> v2(10);      // 10 not an initializer list, matches explicit single-argument constructor

	// List init
	std::vector<int> v3{ 10 };    // { 10 } interpreted as initializer list, matches list constructor

	// Copy list init
	std::vector<int> v4 = { 10 }; // { 10 } interpreted as initializer list, matches list constructor
	std::vector<int> v5({ 10 });  // { 10 } interpreted as initializer list, matches list constructor

        // Default init
        std::vector<int> v6 {};       // {} is empty initializer list, matches default constructor
        std::vector<int> v7 = {};     // {} is empty initializer list, matches default constructor

W przypadku v1 wartość inicjująca 10 nie jest listą inicjalizującą, więc konstruktor listy nie jest zgodny. Konstruktor jednoargumentowy explicit std::vector<T>(std::size_t) również nie będzie pasował, ponieważ inicjalizacja kopiowania nie będzie pasować do jawnych konstruktorów. Ponieważ żaden konstruktor nie pasuje, jest to błąd kompilacji.

W przypadku v2 wartość inicjująca 10 nie jest listą inicjalizującą, więc konstruktor listy nie jest zgodny. Konstruktor jednoargumentowy explicit std::vector<T>(std::size_t) jest dopasowaniem, więc wybierany jest konstruktor jednoargumentowy.

W przypadku v3 (inicjalizacja listy) { 10 } można dopasować za pomocą konstruktora listy lub explicit std::vector<T>(std::size_t). Konstruktor listy ma pierwszeństwo przed innymi pasującymi konstruktorami i jest wybierany.

W przypadku v4 (inicjalizacja kopiowania listy), { 10 } można dopasować do konstruktora listy (który jest konstruktorem niejawnym, więc można go używać z inicjalizacją kopiowania). Wybrano konstruktor listy.

Case v5 co zaskakujące, jest alternatywną składnią inicjalizacji listy kopiowania (nie inicjalizacji bezpośredniej) i jest taki sam jak v4.

To jest jedna z cech inicjalizacji C++: { 10 } dopasuje konstruktor listy, jeśli taki istnieje, lub konstruktor jednoargumentowy, jeśli konstruktor listy nie istnieje. Oznacza to, że zachowanie zależy od tego, czy istnieje konstruktor list! Ogólnie można założyć, że kontenery mają konstruktory list.

v6 i v7 oba są inicjowane przy użyciu pustych list inicjatorów. W tym przypadku konstruktor domyślny ma pierwszeństwo.

Podsumowując, inicjatory list są generalnie zaprojektowane tak, aby umożliwić nam inicjalizację kontenera z listą wartości elementów i powinny być używane w tym celu. W każdym razie tego właśnie chcemy przez większość czasu. Dlatego { 10 } jest właściwe, jeśli 10 ma być wartością elementu. Jeśli 10 ma być argumentem konstruktora kontenera niebędącego listą, użyj bezpośredniej inicjalizacji.

#include <vector>

struct Foo
{
    std::vector<int> v1(8); // compile error: direct initialization not allowed for member default initializers
};

struct Foo
{
    std::vector<int> v{ std::vector<int>(8) }; // ok 
};

Const i constexpr std::vector

Obiekty typu std::vector można utworzyć const:

#include <vector>

int main()
{
    const std::vector<int> prime { 2, 3, 5, 7, 11 }; // prime and its elements cannot be modified

    return 0;
}

A const std::vector należy zainicjować i nie można ich modyfikować. Elementy takiego wektora są traktowane tak, jakby były stałe.

Typ elementu a std::vector nie może być zdefiniowany jako const (np. std::vector<const int> jest niedozwolony).

Jedną z największych wad std::vector jest to, że nie można go wykonać constexpr. Jeśli potrzebujesz constexpr tablicy, użyj std::array.

Dlaczego nazywa się to wektorem?

Kiedy ludzie używają w rozmowie terminu „wektor”, zazwyczaj mają na myśli wektor geometryczny, który jest obiektem o wielkości i kierunku. Skąd więc wzięła się std::vector nazwa, skoro nie jest to wektor geometryczny?

W książce „Od matematyki do programowania generycznego” Aleksander Stiepanow napisał: „Wektor nazw w STL został zaczerpnięty z wcześniejszych języków programowania Scheme i Common Lisp. Niestety, było to niezgodne ze znacznie starszym znaczeniem tego terminu w matematyce… tę strukturę danych należało nazwać tablicą. Niestety, jeśli popełnisz błąd i naruszysz te zasady, wynik może pozostać w pamięci przez długi czas.”

Zasadniczo std::vector ma błędną nazwę, ale jest już za późno, aby ją zmienić.

Czas quizu

Pytanie nr 1

Zdefiniuj std::vector używając CTAD i inicjując go pierwszymi 5 dodatnimi liczbami kwadratowymi (1, 4, 9, 16 i 25).

Pokaż rozwiązanie

std::vector squares{ 1, 4, 9, 16, 25 };

Pytanie nr 2

Jaka jest różnica w zachowaniu między tymi dwoma definicje?

std::vector<int> v1 { 5 };
std::vector<int> v2 ( 5 );

Pokaż rozwiązanie

Pytanie nr 3

Zdefiniuj std::vector (używając jawnego argumentu typu szablonu) do utrzymywania wysokiej temperatury (z dokładnością do najbliższej dziesiątej stopnia) przez każdy dzień w roku (zakładając, że 365 dni w roku rok).

Pokaż rozwiązanie

std::vector<double> temperature (365); // create a vector to hold 365 double values

Pytanie nr 4

Wykorzystując std::vector napisz program, który poprosi użytkownika o wprowadzenie 3 wartości całkowitych. Wydrukuj sumę i iloczyn tych wartości.

Wyjście powinno być zgodne z poniższymi informacjami:

Enter 3 integers: 3 4 5
The sum is: 12
The product is: 60

Pokaż rozwiązanie

#include <iostream>
#include <vector>

int main()
{
	std::vector<int> arr(3); // create a vector of length 3
	
	std::cout << "Enter 3 integers: ";
	std::cin >> arr[0] >> arr[1] >> arr[2];

	std::cout << "The sum is: " << arr[0] + arr[1] + arr[2] << '\n';
	std::cout << "The product is: " << arr[0] * arr[1] * arr[2] << '\n';

	return 0;
}