Suche…
C Iteratoren (Zeiger)
// 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
Dieser Code würde die Zahlen 1 bis 5 ausgeben, eine in jeder Zeile wie folgt:
1
2
3
4
5
Brechen sie ab
const int array[] = { 1, 2, 3, 4, 5 };
Diese Zeile erstellt ein neues Integer-Array mit 5 Werten. C-Arrays sind nur Zeiger auf Speicher, in denen jeder Wert zusammen in einem zusammenhängenden Block gespeichert wird.
const int* first = array;
const int* afterLast = first + sizeof(array) / sizeof(array[0]);
Diese Linien erzeugen zwei Zeiger. Der erste Zeiger erhält den Wert des Arrayzeigers, der die Adresse des ersten Elements im Array ist. Der Operator sizeof bei Verwendung in einem C-Array die Größe des Arrays in Byte zurück. Geteilt durch die Größe eines Elements ergibt sich die Anzahl der Elemente im Array. Damit können wir die Adresse des Blocks nach dem Array ermitteln.
for (const int* i = first; i < afterLast; ++i) {
Hier erstellen wir einen Zeiger, den wir als Iterator verwenden werden. Es wird mit der Adresse des ersten Elements wir iterieren wollen initialisiert und wir werden so lange iteriert weiterhin als i kleiner als ist afterLast , die so lange Mittel wie i innerhalb einer Adresse zeigt array .
std::cout << *i << std::endl;
Schließlich innerhalb der Schleife können wir den Wert unserer Iterator zugreifen i zu zeigt , indem sie es dereferencing. Hier gibt der Dereferenzierungsoperator * den Wert an der Adresse in i .
Überblick
Iteratoren sind Positionen
Iteratoren sind ein Mittel zum Navigieren und Bedienen einer Folge von Elementen und sind eine verallgemeinerte Erweiterung von Zeigern. Konzeptionell ist es wichtig zu wissen, dass Iteratoren Positionen und keine Elemente sind. Nehmen Sie zum Beispiel die folgende Reihenfolge:
A B C
Die Sequenz enthält drei Elemente und vier Positionen
+---+---+---+---+
| A | B | C | |
+---+---+---+---+
Elemente sind Dinge innerhalb einer Sequenz. Positionen sind Orte, an denen sinnvolle Operationen mit der Sequenz passieren können. Zum Beispiel fügt man in eine Position vor oder nach Element A ein, nicht in ein Element. Selbst das Löschen eines Elements ( erase(A) ) erfolgt, indem zuerst die Position ermittelt und anschließend gelöscht wird.
Von Iteratoren zu Werten
Um von einer Position in einen Wert umzuwandeln, wird ein Iterator dereferenziert :
auto my_iterator = my_vector.begin(); // position
auto my_value = *my_iterator; // value
Man kann sich einen Iterator als Dereferenzierung auf den Wert vorstellen, auf den er in der Sequenz verweist. Dies ist besonders nützlich, um zu verstehen, warum Sie niemals den end() Iterator in einer Sequenz dereferenzieren sollten:
+---+---+---+---+
| A | B | C | |
+---+---+---+---+
↑ ↑
| +-- An iterator here has no value. Do not dereference it!
+-------------- An iterator here dereferences to the value A.
In allen Sequenzen und Containern, die in der C ++ - Standardbibliothek zu finden sind, bringt begin() einen Iterator an die erste Position zurück und end() einen Iterator an die letzte Position ( nicht an die letzte Position!). Daher werden die Namen dieser Iteratoren in Algorithmen oft als first und last :
+---+---+---+---+
| A | B | C | |
+---+---+---+---+
↑ ↑
| |
+- first +- last
Es ist auch möglich, einen Iterator für eine beliebige Sequenz zu erhalten , da selbst eine leere Sequenz mindestens eine Position enthält:
+---+
| |
+---+
In einer leeren Sequenz sind begin() und end() die gleiche Position und keine dereferenziert werden kann:
+---+
| |
+---+
↑
|
+- empty_sequence.begin()
|
+- empty_sequence.end()
Die alternative Visualisierung von Iteratoren besteht darin, dass sie die Positionen zwischen den Elementen markieren:
+---+---+---+
| A | B | C |
+---+---+---+
↑ ^ ^ ↑
| |
+- first +- last
und dereferenzieren eines Iterators gibt eine Referenz auf das Element zurück, das nach dem Iterator kommt. Einige Situationen, in denen diese Ansicht besonders nützlich ist, sind:
-
insertwerden Elemente in die vom Iterator angegebene Position eingefügt. -
erasegeben einen Iterator zurück, der der gleichen Position entspricht wie der übergebene, - Ein Iterator und sein entsprechender Reverse-Iterator befinden sich in derselben Position zwischen den Elementen
Ungültige Iteratoren
Ein Iterator wird ungültig, wenn (z. B. während einer Operation) seine Position nicht mehr Teil einer Sequenz ist. Ein ungültiger Iterator kann nicht dereferenziert werden, bis er einer gültigen Position zugewiesen wurde. Zum Beispiel:
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
Für die vielen Algorithmen und Sequenzelementfunktionen in der C ++ - Standardbibliothek gelten Regeln, wenn Iteratoren ungültig gemacht werden. Jeder Algorithmus unterscheidet sich in der Art und Weise, wie er Iteratoren behandelt (und ungültig macht).
Mit Iteratoren navigieren
Wie wir wissen, sind Iteratoren für das Navigieren von Sequenzen. Zu diesem Zweck muss ein Iterator seine Position während der gesamten Sequenz verschieben. Iteratoren können in der Sequenz vorwärts und einige rückwärts vorrücken:
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.
Beachten Sie, dass das zweite Argument von std :: distance vom ersten Argument aus erreichbar sein sollte (oder anders ausgedrückt, das first sollte kleiner oder gleich dem second ).
Obwohl Sie arithmetische Operatoren mit Iteratoren ausführen können, sind nicht alle Operationen für alle Arten von Iteratoren definiert. a = b + 3; würde für Random Access Iterators funktionieren, aber nicht für Forward- oder Bidirectional Iterators, die immer noch um 3 Positionen mit etwas wie b = a; ++b; ++b; ++b; vorgerückt werden können b = a; ++b; ++b; ++b; . Es wird daher empfohlen, spezielle Funktionen zu verwenden, wenn Sie nicht sicher sind, um welchen Iteratortyp es sich handelt (z. B. in einer Vorlagenfunktion, die den Iterator akzeptiert).
Iterator-Konzepte
Der C ++ - Standard beschreibt verschiedene Iteratorkonzepte. Diese werden nach ihrem Verhalten in den Sequenzen gruppiert, auf die sie sich beziehen. Wenn Sie das Konzept kennen, das ein Iterator modelliert (verhält sich wie), können Sie sich auf das Verhalten dieses Iterators verlassen, unabhängig von der Sequenz, zu der er gehört . Sie werden oft in der Reihenfolge von am wenigsten bis am wenigsten einschränkend beschrieben (da das nächste Iteratorkonzept einen Schritt besser ist als sein Vorgänger):
- Eingabe-Iteratoren: Kann nur einmal pro Position dereferenziert werden. Kann nur vorrücken und jeweils nur eine Position.
- Forward-Iteratoren: Ein Eingabe-Iterator, der beliebig oft dereferenziert werden kann.
- Bidirektionale Iteratoren: Ein Vorwärts-Iterator, der auch eine Position nach hinten vorrücken kann.
- Iteratoren mit wahlfreiem Zugriff: Ein bidirektionaler Iterator, der eine beliebige Anzahl von Positionen gleichzeitig vor- oder zurückbewegen kann.
- Angrenzende Iteratoren (seit C ++ 17): Ein Iterator mit wahlfreiem Zugriff, der garantiert, dass die zugrunde liegenden Daten im Speicher zusammenhängend sind.
Algorithmen können je nach Konzept variieren, das von den angegebenen Iteratoren modelliert wird. Obwohl random_shuffle beispielsweise für Forward-Iteratoren random_shuffle kann, könnte eine effizientere Variante bereitgestellt werden, die Iteratoren mit wahlfreiem Zugriff erfordert.
Iterator-Merkmale
Iterator-Merkmale bieten eine einheitliche Schnittstelle zu den Eigenschaften von Iteratoren. Damit können Sie Werte, Unterschiede, Zeiger, Referenztypen und auch die Kategorie des Iterators abrufen:
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;
}
Die Kategorie des Iterators kann zur Spezialisierung von Algorithmen verwendet werden:
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());
}
Kategorien von Iteratoren sind im Wesentlichen Iteratorkonzepte, mit der Ausnahme, dass fortlaufende Iteratoren kein eigenes Tag haben, da festgestellt wurde, dass sie Code beschädigen.
Umgekehrte Iteratoren
Wenn wir durch eine Liste oder einen Vektor rückwärts iterieren möchten, können wir einen reverse_iterator . Ein Reverse-Iterator wird aus einem bidirektionalen oder Random-Access-Iterator erstellt, den er als Mitglied speichert, auf das über base() zugegriffen werden kann.
Um rückwärts zu iterieren, verwenden Sie rbegin() und rend() als Iteratoren für das Ende der Sammlung bzw. den Beginn der Sammlung.
Um zum Beispiel rückwärts zu iterieren, verwenden Sie:
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
Ein Reverse-Iterator kann über die base() Member-Funktion in einen Forward-Iterator konvertiert werden. Die Beziehung ist, dass der Reverse-Iterator auf ein Element hinter dem Iterator base() verweist:
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 der Visualisierung, wo Iteratoren Positionen zwischen Elementen markieren, ist die Beziehung einfacher:
+---+---+---+---+---+
| 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+
↑ ↑
| |
| end()
| rbegin()
begin() rbegin().base()
rend()
rend().base()
Vektor-Iterator
begin gibt einen iterator an das erste Element im Sequenzcontainer zurück.
end gibt einen iterator an das erste Element nach dem Ende zurück.
Wenn das Vektorobjekt const , geben sowohl begin als auch end einen const_iterator . Wenn Sie möchten, dass const_iterator zurückgegeben wird, auch wenn Ihr Vektor nicht const , können Sie cbegin und cend .
Beispiel:
#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;
}
Ausgabe:
1 2 3 4 5
Karten-Iterator
Ein Iterator für das erste Element im Container.
Wenn ein Kartenobjekt für const qualifiziert ist, gibt die Funktion einen const_iterator . Andernfalls wird ein 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';
Ausgabe:
a => 200
b => 100
c => 300
Stream-Iteratoren
Stream-Iteratoren sind nützlich, wenn Sie eine Sequenz lesen oder formatierte Daten aus einem Container drucken müssen:
// 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, " -- "));
Das Beispielprogramm druckt 1 -- 2 -- 3 -- 4 -- zur Standardausgabe.
Schreiben Sie Ihren eigenen Iterator mit Generatorunterstützung
Ein weit verbreitetes Muster in anderen Sprachen ist die Funktion, die einen "Strom" von Objekten erzeugt und in der Lage ist, Schleifencode zum Schleifen darüber zu verwenden.
Wir können dies in C ++ als modellieren
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;
};
Wir speichern das generierte Element frühzeitig, sodass wir leichter erkennen können, ob wir bereits am Ende sind.
Da die Funktion eines End-Generator-Iterators nie verwendet wird, können wir eine Reihe von Generator-Iteratoren erstellen, indem Sie die std::function nur einmal kopieren. Ein standardmäßig erstellter Generator-Iterator vergleicht gleich mit sich selbst und mit allen anderen End-Generator-Iteratoren.
