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

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

SeppJ

Wenn du Zeile 7 zu

return (cont_it == it.cont_it && ( cont_it==cont_end || val_it == it.val_it));

änderst, dann passt es.

Sieht jetzt für mich auf den ersten Blick so aus wie eine korrigierte Variante meines fehlerhaften Vorschlags von Seite 1 unten. Ich muss mal meditieren, was die Vor- und Nachteile wären.

Shade Of Mine

SeppJ schrieb:

Wenn du Zeile 7 zu
return (cont_it == it.cont_it && ( cont_it==cont_end || val_it == it.val_it));
änderst, dann passt es.

Ja, korrekt.

Sieht jetzt für mich auf den ersten Blick so aus wie eine korrigierte Variante meines fehlerhaften Vorschlags von Seite 1 unten. Ich muss mal meditieren, was die Vor- und Nachteile wären.

prinzipiell ja.

ich wollte damit eigentlich nur den static end iterator wegbekommen. sonst ist alles gleich - wenn es ein end iterator ist, wird val_it nicht mehr beachtet.

hustbaer

SeppJ schrieb:

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

BTW: nimm char oder int als Flag. Ein bool == Vergleich könnte u.U. teurer sein.