16.10 — std::vector zmiana rozmiaru i pojemność

W poprzednich lekcjach w tym rozdziale przedstawiliśmy kontenery, tablice i std::vector. Omówiliśmy także takie tematy, jak uzyskiwanie dostępu do elementów tablicy, uzyskiwanie długości tablicy i poruszanie się po tablicy. Chociaż używaliśmy std::vector w naszych przykładach, koncepcje, które omówiliśmy, mają ogólne zastosowanie do wszystkich typów tablic.

W pozostałych lekcjach w tym rozdziale skupimy się na jednej rzeczy, która std::vector znacznie różni się od większości pozostałych typów tablic: możliwości zmiany rozmiaru po utworzeniu instancji.

Tablice o stałym rozmiarze a dynamiczne arrays

Większość typów tablic ma istotne ograniczenie: długość tablicy musi być znana w momencie tworzenia instancji, a następnie nie można jej zmienić. Takie tablice nazywane są tablicami o stałym rozmiarze lub tablicami o stałej długości. Obydwa std::array i C-style arrays są typami tablic o stałym rozmiarze. Omówimy je szczegółowo w następnym rozdziale.

Z drugiej strony std::vector to tablica dynamiczna. A dynamicznymi array (zwana także resizable array) to tablica, której rozmiar można zmienić po utworzeniu instancji. Ta możliwość zmiany rozmiaru sprawia, że std::vector jest wyjątkowa.

Zmiana rozmiaru std::vector w czasie wykonywania

A std::vector można zmienić rozmiar po utworzeniu instancji, wywołując resize() funkcji składowej o nowej żądanej długości:

#include <iostream>
#include <vector>

int main()
{
    std::vector v{ 0, 1, 2 }; // create vector with 3 elements
    std::cout << "The length is: " << v.size() << '\n';

    v.resize(5);              // resize to 5 elements
    std::cout << "The length is: " << v.size() << '\n';

    for (auto i : v)
        std::cout << i << ' ';

    std::cout << '\n';

    return 0;
}

Wypisuje:

The length is: 3
The length is: 5
0 1 2 0 0

Tutaj należy zwrócić uwagę na dwie rzeczy. Po pierwsze, kiedy zmieniliśmy rozmiar wektora, istniejące wartości elementów zostały zachowane! Po drugie, nowe elementy są inicjowane wartością (która wykonuje domyślną inicjalizację dla typów klas i inicjalizację zerową dla innych typów). Zatem dwa nowe elementy typu int zostały zainicjowane od zera do wartości 0.

. Rozmiar wektorów można również zmienić na mniejszy:

#include <iostream>
#include <vector>

void printLength(const std::vector<int>& v)
{
	std::cout << "The length is: "	<< v.size() << '\n';
}

int main()
{
    std::vector v{ 0, 1, 2, 3, 4 }; // length is initially 5
    printLength(v);

    v.resize(3);                    // resize to 3 elements
    printLength(v);

    for (int i : v)
        std::cout << i << ' ';

    std::cout << '\n';

    return 0;
}

Wypisuje:

The length is: 5
The length is: 3
0 1 2

Długość a pojemność std::vector

Rozważmy rząd 12 domów. Powiedzielibyśmy, że liczba domów (lub długość rzędu domów) wynosi 12. Gdybyśmy chcieli wiedzieć, który z tych domów jest obecnie zamieszkały… musielibyśmy to ustalić w inny sposób (np. zadzwonić do drzwi i zobaczyć, czy ktoś otwiera). Kiedy mamy tylko długość, wiemy tylko, ile rzeczy istnieje.

Rozważmy teraz karton jaj, w którym obecnie znajduje się 5 jaj. Powiedzielibyśmy, że liczba jaj wynosi 5. Jednak w tym kontekście interesuje nas jeszcze jeden wymiar: ile jaj zmieściłoby się w kartonie, gdyby był pełny. Powiedzielibyśmy, że pojemność kartonu jaj wynosi 12. W kartonie jest miejsce na 12 jaj, a używane jest tylko 5 – dlatego moglibyśmy dodać 7 jaj więcej, nie przepełniając kartonu. Kiedy mamy zarówno długość, jak i pojemność, możemy rozróżnić, ile rzeczy aktualnie istnieje, od tego, na ile rzeczy jest miejsce.

Do tego momentu mówiliśmy tylko o długości std::vector. Ale std::vector ma też pojemność. W kontekście std::vector, pojemność to liczba elementów, dla których std::vector przydzielono pamięć, i długość jest ile elementów jest aktualnie używanych.

