Schnittstelle für Iteration durch Member-Container

Nexus

Hallo miteinander,

Es gab zu etwas Ähnlichem mal einen Thread. Dort ging es um die Schnittstelle bei Member-Containern im Allgemeinen, ich beziehe mich nur aufs Iterieren. Konkret geht es mir darum, eine möglichst saubere Schnittstelle für eine Klasse zu finden, welche einen Container als Member hält und die Funktionalität des Iterierens über alle Elemente anbieten soll. Die Klasse repräsentiert selbst keinen Container, sondern soll lediglich die For-Each-Semantik nach aussen hin anbieten.

// value_type des Containers
struct Element
{
	void DoSomething();
};

// Kapselnde Klasse
class MyClass
{
	public:
		// Schnittstelle noch zu definieren
	private:
		Container MyContainer; // irgendein STL-kompatibler Container
};

Ich habe mir dazu einige Ansätze überlegt, die ich im Folgenden diskutieren möchte:

1) Typedef und zwei Funktionen für Range-Grenzen.
Aufrufe von Begin() und End() werden an den Container 1:1 weitergeleitet. Diese Möglichkeit gefällt mir nicht sehr, weil MyClass an sich ja keinen Containertyp darstellt und mir solche typischen Containermethoden etwas unangebracht vorkommen (besonders, falls in der Klasse mehrere Container vorhanden sind). Wäre auch nicht schlecht, den Iterator noch zusätzlich einzuschränken...

// --- Schnittstelle ----------------------------------------------------------
typedef Container::iterator Iterator;
Container::iterator Begin();
Container::iterator End();

// --- Anwendung --------------------------------------------------------------
MyClass Obj;
for (MyClass::Iterator Itr = Obj.Begin(), End = Obj.End(); Itr != End; ++Itr)
{
	Itr->DoSomething();
}

2) bool-Funktion, die Elemente einzeln ausliest.
Sehr elegant in der Anwendung, aber gefährlich, wenn die while -Schleife vorzeitig verlassen wird (z.B. Exception), da die Klasse sich intern ja einen Iterator speichert, der nach Iterationsende korrekt zurückgesetzt werden muss. Lösung wäre zwar eine Reset() -Funktion, aber grundsätzlich gefällt mir der Gedanke, dass der Iterationszustand zur Klasse gehört, nicht besonders.

// --- Schnittstelle ----------------------------------------------------------
bool Iterate(Element& CurrentElem);

// --- Anwendung --------------------------------------------------------------
MyClass Obj;
Element Elem;
while (Obj.Iterate(Elem))
{
	Elem.DoSomething();
}

3) Wrapper-Iterator.
Besser als Reset wäre eine Art Init-Funktion. Mit diesem Ansatz kann man wirklich nur vorwärts iterieren, hat also keine unnötige Funktionalität zur Verfügung. Ebenfalls als Vorteil erachte ich die Tatsache, dass man sich nicht um end() oder sowas kümmern muss. In entfernter Anlehnung an Java:

// --- Schnittstelle ----------------------------------------------------------
class Iterator // Nested-Typ
{
	public:
		bool HasMoreElements() const;
		Iterator& operator++ ();
		Element&  operator* ();
		Element*  operator-> ();
	// ...
};

Iterator GetIterator();

// --- Anwendung --------------------------------------------------------------
MyClass Obj;
for (MyClass::Iterator Itr = Obj.GetIterator(); Itr.HasMoreElements(); ++Itr)
{
	Itr->DoSomething();
}

4) Funktionale Programmierung.
Umsetzung im std::for_each() -Stil. Sehr praktisch, wenn schon fertige Funktionen oder Funktoren bereitstehen, ansonsten mangels Lambda-Ausdrücken nicht immer ideal. Aber grundsätzlich grösste Kapselung, weil sicher für alle Elemente die gleiche Aktion genau einmal durchgeführt wird (von einer Exception abgesehen) und man nie direkten Zugriff auf die Elemente erhält. Diese Einschränkung kann sich jedoch als Nachteil erweisen, wenn primär Lesezugriff und Informationsübermittlung nach aussen erwünscht ist.

