18.2 -- Wprowadzenie do iteratorów

Iteracja po tablicy (lub innej strukturze) danych jest dość powszechną rzeczą robić w programowaniu. Jak dotąd omówiliśmy wiele różnych sposobów, aby to zrobić: za pomocą pętli i indeksu (for-loops i while loops), wskaźników i arytmetyki wskaźników oraz range-based for-loops:

#include <array>
#include <cstddef>
#include <iostream>

int main()
{
    // In C++17, the type of variable arr is deduced to std::array<int, 7>
    // If you get an error compiling this example, see the warning below
    std::array arr{ 0, 1, 2, 3, 4, 5, 6 };
    std::size_t length{ std::size(arr) };

    // while-loop with explicit index
    std::size_t index{ 0 };
    while (index < length)
    {
        std::cout << arr[index] << ' ';
        ++index;
    }
    std::cout << '\n';

    // for-loop with explicit index
    for (index = 0; index < length; ++index)
    {
        std::cout << arr[index] << ' ';
    }
    std::cout << '\n';

    // for-loop with pointer (Note: ptr can't be const, because we increment it)
    for (auto ptr{ &arr[0] }; ptr != (&arr[0] + length); ++ptr)
    {
        std::cout << *ptr << ' ';
    }
    std::cout << '\n';

    // range-based for loop
    for (int i : arr)
    {
        std::cout << i << ' ';
    }
    std::cout << '\n';

    return 0;
}

Pętla z użyciem indeksów wymaga więcej pisania niż potrzeba, jeśli używamy indeksu tylko do uzyskania dostępu do elementów. Działa to również tylko wtedy, gdy kontener (np. tablica) zapewnia bezpośredni dostęp do elementów (co robią tablice, ale niektóre inne typy kontenerów, takie jak listy, nie).

Pętla z wskaźniki i arytmetyka wskaźników jest gadatliwa i może być myląca dla czytelników, którzy nie znają zasad arytmetyki wskaźników. Arytmetyka wskaźników działa również tylko wtedy, gdy elementy znajdują się w pamięci po sobie (co dotyczy tablic, ale nie dotyczy innych typów kontenerów, takich jak listy, drzewa i mapy).

Pętle for oparte na zakresach są nieco bardziej interesujące, ponieważ mechanizm iteracji po naszym kontenerze jest ukryty - a mimo to nadal działają w przypadku wszelkiego rodzaju różnych struktur (tablic, list, drzew, map itp.). iteratory.

Iteratory

An iterator to obiekt przeznaczony do przechodzenia przez kontener (np. wartości w tablicy lub znaki w ciągu znaków), zapewniający po drodze dostęp do każdego elementu.

Kontener może udostępniać różne rodzaje iteratorów Na przykład kontener tablicy może oferować iterator do przodu, który przechodzi przez tablicę w kolejności do przodu, oraz iterator odwrotny, który przechodzi przez tablicę w odwrotnej kolejności.

Po utworzeniu odpowiedniego typu iteratora programista może następnie używać interfejsu dostarczonego przez iterator do przeglądania elementów i uzyskiwania dostępu do nich bez konieczności martwienia się o rodzaj wykonywanego przechodzenia lub w jaki sposób dane są przechowywane w kontenerze. A ponieważ iteratory C++ zazwyczaj używają tego samego interfejsu do przechodzenia (operator++ do przejścia do następnego elementu) i dostępu (operator* do uzyskiwania dostępu do elementu). bieżący element), możemy iterować po wielu różnych typach kontenerów, stosując spójną metodę.

Wskaźniki jako iterator

Najprostszym rodzajem iteratora jest wskaźnik, który (przy użyciu arytmetyki wskaźników) działa dla danych przechowywanych sekwencyjnie w pamięci. Przyjrzyjmy się ponownie prostemu przechodzeniu przez tablicę przy użyciu arytmetyki wskaźników i wskaźników:

#include <array>
#include <iostream>