A std::vector o pojemności 5 przydzielono miejsce na 5 elementów. Jeśli wektor zawiera 2 elementy w aktywnym użyciu, długość (rozmiar) wektora wynosi 2. Pozostałym 3 elementom przydzielono pamięć, ale nie są one uważane za aktywnie używane. Można ich później użyć bez przepełnienia wektora.

Uzyskiwanie pojemności std::vector

Możemy zapytać std::vector o jego pojemność poprzez capacity() funkcja składowa.

Na przykład:

#include <iostream>
#include <vector>

void printCapLen(const std::vector<int>& v)
{
	std::cout << "Capacity: " << v.capacity() << " Length:"	<< v.size() << '\n';
}

int main()
{
    std::vector v{ 0, 1, 2 }; // length is initially 3

    printCapLen(v);

    for (auto i : v)
        std::cout << i << ' ';
    std::cout << '\n';

    v.resize(5); // resize to 5 elements

    printCapLen(v);

    for (auto i : v)
        std::cout << i << ' ';
    std::cout << '\n';

    return 0;
}

Na maszynie autora wypisuje to:

Capacity: 3  Length: 3
0 1 2
Capacity: 5  Length: 5
0 1 2 0 0

Najpierw inicjujemy wektor z 3 elementami. To powoduje, że wektor przydziela pamięć dla 3 elementów (pojemność wynosi 3) i wszystkie 3 elementy są uważane za aktywnie używane (długość = 3).

Następnie wywołujemy resize(5), co oznacza, że chcemy teraz wektor o długości 5. Ponieważ wektor ma pamięć tylko dla 3 elementów, ale potrzebuje 5, wektor musi zdobyć więcej pamięci, aby pomieścić dodatkowe elementy.

Po wywołanie resize() zostało zakończone, możemy zobaczyć, że wektor ma teraz miejsce na 5 elementów (pojemność wynosi 5) i że wszystkie 5 elementów jest teraz uznawanych za używane (długość wynosi 5).

W większości przypadków nie będziesz musiał używać funkcji capacity() , ale będziemy jej często używać w poniższych przykładach, abyśmy mogli zobaczyć, co dzieje się z pamięcią wektora.

Relokacja pamięci i dlaczego jest ona kosztowna

Kiedy std::vector zmienia ilość zarządzanej pamięci, proces ten nazywa się realokacją. Nieformalnie proces realokacji przebiega mniej więcej tak:

• Klasa std::vector pozyskuje nową pamięć o pojemności na żądaną liczbę elementów. Elementy te są inicjowane wartością.
• Elementy ze starej pamięci są kopiowane (lub przenoszone, jeśli to możliwe) do nowej pamięci. Stara pamięć jest następnie zwracana do systemu.
• Pojemność i długość std::vector zostają ustawione na nowe wartości.

Z zewnątrz wygląda na to, że std::vector zmieniono rozmiar. Ale wewnętrznie pamięć (i wszystkie jej elementy) została faktycznie wymieniona!

Ponieważ realokacja zazwyczaj wymaga skopiowania każdego elementu tablicy, ponowna alokacja jest kosztownym procesem. W rezultacie chcemy w miarę możliwości unikać realokacji.

Po co różnicować długość i pojemność?

A std::vector w razie potrzeby dokona ponownej alokacji pamięci, ale podobnie jak Bartleby Melville’a wolałby tego nie robić, ponieważ ponowna alokacja pamięci jest kosztowna obliczeniowo.

Jeśli a std::vector śledziła tylko jej długość, wówczas każde resize() żądanie skutkowałoby kosztowną realokacją do nowej długości. Oddzielenie długości i pojemności daje std::vector możliwość mądrzejszego podejmowania decyzji o konieczności ponownej alokacji.

Poniższy przykład ilustruje to:

#include <iostream>
#include <vector>

void printCapLen(const std::vector<int>& v)
{
	std::cout << "Capacity: " << v.capacity() << " Length:"	<< v.size() << '\n';
}

int main()
{
    // Create a vector with length 5
    std::vector v{ 0, 1, 2, 3, 4 };
    v = { 0, 1, 2, 3, 4 }; // okay, array length = 5
    printCapLen(v);

    for (auto i : v)
        std::cout << i << ' ';
    std::cout << '\n';

    // Resize vector to 3 elements
    v.resize(3); // we could also assign a list of 3 elements here
    printCapLen(v);

    for (auto i : v)
        std::cout << i << ' ';
    std::cout << '\n';

    // Resize vector back to 5 elements
    v.resize(5);
    printCapLen(v);

    for (auto i : v)
        std::cout << i << ' ';
    std::cout << '\n';

    return 0;
}

