C++
Iteratory

Iteratory C (wskaźniki)

// This creates an array with 5 values.
const int array[] = { 1, 2, 3, 4, 5 };

#ifdef BEFORE_CPP11

// You can use `sizeof` to determine how many elements are in an array.
const int* first = array;
const int* afterLast = first + sizeof(array) / sizeof(array[0]);

// Then you can iterate over the array by incrementing a pointer until
// it reaches past the end of our array.
for (const int* i = first; i < afterLast; ++i) {
    std::cout << *i << std::endl;
}

#else

// With C++11, you can let the STL compute the start and end iterators:
for (auto i = std::begin(array); i != std::end(array); ++i) {
    std::cout << *i << std::endl;
}

#endif

Ten kod wyświetliłby liczby od 1 do 5, po jednym w każdym wierszu, jak poniżej:

1
2)
3)
4
5

Breaking It Down

const int array[] = { 1, 2, 3, 4, 5 };

Ta linia tworzy nową tablicę liczb całkowitych o 5 wartościach. Tablice C są tylko wskaźnikami do pamięci, w których każda wartość jest przechowywana razem w ciągłym bloku.

const int* first = array;
const int* afterLast = first + sizeof(array) / sizeof(array[0]);

Te linie tworzą dwa wskaźniki. Pierwszy wskaźnik otrzymuje wartość wskaźnika tablicy, który jest adresem pierwszego elementu w tablicy. Operator sizeof , gdy jest używany w tablicy C, zwraca rozmiar tablicy w bajtach. Dzielony przez rozmiar elementu daje liczbę elementów w tablicy. Możemy to wykorzystać do znalezienia adresu bloku za tablicą.

