Eigener Iterator auf STL-Basis: Wie Ende markieren? [gelöst]

[SeppJ]

Ich brauche einen Iterator, der über eine Reihe von gleichartigen Containern iterieren kann. Den habe ich mir einfach geschrieben, indem ich über die Iteratoren der Einzelcontainer iteriere und bei Erreichen des Endes zum nächsten Container springe. Nun das Problem: Um diesen Iterator sinnvoll in einem Container zu benutzen, muss es irgendeinen vergleichbaren Wert für das Ende geben. Dazu benutze ich derzeit einen Default-konstruierten Wert des unterliegenden STL(oder woher auch immer)-Iterators. Das funktioniert auch praktisch ganz wunderbar, aber theoretisch gibt es ein Problem: Man darf solch einen Iterator nicht mit einem Iterator aus einem anderen Container vergleichen. Das Ende des letzten Containers zu nehmen wäre auch keine Lösung, da man auch nicht Iteratoren aus unterschiedlichen Containern vergleichen darf.

Wie kann ich sinnvoll und standardkonform einen end()-Wert festlegen? Und das noch möglichst ohne Overhead, dieser Iterator steht später in einer kritischen Schleife!

Wer jetzt einwendet, dass das praktisch ja auch so funktioniert (tut es auch): Es funktioniert nicht mehr beim Debuggen mit den STL-Checks des GCC. Da fliegt knallhart eine Assertion, da man einen dereferenceable Iterator mit einem singular Iterator vergleicht. Und das ist ja auch korrekt so. Das dumme ist bloß, dass man dann den Rest des Programms nicht mehr Debuggen kann, wenn es schon an solch einer Kleinigkeit sofort abbricht.

Hier der Code:

#include <iterator>

template <typename ContainerIteratorType, typename ValueIteratorType> 
class MultiContainerIterator
{
  typedef typename std::iterator_traits<ValueIteratorType>::value_type ValueType;
  typedef MultiContainerIterator<ContainerIteratorType, ValueIteratorType> Self;

  ContainerIteratorType cont_it, cont_end;  // Liste der Container
  ValueIteratorType val_it,    // Position im derzeitigen Container 
    val_end;   // Ende des derzeitigen Containers

  static const ValueIteratorType end_iterator;  // WAS NEHMEN?

 public:
  MultiContainerIterator(): val_it(end_iterator) {} // Gibt einen Endwert.

  MultiContainerIterator(ContainerIteratorType begin, ContainerIteratorType end):
    cont_it(begin), cont_end(end), val_it(begin->begin()), val_end(begin->end()) 
    { next(); }

  Self &operator++() 
  {
    ++val_it;
    next();
    return *this;
  }

  const ValueType& operator*() const { return *val_it; }
  const ValueType* operator->() const { return &*val_it; }

  bool operator== (const Self& it) const { return (val_it == it.val_it); } // PROBLEM
  bool operator!= (const Self& it) const { return (val_it != it.val_it); } // PROBLEM

 private:
  void next() // Prüft, ob der val_it auf etwas gültiges zeigt, setzt ihn ggf. weiter.
  {
    while (val_it == val_end) // Am Containerende (oder Container war leer)
      {
        ++cont_it; // Nächster Container
        if (cont_it == cont_end)  // Das war schon der letzte Container: Wir sind am Ende
          {
            val_it = end_iterator; // WAS HIER ZURÜCK GEBEN?
            break;
          }
        val_it = cont_it->begin();
        val_end = cont_it -> end();
      }
  }
};

template <typename ContainerIteratorType, typename ValueIteratorType> 
const ValueIteratorType 
MultiContainerIterator<ContainerIteratorType, ValueIteratorType>::end_iterator
= ValueIteratorType();  // WELCHEN WERT HIER NEHMEN

// #### Begin des Beispiels. Ja, das Beispiel ist sinnlos. #####

