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

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.

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.

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).

otze

hustbaer schrieb:

@otze ...

Ja, das war in meiner Anwendung nicht gefordert. Das Ding wird in einem Adapter eingesetzt, der selbst natürlich eine konstante Struktur hat. Aber guter Hinweis, sollte ich vielleicht in die Dokumentation packen, dass er bei Änderungen des zugrunde liegenden Containers invalidiert wird.

SeppJ schrieb:

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

Direkt nicht, aber was wäre denn mit einem indirekten Vergleich?

SeppJ

aöfasföefi schrieb:

SeppJ schrieb:

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

Direkt nicht, aber was wäre denn mit einem indirekten Vergleich?

Was meinst du damit?

Meep Meep

was waere wenn du dir einen leeren container erstellst, der immer am ende deine container-chain angehaengt ist ? dann brauechtest du nur vergleichen ob der iterator in dem container gelandet ist. wenn das der fall is, dann bist am ende.

Meep Meep

SeppJ

Meep Meep schrieb:

was waere wenn du dir einen leeren container erstellst, der immer am ende deine container-chain angehaengt ist ? dann brauechtest du nur vergleichen ob der iterator in dem container gelandet ist. wenn das der fall is, dann bist am ende.

Das ist konzeptionell ein Ende-Flag mit unnötigen Zusatzkosten. Außerdem ist ein Iterator übel, der die zugrundeliegende Sequenz ändert.

Ich sollte den Thread mal auf gelöst setzen. Ich war schon auf Seite 2 mit den Lösungen 100% zufrieden.

Shade Of Mine

SeppJ schrieb:

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

Geht nicht auch mit cont_it==cont_end als end definition folgendes:

MultiContainerIterator(ContainerIteratorType first, ContainerIteratorType last)
: cont_it(first), cont_end(last)
, val_it(first!=last?first->begin():ValueIteratorType())
{ next(); }

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

void next() {
    while ( cont_it != cont_end && val_it == cont_it->end() ) {
    	if(++cont_it != cont_end) val_it=cont_it->begin();
}

end iterator ist hier natürlich MultiContainerIterator(data.end(), data.end())