 |
C++Talk.NET C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Marcel Müller Guest
|
Posted: Thu Mar 01, 2007 11:52 pm Post subject: Polymorphe, kopierbare Iteratorklassen |
|
|
Hallo,
ich knuspere gerade an einer Designfrage für eine hierarchische
Objektstruktur. Ich mache es mal am Filesystem fest, obwohl es das
später nicht alleine werden soll, eher eine generalisierte Playliste.
Folgender vereinfachter Pseusocode zur Verdeutlichung:
class Iany
{
};
class Iatomic : public Iany // also z.B. ein File
{
};
class Icontainer : public Iany // irgendeine Aufzählung
{public:
class iterator
{ virtual any& operator*() = 0;
virtual iterator& operator++() = 0;
virtual iterator& operator--() = 0;
};
virtual iterator begin() = 0;
virtual iterator end() = 0;
};
class folder : public Icontainer // ein Ordner
{private:
class my_iterator : public iterator
{ virtual any& operator*();
virtual iterator& operator++();
virtual iterator& operator--();
};
public:
virtual iterator begin();
virtual iterator end();
};
class linklist : public Icontainer // eine Liste von beliebigen Files
{private:
class my_iterator : public iterator
{ virtual any& operator*();
virtual iterator& operator++();
virtual iterator& operator--();
};
public:
virtual iterator begin();
virtual iterator end();
};
Das funktioniert natürlich nicht, da die virtuellen Funktionen begin und
end natürlich die abstrakte Klasse container::iterator nicht by value
zurückliefern können. Aber das ist gerade eine essentielle Eigenschaft
bei Iteratoren, dass sie eben (billig) kopierbar sind.
Wie kann man das Problem in den Griff bekommen, ohne die Iteratoren auf
den konkreten Typ des Containers typisieren zu müssen?
Das interessiert die nutzenden Programmteile nämlich kein bisschen. Sie
nutzen eigentlich nur Icontainer und Iany. Streng genommen noch nicht
einmal Icontainer, da eine weitere Hilfsklasse im Interface Iany
(atomiciterator) die Stuktur platt macht und nur über die atomic-Objekte
iteriert.
STL-Klassen sind übrigens wegen den C++-technisch relativ alten
Kompilern so oder so keine Option, ebenso wenig Smartpointer jeglicher
Art. Derzeit werden u.a. IBM VAC++ 3.0, IBM VAC++ 4.0, OpenWatcom und
gcc 3.3 unterstützt. Ich arbeite vorwiegend mit ersterem.
Marcel |
|
| Back to top |
|
 |
Stefan Reuther Guest
|
Posted: Fri Mar 02, 2007 11:28 pm Post subject: Re: Polymorphe, kopierbare Iteratorklassen |
|
|
Hallo,
Marcel Müller wrote:
| Quote: | Das funktioniert natürlich nicht, da die virtuellen Funktionen begin und
end natürlich die abstrakte Klasse container::iterator nicht by value
zurückliefern können. Aber das ist gerade eine essentielle Eigenschaft
bei Iteratoren, dass sie eben (billig) kopierbar sind.
Wie kann man das Problem in den Griff bekommen, ohne die Iteratoren auf
den konkreten Typ des Containers typisieren zu müssen?
|
Ich bevorzuge in so einem Fall eine Enumerator-Schnittstelle wie diese:
template<class T>
class Enumeration : public Object {
public:
virtual ~Enumeration() { }
virtual bool hasMoreElements() = 0;
virtual T getNextElement() = 0;
};
Statt
for (x::iterator i = someX.begin(); i != someX.end(); ++i)
process(*i);
schreibt man dann
auto_ptr<Enumeration<Elem&> > i = someX.getElements();
while (i.hasMoreElements())
process(i.getNextElement());
Statt auto_ptr tut's auch jede andere Möglichkeit, exceptionsicher mit
solchen Objekten umgehen zu können (z.B. scoped_ptr).
| Quote: | STL-Klassen sind übrigens wegen den C++-technisch relativ alten
Kompilern so oder so keine Option,
|
Dann fällt es ja auch nicht auf, wenn du keine begin/end-Iteratoren
benutzt :-)
Stefan |
|
| Back to top |
|
 |