#include <list>
#include <vector>
#include <iostream>
using namespace std;
class ExampleMultiContainer
{
  vector<list<int> > data;
public:
  ExampleMultiContainer()
  {
    list<int> insert;
    insert.assign(1,4);
    data.push_back(insert);
    insert.assign(3,6);
    data.push_back(insert);
    insert.assign(2,3);
    data.push_back(insert);
  }
  typedef MultiContainerIterator<vector<list<int> >::iterator, list<int>::iterator> iterator;

  iterator begin() { return iterator(data.begin(), data.end()); }
  iterator end() { return iterator(); }
};

int main()
{
  ExampleMultiContainer foo;
  for (ExampleMultiContainer::iterator it = foo.begin(), end=foo.end();
       it != end;   // HIER DER FEHLER
       ++it)
    cout << *it << '\n';
}

[camper]

SeppJ schrieb:

as Ende des letzten Containers zu nehmen wäre auch keine Lösung, da man auch nicht Iteratoren aus unterschiedlichen Containern vergleichen darf.

Ist mir neu, hast du eine Referenz? Selbst wenn das so ist, stellt es kein Problem dar; dann musst du ja sowieso erst einmal schauen, ob die beiden Iteratoren in den gleichen Container zeigen.
ContainerIteratorType sollte dann nach Möglichkeit mindestens bidirektional sein, damit der letzte Container schnelle gefunden werden kann.

Eine gute Lösung ür den Fall einer leeren Containersequenzt habe ich allerdings auch nicht, evtl. kann man das ja auscchließen, wenn es praktisch nicht gebraucht werden sollte.

[SeppJ]

camper schrieb:

]Ist mir neu, hast du eine Referenz?

Ich weiß gerade nicht, ob es schon in C++98 ist, aber C++11 ist recht eindeutig:

24.2.1,6 schrieb:

An iterator j is called reachable from an iterator i if and only if there is a finite sequence of applications of
the expression ++i that makes i == j. If j is reachable from i, they refer to elements of the same sequence.

24.2.5,2 schrieb:

The domain of == for forward iterators is that of iterators over the same underlying sequence.

Der GCC meckert auch rum, wenn man es versucht.

Selbst wenn das so ist, stellt es kein Problem dar; dann musst du ja sowieso erst einmal schauen, ob die beiden Iteratoren in den gleichen Container zeigen.

Das wäre dann der erwähnte Overhead .

camper schrieb:

Eine gute Lösung ür den Fall einer leeren Containersequenzt habe ich allerdings auch nicht, evtl. kann man das ja auscchließen, wenn es praktisch nicht gebraucht werden sollte.

Die Container können zwar alle leer sein, aber die Sequenz per Konstruktion nicht. Das könnte ich also ausnutzen. Ihh, ich sehe gerade, das wird ekelig vom Design. Aber zur Not gangbar.

[Shade Of Mine]

Wäre es nicht möglich zu sagen, der iterator ist dann ein end iterator wenn cont_it==cont_end ?

[knivil]

Ich brauche einen Iterator, der über eine Reihe von gleichartigen Containern iterieren kann.

Korrigiere mich, wenn ich falsch liege, aber meinst du nicht eher: Du hast eine Menge A von Mengen B_i und moechtest ueber die Elemente aller B_i normal iterieren und den Benutzer vom Umweg ueber A entlasten? Ich wuerde es wie ein Tachometer implementieren und beim Hochzaehlen nicht wie jetzt mit einem allgemeinen Enditerator vergleichen, sondern mit dem konkreten des aktuellen B_i.

Zeite Auffaelligkeit: Warum ValueIteratorType fuer Menge B_i? Kann der Typ nicht vom Elementtyp des Containers A abgeleitet werden?

[SeppJ]

knivil schrieb:

Ich brauche einen Iterator, der über eine Reihe von gleichartigen Containern iterieren kann.

