Iterator Frage: Container Abstrahieren

[Michael E.]

Args, hab mich davon ablenken lassen, dass du sagtest, du bräuchtest Polymorphie. Brauchst du aber gar nicht. So was hier langt:

template<class ContainerT>
struct Interface
{
	virtual typename ContainerT::const_iterator getBegin() const = 0;
};

// Foo ist eine Klasse, die das Interface implementiert, in diesem Fall mit vector
struct Foo : public Interface<vector<StaticVoc> >
{
	virtual vector<StaticVoc>::const_iterator getBegin() const
	{
		...
	}
};

[Michael E.]

David_pb schrieb:

Michael E. schrieb:

Wie wärs hiermit?

template<class T, template<typename ElemT, typename = std::allocator<ElemT> > class ContainerT = vector>
struct Container : public ContainerT<T>
{
	typedef typename ContainerT<T>::iterator iterator;

	iterator getBegin() const
	{
		...
	}
};

Sicher dass das funktioniert?

Ja. In welchem Sinne?

Im übrigen ist es grundlegend kein guter Gedanke von einem STL Kontainer abzuleiten.

Kann sein, sowas vergess ich immer. Begründung?

[David_pb]

Ein nicht virtueller Destruktor der STL Kontainerklassen!

[Michael E.]

David_pb schrieb:

Ein nicht virtueller Destruktor der STL Kontainerklassen!

Solang ich keine Membervariablen anleg, gehts.

[sapiens.dyslexia]

Michael E. schrieb:

Args, hab mich davon ablenken lassen, dass du sagtest, du bräuchtest Polymorphie. Brauchst du aber gar nicht. So was hier langt:

template<class ContainerT>
struct Interface
{
	virtual typename ContainerT::const_iterator getBegin() const = 0;
};

// Foo ist eine Klasse, die das Interface implementiert, in diesem Fall mit vector
struct Foo : public Interface<vector<StaticVoc> >
{
	virtual vector<StaticVoc>::const_iterator getBegin() const
	{
		...
	}
};

Hmm, I don't get it.

Die Interfaceklasse soll doch gerade den den Container verstecken.
Ich kann:

Interface* interface = new Foo;

Nicht schreiben da ich den Container als Templateargument mit angeben muss.

Eigentlich bräuchte ich einen Iterator, von dem alle STL Iteratoren erben um sowas:

inline void print_static_voc(StaticVoc v){std::cout << v.first() << std::endl;}

void ListAll(AbstractIterator it) {
	std::for_each(it.begin(),it.end(),print_static_voc());
}

schreiben zu können. So bräuchte (Polymorphie halt) erst zur LAUFZEIT klar sein, was für einen Container ich verwende...

Ich meine, die Methoden "begin()", "end()" sind doch im Prinzip bei allen Containern gleich anwendbar und "operator++", "operator--" und "operator*" auch!

Kann man von Containertyp nicht irgendwie OHNE explizit anzugebende Templates abstrahieren?

IMHO sollte das doch aufgrund des gleichen verhaltens durchaus möglich sein?

Gruß

[sapiens.dyslexia]

Tschuldigung.. ich kann nicht editieren:

EDIT:

inline void print_static_voc(cosnt StaticVoc& v){std::cout << v.first() << std::endl;}

void ListAll(AbstractIterator* it) {
    std::for_each(it->begin(),it->end(),print_static_voc());
}

[Z2]

sapiens.dyslexia schrieb:

Kann man von Containertyp nicht irgendwie OHNE explizit anzugebende Templates abstrahieren?

IMHO sollte das doch aufgrund des gleichen verhaltens durchaus möglich sein?

Nein, kann mann nicht. Das ist nicht möglich. Macht auch überhaupt keinen Sinn Polymorphie und STL-Container auf diese Weise zu verwenden. Die Container haben nicht die gleiche Fähigkeiten. Nicht einmal die Iteratoren verschiedener Container haben die gleichen Fähigkeiten. Es hat schon gute Gründe, daß bei der Implementierung der STL keine Polymorphie eingesetzt wurde (abgesehen von der Effizienz). Entscheide dich für einen Containertyp und dann bleib dabei. Alles andere ist im Grunde von Anfang an zum Scheitern verurteilt (einzige Möglichkeit wäre den Iterator zu Wrappen, aber das wird so aufwändig, daß es nun gar keinen Sinn mehr macht).

[Mr. N]

Ich wurde angewiesen (:D), das hier zu posten:

#include <vector>
#include <iterator>
#include <iostream>

template<class ValueType>
class iterator_base {
public:
	typedef ValueType value_type;
	typedef value_type &reference;
	typedef value_type *pointer;