Owocuje to, co następuje:

Capacity: 5  Length: 5
0 1 2 3 4 
Capacity: 5  Length: 3
0 1 2 
Capacity: 5  Length: 5
0 1 2 0 0

Kiedy inicjowaliśmy nasz wektor za pomocą 5 elementów, pojemność została ustawiona na 5, co oznacza, że ​​nasz wektor początkowo przydzielił miejsce na 5 elementów. Długość również została ustawiona na 5, co oznacza, że ​​wszystkie te elementy są w użyciu.

Po wywołaniu v.resize(3) długość została zmieniona na 3, aby spełnić naszą prośbę o mniejszą tablicę. Należy jednak pamiętać, że pojemność nadal wynosi 5, co oznacza, że ​​wektor nie dokonał realokacji!

W końcu wywołaliśmy v.resize(5). Ponieważ wektor miał już pojemność 5, nie trzeba było go ponownie alokować. Po prostu zmienił długość z powrotem na 5 i zainicjował wartość dwóch ostatnich elementów.

Oddzielając długość i pojemność, w tym przykładzie uniknęliśmy dwóch realokacji, które w przeciwnym razie miałyby miejsce. W następnej lekcji zobaczymy przykłady, w których dodajemy elementy do wektora jeden po drugim. W takich przypadkach możliwość nierelokacji przy każdej zmianie długości jest jeszcze ważniejsza.

Indeksowanie wektorów opiera się na długości, a nie pojemności

Możesz być zaskoczony, gdy odkryjesz, że prawidłowe indeksy dla operatora indeksu dolnego (operator[]) i at() funkcja składowa opiera się na długości wektora, a nie na jego pojemności.

W przykładzie powyżej, gdy v ma pojemność 5 i długość 3, ważne są tylko indeksy od 0 do 2. Nawet jeśli istnieją elementy o indeksach od długości 3 (włącznie) do pojemności 5 (wyłącznie), ich indeksy są uważane za wykraczające poza zakres.

Zmniejszanie std::vector

Zmiana rozmiaru wektora na większy zwiększy długość wektora i, jeśli to konieczne, zwiększy jego pojemność. Jednak zmiana rozmiaru wektora na mniejszy spowoduje jedynie zmniejszenie jego długości, a nie pojemności.

Ponowna alokacja wektora tylko po to, aby odzyskać pamięć z niewielkiej liczby elementów, które nie są już potrzebne, jest złym wyborem. Jednakże w przypadku, gdy mamy wektor z dużą liczbą elementów, których już nie potrzebujemy, marnotrawstwo pamięci może być znaczne.

Aby pomóc zaradzić tej sytuacji, std::vector posiada funkcję składową zwaną shrink_to_fit() wymaga to, aby wektor zmniejszył swoją pojemność, aby dopasować się do jego długości. To żądanie nie jest wiążące, co oznacza, że ​​wdrożenie może je zignorować. W zależności od tego, co implementacja uzna za najlepsze, implementacja może zdecydować się spełnić żądanie, może je częściowo spełnić (np. zmniejszyć pojemność, ale nie całkowicie) lub może całkowicie zignorować żądanie.

Oto przykład:

#include <iostream>
#include <vector>

void printCapLen(const std::vector<int>& v)
{
	std::cout << "Capacity: " << v.capacity() << " Length:"	<< v.size() << '\n';
}

int main()
{

	std::vector<int> v(1000); // allocate room for 1000 elements
	printCapLen(v);

	v.resize(0); // resize to 0 elements
	printCapLen(v);

	v.shrink_to_fit();
	printCapLen(v);

	return 0;
}

Na maszynie autora daje to następujący wynik:

Capacity: 1000  Length: 1000
Capacity: 1000  Length: 0
Capacity: 0  Length: 0

Jak widać, kiedy v.shrink_to_fit() został wywołany, wektor ponownie przydzielił swoją pojemność do 0, zwalniając pamięć na 1000 elementów.

Czas quizu

Pytanie nr 1

Co reprezentuje długość i pojemność std::vector?

Pokaż rozwiązanie

Dlaczego długość i pojemność to oddzielne wartości?

Pokaż rozwiązanie

Czy ważne indeksy dla std::vector w oparciu o długość czy pojemność?

Pokaż rozwiązanie