int main()
{
    std::array arr{ 0, 1, 2, 3, 4, 5, 6 };

    auto begin{ &arr[0] };
    // note that this points to one spot beyond the last element
    auto end{ begin + std::size(arr) };

    // for-loop with pointer
    for (auto ptr{ begin }; ptr != end; ++ptr) // ++ to move to next element
    {
        std::cout << *ptr << ' '; // Indirection to get value of current element
    }
    std::cout << '\n';

    return 0;
}

Wyjście:

0 1 2 3 4 5 6

In. powyżej zdefiniowaliśmy dwie zmienne: begin (która wskazuje początek naszego kontenera) i end (która wyznacza punkt końcowy). W przypadku tablic znacznikiem końcowym jest zazwyczaj miejsce w pamięci, w którym znajdowałby się ostatni element, gdyby kontener zawierał jeszcze jeden element.

Wskaźnik następnie wykonuje iterację pomiędzy begin i end, a dostęp do bieżącego elementu można uzyskać poprzez wyłuskanie elementu wskaźnik.

int* end{ &arr[std::size(arr)] };

int* end{ arr.data() + std::size(arr) }; // data() returns a pointer to the first element

Iteratorów standardowych bibliotek

Iteracja jest tak powszechną operacją że wszystkie standardowe kontenery bibliotek oferują bezpośrednie wsparcie dla iteracji. Zamiast obliczać własne punkty początkowe i końcowe, możemy po prostu zapytać kontener o punkty początkowe i końcowe za pomocą funkcji składowych o wygodnej nazwie begin() i end():

#include <array>
#include <iostream>

int main()
{
    std::array array{ 1, 2, 3 };

    // Ask our array for the begin and end points (via the begin and end member functions).
    auto begin{ array.begin() };
    auto end{ array.end() };

    for (auto p{ begin }; p != end; ++p) // ++ to move to next element.
    {
        std::cout << *p << ' '; // Indirection to get value of current element.
    }
    std::cout << '\n';

    return 0;
}

Wypisuje:

1 2 3

Klasa iterator nagłówek zawiera również dwie funkcje ogólne (std::begin i std::end), których można użyć.

#include <array>    // includes <iterator>
#include <iostream>

int main()
{
    std::array array{ 1, 2, 3 };

    // Use std::begin and std::end to get the begin and end points.
    auto begin{ std::begin(array) };
    auto end{ std::end(array) };

    for (auto p{ begin }; p != end; ++p) // ++ to move to next element
    {
        std::cout << *p << ' '; // Indirection to get value of current element
    }
    std::cout << '\n';

    return 0;
}

To również wypisuje:

1 2 3

Nie przejmuj się na razie typami iteratorów, wrócimy do iteratorów w późniejszym rozdziale. Ważne jest to, że iterator dba o szczegóły iteracji po kontenerze. Potrzebujemy tylko czterech rzeczy: punktu początkowego, punktu końcowego, operatora++ do przeniesienia iteratora do następnego elementu (lub końca) i operatora* do pobrania wartości bieżącego elementu.

operator< vs operator!= W przypadku iteratorów

W lekcji 8.10 -- Dla instrukcji zauważyliśmy, że użycie operator< było preferowane zamiast operator!= podczas wykonywania porównań numerycznych w warunku pętli:

    for (index = 0; index < length; ++index)

Z iteratorów, zwykle używa się operator!= do sprawdzenia, czy iterator osiągnął element końcowy:

    for (auto p{ begin }; p != end; ++p)

Dzieje się tak, ponieważ niektóre typy iteratorów nie są relacyjne porównywalne. operator!= działa ze wszystkimi typami iteratorów.

Powrót do pętli for opartych na zakresach

Wszystkie typy, które mają obie begin() i end() funkcje składowe lub których można używać z std::begin() i std::end(), można używać w pętlach for opartych na zakresach.

#include <array>
#include <iostream>