	reference operator*() const {
		return *get();
	}
	pointer operator->() const {
		return get();
	}
	iterator_base &operator++() {
		next();
		return *this;
	}
	iterator_base operator++(int) {
		iterator_base tmp(*this);
		next();
		return tmp;
	}

	bool operator==(iterator_base const &o) {
		return typeid(*this) == typeid(o) && equals(&o);
	}

	bool operator!=(iterator_base const &o) {
		return !(*this == o);
	}

	virtual iterator_base *clone() const = 0;

protected:
	virtual pointer get() const = 0;
	virtual void next() = 0;
	virtual bool equals(iterator_base const *o) const = 0;
};

template<class Iterator>
class concrete_iterator
: public iterator_base<typename std::iterator_traits<Iterator>::value_type> {
public:
	typedef Iterator iterator;
	typedef typename std::iterator_traits<iterator>::value_type value_type;
	typedef iterator_base<value_type> base;
	typedef typename base::pointer pointer;

	concrete_iterator(iterator const &pos) : pos(pos) {}

private:
	base *clone() const {
		return new concrete_iterator(*this);
	}

	pointer get() const {
		return &*pos;
	}

	void next() {
		++pos;
	}

	bool equals(base const *o) const {
		return pos == static_cast<concrete_iterator const *>(o)->pos;
	}

private:
	iterator pos;
};

template<class T>
struct iterator_proxy {
public:
	typedef T value_type;
	typedef typename iterator_base<T>::reference reference;
	typedef typename iterator_base<T>::pointer pointer;

	template<class Iterator>
	iterator_proxy(Iterator const &it) : p(new concrete_iterator<Iterator>(it)) {}

	iterator_proxy(iterator_base<T> const &it) : p(it.clone()) {}

	~iterator_proxy() {
		delete p;
	}

	iterator_proxy(iterator_proxy const &o) : p(o.p->clone()) {}

	void swap(iterator_proxy &o) {
		iterator_base<T> *tmp = p;
		p = o.p;
		o.p = tmp;
	}

	void operator=(iterator_proxy o) {
		o.swap(*this);
	}

	bool operator==(iterator_proxy const &o) {
		return *p == *o.p;
	}
	bool operator!=(iterator_proxy const &o) {
		return *p != *o.p;
	}

	reference operator*() const {
		return *get();
	}
	pointer operator->() const {
		return get();
	}
	iterator_proxy &operator++() {
		++*p;
		return *this;
	}
	iterator_proxy operator++(int) {
		iterator_proxy tmp(*this);
		++*p;
		return tmp;
	}

private:
	pointer get() const {
		return p->operator->();
	}

	iterator_base<T> *p;
};

int main() {
	std::vector<int> v;
	v.push_back(4);
	v.push_back(5);
	v.push_back(7);
	iterator_proxy<int> a(v.begin());
	iterator_proxy<int> b(v.end());
	while (a != b) {
		std::cout << *a << std::endl;
		++a;
	}
}

Je nach Bedürfnis ließe sich das noch vereinfachen. Oder erweitern. Für alle, die eine Version mit std::auto_ptr kennen: Ja, ich habe einen Proxy gebaut.

Viel Spaß!

EDIT: #include <memory> wird nicht mehr gebraucht, wurde daher gelöscht.
EDIT 2: Brauche kein const_reference etc. Das vereinfacht doch sehr :D.

[Apollon]

Z2 schrieb:

sapiens.dyslexia schrieb:

Kann man von Containertyp nicht irgendwie OHNE explizit anzugebende Templates abstrahieren?

IMHO sollte das doch aufgrund des gleichen verhaltens durchaus möglich sein?

Nein, kann mann nicht. Das ist nicht möglich. Macht auch überhaupt keinen Sinn Polymorphie und STL-Container auf diese Weise zu verwenden. Die Container haben nicht die gleiche Fähigkeiten. Nicht einmal die Iteratoren verschiedener Container haben die gleichen Fähigkeiten. Es hat schon gute Gründe, daß bei der Implementierung der STL keine Polymorphie eingesetzt wurde (abgesehen von der Effizienz). Entscheide dich für einen Containertyp und dann bleib dabei. Alles andere ist im Grunde von Anfang an zum Scheitern verurteilt (einzige Möglichkeit wäre den Iterator zu Wrappen, aber das wird so aufwändig, daß es nun gar keinen Sinn mehr macht).

Das ist doch Unfug. Ich kann ganz locker vector durch list ersetzen und der Code klappt wie gewohnt. Eben weil das Iterator-Pattern davon abstrahiert.

Der Threadsteller will JAVA kopieren.

[Z2]

Apollon schrieb:

Z2 schrieb:

sapiens.dyslexia schrieb:

Kann man von Containertyp nicht irgendwie OHNE explizit anzugebende Templates abstrahieren?

IMHO sollte das doch aufgrund des gleichen verhaltens durchaus möglich sein?

Nein, kann mann nicht. Das ist nicht möglich. Macht auch überhaupt keinen Sinn Polymorphie und STL-Container auf diese Weise zu verwenden. Die Container haben nicht die gleiche Fähigkeiten. Nicht einmal die Iteratoren verschiedener Container haben die gleichen Fähigkeiten. Es hat schon gute Gründe, daß bei der Implementierung der STL keine Polymorphie eingesetzt wurde (abgesehen von der Effizienz). Entscheide dich für einen Containertyp und dann bleib dabei. Alles andere ist im Grunde von Anfang an zum Scheitern verurteilt (einzige Möglichkeit wäre den Iterator zu Wrappen, aber das wird so aufwändig, daß es nun gar keinen Sinn mehr macht).

Das ist doch Unfug. Ich kann ganz locker vector durch list ersetzen und der Code klappt wie gewohnt. Eben weil das Iterator-Pattern davon abstrahiert.

Das ist kein Unfug. Das klappt vielleicht, wenn du dich auf eine Teilmenge der Funktionalität des vector-Interators beschränkst. Aber auch nur dann. Der vektor-Iterator kann mehr als der list-Iterator. Siehe dazu jede bessere STL-Dokumentation.

Apollon schrieb:

Der Threadsteller will JAVA kopieren.

Schwerer Fehler. Auch wenn ich damit auf das offensichtliche hinweisen muß:

C++ != Java

@Mr. N: Ok, schön gewrappt. Aber wie übergibst du deinen Iterator nun an einen Algorithmus?

[Artchi]

Die Container lassen sich nicht einfach beliebig austauschen. Z.B. kann ich std::sort() auf vector anwenden, aber bei list gehts schon mal nicht. Weil Iteratoren der jeweilgen Container nicht gleiche Features haben. Sie haben einen gewissen gemeinsammen Nenner, aber mehr auch nicht.

Man könnte höchstens einen Wrapper bauen, obwohl die Iteratoren das ja schon sind. Aber diese kann man natürlich nochmal verstecken, wie es Mr. N gemacht hat eine eine Möglichkeit.

[Simon2]

Z2 schrieb:

...
C++ != Java
...

Naja, wenn er unbedingt einen "Laufzeit-kontrollierten Container" (wie es sie in schon Java gibt) bauen möchte, kann er das ja tun - ich persönlich halte das zwar für einen unnötigen Rückschritt, aber das bedeutet ja noch nicht, dass es nicht ginge.
Letztlich würde ich dann aber komplett die Java-Variante durchziehen und mit void* bzw. ContainerItemBase* und entsprechenden casts arbeiten.

@sapiens.dyslexia: Wieso ist Dir Laufzeitdefinition/Polymorphie so wichtig, dass es Compiletime-Definition nicht tut ?
Habe ich richtig verstanden: Du willst erst zur Laufzeit entscheiden, welcher Container verwendet wird .... und zwar bei STL-Containern, die zur Compilezeit definiert werden ?

Gruß,

Simon2.

[Mr. N]

Z2 schrieb:

@Mr. N: Ok, schön gewrappt. Aber wie übergibst du deinen Iterator nun an einen Algorithmus?

Indem ich ihn übergebe:

algorithmus_der_nur_einen_iterator_braucht(it);

Das nennt man Parameterübergabe. Das ist so ein ganz fieser Trick von C++, mit dem man viele böse Hacks machen kann. </sarkasmus>

Im Ernst: Ich übergebe iterator_proxy<T> und das wars dann. Es gibt kein Problem.

Übrigens halte ich es für vollkommen irrelevant, was Java-typisch ist und was nicht. Iteratoren nicht polymorph zu machen war eine bewusste Entscheidung des Komitees (Grund war bestimmt die Geschwindigkeit) und übrigens ein Kompromiss. Und ich muss zugeben, ich habe meine heute gebauten iterator_proxys zwar noch nie verwendet, aber vielleicht wäre das an manchen Stellen gut gewesen.

[Artchi]

Wir haben halt Templates, der Algos müssen keine polymorphen Iteratoren verlangen. Hätten wir keine Templates, hätten die Algos sicherlich einen Iterator-Basistyp verlangt.

[Shade Of Mine]

Artchi schrieb:

Die Container lassen sich nicht einfach beliebig austauschen.

Du hast das Iterator-Pattern nicht verstanden. Bitte nochmal lesen.

