Verkettung Iteratoren für C++

Question

Python Itertools implementieren einen chain Iterator, der im Wesentlichen eine Reihe von verschiedenen Iteratoren verkettet, um alles aus einzelnen Iterator bereitzustellen.

Gibt es in C++ etwas Ähnliches? Ein kurzer Blick auf die Boost-Bibliotheken ergab nichts Ähnliches, was für mich ziemlich überraschend ist. Ist es schwierig, diese Funktionalität zu implementieren?

Answer 1

Kam über diese Frage während der Untersuchung für ein ähnliches Problem.

Auch wenn die Frage alt ist, jetzt in der Zeit von C++ 11 und Boost 1.54 ist es ziemlich einfach, mit der Boost.Range Bibliothek zu tun. Es verfügt über eine join-function, die zwei Bereiche zu einem einzigen verbinden kann. Hier kann es zu Leistungseinbußen kommen, da das niedrigste gemeinsame Bereichskonzept (dh Single Pass Range or Forward Range usw.) als neue Bereichskategorie verwendet wird und während der Iteration der Iterator überprüft werden kann, ob er zu dem neuen Bereich springen muss, aber Ihr Code sein kann leicht geschrieben wie:

#include <boost/range/join.hpp> 

#include <iostream> 
#include <vector> 
#include <deque> 

int main() 
{ 
    std::deque<int> deq = {0,1,2,3,4}; 
    std::vector<int> vec = {5,6,7,8,9}; 

    for(auto i : boost::join(deq,vec)) 
    std::cout << "i is: " << i << std::endl; 

    return 0; 
} 

Answer 2

Nicht in der Standardbibliothek. Boost könnte etwas haben.

Aber eigentlich sollte so etwas trivial zu implementieren sein. Machen Sie sich einfach einen Iterator mit einem Vektor von Iteratoren als Mitglied. Ein sehr einfacher Code für Operator ++, und du bist da.

Answer 3

In C++ macht ein Iterator normalerweise außerhalb eines Kontextes am Anfang und am Ende eines Bereichs keinen Sinn. Der Iterator selbst weiß nicht, wo der Anfang und das Ende sind. Um also so etwas zu tun, müssen Sie stattdessen Bereiche von Iteratoren verketten - Bereich ist ein (Anfangs-, Ende-) Paar von Iteratoren.

Werfen wir einen Blick auf die boost::range Dokumentation. Es kann Werkzeuge zum Erstellen einer Kette von Bereichen bereitstellen. Der einzige Unterschied besteht darin, dass sie vom selben Typ sein müssen und den gleichen Typ von Iterator zurückgeben müssen. Es kann weiterhin möglich sein, dieses generische Verfahren so zu gestalten, dass verschiedene Arten von Bereichen mit etwas wie any_iterator verknüpft werden, aber möglicherweise nicht.

Answer 4

Ich habe eine zuvor geschrieben (eigentlich nur zwei Paare von Iteratoren zusammen zu ketten). Es ist nicht so schwer, vor allem, wenn Sie Boost iterator_facade verwenden.

Einen Eingabe-Iterator zu erstellen (was effektiv ist, was Python chain tut) ist ein einfacher erster Schritt. Die richtige Kategorie für einen Iterator zu finden, der eine Kombination verschiedener Iterator-Kategorien verkettet, bleibt als Übung für den Leser übrig ;-).

Answer 5

Keine Funktion existiert in Boost, die dies implementiert, nach meinem besten Wissen - ich habe eine ziemlich umfangreiche Suche.

Ich dachte, ich würde dies leicht letzte Woche implementieren, aber ich lief in einen Haken: die STL, die mit Visual Studio 2008 kommt, wenn Bereichsüberprüfung aktiviert ist, erlaubt nicht Iteratoren aus verschiedenen Containern zu vergleichen kann somevec1.end() nicht mit somevec2.end()) vergleichen. Auf einmal wurde es viel schwieriger, dies zu implementieren, und ich habe noch nicht ganz entschieden, wie ich es machen soll.

Ich schrieb andere Iteratoren in der Vergangenheit mit Iterator_Facade und Iterator_Adapter von Boost, die besser als das Schreiben von 'Raw' Iteratoren sind, aber ich finde immer noch Schreiben von benutzerdefinierten Iteratoren in C++ ziemlich chaotisch.