for (const int* i = first; i < afterLast; ++i) {

Tutaj tworzymy wskaźnik, którego będziemy używać jako iteratora. Jest inicjowany adresem pierwszego elementu, który chcemy iterować, i będziemy kontynuować iterację tak długo, jak i będzie mniejsze niż afterLast , co oznacza, o ile i wskazuje adres w array .

    std::cout << *i << std::endl;

Wreszcie w pętli możemy uzyskać dostęp do wartości, na którą wskazuje nasz iterator i usuwając z niej odniesienia. Tutaj operator dereferencji * zwraca wartość pod adresem w i .

Przegląd

Iteratory są pozycjami

Iteratory są sposobem nawigacji i działania na sekwencji elementów i stanowią uogólnione rozszerzenie wskaźników. Koncepcyjnie ważne jest, aby pamiętać, że iteratory są pozycjami, a nie elementami. Na przykład weź następującą sekwencję:

A B C

Sekwencja zawiera trzy elementy i cztery pozycje

+---+---+---+---+
| A | B | C |   |
+---+---+---+---+

Elementy są elementami w sekwencji. Pozycje to miejsca, w których mogą wystąpić znaczące operacje na sekwencji. Na przykład, wstawia się w pozycję przed lub za elementem A, a nie w element. Nawet usunięcie elementu ( erase(A) ) odbywa się najpierw poprzez znalezienie jego pozycji, a następnie usunięcie.

Od iteratorów do wartości

Aby przekonwertować z pozycji na wartość, iterator jest usuwany z dereferencji :

auto my_iterator = my_vector.begin(); // position
auto my_value = *my_iterator; // value

Można myśleć o iteratorze jako o dereferencji do wartości, do której się odwołuje w sekwencji. Jest to szczególnie przydatne w zrozumieniu, dlaczego nigdy nie powinieneś rezygnować z iteratora end() w sekwencji:

+---+---+---+---+
| A | B | C |   |
+---+---+---+---+
  ↑           ↑
  |           +-- An iterator here has no value. Do not dereference it!
  +-------------- An iterator here dereferences to the value A.

We wszystkich sekwencjach i kontenerach znalezionych w standardowej bibliotece C ++, begin() zwróci iterator do pierwszej pozycji, a end() zwróci iterator do przeszłości za ostatnią pozycją ( nie ostatnią pozycją!). W związku z tym nazwy tych iteratorów w algorytmach są często oznaczone jako first i last :

+---+---+---+---+
| A | B | C |   |
+---+---+---+---+
  ↑           ↑
  |           |
  +- first    +- last

Możliwe jest również uzyskanie iteratora dla dowolnej sekwencji , ponieważ nawet pusta sekwencja zawiera co najmniej jedną pozycję:

+---+
|   |
+---+

W pustej sekwencji, begin() i end() będą w tej samej pozycji i żadna z nich nie będzie dereferencyjna:

+---+
|   |
+---+
  ↑
  |
  +- empty_sequence.begin()
  |
  +- empty_sequence.end()

Alternatywną wizualizacją iteratorów jest zaznaczenie pozycji między elementami:

+---+---+---+
| A | B | C |
+---+---+---+
↑   ^   ^   ↑
|           |
+- first    +- last

a usunięcie odniesienia z iteratora zwraca odwołanie do elementu występującego po iteratorze. Niektóre sytuacje, w których ten widok jest szczególnie użyteczny, to:

• insert operacji spowoduje wstawienie elementów do pozycji wskazanej przez iteracyjnej,
• operacje erase zwrócą iterator odpowiadający tej samej pozycji, co przekazany,
• iterator i odpowiadający mu iterator zwrotny znajdują się w tej samej pozycji między elementami

Nieprawidłowe iteratory

Iterator zostaje unieważniony, jeśli (powiedzmy w trakcie operacji) jego pozycja nie jest już częścią sekwencji. Unieważnionego iteratora nie można wyrejestrować, dopóki nie zostanie ponownie przypisany do prawidłowej pozycji. Na przykład:

std::vector<int>::iterator first;
{
    std::vector<int> foo;
    first = foo.begin(); // first is now valid
} // foo falls out of scope and is destroyed
// At this point first is now invalid

Wiele algorytmów i funkcji członka sekwencji w standardowej bibliotece C ++ ma reguły rządzące, gdy iteratory są unieważniane. Każdy algorytm różni się sposobem, w jaki traktują (i unieważniają) iteratory.

Nawigacja za pomocą Iteratorów

Jak wiemy, iteratory służą do nawigacji w sekwencjach. W tym celu iterator musi migrować swoją pozycję w sekwencji. Iteratory mogą przejść do przodu w sekwencji, a niektóre mogą przejść do tyłu:

auto first = my_vector.begin();
++first;                                             // advance the iterator 1 position
std::advance(first, 1);                              // advance the iterator 1 position
first = std::next(first);                            // returns iterator to the next element
std::advance(first, -1);                             // advance the iterator 1 position backwards
first = std::next(first, 20);                        // returns iterator to the element 20 position forward
first = std::prev(first, 5);                         // returns iterator to the element 5 position backward
auto dist = std::distance(my_vector.begin(), first); // returns distance between two iterators.

Zauważ, że drugi argument std :: distance powinien być osiągalny od pierwszego (lub innymi słowy first powinien być mniejszy lub równy od second ).

Mimo że za pomocą iteratorów można wykonywać operatory arytmetyczne, nie wszystkie operacje są zdefiniowane dla wszystkich typów iteratorów. a = b + 3; działałby w przypadku iteratorów o dostępie swobodnym, ale nie działałby w przypadku iteratorów do przodu lub dwukierunkowych, które nadal można przesunąć o 3 pozycje z czymś w rodzaju b = a; ++b; ++b; ++b; . Dlatego zaleca się stosowanie funkcji specjalnych w przypadku, gdy nie masz pewności, jaki jest typ iteratora (na przykład w funkcji szablonu akceptującej iterator).

Iterator Concepts

Standard C ++ opisuje kilka różnych koncepcji iteratora. Są one pogrupowane według zachowań w sekwencjach, do których się odnoszą. Jeśli znasz koncepcję, którą iterator modeluje (zachowuje się jak), możesz być pewien zachowania tego iteratora niezależnie od sekwencji, do której należy . Często są one opisane w kolejności od najbardziej restrykcyjnego (ponieważ następna koncepcja iteratora jest o krok lepsza niż jej poprzedniczka):

• Iteratory wejściowe: Można je wyłuskać tylko raz na pozycję. Może tylko awansować i tylko jedna pozycja na raz.
• Iteratory do przodu: iterator wejściowy, który można usunąć dowolną liczbę razy.
• Iteratory dwukierunkowe: iterator do przodu, który może również przewijać do tyłu o jedną pozycję na raz.
• Iteratory o dostępie swobodnym: dwukierunkowy iterator, który może przesuwać do przodu lub do tyłu dowolną liczbę pozycji jednocześnie.
• Iteratory ciągłe (od C ++ 17): iterator o dostępie swobodnym, który gwarantuje, że leżące u jego podstaw dane są ciągłe w pamięci.

Algorytmy mogą się różnić w zależności od koncepcji modelowanej przez podane iteratory. Na przykład, chociaż random_shuffle może być zaimplementowane dla iteratorów przesyłania dalej, można zapewnić bardziej wydajny wariant, który wymaga iteratorów dostępu swobodnego.

Cechy iteratora

Cechy iteratorów zapewniają jednolity interfejs do właściwości iteratorów. Pozwalają pobrać wartość, różnicę, wskaźnik, typy referencyjne, a także kategorię iteratora:

template<class Iter>
Iter find(Iter first, Iter last, typename std::iterator_traits<Iter>::value_type val)  {
    while (first != last) {
        if (*first == val)
            return first;
        ++first;
    }
    return last;
}

Kategoria iteratora może służyć do specjalizacji algorytmów:

template<class BidirIt>
void test(BidirIt a, std::bidirectional_iterator_tag)  {
    std::cout << "Bidirectional iterator is used" << std::endl;
}
 
template<class ForwIt>
void test(ForwIt a, std::forward_iterator_tag)  {
    std::cout << "Forward iterator is used" << std::endl;
}
 
template<class Iter>
void test(Iter a)  {
    test(a, typename std::iterator_traits<Iter>::iterator_category());
}

Kategorie iteratorów to w zasadzie pojęcia iteratorów, z tym wyjątkiem, że ciągłe iteratory nie mają własnego znacznika, ponieważ stwierdzono, że łamie kod.

Iteratory odwrotne

Jeśli chcemy iterować wstecz przez listę lub wektor, możemy użyć reverse_iterator . Iterator zwrotny jest tworzony z dwukierunkowego lub iteratora o dostępie swobodnym, który zachowuje jako element członkowski, do którego można uzyskać dostęp poprzez base() .

Aby iterować wstecz użyj rbegin() i rend() jako iteratorów odpowiednio dla końca kolekcji i początku kolekcji.

Na przykład, aby wykonać iterację wstecz, użyj:

std::vector<int> v{1, 2, 3, 4, 5};
for (std::vector<int>::reverse_iterator it = v.rbegin(); it != v.rend(); ++it)
{
    cout << *it;
} // prints 54321

Iterator zwrotny można przekształcić w iterator do przodu za pomocą funkcji elementu base() . Zależność polega na tym, że iterator do tyłu odwołuje się do jednego elementu za iteratorem base() :

std::vector<int>::reverse_iterator r = v.rbegin();
std::vector<int>::iterator i = r.base();
assert(&*r == &*(i-1)); // always true if r, (i-1) are dereferenceable
                        // and are not proxy iterators

 +---+---+---+---+---+---+---+
 |   | 1 | 2 | 3 | 4 | 5 |   |
 +---+---+---+---+---+---+---+
   ↑   ↑               ↑   ↑
   |   |               |   |
rend() |         rbegin()  end()
       |                   rbegin().base()
     begin()
     rend().base()

W wizualizacji, w której iteratory zaznaczają pozycje między elementami, relacja jest prostsza:

  +---+---+---+---+---+
  | 1 | 2 | 3 | 4 | 5 |
  +---+---+---+---+---+
  ↑                   ↑
  |                   |
  |                 end()
  |                 rbegin()
begin()             rbegin().base()
rend()
rend().base()

Iterator wektorowy

begin zwraca iterator do pierwszego elementu w kontenerze sekwencji.

end zwraca iterator do pierwszego elementu za końcem.

Jeśli obiektem wektorowym jest const , zarówno begin , jak i end zwracają const_iterator . Jeśli chcesz const_iterator zostać zwrócony nawet jeśli wektor nie jest const , można użyć cbegin i cend .

Przykład:

#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = { 1, 2, 3, 4, 5 };  //intialize vector using an initializer_list

    for (std::vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
        std::cout << *it << " ";
    }

    return 0;
}