int main()
{
    std::array array{ 1, 2, 3 };

    // This does exactly the same as the loop we used before.
    for (int i : array)
    {
        std::cout << i << ' ';
    }
    std::cout << '\n';

    return 0;
}

Za kulisami wywołania pętli for oparte na zakresach begin() i end() typu, po którym można iterować. std::array has begin i end funkcje składowe, dzięki czemu możemy ich używać w pętli opartej na zakresach. Stałych tablic w stylu C można używać z funkcjami std::begin i std::end , więc możemy je przeglądać również za pomocą pętli opartej na zakresie. Dynamiczne tablice w stylu C (lub tablice w stylu C) nie działają, ponieważ nie ma dla nich std::end funkcji (ponieważ informacja o typie nie zawiera długości tablicy).

Jak dodać te funkcje do typów dowiesz się później, aby można było ich używać również z pętlami for opartymi na zakresach.

Pętle for oparte na zakresach nie są najlepszym rozwiązaniem jedyna rzecz, która korzysta z iteratorów. Są one również używane w std::sort i innych algorytmach. Teraz, gdy już wiesz, czym one są, zauważysz, że są często używane w bibliotece standardowej.

Unieważnianie iteratorów (iteratory wiszące)

Podobnie jak wskaźniki i referencje, iteratory mogą pozostać „zawieszone”, jeśli elementy poddawane iteracji zmienią adres lub zostaną zniszczone. Gdy tak się stanie, mówimy, że iterator został unieważniają. Dostęp do unieważnionego iteratora powoduje niezdefiniowane zachowanie.

Niektóre operacje modyfikujące kontenery (takie jak dodanie elementu do std::vector) mogą mieć efekt uboczny w postaci spowodowania zmiany adresów elementów w kontenerze. Kiedy tak się stanie, istniejące iteratory tych elementów zostaną unieważnione. Dobra dokumentacja referencyjna C++ powinna zawierać informacje, które operacje kontenerowe mogą lub spowodują unieważnienie iteratorów. Jako przykład zobacz sekcję „Unieważnianie iteratora” w std::vector na temat cppreference.

Ponieważ pętle for oparte na zakresach używają iteratorów za kulisami, musimy uważać, aby nie zrobić niczego, co unieważnia iteratory kontenera, przez który aktywnie przechodzimy:

#include <vector>

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

    for (auto num : v) // implicitly iterates over v
    {
        if (num % 2 == 0)
            v.push_back(num + 1); // when this invalidates the iterators of v, undefined behavior will result
    }

    return 0;
}

Oto kolejny przykład iteratora unieważnienie:

#include <iostream>
#include <vector>

int main()
{
	std::vector v{ 1, 2, 3, 4, 5, 6, 7 };

	auto it{ v.begin() };

	++it; // move to second element
	std::cout << *it << '\n'; // ok: prints 2

	v.erase(it); // erase the element currently being iterated over

	// erase() invalidates iterators to the erased element (and subsequent elements)
	// so iterator "it" is now invalidated

	++it; // undefined behavior
	std::cout << *it << '\n'; // undefined behavior

	return 0;
}

Unieważnione iteratory można ponownie sprawdzić, przypisując im prawidłowy iterator (np. begin(), end() lub wartość zwracaną przez inną funkcję, która zwraca iterator).

Klasa erase() zwraca iterator do elementu pierwszego za usuniętym elementem (lub end() jeśli ostatni element został usunięty). Dlatego możemy naprawić powyższy kod w następujący sposób:

#include <iostream>
#include <vector>

int main()
{
	std::vector v{ 1, 2, 3, 4, 5, 6, 7 };

	auto it{ v.begin() };

	++it; // move to second element
	std::cout << *it << '\n';

	it = v.erase(it); // erase the element currently being iterated over, set `it` to next element

	std::cout << *it << '\n'; // now ok, prints 3

	return 0;
}

(h/t do nascarddriver za znaczący wkład w tę lekcję)