// --- Schnittstelle ----------------------------------------------------------
template <typename Function>
void ForEach(Function Func);

// --- Anwendung --------------------------------------------------------------
void MyFunction(Element& CurrentElem);

MyClass Obj;
Obj.ForEach(MyFunction);

5) Zurückgeben des gesamten Containers als Const-Referenz.
Gefällt mir eigentlich überhaupt nicht, da man so viel Irrelevantes über den Container selbst erfährt. Auf die Elemente kann auch nur lesend zugegriffen werden. Das einzig Schöne an diesem Ansatz ist, dass er gut mit BOOST_FOREACH verwendet werden kann:

// --- Schnittstelle ----------------------------------------------------------
const Container& GetContainer() const;

// --- Anwendung --------------------------------------------------------------
MyClass Obj;
BOOST_FOREACH(const Element& Elem, Obj.GetContainer())
{
	Elem.DoSomething(); // DoSomething müsste const sein
}

Soviel dazu. Ich müsste Const-Correctness mit der Zeit noch genauer festlegen, aber das sollte kein grosses Problem darstellen. Welcher dieser Ansätze gefällt euch am besten? Oder habt ihr weitere Vorschläge?

Shade Of Mine

Nexus schrieb:

Welcher dieser Ansätze gefällt euch am besten? Oder habt ihr weitere Vorschläge?

algorithmen in c++ arbeiten auf ranges, also musst du ranges anbieten wenn du dich in die bestehenden algos einbinden lassen willst.

bleibt also nur 1 und 5. Ich nehme immer 1.

Nexus

Das stimmt zwar, aber ich brauche eigentlich keine Algorithmen im STL-Sinne. Das heisst, die Elemente sollen alle in ihrer Reihenfolge belassen werden (keine permutierenden Algorithmen wie sort() , remove_if() etc.). Erweiterte Funktionalität wie find() , replace() und solche Dinge sind fürs Erste ebenfalls nicht nötig und können bei Bedarf durch zusätzliche Memberfunktionen nachgerüstet werden.

Es geht mir vorerst wirklich nur um die Semantik, für alle Elemente eine bestimmte Operation durchzuführen, ohne den Container selbst zu modifizieren.

pumuckl

Eine Klasse, die zwar Iteratoren anbietet, aber nicht den vollen Umfang einer Containerschnittstelle liefert klingt mir genau nach der Zielgruppe von boost.range: http://www.boost.org/doc/libs/1_40_0/libs/range/doc/range.html
hab mich da allerdings noch nicht näher mit auseinandergesetzt.

knivil

Naja ... wie sehen denn die use cases aus? Wenn nur for_each gebraucht wird, dann halt sollte die for_each Sache auch nur angeboten werden.

mangels Lambda-Ausdrücken nicht immer ideal

Das ist kein Grund, nur eine schlechte Ausrede.

Warum willst du ueberhaupt einen Container kapseln, wenn die Klasse Funktionalitaeten eines Containers anbieten soll?

Shade Of Mine

Nexus schrieb:

Es geht mir vorerst wirklich nur um die Semantik, für alle Elemente eine bestimmte Operation durchzuführen, ohne den Container selbst zu modifizieren.

Naja, was du machst ist im Prinzip ein eigenes for_each() zu schreiben. Aber die C++ Library bietet dir ja ein for_each schon an. Wozu also das Rad neu erfinden?

Ranges oder iteratoren anbieten (nimmt sich nicht viel), weil du dann eben offen bist. Funktionalität als member funktion ist nur eine notlösung. gute schnittstellen bieten die funktionalität implizit an.

welchen vorteil bieten die lösungen 2-4 denn gegenüber der variante 1 oder einem range-objekt?

wenn es keine relevanten vorteile gibt, dann ist variante 1 die beste, weil es die standard variante ist.

Nexus

Danke für die Antworten.