@Simon2:
Diese Anforderung ist ganz normal. Simpelstes Beispiel: Plugins. Warum sollte ich einem Plugin vorschreiben dass es seine Daten als vector speichert? Ich definiere da lieber "muss forward iteratoren anbieten" und fertig.

[Artchi]

Shade Of Mine schrieb:

Artchi schrieb:

Die Container lassen sich nicht einfach beliebig austauschen.

Du hast das Iterator-Pattern nicht verstanden. Bitte nochmal lesen.

Dann kannst du mir sicherlich sagen, warum std::list eine eigene sort-Methode braucht? Wie kann ich also std::sort eine list übergeben? Ich kann zwar mit einem Iterator auf einen Container rumwandern, aber ich kann nochlange nicht beliebig alles mit einem beliebigen Container machen.

Kann aber auch sein, das ich es wirklich nicht verstanden habe, dann wäre ne Lösung für ein einfaches Beispiel wie std::sort und std::list super. Danke!

[Simon2]

Shade Of Mine schrieb:

...
@Simon2:
Diese Anforderung ist ganz normal. Simpelstes Beispiel: Plugins. Warum sollte ich einem Plugin vorschreiben dass es seine Daten als vector speichert? Ich definiere da lieber "muss forward iteratoren anbieten" und fertig.

Aho !
Ich hatte das immer von der andern Seite betrachtet (sprich: Er will über seinen STL-Container einen "polymorphen Stub" implementieren und mir fiel kein Grund dafür ein).

Sowas kann man natürlich machen. Ob man sowas dann aber tatsächlich mit "Standardpolymorphie" und nicht mit "technischeren Methoden", weiß ich nicht.

Aber Danke für das Beispiel.

Gruß,

Simon2.

[Shade Of Mine]

Artchi schrieb:

Dann kannst du mir sicherlich sagen, warum std::list eine eigene sort-Methode braucht?

weil das design kacke ist?

list sollte std::sort spezialisieren fuer seine eigenen iteratoren. oder genereller: sort sollte fuer bidirectional iteratoren spezialisiert sein um auch so einen container sortieren zu koennen.

aber das tut nichts zur sache.
Lies das Iterator Pattern.

Wie kann ich also std::sort eine list übergeben? Ich kann zwar mit einem Iterator auf einen Container rumwandern, aber ich kann nochlange nicht beliebig alles mit einem beliebigen Container machen.

Du hast das Iterator Pattern nicht verstanden.

Es geht nicht darum dass du alles mit allem machen kannst. Sondern dass du aequivalente Collections untereinander tauschen kannst.

zB wenn random access iteratoren die anforderung sind, dann braucht man einen container der das unterstuetzt. Ein stack waere zB ungeeignet hier als drop in replace zu dienen.

ABER:
ich kann std::vector und boost::array frei tauschen. Beide erfuellen meine Anfoerderungen an die Collection.

Das ist das Iterator-Pattern.

Ich kann die Collections implementieren wie ich will. Sie muessen nur die Anforderung erfuellen.

Kommt dir das bekannt vor? nein? kleiner tipp:
Was ist denn Vererbung? Also eine virtuelle methode:

class Base {
public:
  virtual int get_random_number() = 0;
};

Hier kann ich von Base erben und get_random_number implementieren wie ich will, oder?

falsch:

class Derived : public Base {
public:
  void get_random_number(int& num);
};

geht ja nicht.

jetzt denkst du dir sicher "na lol, ist doch logisch - du musst die anfoerdung erfuellen, dass ein int returned wird, die exception spezifikationen duerfen nicht lockerer sein als in base,..."

denk darueber mal nach.

ist es beim auswechseln der collections nicht genauso? ich muss nur ein paar anforderungen erfuellen - aber wie ich es implementiere ist meine sache.

[Simon2]

Shade Of Mine schrieb:

Artchi schrieb:

Dann kannst du mir sicherlich sagen, warum std::list eine eigene sort-Methode braucht?

weil das design kacke ist?...

Manchmal sind die naheliegensten Antworten die besten.

Gruß,

Simon2.

[Plotzenhotz]

Artchi schrieb:

Dann kannst du mir sicherlich sagen, warum std::list eine eigene sort-Methode braucht?

Naja, du kannst für so ziemlich alles std::stable_sort verwenden (was halt langsamer ist). Oder du schreibst dir deine eigene kleine sort Funktion (Template), und verwendest std::iterator_traits<T>::iterator_category um zwischen "random-access" und "bidirectional" Iteratoren zu unterscheiden.

Is natürlich schade dass es nicht im Standard enthalten ist, aber ist halt so. std::copy_if fehlt ja auch immer noch... (wird aber im nächsten Standard drinnen sein, std::copy_if mein' ich jetzt).