Marcel Müller Guest
|
Posted: Sat Mar 03, 2007 3:38 am Post subject: Re: Polymorphe, kopierbare Iteratorklassen |
|
|
Stefan Reuther wrote:
| Quote: | Ich bevorzuge in so einem Fall eine Enumerator-Schnittstelle wie diese:
template<class T
class Enumeration : public Object {
public:
virtual ~Enumeration() { }
virtual bool hasMoreElements() = 0;
virtual T getNextElement() = 0;
};
|
Ja, der Java-Stil hat so seine Vorteile.
| Quote: | Statt
for (x::iterator i = someX.begin(); i != someX.end(); ++i)
process(*i);
schreibt man dann
auto_ptr<Enumeration<Elem&> > i = someX.getElements();
while (i.hasMoreElements())
process(i.getNextElement());
Statt auto_ptr tut's auch jede andere Möglichkeit, exceptionsicher mit
solchen Objekten umgehen zu können (z.B. scoped_ptr).
|
Nur hat das mit meinem Problem in keiner Weise zu tun. Denn die
Möglichekeit zur Polymorphie entsteht alleine durch die Tatsache, dass
getElements() einen /Pointer/ auf die Enumerationsklasse liefert, der
natürlich auch wieder freigegeben werden muss. Das hat aber den
Nachteil, dass man sich selebr um die Freigabe und das Kopieren kümmern
muss und die Syntax i->function_of_Elem() nicht mehr funktioniert.
| Quote: | STL-Klassen sind übrigens wegen den C++-technisch relativ alten
Kompilern so oder so keine Option,
Dann fällt es ja auch nicht auf, wenn du keine begin/end-Iteratoren
benutzt
|
Das ist richtig. Es wirft allerdings auch ernste Probleme mit
#include<memory> auf. Das wird nämlich nix. Also kein auto_ptr und auch
keine anderen Smartpointer. Und ohne selbige gerät das Hantieren mit den
Iteratoren zum Drahtseilakt. Von der Anforderung der Kopierbarkeit her
wäre auch mindestens ein Referenzzählender Smartpointer benötigt.
ich habe mir jetzt erstmal mit einer Proxy-Klasse beholfen.
class iterator;
class Iiterator
{private:
Iiterator(const Iiterator&); // non copyable
void operator=(const Iiterator&);
protected:
Iiterator() {}
public:
virtual Iiterator* clone() const = 0;
virtual IPlayable& operator*() const = 0;
virtual void operator++() = 0;
virtual void operator--() = 0;
virtual bool operator==(const Iiterator& r) const = 0;
};
class iterator
{private:
Iiterator* imp;
public:
iterator() : imp(NULL) {}
iterator(Iiterator* imp) : imp(imp) {}
iterator(const iterator& r) : imp(r.imp->clone()) {}
~iterator() { delete imp; }
iterator& operator=(const iterator& r)
{ delete imp; imp = r.imp ? r.imp->clone() : NULL; return *this; }
IPlayable& operator*() const { return **imp; }
IPlayable* operator->() const { return &**imp; }
iterator operator++() { ++*imp; return *this; }
iterator operator--() { --*imp; return *this; }
friend bool operator==(const iterator& l, const iterator& r);
friend bool operator!=(const iterator& l, const iterator& r);
};
Aber schön ist das absolut nicht.
Marcel |
|
| Back to top |
|
 |