pumuckl schrieb:

Eine Klasse, die zwar Iteratoren anbietet, aber nicht den vollen Umfang einer Containerschnittstelle liefert klingt mir genau nach der Zielgruppe von boost.range:

Das könnte vielleicht eine Möglichkeit sein. Aber so wie ich Ranges verstanden habe, geht es Hauptsächlich darum, einen neuen Blickwinkel auf Container zu geben - ich weiss nicht, ob der grösste Teil für meinen Fall nicht nur Overkill ist (ich benötige eben kein STL-kompatibles Iterator-Interface).

knivil schrieb:

Das ist kein Grund, nur eine schlechte Ausrede.

Wieso ist das Nichtvorhandensein von Lambda-Ausdrücken eine schlechte Ausrede? Wenn es eine schönere Möglichkeit gibt, möchte ich nicht unbedingt jedes Mal eine Extra-Funktion definieren. Zudem hat jener Ansatz wie erwähnt auch Probleme, falls man etwas auslesen will.

knivil schrieb:

Warum willst du ueberhaupt einen Container kapseln, wenn die Klasse Funktionalitaeten eines Containers anbieten soll?

Soll sie eben nicht (zumindest nur sehr eingeschränkte). Die Klasse hat nicht in erster Linie die Aufgabe, mehrere Elemente zu speichern und zu verwalten - das ergibt sich nur aus den Eigenschaften des Typs.

Shade Of Mine schrieb:

Naja, was du machst ist im Prinzip ein eigenes for_each() zu schreiben. Aber die C++ Library bietet dir ja ein for_each schon an. Wozu also das Rad neu erfinden?
[...]
welchen vorteil bieten die lösungen 2-4 denn gegenüber der variante 1 oder einem range-objekt?

Ich möchte eben die Schnittstelle möglichst stark einschränken. Man soll wirklich nicht mehr als For-Each-Semantik benutzen können, ich brauche hier keine Flexibilität. Bei Lösung 1 könnte man zwar std::for_each() direkt anwenden, aber eben auch noch einige andere Dinge. Zum Beispiel will ich verbieten, dass die Reihenfolge geändert oder sonst ein Algorithmus angewandt wird. Und um diese Funktionalität einzuschränken, habe ich eben an die Lösungen 2-4 gedacht.

Shade Of Mine schrieb:

Ranges oder iteratoren anbieten (nimmt sich nicht viel), weil du dann eben offen bist. Funktionalität als member funktion ist nur eine notlösung. gute schnittstellen bieten die funktionalität implizit an.

Meiner Ansicht nach ist diese Offenheit hier eher hinderlich. Ich würde gerne die Abhängigkeiten zur Klasse klein halten. Das geht besser, wenn man von aussen nicht zu viel über den Container weiss (eigentlich nicht einmal, dass überhaupt ein Container verwendet wird), sondern lediglich eine Schnittstelle zur Verfügung hat, um für mehrere Elemente etwas durchzuführen. Diese Schnittstelle muss ja nicht zwingend aus Iteratoren bestehen, nur weil das in C++ gängige Praxis ist. Zu den Abhängigkeiten: Es könnte ja mal sein, dass ich in Zukunft auf einen dynamischen Container als Member verzichte und die einzelnen Elemente jeweils neu berechne (aus welchem Grund auch immer). Mit einer Indirektion (Fälle 2-4) könnte ich die Schnittstelle trotz anderer Implementierung erhalten.

Ich will versuchen, einen vernünftigen Anwendungsfall zu beschreiben. Statt eines gekünstelten Beispiels nehme ich gleich einen Fall aus einem Projekt (einem Jump'n'Run-Spiel :)).
Also, ich habe zum Beispiel eine Klasse Lift , die bewegliche Plattformen darstellt. Um ihren Weg in der Welt festzulegen, besitzt die Plattform einen Container mit Koordinaten. Diese Koordinaten stehen für die Wegpunkte, also die Orte, die nacheinander passiert werden. Nun kommt es oft vor, dass ich von aussen etwas für alle Wegpunkte erledigen will. Beispielsweise möchte ich den Weg grafisch darstellen oder bei Spielbeginn prüfen, ob alle Wegpunkte gültig sind (nicht etwa ausserhalb der Welt). Momentan habe ich das eben noch über Ansatz 5 gelöst, aber ein gutes Gefühl habe ich dabei nicht. Mir wäre es lieber, den öffentlichen Zugriff auf das Durchiterieren zu beschränken.

