C++
iterators

C Iterators (Pointers)

// 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

Deze code geeft de cijfers 1 tot en met 5 uit, één op elke regel als volgt:

1
2
3
4
5

Het afbreken

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

Deze regel maakt een nieuwe integer-array met 5 waarden. C-arrays zijn slechts verwijzingen naar het geheugen, waarbij elke waarde samen wordt opgeslagen in een aaneengesloten blok.

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

Deze lijnen creëren twee verwijzingen. De eerste pointer krijgt de waarde van de arraypointer, wat het adres is van het eerste element in de array. De operator sizeof wanneer gebruikt op een C-array retourneert de grootte van de array in bytes. Gedeeld door de grootte van een element geeft dit het aantal elementen in de array. We kunnen dit gebruiken om het adres van het blok na de array te vinden.

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

Hier maken we een aanwijzer die we als iterator zullen gebruiken. Het wordt geïnitialiseerd met het adres van het eerste element waarover we willen itereren, en we zullen blijven itereren zolang i minder is dan afterLast , wat betekent dat i naar een adres binnen de array wijs.

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

Tot slot zullen in de loop we kunnen toegang krijgen tot de waarde die onze iterator i verwijst naar door dereferentie het. Hier retourneert de dereferentie-operator * de waarde op het adres in i .

Overzicht

Iterators zijn posities

Iterators zijn een middel om te navigeren en te werken op een reeks elementen en zijn een algemene uitbreiding van pointers. Conceptueel is het belangrijk om te onthouden dat iterators posities zijn, geen elementen. Neem bijvoorbeeld de volgende volgorde:

A B C

De reeks bevat drie elementen en vier posities

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

Elementen zijn dingen binnen een reeks. Posities zijn plaatsen waar zinvolle bewerkingen kunnen gebeuren met de reeks. Men voegt bijvoorbeeld een positie in, voor of na element A, niet in een element. Zelfs het verwijderen van een element ( erase(A) ) gebeurt door eerst zijn positie te vinden en vervolgens te verwijderen.

Van Iterators tot waarden

Om van een positie naar een waarde te converteren, wordt van een iterator verwijderd :

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

Je kunt een iterator beschouwen als een verwijzing naar de waarde waarnaar deze in de reeks verwijst. Dit is vooral handig om te begrijpen waarom je nooit de end() iterator in een reeks zou moeten afschrijven:

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

In alle sequenties en containers gevonden in de standaardbibliotheek C ++, zal begin() een iterator terugbrengen naar de eerste positie, en end() zal een iterator terugbrengen naar een voorbij de laatste positie ( niet de laatste positie!). Bijgevolg worden de namen van deze iterators in algoritmen vaak als first en last gelabeld:

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

Het is ook mogelijk om een iterator voor elke reeks te verkrijgen, omdat zelfs een lege reeks ten minste één positie bevat:

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

In een lege volgorde zullen begin() en end() dezelfde positie hebben, en geen van beide kan worden verwijderd:

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

De alternatieve visualisatie van iterators is dat ze de posities tussen elementen markeren:

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

en als een iterator van een referentie wordt verwijderd, wordt een verwijzing geretourneerd naar het element dat na de iterator komt. Sommige situaties waarin deze weergave bijzonder nuttig is, zijn:

• insert zullen elementen invoegen in de positie aangegeven door de iterator,
• erase retourneren een iterator die overeenkomt met dezelfde positie als de ingevoerde,
• een iterator en de bijbehorende omgekeerde iterator bevinden zich in dezelfde positie tussen elementen

Ongeldige Iterators

Een iterator wordt ongeldig als (bijvoorbeeld tijdens een operatie) zijn positie niet langer deel uitmaakt van een reeks. Een ongeldige iterator kan niet meer worden verwijderd voordat deze opnieuw is toegewezen aan een geldige positie. Bijvoorbeeld:

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

De vele algoritmen en sequentielidfuncties in de standaardbibliotheek C ++ hebben regels die bepalen wanneer iterators ongeldig zijn. Elk algoritme is anders in de manier waarop ze iterators behandelen (en ongeldig maken).

Navigeren met Iterators

Zoals we weten, zijn iterators bedoeld om door sequenties te navigeren. Om dat te doen moet een iterator zijn positie door de reeks migreren. Iterators kunnen vooruit gaan in de reeks en sommige kunnen achteruit gaan:

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.

Let op, het tweede argument van std :: afstand moet bereikbaar zijn vanaf het eerste (of, met andere woorden, het first moet kleiner of gelijk zijn aan het second ).