Wynik:

1 2 3 4 5

Mapa Iterator

Iterator do pierwszego elementu w kontenerze.

Jeśli obiekt mapy ma stałą kwalifikację, funkcja zwraca const_iterator . W przeciwnym razie zwraca iterator .

// Create a map and insert some values
std::map<char,int> mymap;
mymap['b'] = 100;
mymap['a'] = 200;
mymap['c'] = 300;

// Iterate over all tuples
for (std::map<char,int>::iterator it = mymap.begin(); it != mymap.end(); ++it)
    std::cout << it->first << " => " << it->second << '\n';

Wynik:

a => 200
b => 100
c => 300

Iteratory strumieniowe

Iteratory strumienia są przydatne, gdy potrzebujemy odczytać sekwencję lub wydrukować sformatowane dane z kontenera:

// Data stream. Any number of various whitespace characters will be OK.
std::istringstream istr("1\t 2     3 4");
std::vector<int> v;

// Constructing stream iterators and copying data from stream into vector.
std::copy(
    // Iterator which will read stream data as integers.
    std::istream_iterator<int>(istr),
    // Default constructor produces end-of-stream iterator.
    std::istream_iterator<int>(),
    std::back_inserter(v));

// Print vector contents.
std::copy(v.begin(), v.end(),
    //Will print values to standard output as integers delimeted by " -- ".
    std::ostream_iterator<int>(std::cout, " -- "));