Wenn jemand einen Pseudocode veröffentlichen kann, wie das gemacht werden könnte/ohne/Iteratoren aus verschiedenen Containern zu vergleichen, wäre ich sehr dankbar.

Answer 6

Überprüfen Sie Views Template Library (VTL). Es kann nicht direkt den 'verketteten Iterator' bereitstellen. Aber ich denke, dass es alle notwendigen Tools/Templates zur Verfügung hat, um einen eigenen 'Chained Iterator' zu implementieren.

---

Von der VTL Seite:

Eine Ansicht ist ein Container-Adapter, die eine Behälter-Schnittstelle zu

1. Teile der Daten oder
2. eine Umlagerung der Daten oder
bietet
3. transformierten Daten oder
4. eine geeignete Kombination aus den Datensätzen

des darunterliegenden Behälters (s). Da Ansichten selbst die Container-Schnittstelle bereitstellen, können sie einfach kombiniert und gestapelt werden. Aufgrund von Vorlagentricks können Ansichten ihre Schnittstelle an die zugrunde liegenden Container anpassen. Ein ausgefeilterer Vorlagentrick macht diese leistungsstarke Funktion einfach zu benutzen.

Verglichen mit intelligenten Iteratoren sind Ansichten nur intelligente Iteratorfactories.

Answer 7

Was Sie suchen im Wesentlichen für eine Fassade Iterator, die Verfahrgeschwindigkeit durch mehrere Sequenzen abstrahiert.

Da Sie von einem Python-Hintergrund kommen Ich nehme an, dass Sie mehr über Flexibilität sorgen, anstatt Geschwindigkeit. Mit Flexibilität meine ich die Fähigkeit, durch verschiedene Sequenztypen (Vektor, Array, verknüpfte Liste, Menge usw.) zu iterieren und mit Geschwindigkeit nur Speicher aus dem Stack zuzuordnen.

Wenn dies der Fall ist, dann mögen Sie vielleicht am any_iterator von Adobe Labs suchen: http://stlab.adobe.com/classadobe_1_1any__iterator.html

Dieser Iterator gibt Ihnen die Möglichkeit, durch eine beliebigen Sequenztyp zur Laufzeit zu durchlaufen. Zur Verkettung würden Sie einen Vektor (oder ein Array) von 3-Tupel-Any_iteratoren haben, das heißt drei Any_iteratoren für jeden Bereich, den Sie verketten (Sie benötigen drei, um vorwärts oder rückwärts zu iterieren, wenn Sie nur vorwärts iterieren wollen, werden zwei ausreichen).

Lassen Sie uns sagen, dass Sie zu Ketten Iterierte durch eine Folge von ganzen Zahlen wollte:

(Ungeprüfte psuedo-C++ Code)

typedef Adobe :: any_iterator AnyIntIter;

struct AnyRange { AnyIntIter beginnen; AnyIntIter curr; AnyIntIter Ende; };

Sie einen Bereich definieren, könnten wie:

int_array int [] = {1, 2, 3, 4}; AnyRange sequenz_0 = {int_array, int_array, int_array + ARRAYSIZE (int_array)};

Ihre RangeIterator-Klasse hätte dann einen std :: vector.

<code> 
class RangeIterator { 
public: 
    RangeIterator() : curr_range_index(0) {} 

    template <typename Container> 
    void AddAnyRange(Container& c) { 
    AnyRange any_range = { c.begin(), c.begin(), c.end() }; 
    ranges.push_back(any_range); 
    } 

    // Here's what the operator++() looks like, everything else omitted. 
    int operator++() { 

    while (true) { 
     if (curr_range_index > ranges.size()) { 
     assert(false, "iterated too far"); 
     return 0; 
     } 
     AnyRange* any_range = ranges[curr_range_index]; 
     if (curr_range->curr != curr_range->end()) { 
     ++(curr_range->curr); 
     return *(curr_range->curr); 
     } 
     ++curr_range_index;  
    } 
    } 


private: 
    std::vector<AnyRange> ranges; 
    int curr_range_index; 
}; 
</code> 

Ich möchte jedoch feststellen, dass diese Lösung sehr langsam ist. Der bessere, C++ - ähnliche Ansatz besteht lediglich darin, alle Zeiger auf die Objekte zu speichern, auf denen Sie arbeiten und diese durchlaufen möchten. Alternativ können Sie einen Funktor oder einen Besucher auf Ihre Bereiche anwenden.