Th69

Wenn du einen gekapselten Zugriff willst, dann würde ich den auch nutzen, d.h. du definierst dir einfach eine friend-Klasse, in der du dann deine Zugriffe auf den internen (privaten) Container ausführst (bzw. dessen (const_)iteratoren). So hast du den Zugriff nur in EINER externen Klasse und kannst ihn besser kontrollieren.

Nexus

In dieser ausgelagerten Klasse müsste ich mir aber trotzdem überlegen, was für eine Schnittstelle ich anbiete. Ich sehe auch den Sinn einer Aufteilung nicht ganz. Es scheint mir unproblematisch, gleich die Klasse anzusprechen, die den Container besitzt.

pumuckl

Hm. ich würd eine Schnittstelle anbieten, die ein Akkumulatorobjekt annimmt, da nacheinander die Elemente des containers reinstopft und dann den Akkumulator wieder zurückgibt. Der Akkumulator muss nur einen op() mit einem Element als argument haben. Beispiel:

struct Element { int i; };

class MyClass
{
  std::vector<Element> myvec;
public:
  template <class Acc>
  void allElems(Acc& acc)
  {
    BOOST_FOREACH(Element& e, myvec)
    {
      acc(e);
    }
  }
};

struct MaxAcc
{
  Element * pE;
  void operator(Element& e)
  {
     if (pE == 0 || e.i > pE->i) pE = &e;
  }
  MaxAcc() : pE (0) {}
}

struct ContainsZeroAcc
{
  bool hasZero;
  ContainsZeroAcc() : hasZero(false) {}

  void operator(Element& e)
  {
     if (e.i == 0) hasZero = true;
  }
}

Ich denk du siehst worauf ich hinauswill.

otze

was spricht gegen const_iterator? Dann hast du lesezugriff, aber niemand kann deine Elemente verändern.

Nexus

pumuckl schrieb:

Hm. ich würd eine Schnittstelle anbieten, die ein Akkumulatorobjekt annimmt, da nacheinander die Elemente des containers reinstopft und dann den Akkumulator wieder zurückgibt.

Das wäre dann eine ausgebaute Version von Punkt 4), bei der man auch Daten nach aussen transportieren kann. Sieht schonmal sehr gut aus, vielen Dank für den Vorschlag!

otze schrieb:

was spricht gegen const_iterator? Dann hast du lesezugriff, aber niemand kann deine Elemente verändern.

Teilweise will ich ja die Elemente verändern können. Mir gefällt hier einfach dieser standardmässige Iteratoransatz nicht besonders. Klar, das Iterator-Konzept ist eigentlich genial, besonders in Zusammenarbeit mit generischen STL-Algorithmen und solchen Sachen. Trotzdem scheinen mir hier andere Verfahren geeigneter.

Noch eine allgemeine Frage: Habt ihr schon jemals sowas Ähnliches wie bei Punkt 2) und 3), besonders 2) verwendet? Die Vorgehensweise dort weist zwar einige Probleme auf, aber grundsätzlich finde ich die Idee sehr interessant, besonders weil die Anwendung wahnsinnig simpel ist.

hustbaer

Nexus schrieb:

Noch eine allgemeine Frage: Habt ihr schon jemals sowas Ähnliches wie bei Punkt 2) und 3), besonders 2) verwendet? Die Vorgehensweise dort weist zwar einige Probleme auf, aber grundsätzlich finde ich die Idee sehr interessant, besonders weil die Anwendung wahnsinnig simpel ist.

