16.11 — std::vector i zachowanie stosu

Rozważmy przypadek, w którym piszesz program, w którym użytkownik wprowadzi listę wartości (np. kilka wyników testów). W takim przypadku liczba wartości, które będą wprowadzane, nie jest znana w czasie kompilacji i może się zmieniać przy każdym uruchomieniu programu. Będziesz przechowywać te wartości w std::vector w celu wyświetlenia i/lub przetworzenia.

W oparciu o to, co omówiliśmy do tej pory, możesz do tego podejść na kilka sposobów:

Najpierw możesz zapytać użytkownika, ile ma wpisów, utworzyć wektor o tej długości, a następnie poprosić użytkownika o wprowadzenie tej liczby wartości.

To nie jest złe podejście, ale wymaga użytkownik wiedział wcześniej dokładnie, ile ma wpisów i nie pomylił się w liczeniu. Ręczne liczenie więcej niż dziesięciu lub dwudziestu elementów może być żmudne — więc po co prosić użytkownika o zliczenie liczby wprowadzonych wartości, skoro powinniśmy to za niego zrobić?

Alternatywnie możemy po prostu założyć, że użytkownik nie będzie chciał wprowadzić więcej niż określonej liczby wartości (np. 30) i utworzyć (lub zmienić rozmiar) wektora zawierającego tak wiele elementów. Następnie możemy poprosić użytkownika o wprowadzanie danych do momentu ich zakończenia (lub osiągnięcia 30 wprowadzonych wartości). Ponieważ długość wektora ma oznaczać liczbę użytych elementów, możemy następnie zmienić rozmiar wektora na liczbę wartości faktycznie wprowadzonych przez użytkownika.

Wadą tego podejścia jest to, że użytkownik jest ograniczony do wprowadzenia 30 wartości i nie mamy pojęcia, czy to za dużo, czy za mało. Jeśli użytkownik chce wprowadzić więcej wartości, to trudno.

Moglibyśmy rozwiązać ten problem, dodając logikę zwiększającą rozmiar wektora za każdym razem, gdy użytkownik osiągnie maksymalną liczbę wartości. Oznacza to jednak, że musimy teraz połączyć zarządzanie rozmiarem tablicy z logiką naszego programu, co znacznie zwiększy złożoność naszego programu (co nieuchronnie doprowadzi do błędów).

Prawdziwym problemem jest to, że próbujemy zgadnąć, ile elementów może wprowadzić użytkownik, abyśmy mogli odpowiednio zarządzać rozmiarem wektora. W sytuacjach, gdy liczba elementów, które należy wprowadzić, nie jest z góry znana, istnieje lepsze podejście.

Ale zanim do tego dojdziemy, musimy na chwilę przejść do paska bocznego.

Co to jest stos?

Czas na analogię! Weźmy pod uwagę stos talerzy w stołówce. Z nieznanego powodu te płyty są wyjątkowo ciężkie i można je podnosić tylko pojedynczo. Ponieważ płyty są ułożone w stosy i ciężkie, możesz modyfikować stos płyt tylko na jeden z dwóch sposobów:

1. Ułóż nową płytkę na wierzchu stosu (ukrywając płytę pod spodem, jeśli istnieje)
2. Usuń górną płytę ze stosu (odsłaniając płytkę znajdującą się pod spodem, jeśli istnieje)

Dodawanie lub usuwanie talerza ze środka lub dołu stosu jest niedozwolone, ponieważ wymagałoby to podnoszenia więcej niż jednego talerza talerz na raz.

Kolejność w którym elementy są dodawane i usuwane ze stosu, można opisać jako ostatni na wejściu, pierwszy na wyjściu (LIFO). Ostatnia płyta dodana do stosu będzie pierwszą, która zostanie usunięta.

Stosy w programowaniu

W programowaniu stos jest typem danych kontenera, w którym wstawianie i usuwanie elementów odbywa się w sposób LIFO o nazwie push i pop:

Wiele implementacji stosu opcjonalnie obsługuje także inne przydatne operacje:

Stosy są powszechne w programowaniu. Na lekcji 3.9 — Korzystanie ze zintegrowanego debugera: Stos wywołań, omówiliśmy stos wywołań, który śledzi, które funkcje zostały wywołane. Stos wywołań to… stos! (Wiem, to ujawnienie było rozczarowaniem). Kiedy funkcja jest wywoływana, na górze stosu wywołań dodawany jest wpis z informacją o tej funkcji. Kiedy funkcja powraca, wpis zawierający informacje o tej funkcji jest usuwany ze szczytu stosu wywołań. W ten sposób wierzchołek stosu wywołań zawsze reprezentuje aktualnie wykonywaną funkcję, a każdy kolejny wpis reprezentuje funkcję, która była wykonywana poprzednio.

