Iterator Frage: Container Abstrahieren

Hi, ich habe eine Interfaceklasse, die je für den Anfang und das Ende eines Containers eine Methode (begin() end()), die einene Iterator returnen soll.

Nun muss ich bei den STL Iteratoren aber angeben ob sie ein list<...>::iterator oder vector<...>::iterator sind.

Wie kann ich das Abstrahieren?

Ich möchte also einfach einen Iterator returnen, ich weiß nur den gespeicherten Typ (StaticVoc), aber NICHT den Container.

Bisher sieht's leider so aus:

//class...
public:
	//Access
	virtual std::list<StaticVoc>::const_iterator getBegin()const=0;
	virtual std::list<StaticVoc>::const_iterator getEnd()const=0;
// /class...

Danke im Voraus!

Spacelord

Ist der Containertyp nen template Parameter ,oder wann wird der genaue Typ des Containers festgelegt?

Gruß Spacelord

Michael E.

Ich hoffe, ich hab dich richtig verstanden. Willst du sowas?

#include <vector>
#include <list>
using namespace std;

template<class T, template<typename ElemT, typename = std::allocator<ElemT> > class ContainerT = list >
struct IteratorTraits
{
	typedef typename ContainerT<T>::iterator iterator;
	typedef typename ContainerT<T>::const_iterator const_iterator;
};

int main()
{
	vector<int> foo;
	IteratorTraits<int, vector>::iterator bar = foo.begin();
}

Danke für euere Antworten.

Spacelord schrieb:

Ist der Containertyp nen template Parameter ,oder wann wird der genaue Typ des Containers festgelegt?

Der Containertyp soll von der das Interface implementierenden Klasse festgelegt werden, also als Implementierungsdetail gelten und folglich nicht in der Interface-Klasse erwähnt werden.

Michael E. schrieb:

Ich hoffe, ich hab dich richtig verstanden. Willst du sowas?

#include <vector>
#include <list>
using namespace std;

template<class T, template<typename ElemT, typename = std::allocator<ElemT> > class ContainerT = list >
struct IteratorTraits
{
	typedef typename ContainerT<T>::iterator iterator;
	typedef typename ContainerT<T>::const_iterator const_iterator;
};

int main()
{
	vector<int> foo;
	IteratorTraits<int, vector>::iterator bar = foo.begin();
}

Ich schätze ich kenne mich mit Templates nicht genug aus um dir darauf zu Antworten. Also versuche ich meine Frage nochmal zusammenzufassen und dann, soweit ich das kann, Bezug auf dein Codefragment zu geben:

Ich möchte eine Interfaceklasse schreiben.
Diese soll eine abstrakte Methode (z.B. namens .getBegin() ) besitzen, welche einen Iterator auf einen unbekannten Containertyp zurückgibt.

Mein Problem ist also, soweit ich das einschätze, dass die STL-Iteratoren keine gemeinsamme Parentalklasse haben. Ansonsten würde diese einfach im als Rückgabetyp angeben und dank Polymorphie könnte jeder beliebige Container in der Imlpementierungsklasse verwendet werden.

Deine (sehr interessante) Klasse scheint den Containertyp als Template-Argument übergeben zu bekommen, womit sie doch zur Kompilierzeit auf einen Container beschränkt wird?

Ich bräuchte so etwas wie Polymorphie, bin mir aber unsicher ob und wie man deine Klasse dafür verwenden kann.

Gruß

Michael E.

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
	{
		...
	}
};

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
	{
		...
	}
};

Wie kann man Polymorphie damit verwenden?
Kann ich einen Pointer auf Container verwenden und getBegin() aufrufen, ohne dabei ContainerT anzugeben?

Ich muss Methoden/Funktionen schreiben können, die einen Pointer auf meinen "Container" haben aber nichts von dem darunterliegenden Container wissen..

Eventuell verstehe ich deinen Code nur falsch, kannst du mir vieleicht zeigen wie man eine Funktion

void foo(/*iterator auf unbekannten Container*/);

schreiben kann, ohne dabei Templates für diese Funktion zu verwenden?

Gruß und Dank soweit!

David_pb

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? Im übrigen ist es grundlegend kein guter Gedanke von einem STL Kontainer abzuleiten.

grüße

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.

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ß

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.