Von 2) würde ich in jedem Fall die Finger lassen, da du dadurch zwei Dinge vermischt: das eigentliche Objekt, und den Enumerations-Status. Letzterer hat da drin nämlich nix verloren. Man kann sich damit z.B. schnell ins Knie schiessen, wenn an mehreren Stellen enumeriert wird. Wenn FunktionA() enumeriert, mitten drin FunktionB() aufruft, die wieder enumertiert -> Chaos perfekt.

Was du als Wrapper-Iterator bezeichnest (3), würde ich Enumerator nennen. Siehe .NET Framework und Java Standard-Library. Grundsätzlich OK, wenn auch etwas unüblich in C++.

Nexus

hustbaer schrieb:

Von 2) würde ich in jedem Fall die Finger lassen, da du dadurch zwei Dinge vermischt: das eigentliche Objekt, und den Enumerations-Status. Letzterer hat da drin nämlich nix verloren. Man kann sich damit z.B. schnell ins Knie schiessen, wenn an mehreren Stellen enumeriert wird. Wenn FunktionA() enumeriert, mitten drin FunktionB() aufruft, die wieder enumertiert -> Chaos perfekt.

Genau, das hab ich dort ja noch hingeschrieben. Hmm, es ist wohl tatsächlich klüger, wenn ich da nichts für eine etwas schönere Anwendung riskiere. Es gibt ja schliesslich immer noch Makros...

hustbaer schrieb:

Was du als Wrapper-Iterator bezeichnest (3), würde ich Enumerator nennen. Siehe .NET Framework und Java Standard-Library. Grundsätzlich OK, wenn auch etwas unüblich in C++.

Okay. Vielen Dank für die Anmerkungen!

hustbaer

Nexus schrieb:

hustbaer schrieb:

Von 2) würde ich in jedem Fall die Finger lassen, da du dadurch zwei Dinge vermischt: das eigentliche Objekt, und den Enumerations-Status. Letzterer hat da drin nämlich nix verloren. Man kann sich damit z.B. schnell ins Knie schiessen, wenn an mehreren Stellen enumeriert wird. Wenn FunktionA() enumeriert, mitten drin FunktionB() aufruft, die wieder enumertiert -> Chaos perfekt.

Genau, das hab ich dort ja noch hingeschrieben.

Oops, ja, hab ich überlesen.

Hmm, es ist wohl tatsächlich klüger, wenn ich da nichts für eine etwas schönere Anwendung riskiere. Es gibt ja schliesslich immer noch Makros...

AAAAH!
Wo willst du da Makros einsetzen? Und wieso?

Shade Of Mine

Nexus schrieb:

Diese Schnittstelle muss ja nicht zwingend aus Iteratoren bestehen, nur weil das in C++ gängige Praxis ist. Zu den Abhängigkeiten: Es könnte ja mal sein, dass ich in Zukunft auf einen dynamischen Container als Member verzichte und die einzelnen Elemente jeweils neu berechne (aus welchem Grund auch immer). Mit einer Indirektion (Fälle 2-4) könnte ich die Schnittstelle trotz anderer Implementierung erhalten.

Iteratoren würden dir diese flexibilität ebenfalls lassen.

Es gibt auch keine Abhängigkeiten oder sonstwas.

Ich sehe immer noch keinen Grund gegen Iteratoren/Ranges.

Nexus

hustbaer schrieb:

AAAAH!
Wo willst du da Makros einsetzen? Und wieso?

Habe ich nicht wirklich vor, der Satz war nicht allzu ernst gemeint...

Shade Of Mine schrieb:

Iteratoren würden dir diese flexibilität ebenfalls lassen.
[...]
Ich sehe immer noch keinen Grund gegen Iteratoren/Ranges.