Na przykład, oto krótka sekwencja pokazująca, jak działa wypychanie i otwieranie stosu:

       (Stack: empty)
Push 1 (Stack: 1)
Push 2 (Stack: 1 2)
Push 3 (Stack: 1 2 3)
Pop    (Stack: 1 2)
Push 4 (Stack: 1 2 4)
Pop    (Stack: 1 2)
Pop    (Stack: 1)
Pop    (Stack: empty)

Stosy w C++

W niektórych językach stos jest implementowany jako odrębny typ kontenera (oddzielny od innych kontenerów). Może to jednak być dość ograniczające. Rozważmy przypadek, w którym chcemy wydrukować wszystkie wartości ze stosu bez modyfikowania stosu. Interfejs czystego stosu nie zapewnia bezpośredniej metody wykonania tego zadania.

W C++ zamiast tego dodano operacje podobne do stosu (jako funkcje składowe) do istniejących klas kontenerów biblioteki standardowej, które obsługują efektywne wstawianie i usuwanie elementów na jednym końcu (std::vector, std::deque i std::list). Dzięki temu każdy z tych kontenerów może być używany jako stosy, oprócz ich natywnych możliwości.

W dalszej części tej lekcji sprawdzimy, jak działa interfejs stosu std::vector , a następnie zakończymy, pokazując, jak pomaga nam on rozwiązać wyzwanie przedstawione na początku lekcji.

Stos zachowanie z std::vector

Zachowanie stosu w std::vector jest implementowane poprzez następujące funkcje składowe:

Przyjrzyjmy się przykładowi wykorzystującemu niektóre z nich funkcje:

#include <iostream>
#include <vector>

void printStack(const std::vector<int>& stack)
{
	if (stack.empty()) // if stack.size == 0
		std::cout << "Empty";

	for (auto element : stack)
		std::cout << element << ' ';

	// \t is a tab character, to help align the text
	std::cout << "\tCapacity: " << stack.capacity() << "  Length " << stack.size() << "\n";
}

int main()
{
	std::vector<int> stack{}; // empty stack

	printStack(stack);

	stack.push_back(1); // push_back() pushes an element on the stack
	printStack(stack);

	stack.push_back(2);
	printStack(stack);

	stack.push_back(3);
	printStack(stack);

	std::cout << "Top: " << stack.back() << '\n'; // back() returns the last element

	stack.pop_back(); // pop_back() pops an element off the stack
	printStack(stack);

	stack.pop_back();
	printStack(stack);

	stack.pop_back();
	printStack(stack);

	return 0;
}

W GCC lub Clang wypisuje:

Empty   Capacity: 0  Length: 0
1       Capacity: 1  Length: 1
1 2     Capacity: 2  Length: 2
1 2 3   Capacity: 4  Length: 3
Top:3
1 2     Capacity: 4  Length: 2
1       Capacity: 4  Length: 1
Empty   Capacity: 4  Length: 0

Pamiętaj, długość to liczba elementów wektora, która w tym przypadku jest liczbą elementów na naszym stosie.

W przeciwieństwie do operatora indeksu dolnego operator[] lub at() funkcja składowa, push_back() (oraz emplace_back()) zwiększy długość wektora i spowoduje ponowną alokację, jeśli pojemność nie będzie wystarczająca do wstawienia wartości.

W powyższym przykładzie wektor zostanie przeniesiony 3 razy (z pojemności 0 do 1, 1 do 2 i 2 do 4).

Dodatkowa wydajność w wyniku wypychania

W powyższym wyniku należy zauważyć, że kiedy nastąpiła ostatnia z trzech realokacji, pojemność wzrosła z 2 do 4 (mimo że przesuwaliśmy tylko jeden element). Kiedy naciśnięcie powoduje ponowną alokację, std::vector zazwyczaj przydziela pewną dodatkową pojemność, aby umożliwić dodanie dodatkowych elementów bez wyzwalania kolejnej ponownej alokacji przy następnym uruchomieniu elementu. dodano.

ile dodatkowej pojemności zostanie przydzielonej, zależy od implementacji std::vector przez kompilator, a różne kompilatory zazwyczaj robią różne rzeczy:

• GCC i Clang podwajają bieżącą pojemność. Po wyzwoleniu ostatniej zmiany rozmiaru pojemność zostaje podwojona z 2 do 4.
• Visual Studio 2022 mnoży bieżącą pojemność przez 1,5. Po wyzwoleniu ostatniej zmiany rozmiaru pojemność zmienia się z 2 na 3.

W rezultacie poprzedni program może mieć nieco inny wynik w zależności od używanego kompilatora.