Korrigiere mich, wenn ich falsch liege, aber meinst du nicht eher: Du hast eine Menge A von Mengen B_i und moechtest ueber die Elemente aller B_i normal iterieren und den Benutzer vom Umweg ueber A entlasten?

Ja. Entschuldigung für die Unklarheit.

Shade Of Mine schrieb:

Wäre es nicht möglich zu sagen, der iterator ist dann ein end iterator wenn cont_it==cont_end ?

So ist es. Das stellt die next()-Methode auch fest. Das Problem ist, wie man diese Feststellung nach außen trägt. Irgendwo will ich ja it != end schreiben, aber was ist end?

[knivil]

end ist das Ende des letzten Containers. Konkret A.last().end() . Leider abstrahierst du auf Iteratorbasis und laesst den Container voellig ausser acht. Werden waehrend des Iterationsprozess neue Container angefuegt bzw. einem B_i Elemente hinzugefuegt, dann muss er bei jedem Vergleich neu berechnet werden indem mittels ++ ans Ende des Containers A mittels deines Iterators gegangen wird. Das ist fuer die Anforderung "dieser Iterator steht später in einer kritischen Schleife" vielleicht hinderlich. Ein spezieller Iterator fuer die konkrete Datenstruktur ist da wahrscheinlich der bessere Weg.

Und: Denke bitte an die Leute, die deinen Code pflegen muessen. Ich wuerde bestimmt nicht erfreut sein ... wobei das Ding da oben noch geht.

[performer]

Wozu überabstrahieren? Ein Makro tuts auch.