Stefan Reuther Guest
|
Posted: Sat Mar 03, 2007 11:02 pm Post subject: Re: Polymorphe, kopierbare Iteratorklassen |
|
|
Marcel Müller wrote:
| Quote: | Stefan Reuther wrote:
Statt
for (x::iterator i = someX.begin(); i != someX.end(); ++i)
process(*i);
schreibt man dann
auto_ptr<Enumeration<Elem&> > i = someX.getElements();
while (i.hasMoreElements())
process(i.getNextElement());
Statt auto_ptr tut's auch jede andere Möglichkeit, exceptionsicher mit
solchen Objekten umgehen zu können (z.B. scoped_ptr).
Nur hat das mit meinem Problem in keiner Weise zu tun. Denn die
Möglichekeit zur Polymorphie entsteht alleine durch die Tatsache, dass
getElements() einen /Pointer/ auf die Enumerationsklasse liefert
|
Eben. Die STL-Iteratoren basieren aber eben darauf, dass Iteratoren
billig zu kopieren sind. Würde man das gleiche mit polymorphen Klassen
umsetzen wollen, müsste man eben alle Iteratoren bei allen möglichen
Operationen mittels 'clone()' duplizieren. Code wie
for (x::iterator i = someX.begin(); i != someX.end(); ++i) ...
würde bei jedem Schleifentest einen end-Iterator auf dem Heap erstellen,
ggf. im Rahmen der Rückgabe aus der end()-Funktion duplizieren,
vergleichen und wieder wegwerfen. Das ist mir zu viel Laufzeitaufwand.
Der Java-Stil hat an der Stelle den Vorteil, dass man genau dieses eine
Iterator-Objekt in der Hand hat, auf dem man einige wenige Operationen
ausführen kann. Die aufwändige Duplikation muss man selbst codieren,
falls nötig.
| Quote: | Dann fällt es ja auch nicht auf, wenn du keine begin/end-Iteratoren
benutzt :-)
Das ist richtig. Es wirft allerdings auch ernste Probleme mit
#include<memory> auf. Das wird nämlich nix. Also kein auto_ptr und auch
keine anderen Smartpointer. Und ohne selbige gerät das Hantieren mit den
Iteratoren zum Drahtseilakt.
|
Ein Smart-Pointer, der mit sowas umgehen kann, ist in nullkommanix
selbstgestrickt. Ich würde mit einfach sowas anfangen wie
template<typename T>
class scoped_ptr {
T* ptr;
void operator=(const scoped_ptr&);
scoped_ptr(const scoped_ptr&);
public:
scoped_ptr(T* ptr) : ptr(ptr) { }
~scoped_ptr() { delete ptr; }
T* operator->() { return ptr; }
};
Die get-Funktion liefert einfach einen Enumeration<T>*.
| Quote: | class iterator
{private:
Iiterator* imp;
public:
iterator() : imp(NULL) {}
iterator(Iiterator* imp) : imp(imp) {}
iterator(const iterator& r) : imp(r.imp->clone()) {}
|
Das wäre mir einfach zu viel Dupliziererei.
| Quote: | ~iterator() { delete imp; }
iterator& operator=(const iterator& r)
{ delete imp; imp = r.imp ? r.imp->clone() : NULL; return *this; }
|
<nitpick> hier fehlt die Behandlung von this==&r (bzw. imp==r.imp).
Ein anderer Ansatz ist noch, zu versuchen, die Iteration auf eine
Handvoll immer gleiche Parameter abzubilden. Beispielsweise haben die
Containerklassen (virtuelle) Methoden
int getNumItems()
Item& getItemByNumber(int n)
und ein Iterator enthält dann einfach einen Index und einen Zeiger auf
den entsprechenden Container. Das ist natürlich nicht immer möglich. Du
schriebst von Dateisystem/Playlist: bei meiner Implementation einer
solchen Datenstruktur war es einfach möglich. Ich hab mir allerdings
nicht die Mühe gemacht, da noch eine hübsche Iteratorklasse zu bauen,
sondern renne gleich mit den Indizes durch die Container.
Stefan |
|
| Back to top |
|
 |
Marcel Müller Guest
|
Posted: Sun Mar 04, 2007 1:28 am Post subject: Re: Polymorphe, kopierbare Iteratorklassen |
|
|
Stefan Reuther wrote:
| Quote: | Eben. Die STL-Iteratoren basieren aber eben darauf, dass Iteratoren
billig zu kopieren sind. Würde man das gleiche mit polymorphen Klassen
umsetzen wollen, müsste man eben alle Iteratoren bei allen möglichen
Operationen mittels 'clone()' duplizieren.
|
ACK.
| Quote: | Code wie
for (x::iterator i = someX.begin(); i != someX.end(); ++i) ...
würde bei jedem Schleifentest einen end-Iterator auf dem Heap erstellen,
ggf. im Rahmen der Rückgabe aus der end()-Funktion duplizieren,
vergleichen und wieder wegwerfen. Das ist mir zu viel Laufzeitaufwand.
|
Das kann man verhindern, indem man die Iteratoren für begin() und end()
in je einer (logisch) konstanten Instanz in der Containerklasse hält und
den Returntyp von begin() und end() auf const iterator& ändert. Dann
erzeugt nur das erste Statement "x::iterator i = someX.begin()" einen
clone()-Aufruf im Kopierkonstruktor und die Aufwandsklasse für die
Allozierung bleibt O(1).
| Quote: | Der Java-Stil hat an der Stelle den Vorteil, dass man genau dieses eine
Iterator-Objekt in der Hand hat, auf dem man einige wenige Operationen
ausführen kann. Die aufwändige Duplikation muss man selbst codieren,
falls nötig.
|
Ich werde es nochmal überdenken. Möglicherweise ist das doch die Lösung.
| Quote: | Ein Smart-Pointer, der mit sowas umgehen kann, ist in nullkommanix
selbstgestrickt. Ich würde mit einfach sowas anfangen wie
template<typename T
class scoped_ptr {
T* ptr;
void operator=(const scoped_ptr&);
scoped_ptr(const scoped_ptr&);
public:
scoped_ptr(T* ptr) : ptr(ptr) { }
~scoped_ptr() { delete ptr; }
T* operator->() { return ptr; }
};
Die get-Funktion liefert einfach einen Enumeration<T>*.
|
Das würde noch gehen, aber die Tricks für auto_ptr und boost::shared_ptr
beherscht der uralte Compiler nicht korrekt.
| Quote: | class iterator
{private:
Iiterator* imp;
public:
iterator() : imp(NULL) {}
iterator(Iiterator* imp) : imp(imp) {}
iterator(const iterator& r) : imp(r.imp->clone()) {}
Das wäre mir einfach zu viel Dupliziererei.
|
S.o.
Es hält sich in Grenzen.
| Quote: | ~iterator() { delete imp; }
iterator& operator=(const iterator& r)
{ delete imp; imp = r.imp ? r.imp->clone() : NULL; return *this; }
nitpick> hier fehlt die Behandlung von this==&r (bzw. imp==r.imp).
|
Stimmt.
| Quote: | Ein anderer Ansatz ist noch, zu versuchen, die Iteration auf eine
Handvoll immer gleiche Parameter abzubilden. Beispielsweise haben die
Containerklassen (virtuelle) Methoden
int getNumItems()
Item& getItemByNumber(int n)
und ein Iterator enthält dann einfach einen Index und einen Zeiger auf
den entsprechenden Container.
|
Das habe ich auch schon überlegt. Sozusagen die Iterator-Funktionalität
in den Container verlagern.
| Quote: | Das ist natürlich nicht immer möglich. Du
schriebst von Dateisystem/Playlist: bei meiner Implementation einer
solchen Datenstruktur war es einfach möglich.
|
Nein, gerade nicht, weil es absolut nichttrivial ist, bei einer
Dateisystemiteration wieder aufzusetzten, wenn FindFirst/FindNext
unterbrochen wurde. Das liegt daran, dass die Elemente im Dateisystem in
keiner definierten Reihenfolge kommen und sich der Inhalt ständig ändern
kann.
Marcel |
|
| Back to top |
|
 |
James Kanze Guest
|
Posted: Sun Mar 04, 2007 5:32 pm Post subject: Re: Polymorphe, kopierbare Iteratorklassen |
|
|
On Mar 2, 10:38 pm, Marcel Müller <news.5.ma...@spamgourmet.org>
wrote:
| Quote: | Stefan Reuther wrote:
Ich bevorzuge in so einem Fall eine Enumerator-Schnittstelle wie diese:
template<class T
class Enumeration : public Object {
public:
virtual ~Enumeration() { }
virtual bool hasMoreElements() = 0;
virtual T getNextElement() = 0;
};
Ja, der Java-Stil hat so seine Vorteile.
|
Eher der USL-Stil; so wurde es in der USL-Bibliothek gemacht
(längst vor Java). Noch besser ist der classische Stil, wie es
überall gemacht wurde (außer USL) vor der standard Bibliothek,
mit drei Funktionnen: isDone (oder isValid, oder
hasMoreElements, oder... der Name ist nicht so wichtig), current
(oder element, oder getElement...) und next (oder advance,
oder...). Damit sind die drei Operationen, die man macht,
sauber getrennt, immer aber in einem einzigen Objekt eingebaut.
(Dieser Model wurde auch in "Design Patterns" beschrieben.)
| Quote: | Statt
for (x::iterator i = someX.begin(); i != someX.end(); ++i)
process(*i);
schreibt man dann
auto_ptr<Enumeration<Elem&> > i = someX.getElements();
while (i.hasMoreElements())
process(i.getNextElement());
Statt auto_ptr tut's auch jede andere Möglichkeit, exceptionsicher mit
solchen Objekten umgehen zu können (z.B. scoped_ptr).
Nur hat das mit meinem Problem in keiner Weise zu tun. Denn die
Möglichekeit zur Polymorphie entsteht alleine durch die Tatsache, dass
getElements() einen /Pointer/ auf die Enumerationsklasse liefert, der
natürlich auch wieder freigegeben werden muss. Das hat aber den
Nachteil, dass man sich selebr um die Freigabe und das Kopieren kümmern
muss und die Syntax i->function_of_Elem() nicht mehr funktioniert.
|
In der Tat. Du kommst auf den zweiten großen Unterschied
zwischen Iteratoren: Wert-Semantik, oder Referenz-Semantik. Es
ist möglich, mittels den Brief-Umschlag Pattern, ein
polymorphisches Objekt eine Wert-Semantik zu geben; ich habe es
auch in der Vergangenheit mit Iteratoren gemacht. Nur sind die
Laufzeitkosten bedeutend; jeder Kopie verlangt eine dynamische
Allokierung. Ob das ein Problem ist, oder nicht, hängt von der
Anwendung.
Amsonsten kann man Iteratoren mit Referenz-Semantik benutzen,
wie in der OSE-Bibliothek (http://ose.sourceforge.net/) oder
std::streambuf (der sich auch wie ein Iterator verhält,
funktionniert aber nicht für alle Typen). Es gibt auch Fälle, wo
die Referenz-Semantik sowieso besser anpassen (beim Parsen,
z.B.).
--
James Kanze (Gabi Software) email: james.kanze (AT) gmail (DOT) com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34 |
|
| Back to top |
|
 |
|
|
You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum
|
|