Zmiana rozmiaru wektora nie działa w przypadku zachowania stosu

Ponowna alokacja wektora jest kosztowna obliczeniowo (proporcjonalnie do długości wektora), dlatego chcemy unikać realokacji, gdy jest to uzasadnione więc. W powyższym przykładzie moglibyśmy uniknąć 3-krotnej ponownej alokacji wektora, jeśli na początku programu ręcznie zmienilibyśmy rozmiar wektora do pojemności 3.

Spójrzmy, co się stanie, jeśli zmienimy linię 18 w powyższym przykładzie na następującą:

std::vector<int> stack(3); // parenthesis init to set vector's capacity to 3

Teraz, gdy uruchomimy program ponownie, otrzymamy następujący wynik:

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

To nie prawda -- w jakiś sposób mamy tego mnóstwo wartości 0 na początku naszego stosu! Problem polega na tym, że inicjalizacja nawiasów (aby ustawić początkowy rozmiar wektora) i funkcja resize() ustawiają zarówno pojemność ORAZ długość. Nasz wektor zaczyna się od pojemności 3 (tak właśnie chcieliśmy), ale długość jest również ustawiana na 3. Zatem nasz wektor zaczyna się od 3 elementów o wartości 0. Elementy, które później naciskamy, są umieszczane na tych początkowych elementach.

Klasa resize() Funkcja składowa zmieniająca długość wektora jest w porządku, gdy mamy zamiar używać indeksów dolnych w celu uzyskania dostępu do elementów (ponieważ nasze indeksy muszą być mniejsze niż długość, aby były prawidłowe), ale powoduje problemy, gdy używamy wektora jako stosu.

To, czego naprawdę chcemy, to jakiś sposób na zmianę pojemności (aby uniknąć przyszłych realokacji) bez zmiany długości (co ma efekt uboczny w postaci dodania nowych elementów do naszego stosu).

Klasa reserve() Funkcja składowa zmienia pojemność (ale nie długość)

Klasa reserve() funkcji składowej można użyć do ponownego przydzielenia std::vector bez zmiany bieżącego długość.

Oto ten sam przykład co poprzednio, ale z dodanym wywołaniem reserve() aby ustawić pojemność:

#include <iostream>
#include <vector>

void printStack(const std::vector<int>& stack)
{
	if (stack.empty()) // if stack.size == 0
		std::cout << "Empty";

	for (auto element : stack)
		std::cout << element << ' ';

	// \t is a tab character, to help align the text
	std::cout << "\tCapacity: " << stack.capacity() << "  Length " << stack.size() << "\n";
}

int main()
{
	std::vector<int> stack{};

	printStack(stack);

	stack.reserve(6); // reserve space for 6 elements (but do not change length)
	printStack(stack);

	stack.push_back(1);
	printStack(stack);

	stack.push_back(2);
	printStack(stack);

	stack.push_back(3);
	printStack(stack);

	std::cout << "Top: " << stack.back() << '\n';

	stack.pop_back();
	printStack(stack);

	stack.pop_back();
	printStack(stack);

	stack.pop_back();
	printStack(stack);

	return 0;
}

Na komputerze autora wypisuje:

Empty   Capacity: 0  Length: 0
Empty   Capacity: 6  Length: 0
1       Capacity: 6  Length: 1
1 2     Capacity: 6  Length: 2
1 2 3   Capacity: 6  Length: 3
Top: 3
1 2     Capacity: 6  Length: 2
1       Capacity: 6  Length: 1
Empty   Capacity: 6  Length: 0

Widzisz, że wywołanie reserve(6) zmieniło pojemność na 6, ale nie miało wpływu na długość. Nie ma już więcej realokacji, ponieważ std::vector jest wystarczająco duży, aby pomieścić wszystkie elementy, które wypychamy.

push_back() vs emplace_back()

Oba push_back() i emplace_back() wpychają element na stos. Jeśli obiekt, który ma zostać wypchnięty, push_back() i emplace_back() są równoważne i push_back() powinny być preferowane.

Jednak w przypadkach, gdy tworzymy obiekt tymczasowy (tego samego typu co element wektora) w celu wepchnięcia go na wektor, emplace_back() może być więcej efektywny:

#include <iostream>
#include <string>
#include <string_view>
#include <vector>

class Foo
{
private:
    std::string m_a{};
    int m_b{};

public:
    Foo(std::string_view a, int b)
        : m_a { a }, m_b { b }
        {}

    explicit Foo(int b)
        : m_a {}, m_b { b }
        {};
};

