Wie schreibe ich eine Funktion, die auf generische Weise einen Iterator oder eine Sammlung akzeptiert?

Question

Ich bin seit etwa 8 Jahren fast ausschließlich Java-Programmierer und habe in letzter Zeit wieder mit C++ gespielt. Hier ist ein Problem, das ich im Zusammenhang mit Iteratoren in C++ STL und Java festgestellt habe.

In Java kann man eine Methode schreiben, die einen Iterator nimmt, wie zum Beispiel:

void someMethod(Iterator data) {
    // ...
}

Sie übergeben einen Iterator und die Methode muss nicht wissen, um welche zugrunde liegende Sammlung es sich bei diesem Iterator handelt, was gut ist.

In C++ gibt es keine gemeinsame Basisklasse für Iteratoren (so weit ich weiß). Ich müsste eine Funktion wie diese schreiben:

void some_function(std::vector::const_iterator data) {
    // ...
}

Mit anderen Worten, some_function weiß, dass der Iterator ein Iterator über einen vector ist. Das ist nicht gut, weil ich möchte, dass die Funktion unabhängig davon funktioniert, um welche zugrunde liegende Sammlung es sich bei dem Iterator handelt.

Wie kann ich das in C++ machen? Wenn es wirklich nicht möglich ist, was ist dann der beste Weg, eine Funktion in C++ zu erstellen, die eine Sammlung als Parameter übernimmt, ohne zu wissen, um welche Art von Sammlung es sich genau handelt?

Nachtrag

Danke für die Antworten. Neben den Antworten habe ich einige gute Informationen dazu im Abschnitt 7.5 (Iterator Traits) des Buches The C++ Standard Library: A Tutorial and Reference (von Nicolai M. Josuttis) gefunden. Abschnitt 7.5.1 erklärt, wie man spezialisierte Versionen von Funktionen für verschiedene Iterator-Kategorien schreibt.

Answer 1

Sie möchten wahrscheinlich eine Funktionsvorlage in Betracht ziehen. Schauen Sie sich an, wie einige der std Funktionenvorlagen funktionieren, wie z.B. std::for_each.

z.B.

template< class Iterator >
void some_function( Iterator first, Iterator last )
{
    // ...
}

Sie können dann eine aus dieser Vorlage generierte Funktion mit vielen Arten von iterierbaren Bereichen aufrufen.

z.B.

std::vector< double > my_doubles;
// ... befüllen Sie die doubles
some_function( my_doubles.begin(), my_doubles.end() );

std::set< Custom > my_custom_class_set;
// ... befüllen ...
some_function( my_custom_class_set.begin(), my_custom_class_set.end() );

int raw_array[50];
// ... befüllen ...
some_function( raw_array, raw_array + 50 );

Answer 2

Es ist am besten, durch eine Namenskonvention anzuzeigen, welche Art von Iterator und anschließend welche Art von Eigenschaften der Iterator besitzen muss. Im Folgenden sind einige gängige Namenskonventionen für Iteratoren:

template void foo\_iterator(Iterator begin, Iterator end)
{
   typedef typename std::iterator\_traits::value\_type T;
   ....
}

template void foo\_random\_iterator(RandomIterator begin, RandomIterator end)
{
   typedef typename std::iterator\_traits::value\_type T;
   ....
}

template void foo\_forward\_iterator(ForwardIterator begin, ForwardIterator end)
{
   typedef typename std::iterator\_traits::value\_type T;
   ....
}

template void foo\_forward\_iterator(ReverseIterator begin, ReverseIterator end)
{
   typedef typename std::iterator\_traits::value\_type T;
   ....
}

template void foo\_input\_iterator(InputIterator begin, InputIterator end)
{
   typedef typename std::iterator\_traits::value\_type T;
   ....
}

template void foo\_output\_iterator(OutputIterator out)
{
   // Wir haben keinen Typ T, da wir den Typ nicht "immer" kennen können, da dieser Typ von Iterator ein Sink ist.
   ....
} 