Hoewel u rekenkundige operatoren met iterators kunt uitvoeren, zijn niet alle bewerkingen voor alle typen iterators gedefinieerd. a = b + 3; zou werken voor Random Access Iterators, maar zou niet werken voor Forward of Bidirectionele Iterators, die nog steeds met 3 posities kunnen worden uitgebreid met zoiets als b = a; ++b; ++b; ++b; . Het wordt daarom aanbevolen om speciale functies te gebruiken als u niet zeker weet wat het iteratortype is (bijvoorbeeld in een sjabloonfunctie die iterator accepteert).

Iterator-concepten

De C ++ standaard beschrijft verschillende iteratorconcepten. Deze zijn gegroepeerd op basis van hoe ze zich gedragen in de sequenties waarnaar ze verwijzen. Als u het concept kent dat een iterator modelleert (gedraagt zich als), kunt u verzekerd zijn van het gedrag van die iterator, ongeacht de volgorde waartoe deze behoort . Ze worden vaak beschreven in volgorde van de meest tot de minst beperkende (omdat het volgende iteratorconcept een stap beter is dan zijn voorganger):

• Input Iterators: kan slechts eenmaal per positie worden verwijderd. Kan slechts vooruitgaan, en slechts één positie tegelijk.
• Forward Iterators: een invoer-iterator die een willekeurig aantal keren kan worden verwijderd.
• Bidirectionele Iterators: een voorwaartse iterator die ook één positie tegelijk achteruit kan gaan.
• Random Access Iterators: een bidirectionele iterator die een willekeurig aantal posities tegelijkertijd vooruit of achteruit kan gaan.
• Aaneengesloten herhalers (sinds C ++ 17): een iterator voor willekeurige toegang die garandeert dat onderliggende gegevens aaneengesloten in het geheugen zijn.

Algoritmen kunnen variëren, afhankelijk van het concept gemodelleerd door de iterators die ze krijgen. Hoewel random_shuffle kan worden geïmplementeerd voor doorstuuriterators, kan een efficiëntere variant worden geleverd die iterators met willekeurige toegang vereist.

Iterator-eigenschappen

Iterator-eigenschappen bieden een uniforme interface voor de eigenschappen van iterators. Hiermee kunt u waarde, verschil, aanwijzer, referentietypes en ook categorie van iterator ophalen:

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;
}

Categorie iterator kan worden gebruikt om algoritmen te specialiseren:

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());
}

Categorieën iterators zijn in principe iterators-concepten, behalve dat aaneengesloten iterators geen eigen tag hebben, omdat werd vastgesteld dat deze code verbrak.

Omgekeerde Iterators

Als we achteruit door een lijst of vector willen herhalen, kunnen we een reverse_iterator . Een reverse iterator is gemaakt van een bidirectionele of random access iterator die wordt bewaard als een lid dat toegankelijk is via base() .

Om achteruit te herhalen, gebruikt u respectievelijk rbegin() en rend() als iterators voor het einde van de verzameling en het begin van de verzameling.

Gebruik bijvoorbeeld om achteruit te itereren:

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

Een omgekeerde iterator kan worden omgezet in een voorwaartse iterator via de lidfunctie base() . De relatie is dat de reverse iterator verwijst naar één element voorbij de base() iterator:

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()

In de visualisatie waarbij iterators posities tussen elementen markeren, is de relatie eenvoudiger:

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

Vector Iterator

begin retourneert een iterator naar het eerste element in de reekscontainer.

end retourneert een iterator naar het eerste element voorbij het einde.

Als het vectorobject const , retourneren zowel begin als end een const_iterator . Als u wilt dat een const_iterator worden teruggestuurd, zelfs als uw vector is niet const , kunt u gebruik maken cbegin en cend .

Voorbeeld:

#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;
}

Output:

1 2 3 4 5

Kaart Iterator

Een iterator naar het eerste element in de container.

Als een const_iterator const-gekwalificeerd is, retourneert de functie een const_iterator . Anders wordt een iterator geretourneerd.

// 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';

Output:

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

Stream Iterators

Stream-iterators zijn handig wanneer we een reeks moeten lezen of geformatteerde gegevens uit een container moeten afdrukken:

// 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, " -- "));

Het voorbeeldprogramma drukt 1 -- 2 -- 3 -- 4 -- naar standaarduitvoer.

Schrijf uw eigen iterator met generatorondersteuning

Een gebruikelijk patroon in andere talen is het hebben van een functie die een "stroom" van objecten produceert, en in staat zijn lus-code te gebruiken om erover te lus.

We kunnen dit in C ++ modelleren als

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;
};

live voorbeeld .

We slaan het gegenereerde element vroeg op, zodat we gemakkelijker kunnen detecteren of we al aan het einde zijn.

Omdat de functie van een eindgenerator-iterator nooit wordt gebruikt, kunnen we een reeks generator-iterators maken door de std::function eenmaal te kopiëren. Een standaard geconstrueerde generator-iterator is vergelijkbaar met zichzelf, en met alle andere eind-generator-iterators.