Und ich sehe keinen Grund gegen einen alternativen Ansatz.
Wieso sollte man immer den 0815-Weg wählen? Iteratoren sind in C++ die Standardvorgehensweise fürs Iterieren, aber weshalb engstirnig darauf beharren, wenn bessere Alternativen offen stehen? Was mir an den Iteratoren nicht passt, habe ich ja bereits mehrfach erklärt. Wenn ich direkte Iteratoren in den Container habe, kann ich damit Dinge anstellen, die nicht gewollt sind. Eine Indirektion über Ranges scheint mir etwas kompliziert und vor allem unnötig, da ich einfachere Möglichkeiten sehe, die mir genauso gut oder sogar besser liefern, was ich will. Sind das schlechte Gründe? Falls bei Nicht-Iterator-Ansätzen nur die Flexibilität fehlt, ist das genau das, was ich erreichen möchte.

Was spricht zum Beispiel gegen pumuckls Lösung? Sie ist wohl nicht der Weisheit letzter Schluss, aber für meinen Fall ziemlich ideal. Das einzige, was eventuell ein Nachteil sein könnte, ist eine Extra-Funktion zu schreiben. Aber besonders wenn man viele Aktionen durchführen möchte, bietet sich das sowieso an, und so tragisch ist das wirklich nicht.

Shade Of Mine schrieb:

Es gibt auch keine Abhängigkeiten oder sonstwas.

Mit direkten Iteratoren schon, ich habe ja oben einen solchen Fall beschrieben. Oder inwiefern bist du damit nicht einverstanden? Möglicherweise kann dieses Problem mit einer Range-Abstraktion umgangen werden, aber ich stelle mir das nicht besonders schön vor, wenn kein Container vorhanden ist. Da ich jetzt eine funktionierende und elegante Lösung habe, würde mich trotzdem noch interessieren, was an Iteratoren/Ranges von Vorteil wäre. Wie gesagt: Ich will lediglich für alle Elemente etwas tun, und alles Weitere möglichst vermeiden.

drakon

Da ich jetzt eine funktionierende und elegante Lösung habe, würde mich trotzdem noch interessieren, was an Iteratoren/Ranges von Vorteil wäre. Wie gesagt: Ich will lediglich für alle Elemente etwas tun, und alles Weitere möglichst vermeiden.

Der klare Vorteil von Iteratoren ist ja, dass so beliebige Algorithmen bauen kann, welche auf diesen Iteratoren arbeitet und somit sonst nix von der Klasse sonst wissen muss.
Wenn du das jetzt aber nicht willst/brauchst, oder lediglich ein Subset davon brauchst, dann müsste man es imo nicht wirklich mit Iteratoren machen.

pumuckl

Nexus schrieb:

Wenn ich direkte Iteratoren in den Container habe, kann ich damit Dinge anstellen, die nicht gewollt sind.

Welche zum Beispiel? Du musst ja nicht direkt den RandomAcess-Iterator des std::vector rauslassen sondern könntest stattdessen einen reinen Forward-Iterator anbieten.

Nexus

drakon schrieb:

Wenn du das jetzt aber nicht willst/brauchst, oder lediglich ein Subset davon brauchst, dann müsste man es imo nicht wirklich mit Iteratoren machen.

Danke.

pumuckl schrieb:

Welche zum Beispiel? Du musst ja nicht direkt den RandomAcess-Iterator des std::vector rauslassen sondern könntest stattdessen einen reinen Forward-Iterator anbieten.

Dann müsste ich wieder einen Iterator wrappen, das geht dann in Richtung Ansatz 3), nur halt C++-Style. Du hast Recht, viel Schlimmes kann man damit nicht mehr anstellen, bzw. müsste man das fast mutwillig tun.

Hm... Ich muss mal eine Entscheidung treffen. Vorerst werde ich wahrscheinlich den Funktor-Ansatz verfolgen und schauen, ob er sich auf Dauer bewährt. Mit Iteratoren habe ich schon oft experimentiert, deshalb wäre es auch interessant, mal was Neues auszuprobieren. Es muss sowieso einiges an Code angepasst werden. Später kann ich das immer noch überdenken, sollten sich gewisse Schwierigkeiten erst dort zeigen. Nochmals danke an alle für die Beiträge!