Przykładowy program wydrukuje 1 -- 2 -- 3 -- 4 -- na standardowe wyjście.

Napisz własny iterator wspierany przez generator

Powszechnym wzorcem w innych językach jest funkcja generująca „strumień” obiektów i możliwość użycia pętli-kodu do zapętlenia go.

Możemy to modelować w C ++ as

template<class T>
struct generator_iterator {
  using difference_type=std::ptrdiff_t;
  using value_type=T;
  using pointer=T*;
  using reference=T;
  using iterator_category=std::input_iterator_tag;
  std::optional<T> state;
  std::function< std::optional<T>() > operation;
  // we store the current element in "state" if we have one:
  T operator*() const {
    return *state;
  }
  // to advance, we invoke our operation.  If it returns a nullopt
  // we have reached the end:
  generator_iterator& operator++() {
    state = operation();
    return *this;        
  }
  generator_iterator operator++(int) {
    auto r = *this;
    ++(*this);
    return r;
  }
  // generator iterators are only equal if they are both in the "end" state:
  friend bool operator==( generator_iterator const& lhs, generator_iterator const& rhs ) {
    if (!lhs.state && !rhs.state) return true;
    return false;
  }
  friend bool operator!=( generator_iterator const& lhs, generator_iterator const& rhs ) {
    return !(lhs==rhs);
  }
  // We implicitly construct from a std::function with the right signature:
  generator_iterator( std::function< std::optional<T>() > f ):operation(std::move(f))
  {
    if (operation)
      state = operation();
  }
  // default all special member functions:
  generator_iterator( generator_iterator && ) =default;
  generator_iterator( generator_iterator const& ) =default;
  generator_iterator& operator=( generator_iterator && ) =default;
  generator_iterator& operator=( generator_iterator const& ) =default;
  generator_iterator() =default;
};

przykład na żywo .

Wygenerowany element przechowujemy wcześnie, abyśmy mogli łatwiej wykryć, czy jesteśmy już na końcu.

Ponieważ funkcja iteratora generatora końcowego nigdy nie jest używana, możemy utworzyć zakres iteratorów generatora, kopiując tylko raz std::function . Domyślnie zbudowany iterator generatora porównuje się do siebie i do wszystkich innych iteratorów generatora końcowego.