#define DEEP_FOREACH(elem, cont)               \
  for (auto& _deep_foreach_##elem##_ : cont)   \
    for (auto& elem : _deep_foreach_##elem##_)

[SeppJ]

knivil schrieb:

end ist das Ende des letzten Containers. Werden waehrend des Iterationsprozess neue Container angefuegt bzw. einem B_i hinzugefuegt, dann muss er bei jedem Vergleich neu berechnet werden. Das ist fuer die Anforderung "dieser Iterator steht später in einer kritischen Schleife" vielleicht hinderlich.

Das wäre nicht das Problem, das kann ich als Programmierer optimieren, da ich weiß, dass in der Schleife nichts neues hinzu kommt und mir daher vorher den end-Wert merken kann (so wie bei meinem Beispiel)

Ein spezieller Iterator fuer die konkrete Datenstruktur ist da wahrscheinlich der bessere Weg. Konkret A.last().end() .

Dann hätte man den Vergleich von Iteratoren aus unterschiedlichen Sequenzen und das wäre auch ungültig.

Bevor noch jemand anderes drauf kommt: Auch folgendes geht nicht:
MultiContainerIterator(ContainerIteratorType end): cont_it(end) {}

[...]

 bool operator== (const Self& it) const { return (cont_it == it.cont_it && val_it == it.val_it); } 

 [...]

 if (cont_it == cont_end)
   {
      val_it = ValueIteratorType();
       break;
    }

(In Worten: Erst Containeriteratoren vergleichen, dann ggf. Valueiteratoren vergleichen)

Dann würde man nämlich am Ende zwei singuläre Iteratoren vergleichen, was auch ungültig ist.

[SeppJ]

performer schrieb:

Wozu überabstrahieren? Ein Makro tuts auch.

#define DEEP_FOREACH(elem, cont)               \
  for (auto& _deep_foreach_##elem##_ : cont)   \
    for (auto& elem : _deep_foreach_##elem##_)

Weil Abstraktion etwas Gutes ist. Der Code wird mehrmals für verschiedenartige Container benutzt, daher der hohe Abstraktionsgrad. Auf Nutzerebene dürfen nur noch der Gesamtcontainer und seine Iteratoren bekannt sein, so wie in dem gezeigten Beispiel. Implementierungsdetails haben da nichts zu suchen.

[knivil]

Ok, was ist mit einem einfachen Flag "ich bin am Ende". Jeder Iteratorvergleich prueft dann erstmal diese Flags? Jaja, ein Quickhack.

[SeppJ]

knivil schrieb:

Ok, was ist mit einem einfachen Flag "ich bin am Ende". Jeder Iteratorvergleich prueft dann erstmal diese Flags? Jaja, ein Quickhack.

Ja, das wäre möglich.

Während du schriebst, hatte ich jedoch eine ganz ähnliche Idee, die zwar vom Design her nicht so allgemein ist, aber einen Hauch weniger Laufzeitkosten haben sollte. Dies nutzt aus, dass ich weiß, dass die Containersequenz nicht leer ist:

template <typename ContainerIteratorType, typename ValueIteratorType> 
class MultiContainerIterator
{
 public:
  MultiContainerIterator(ContainerIteratorType end):
    cont_it(end), val_it((end-1)->end()) {}  // Der Endwert: Ende der Containersequenz, Ende der Valuesequenz des vorletzten Containers

  bool operator== (const Self& it) const { return (cont_it == it.cont_it && val_it == it.val_it); } // Dank short-circuit nicht sehr teuer

  void next()
  {
    while (val_it == val_end) 
      {
        ++cont_it; 
        if (cont_it == cont_end)
          {
            // Hier einfach nichts tun. Dadurch:
            // cont_it zeigt nun auf Ende der Containersequenz -> gültiger Iterator
            // value_it zeigt auf Ende des vorletzten Containers -> gültiger Iterator
            break;
          }
        val_it = cont_it->begin();
        val_end = cont_it -> end();
      }
  }
};

[...]

  iterator end() { return iterator(data.end()); } // Endwert ist nun von der Sequenz abhängig

Dies ist zwar nicht befriedigend, aber eine Lösung.

[performer]

SeppJ schrieb:

performer schrieb:

Wozu überabstrahieren? Ein Makro tuts auch.

Weil Abstraktion etwas Gutes ist. Der Code wird mehrmals für verschiedenartige Container benutzt, daher der hohe Abstraktionsgrad.

Bei Bibliotheken gebe ich dir recht, aber bei Anwendungscode, insbesondere bei performancekritischen Stellen setze ich die Latte niedriger.

Wenn an einer Stelle Performanz entscheidend ist, dann verzichte halt dort auf die Abstraktion und iteriere mit einem Makro. Aber ich seh schon, das willst du nicht.

dieser Iterator steht später in einer kritischen Schleife [...] Es funktioniert nicht mehr beim Debuggen mit den STL-Checks des GCC.

Dann mach bedingte Kompilierung. Nimm die langsame Lösung, wo zuerst der Container verglichen wird, dann der Iterator wenn ein bestimmtes Debug-Makro aktiviert ist. Wenn Speed ausdrücklich gewünscht (ifdef PERFORM_UNSAFE_HACKS), dann schnelle.

[SeppJ]

performer schrieb:

SeppJ schrieb:

performer schrieb:

Wozu überabstrahieren? Ein Makro tuts auch.

Weil Abstraktion etwas Gutes ist. Der Code wird mehrmals für verschiedenartige Container benutzt, daher der hohe Abstraktionsgrad.

Bei Bibliotheken gebe ich dir recht, aber bei Anwendungscode, insbesondere bei performancekritischen Stellen setze ich die Latte niedriger.

Es ist eine Bibliothek die ich schreibe :p

Dann mach bedingte Kompilierung. Nimm die langsame Lösung, wo zuerst der Container verglichen wird, dann der Iterator wenn ein bestimmtes Debug-Makro aktiviert ist. Wenn Speed ausdrücklich gewünscht (ifdef PERFORM_UNSAFE_HACKS), dann schnelle.

Das ist eine gute Idee! Das mache ich. Das ich darauf nicht gekommen bin *stirnklatsch*!

Dann kann ich auch das Ende-Flag benutzen. Das ist wesentlich einfacher zu verstehen als meine obige "Lösung", aber wenn es nur beim Debuggen benutzt wird, ist der Performanceverlust egal.

[hustbaer]

SeppJ schrieb:

Dann kann ich auch das Ende-Flag benutzen. Das ist wesentlich einfacher zu verstehen als meine obige "Lösung", aber wenn es nur beim Debuggen benutzt wird, ist der Performanceverlust egal.

Naja, wenn man davon ausgeht dass die allermeisten Vergleiche zwischen "end" und "nicht end" Iteratoren gemacht werden, dann wäre das vielleicht ne akzeptable Lösung:

bool operator== (const Self& it) const
{
    if (is_end != it.is_end)
        return false; // fast path for common case
    else if (!is_end) // 2x "nicht ende"
        return cont_it == it.cont_it && val_it == it.val_it;
    else // 2x ende
        return true;
}

Und...
Den "cont_it" Vergleich brauchst du ja sowieso, auch in der schnellen Version, da ein Iterator sich in seinem operator == ja darauf verlassen könnte dass sein "Vergleichspartner" aus dem selben Container stammt. Und dann u.U. false positives produzieren wenn es nicht so ist.

Stell dir z.B. nen Hashtable vor - der Iterator könnte einfach nen Zeiger auf den Table + den Bucket-Index enthalten. Der operator == müsste aber nur den Bucket-Index vergleichen, denn der Table muss ja der gleiche sein. Und den selben Bucket Index wird man in vielen "fremden" Iteratoren finden.

Und da die "End Flag" Version im "common case" sogar weniger macht als die "Vergleiche Container, dann Iterator" Version, würde ich behaupten (*aus dem Fenster lehn*): das ist deine ideale Lösung, für mit oder ohne Debug.

[otze]

Hmm. ich habe gerade nachgeschaut, wie das bei meinem MultiSequenceIterator ist.

stellt sich heraus, dass ich nebenbei einen Index gezählt hatte, weil ich noch eine index()-Methode brauchte (position des elementes im Container). Aber vielleicht interessiert es ja, ich schneide aber mal alles hier direkt irrelevante aus boost.iterator raus und bastel ihn auf einen reinen forward iterator um.

struct MultiSequenceIterator: ...{
private:
	typedef ... outer_iterator;
	typedef ... inner_iterator;
public:

	MultiSequenceIterator(
		outer_iterator outerPosition,
        outer_iterator outerEnd,
		inner_iterator innerPosition,
		std::size_t positionInSequence 
	):m_outerPosition(outerPosition),
        m_innerPosition(innerPosition),
        m_outerEnd(outerEnd),
        m_positionInSequence(positionInSequence){
		//we can't dereference if we are past the end...
		if(m_outerPosition != m_outerEnd){
			m_innerEnd = boost::end(*m_outerPosition);
		}

	}
private:
//...

	void increment() {
		++m_positionInSequence;
		++m_innerPosition;
		if(m_innerPosition == m_innerEnd){
			++m_outerPosition;
			if (m_outerPosition != m_outerEnd){
				m_innerPosition = boost::begin(*m_outerPosition);
				m_innerEnd = boost::end(*m_outerPosition);
			}
		}
	}
//...	

	template<class Iter>
	bool equal(Iter const& other) const{
		return (m_positionInSequence == other.m_positionInSequence);
	}
	typename Traits::reference dereference() const { 
		return *m_innerPosition;
	}

	outer_iterator m_outerPosition;
	outer_iterator m_outerEnd;

	inner_iterator m_innerPosition;
	inner_iterator m_innerEnd;

	std::size_t m_positionInSequence;
};

mein op== ist unschlagbar schnell(und unsicher). ich habe etwas kosten im op++ da ich jedes mal einen index inkrementiere. Das echte Problem ist aber, dass end() die Größe des Containers kennen muss. zumindest bei meiner Anwendung war das aber kein Problem, da die Anzahl der inneren Container klein ist und ich mir das einmalige Iterieren darüber leisten kann.

[hustbaer]

@otze
Was ist wenn ich deinen MultiSequenceIterator mit einer Liste füttere in der drei Elemente drin sind. Den so erstellten MultiSequenceIterator kopiere ich mir dann erstmal, so dass ich zwei Kopien "a" und "b" habe.

Dann splue ich "a" um 2 Elemente vor so dass a auf's letzte Element zeigt
Jetzt lösche ich das mittlere Element der Liste.
Und dann spule ich "b" um 1 Element vor, so dass auch "b" auf das letzte Element zeigt.

Und jetzt ist a != b. Auch doof. Weil stimmt ja nicht.

[camper]

Spricht etwas dagegen, statisch einen leeren Container anzulegen und dessen iterator zu verwenden? Bei den meisten Container kostet das ja nichts.
Für std::array könnte man spezialisieren und gleich einen Zeiger statt eines Iterators verwenden (und Nullzeiger fürs Ende).

ungefähr

template <typename ContainerIteratorType>
class MultiContainerIterator
{
  typedef typename std::iterator_traits<ContainerIteratorType>::value_type container_type;
  typedef typename container_type::iterator ValueIteratorType;
  typedef typename container_type::value_type ValueType;
  typedef MultiContainerIterator Self;

  ContainerIteratorType cont_it, cont_end;
  ValueIteratorType val_it;

  static container_type end_container = {};
  static const ValueIteratorType end_iterator = end_container.end();

 public:
  MultiContainerIterator(ContainerIteratorType first, ContainerIteratorType last):
    cont_it(first), cont_end(last), val_it(first!=last?first->begin():end_iterator)
    { next(); }
...
  bool operator== (const Self& it) const { return cont_it == it.cont_it && val_it == it.val_it; }
...
  void next()
  {
    while ( cont_it != cont_end && val_it == cont_it->end() )
        val_it = ++cont_it != cont_end ? cont_it->begin() : end_iterator;
  } 
};

template <typename ContainerIteratorType>
typename std::iterator_traits<ContainerIteratorType>::value_type MultiContainerIterator<ContainerIteratorType>::end_container;

template <typename ContainerIteratorType>
const typename std::iterator_traits<ContainerIteratorType>::iterator MultiContainerIterator<ContainerIteratorType>::end_iterator;

[dot]

Wäre es nicht möglich, die Container einfach zu einem großen Container zu mergen und über diesen zu iterieren, anstatt solche...Konstrukte...zu erschaffen? Im Falle einer list wär das sogar praktisch kostenlos...

[SeppJ]

dot schrieb:

Wäre es nicht möglich, die Container einfach zu einem großen Container zu mergen und über diesen zu iterieren, anstatt solche...Konstrukte...zu erschaffen? Im Falle einer list wär das sogar praktisch kostenlos...

Nein. Viel zu teuer. Die Templatemonster hier sehen zwar schlimm aus, aber kosten nicht (merklich) mehr als man mit der naiven Doppelschleife hätte. Und wenn man es einmal hat, ist es dank der hohen Abstraktion absolut universell einsetzbar. All diese Vorteile sind an der Stelle an der ich es brauche extrem wichtig, das ist ja gerade das schöne an C++. In C wäre das überhaupt gar nicht laufzeitkostenlos mit diesem Wiederverwendungsgrad möglich gewesen.

Das Problem ist nun übrigens im Prinzip gelöst, der statische Container ist auch nicht konzeptionell anders als das Ende-Flag. Derzeit steht dieses noch nur in bedingter Compilierung, wenn ich mal Zeit habe prüfe ich hustbaers Vorhersage, dass das Flag gleichschnell wie der ursprüngliche Direktvergleich sein könnte (ich bin noch leicht skeptisch, wegen der erhöhten Code-Komplexität).