Sortieralgorithmus BubbleSort

Ich möchte an der Stelle anmerken, dass es sich bei std::swap und std::sort nicht um Funktionen, sondern um Funktionsvorlagen handelt. Deren Existenz ist es ja, die es erst nützlich macht, Iteratoren als Konzepte statt als konkrete Typen zu definieren.

@Sorex: Die Idee hinter Iteratoren ist etwas nebulös, solange man Templates (d.h. Vorlagen) noch nicht kennt. Es handelt sich bei ihnen, wie oben angemerkt, um Konzepte, was hier bedeutet, dass jeder konkrete Typ als Iterator gilt, der bestimmte Benutzungsformen erlaubt. Dabei gibt es verschiedene, ineinander geschachtelte Iteratorkonzepte. Beispielsweise ist alles ein ForwardIterator, was neben Konstruktion, Zuweisung und Vergleich mit == und != Folgendes erlaubt:

// Sei fwditer ein ForwardIterator

*fwditer;
++fwditer;
fwditer++;
fwditer->member_des_zieltyps;

Ein BidirectionalIterator ist etwas, was zusätzlich

// Sei bditer ein BidirectionalIterator

--bditer;
bditer--;

erlaubt. Jeder BidirectionalIterator ist gleichzeitig ein ForwardIterator. In ähnlicher Weise ist ein RandomAccessIterator ein BidirectionalIterator, der zusätzlich die Operationen

// Seien raiter und raiter2 RandomAccessIteratoren

raiter += n;
raiter -= n;
raiter + n;
raiter - n;
raiter[n];

raiter - raiter2; // Entfernung voneinander
raiter <  raiter2;
raiter <= raiter2;
raiter >  raiter2;
raiter >= raiter2;

erlaubt. Zeiger sind dementsprechend RandomAccessIteratoren (!).

Iteratoren werden generell als Positionsangaben benutzt. Wenn v ein std::vector<int> ist, ist v.begin() die Position des ersten Elements des Vektors und v.end() die Position direkt hinter seinem letzten. Zwei Iteratoren in den selben Container können einen Bereich beschreiben; so ist es bei vielen Standardalgorithmen der Fall. Beispielsweise bedeutet

std::vector<int> v;

...

std::sort(v.begin(), v.end());

soviel wie "sortiere alles zwischen v.begin() und v.end()". Man kann auch

std::sort(v.begin() + 1, v.end() - 1);

schreiben, was soviel bedeutet wie "sortiere alles zwischen v.begin() + 1 und v.end() - 1", also alle Elemente des Vektors außer dem ersten und letzten.

Dass das unabhängig davon möglich ist, welcher konkrete (RandomAccess)Iteratortyp benutzt wird (also dass es sowohl mit std::vector<int>::iterator als auch mit std::list<double>::reverse_iterator als auch mit int* usw. geht), liegt daran, dass es sich bei std::sort nicht um eine Funktion handelt, die einen konkreten Iteratortyp erwartet, sondern um eine Funktionsvorlage, aus der für jeden konkreten Iteratortyp, mit dem du sie benutzt, eine Funktion erstellt wird. Das ist aber ein sehr weitläufiges Thema, das ich nicht in ein paar Minuten erklären kann.

seldon schrieb:

Die Idee hinter Iteratoren ist etwas nebulös, solange man Templates (d.h. Vorlagen) noch nicht kennt.

Eigentlich hat das Konzept hinter Iteratoren nichts mit Templates zu tun.

ISO/IEC 14882:2003 24.1 (1) schrieb:

Iterators are a generalization of pointers that allow a C++ program to work with different data structures (containers) in a uniform manner. To be able to construct template algorithms that work correctly and efficiently on different types of data structures, the library formalizes not just the interfaces but also the semantics and complexity assumptions of iterators.

Nun, dass die STL reichlich davon gebrauch macht ist schon klar, aber das Konzept oder die Idee dahinter hat nichts mit Templates, sogar nicht einmal etwas mit C++ zu tun. Iteratoren sind ein allgemeineres Konzept. Wikipedia hilft dir da sicher weiter.