int main()
{
	std::vector<Foo> stack{};

	// When we already have an object, push_back and emplace_back are similar in efficiency
	Foo f{ "a", 2 };
	stack.push_back(f);    // prefer this one
	stack.emplace_back(f);

	// When we need to create a temporary object to push, emplace_back is more efficient
	stack.push_back({ "a", 2 }); // creates a temporary object, and then copies it into the vector
	stack.emplace_back("a", 2);  // forwards the arguments so the object can be created directly in the vector (no copy made)

	// push_back won't use explicit constructors, emplace_back will
	stack.push_back({ 2 }); // compile error: Foo(int) is explicit
	stack.emplace_back(2);  // ok
    
	return 0;
}

W powyższym przykładzie mamy wektor Foo obiektów. Za pomocą push_back({ "a", 2 }) tworzymy i inicjujemy obiekt tymczasowy Foo , który następnie jest kopiowany do wektora. W przypadku typów kosztownych do kopiowania (takich jak std::string) ta kopia może spowodować spadek wydajności.

Przy emplace_back(), nie musimy tworzyć obiektu tymczasowego, aby przejść. Zamiast tego przekazujemy argumenty, które zostałyby użyte do utworzenia obiektu tymczasowego i emplace_back() przekazujemy je (przy użyciu funkcji zwanej doskonałym przesyłaniem) do wektora, gdzie są wykorzystywane do tworzenia i inicjalizacji obiektu wewnątrz wektora. Pozwala to uniknąć kopii, która w innym przypadku zostałaby wykonana.

Uwaga: push_back() nie użyje jawnych konstruktorów, podczas gdy emplace_back() tak zrobi. To sprawia, że emplace_back jest bardziej niebezpieczny, ponieważ łatwiej jest przypadkowo wywołać jawny konstruktor w celu wykonania konwersji, która nie ma sensu.

Przed C++20 emplace_back() nie działa z inicjalizacją agregowaną.

Sprostanie naszemu wyzwaniu za pomocą operacji na stosie

Teraz powinno być oczywiste, jak powinniśmy stawić czoła wyzwaniu przedstawionemu na początku lekcji. Jeśli nie wiemy z góry, ile elementów zostanie dodanych do naszego std::vector, najlepszym rozwiązaniem będzie użycie funkcji stosu do wstawienia tych elementów.

Oto przykład:

#include <iostream>
#include <limits>
#include <vector>

int main()
{
	std::vector<int> scoreList{};

	while (true)
	{
		std::cout << "Enter a score (or -1 to finish): ";
		int x{};
		std::cin >> x;

		if (!std::cin) // handle bad input
		{
			std::cin.clear();
			std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
			continue;
		}

		// If we're done, break out of loop
		if (x == -1)
			break;

		// The user entered a valid element, so let's push it on the vector
		scoreList.push_back(x);
	}

	std::cout << "Your list of scores: \n";

	for (const auto& score : scoreList)
		std::cout << score << ' ';

	return 0;
}

Ten program pozwala użytkownikowi wprowadzić wyniki testu, dodając każdy wynik do wektora. Po zakończeniu dodawania punktów przez użytkownika drukowane są wszystkie wartości wektora.

Zauważ, że w tym programie nie musimy w ogóle zliczać, indeksować ani zajmować się długościami tablic! Możemy po prostu skupić się na logice tego, co chcemy, aby program zrobił i pozwolić wektorowi zająć się wszystkimi problemami z pamięcią!

Czas quizu

Pytanie nr 1

Napisz program, który wypycha i wyświetla wartości oraz wyprowadza następującą sekwencję:

       (Stack: empty)
Push 1 (Stack: 1)
Push 2 (Stack: 1 2)
Push 3 (Stack: 1 2 3)
Pop    (Stack: 1 2)
Push 4 (Stack: 1 2 4)
Pop    (Stack: 1 2)
Pop    (Stack: 1)
Pop    (Stack: empty)

Pokaż rozwiązanie

#include <iostream>
#include <vector>

void printStackValues(const std::vector<int>& v)
{
    std::cout << "\t(Stack:";
    
    for (auto e : v)
        std::cout << ' ' << e;

    if (v.empty()) // if v.size == 0
        std::cout << " empty";

    std::cout << ")\n";
}

void pushAndPrint(std::vector<int>& v, int val)
{
    v.push_back(val);
    std::cout << "Push " << val;
    printStackValues(v);
}

void popAndPrint(std::vector<int>& v)
{
    v.pop_back();
    std::cout << "Pop ";
    printStackValues(v);
}

int main()
{
    std::vector<int> v {};

    printStackValues(v);

    pushAndPrint(v, 1);
    pushAndPrint(v, 2);
    pushAndPrint(v, 3);
    popAndPrint(v);
    pushAndPrint(v, 4);
    popAndPrint(v);
    popAndPrint(v);
    popAndPrint(v);

    return 0;
}