Im Folgenden finden Sie eine generische Definition für Sequenz-Typ-Container, zu denen Vektor und Warteschlange (deque) gehören.

template class Sequence>
inline void foo\_sequence(Sequence& sequence)
{
   ....
}

Answer 3

Dies ist ein Beispiel für eine der großen Unterschiede zwischen C++ und Java. Das einzige Abstraktionswerkzeug, das Java hat, ist Polymorphismus zur Laufzeit (Schnittstellen und abstrakte Klassen). In C++ sind Sie nicht auf das beschränkt. Sie können Aliasnamen für Typen erstellen und Klassen andere assoziierte/geschachtelte Typen haben lassen. Dies ermöglicht es Ihnen, in vielen Fällen ohne Polymorphie zur Laufzeit auszukommen. Die Art der Generizität zur Übersetzungszeit hat den Vorteil, sehr schnell zu sein (keine virtuellen Funktionsaufrufe, Möglichkeiten für Inlining). Außerdem vereinfacht es das Lebensdauer-Management, wenn Sie keinen Garbage Collector haben. Sie können die Objekte einfach auf dem Stapel erstellen.

Hier ist ein (nicht getestetes) Beispiel:

template
typename std::iterator_traits::value_type
sum(Iter begin, Iter end) {
   typedef typename std::iterator_traits::value_type vt;
   vt accum = vt();
   while (begin!=end) {
      accum += *begin;
      ++begin;
   }
   return accum;
}

Hier ist "Iter" nur ein Name. Es setzt tatsächlich keine Einschränkungen auf den Typ. Wenn Sie diesen Template mit einem Typ instanziieren möchten, der kein Iterator ist (zumindest strukturell betrachtet), erhalten Sie einen Fehler zur Übersetzungszeit (Typisierung zur Übersetzungszeit). Ein Teil Ihrer Aufgabe besteht also darin, die Art des erwarteten Typs zu dokumentieren. Dies wird normalerweise durch die Auswahl einiger beschreibender Namen für Template-Parameter (z.B. ForwardIterator) und Kommentare erreicht.

Ich sollte auch erwähnen, dass mehrere "sum"-Funktionen "instantiiert" werden, wenn Sie diese Funktionenvorlage mit verschiedenen Arten von Iteratoren verwenden. Wenn Sie diese Art von Code-Duplizierung nicht möchten und/oder wirklich Polymorphie zur Laufzeit benötigen, können Sie eine Technik namens "Typumwandlung" anwenden. Typumwandlung für Iteratoren ist jedoch nicht Teil der Standardbibliothek. Außerdem habe ich nie das Bedürfnis verspürt, diese Technik für Iteratoren anzuwenden. Sie finden jedoch die Verwendung von Typumwandlung in anderen Bibliotheken wie boost::any und boost::function.

Es gibt ein paar andere Template-Tricks, die Sie verwenden können, um zwischen verschiedenen Iterator-Kategorien zu unterscheiden (siehe "Tag-Dispatching") oder Ihre Funktionenvorlage einzuschränken (siehe "SFINAE"). Wenn Sie an Typumwandlung interessiert sind, versuchen Sie, nach c++, Typumwandlung, Iterator zu googeln. Sie erstellen im Grunde genommen eine Handle-Klasse, die ein polymorphes Objekt verwaltet (über einen Zeiger). Dieses polymorphe Objekt umhüllt ein anderes Objekt, dessen Typ Sie "löschen" (verbergen) möchten.

Answer 4

Sie können die Header-Datei verwenden und die minimalen Anforderungen angeben, die der Iterator unterstützen muss.

Also in obigem Beispiel möchten Sie die Funktion vielleicht wie folgt umschreiben:

template
void some_function(std::forward_iterator data) {
   ...
}

für etwas, das erfordert, dass der Iterator nur vorwärts (++) durch eine Sammlung bewegt werden kann.