STL-Container und Referenzen
Markus Breuer
Standardcontainer std::list abgelegt. Zwecks Sortierung sollen einzelne
Komponenten der Objekte als Schlüssen für eine std::map herangezogen
werden. Beispiel:
struct Object {
TYPE1 t1;
TYPE2 t2;
TYPE3 t3;
};
std::list<Object> m_liste;
Da die Objekte sehr teuer sind, möchte ich keine Kopien anlegen. Daher
folgende Idee:
std::map< Object&, std::list<Object>::iterator > m_dictionary;
Die Objekte werden als Referenz gespeichert, die Erzeugungskosten dafür
sind vergleichsweise niedrig, der Platzbedarf entspricht dem eines
Pointers. Der value_type ist ein iterator in die Liste. Desweiteren ist
sichergestellt, dass die Operationen Einfügen und Löschen stets auf
beide Container ausgeführt werden, d.h. die map verweist niemals auf ein
Element, dass in der list nicht vorhanden ist. Umgekehrt besitzt jedes
Listenelement einen Eintrag in der map.
Ich mache folgende Feststellungen:
(1) Der iterator auf ein Element von std::list bleibt solange gültig,
wie das Element existiert. Änderungen an anderen Elementen
(Einfügen,Löschen) haben keinen Einfluß auf die Gültigkeit des iterators
bzw. machen ihn ungültig.
(2) Durch die Verwendung des Referenz-Typs als key können die
Vergleichsoperatoren von struct Object ( <,>,==,!=) ausgenutzt werden,
ohne das ein neues Object erstellt werden muss. Der value_type ist von
Typ listen-Iterator und bleibt unter den o.g. Bedingungen gültig.
(3) Von der Liste aus kann der entsprechende map-iterator gefunden
werden. Somit ist es möglich Elemente ausgehend von der Liste aus beiden
Containern zu entfernen.
(4) Durch die Verwendung einen Referenz-Typen ist es nicht zulässig,
neue Elemente mittels Default-Constructor zu erzeugen => value_type&
map.operator[]
(5) Durch die Referenz können auch physikalisch unterschiedliche Objekte
miteinander verglichen werden:
Object o1, o2;
m_dictionary.insert( ValuePair(o1,...) ); //
m_dictionary.find( o2 ); // => liefert liefert iterator auf o1,
falls die Objekte inhaltlich gleich sind
Sind diese Feststellungen korrekt, oder begehe ich gerade einen Denkfehler?
Übersehe ich einen wichtigen Aspekt bei der Verwendung von
Referenz-typen? Kompilieren gängige Compiler (MS VC6,gcc2.95/3.x)
solchen Code Problemlos?
Danke und Gruß,
Markus
--
de.comp.lang.iso-c++ - Moderation: mailto:voyag...@bud.prima.de
FAQ: http://www.voyager.prima.de/cpp/ mailto:voyager+...@bud.prima.de
André Pönitz
> Ich möchte eine Liste von Objekten Indizieren. Die Objekte sind in einem
> Standardcontainer std::list abgelegt. Zwecks Sortierung sollen einzelne
> Komponenten der Objekte als Schlüssen für eine std::map herangezogen
> werden. Beispiel:
>
> struct Object {
> TYPE1 t1;
> TYPE2 t2;
> TYPE3 t3;
> };
>
> std::list<Object> m_liste;
>
> Da die Objekte sehr teuer sind, möchte ich keine Kopien anlegen. Daher
> folgende Idee:
>
> std::map< Object&, std::list<Object>::iterator > m_dictionary;
>
> Die Objekte werden als Referenz gespeichert, die Erzeugungskosten dafür
> sind vergleichsweise niedrig, der Platzbedarf entspricht dem eines
> Pointers.
Mich irritiert, dass das gehen soll.
> [...] Sind diese Feststellungen korrekt, oder begehe ich gerade
> einen Denkfehler?
Ich befuerchte letzteres. Eine Referenz ist kein Objekt.
> Übersehe ich einen wichtigen Aspekt bei der Verwendung von
> Referenz-typen? Kompilieren gängige Compiler (MS VC6,gcc2.95/3.x)
> solchen Code Problemlos?
Warum probierst Du's nicht einfach mit einem beliebigen Compiler aus?
Andre'
André Pönitz
> Ich möchte eine Liste von Objekten Indizieren. Die Objekte sind in einem
> Standardcontainer std::list abgelegt. Zwecks Sortierung sollen einzelne
> Komponenten der Objekte als Schlüssen für eine std::map herangezogen
> werden. Beispiel:
>
> struct Object {
> TYPE1 t1;
> TYPE2 t2;
> TYPE3 t3;
> };
>
> std::list<Object> m_liste;
>
> Da die Objekte sehr teuer sind, möchte ich keine Kopien anlegen. Daher
> folgende Idee:
>
> std::map< Object&, std::list<Object>::iterator > m_dictionary;
Als Loesung sollte std::map< Object *, std::list<Object>::iterator >
gehen. Fuer die Vergleiche musst Du Dir dann halt was basteln.
Andre'
--
Those who desire to give up Freedom in order to gain Security, will not have,
nor do they deserve, either one. (T. Jefferson or B. Franklin or both...)
Rolf Magnus
> Ich möchte eine Liste von Objekten Indizieren. Die Objekte sind in
> einem Standardcontainer std::list abgelegt. Zwecks Sortierung sollen
> einzelne Komponenten der Objekte als Schlüssen für eine std::map
> herangezogen werden. Beispiel:
>
> struct Object {
> TYPE1 t1;
> TYPE2 t2;
> TYPE3 t3;
> };
>
> std::list<Object> m_liste;
>
> Da die Objekte sehr teuer sind, möchte ich keine Kopien anlegen. Daher
> folgende Idee:
>
> std::map< Object&, std::list<Object>::iterator > m_dictionary;
Geht nicht. Referenzen können nicht in Containern gespeichert werden.
Der Rest deiner Argumentation wird dadurch leider hinfällig.
Markus Breuer
> Markus Breuer wrote:
>
>
>>Ich möchte eine Liste von Objekten Indizieren. Die Objekte sind in
>>einem Standardcontainer std::list abgelegt. Zwecks Sortierung sollen
>>einzelne Komponenten der Objekte als Schlüssen für eine std::map
>>herangezogen werden. Beispiel:
>>
>>struct Object {
>> TYPE1 t1;
>> TYPE2 t2;
>> TYPE3 t3;
>>};
>>
>>std::list<Object> m_liste;
>>
>>Da die Objekte sehr teuer sind, möchte ich keine Kopien anlegen. Daher
>>folgende Idee:
>>
>>std::map< Object&, std::list<Object>::iterator > m_dictionary;
>
>
> Geht nicht. Referenzen können nicht in Containern gespeichert werden.
> Der Rest deiner Argumentation wird dadurch leider hinfällig.
Hmmm ... so etwas hatte ich fast schon befürchtet. Kannst du mir noch
sagen, wo man das lesen kann. Ich hatte den Breymann als Nachschlagewerk
verwendet, da er die STL dort recht detailliert erläutert. Aber diese
Info habe ich dort nicht gefunden.
Gibt es vielleicht im Stroustrup ein Kapitel zu diesem Thema?
(mich interessiert jetzt, warum das nicht geht)
Gruß Markus
Martin Horst
Hi,
>Rolf Magnus schrieb:
>> Markus Breuer wrote:
>>
>> ...
>
>Hmmm ... so etwas hatte ich fast schon befürchtet. Kannst du mir noch
>sagen, wo man das lesen kann. Ich hatte den Breymann als Nachschlagewerk
>verwendet, da er die STL dort recht detailliert erläutert. Aber diese
>Info habe ich dort nicht gefunden.
>Gibt es vielleicht im Stroustrup ein Kapitel zu diesem Thema?
>(mich interessiert jetzt, warum das nicht geht)
>
>Gruß Markus
Referenzen sind in C++ statisch gebunden und müssen immer gebunden sein.
Es sind also eher Namenshalter. Der Compiler kann sogar Referenzen komplett
entfernen und durch das eigentlich Objekt ersetzen. Wie soll das bei dynamischen
Containern dann noch funktionieren.
Schreibe mal in deinem Programm:
MyObjekt &obj;
Der Compiler wird das anmeckern
Gruß
Martin
Rolf Magnus
> Rolf Magnus schrieb:
>> Markus Breuer wrote:
>>
>>
>>>Ich möchte eine Liste von Objekten Indizieren. Die Objekte sind in
>>>einem Standardcontainer std::list abgelegt. Zwecks Sortierung sollen
>>>einzelne Komponenten der Objekte als Schlüssen für eine std::map
>>>herangezogen werden. Beispiel:
>>>
>>>struct Object {
>>> TYPE1 t1;
>>> TYPE2 t2;
>>> TYPE3 t3;
>>>};
>>>
>>>std::list<Object> m_liste;
>>>
>>>Da die Objekte sehr teuer sind, möchte ich keine Kopien anlegen.
>>>Daher folgende Idee:
>>>
>>>std::map< Object&, std::list<Object>::iterator > m_dictionary;
>>
>>
>> Geht nicht. Referenzen können nicht in Containern gespeichert werden.
>> Der Rest deiner Argumentation wird dadurch leider hinfällig.
>
> Hmmm ... so etwas hatte ich fast schon befürchtet. Kannst du mir noch
> sagen, wo man das lesen kann. Ich hatte den Breymann als
> Nachschlagewerk verwendet, da er die STL dort recht detailliert
> erläutert. Aber diese Info habe ich dort nicht gefunden.
> Gibt es vielleicht im Stroustrup ein Kapitel zu diesem Thema?
Hab mal gesucht, aber nichts gefunden.
> (mich interessiert jetzt, warum das nicht geht)
Ein Grund ist schon mal, daß man einer Referenz nichts zuweisen kann,
was aber für die Container Voraussetzung ist. Außerdem wird z.B. bei
einem insert eine Referenz auf das Objekt übergeben, und Referenzen auf
Referenzen gibt es nicht. Generell sind Referenzen auch keine richtigen
Objekte, können z.B. nicht mit new erstellt werden, da sie offiziell
keinen Speicher belegen, sondern nur andere Namen für existierende
Objekte sind.
Olaf Krzikalla
Markus Breuer wrote:
> Ich möchte eine Liste von Objekten Indizieren. Die Objekte sind in einem
> Standardcontainer std::list abgelegt. Zwecks Sortierung sollen einzelne
> Komponenten der Objekte als Schlüssen für eine std::map herangezogen
> werden. Beispiel:
>
> struct Object {
> TYPE1 t1;
> TYPE2 t2;
> TYPE3 t3;
> };
>
> std::list<Object> m_liste;
>
> Da die Objekte sehr teuer sind, möchte ich keine Kopien anlegen. Daher
> folgende Idee:
>
> std::map< Object&, std::list<Object>::iterator > m_dictionary;
>
> Die Objekte werden als Referenz gespeichert, die Erzeugungskosten dafür
> sind vergleichsweise niedrig, der Platzbedarf entspricht dem eines
> Pointers. Der value_type ist ein iterator in die Liste. Desweiteren ist
> sichergestellt, dass die Operationen Einfügen und Löschen stets auf
> beide Container ausgeführt werden, d.h. die map verweist niemals auf ein
> Element, dass in der list nicht vorhanden ist. Umgekehrt besitzt jedes
> Listenelement einen Eintrag in der map.
Unabhängig von Deinen Fragen mal eine Designanmerkung: Manchmal (und
IMHO liegt hier so ein Fall vor) ist es sowohl programmtechnisch besser
als auch effizienter, eine intrusive Map zu verwenden. Ich habe letztens
mal selbst sowas programmiert, da originaler C-Code um ein vielfaches
schneller als der daraus resultierende STL-C++-Code war - eben weil in C
viel mit intrusiven Listen etc. gearbeitet wird. Ich denke, dass
C++-Programme an dieser Stelle noch ganz erhebliche Effizienzreserven
haben. Nur leider kenne ich keine state-of-the-art-Bibliotheken für
intrusive Maps bzw. Listen. Eine hatte ich im Netz gefunden, aber die
arbeitete mit Makros bis zum Erbrechen - schön war das nicht. Ich mußte
mir letztendlich mein eigenes (sehr pragmatisches) Gerüst basteln.
Werden generische intrusive Container auch von anderen hier vermißt?
MfG
Olaf Krzikalla
Markus Breuer
> was aber für die Container Voraussetzung ist. Außerdem wird z.B. bei
> einem insert eine Referenz auf das Objekt übergeben, und Referenzen auf
> Referenzen gibt es nicht. Generell sind Referenzen auch keine richtigen
> Objekte, können z.B. nicht mit new erstellt werden, da sie offiziell
> keinen Speicher belegen, sondern nur andere Namen für existierende
> Objekte sind.
Ursprünglich sollte es das Ziel sein, einen Verweis als key-type in der
map zu verwenden. Kopien der Objekte sind zu teuer und einfache Zeiger
haben eigene Vergleichsoperatoren, mit ihnen kann man (zumindest als
key) nicht die Operatoren des dahinterliegenden Objekts aufrufen. Da
eine Referenz praktisch nichts anderes als ein Zeiger ist (dachte ich),
aber implizit die richtigen Operatoren, dachte ich, dieser Weg ist richtig.
Nun bin ich ja eines besseren belehrt worden :)
Stattdessen werde ich jetzt einen günstigen Wrapper/Adapter verwenden!
Gruß Markus
Markus Schaaf
> Unabhängig von Deinen Fragen mal eine Designanmerkung: Manchmal (und
> IMHO liegt hier so ein Fall vor) ist es sowohl programmtechnisch besser
> als auch effizienter, eine intrusive Map zu verwenden. Ich habe letztens
> mal selbst sowas programmiert, da originaler C-Code um ein vielfaches
> schneller als der daraus resultierende STL-C++-Code war - eben weil in C
> viel mit intrusiven Listen etc. gearbeitet wird. Ich denke, dass
> C++-Programme an dieser Stelle noch ganz erhebliche Effizienzreserven
> haben. Nur leider kenne ich keine state-of-the-art-Bibliotheken für
> intrusive Maps bzw. Listen. Eine hatte ich im Netz gefunden, aber die
> arbeitete mit Makros bis zum Erbrechen - schön war das nicht. Ich mußte
> mir letztendlich mein eigenes (sehr pragmatisches) Gerüst basteln.
> Werden generische intrusive Container auch von anderen hier vermißt?
Ich denke, man hätte das Interface der vorhandenen Container gleich so
gestalten können, daß es sich für "intrusive" Varianten eignet.
Markus Breuer
> IMHO liegt hier so ein Fall vor) ist es sowohl programmtechnisch besser
> als auch effizienter, eine intrusive Map zu verwenden. Ich habe letztens
> mal selbst sowas programmiert, da originaler C-Code um ein vielfaches
> schneller als der daraus resultierende STL-C++-Code war - eben weil in C
> viel mit intrusiven Listen etc. gearbeitet wird. Ich denke, dass
> C++-Programme an dieser Stelle noch ganz erhebliche Effizienzreserven
> haben. Nur leider kenne ich keine state-of-the-art-Bibliotheken für
> intrusive Maps bzw. Listen. Eine hatte ich im Netz gefunden, aber die
> arbeitete mit Makros bis zum Erbrechen - schön war das nicht. Ich mußte
> mir letztendlich mein eigenes (sehr pragmatisches) Gerüst basteln.
> Werden generische intrusive Container auch von anderen hier vermißt?
Mir ist der Begriff intrusiv nicht geläufig. Beim googeln habe ich
diverse Seiten gefunden, die intrusive Containern behandeln. Intrusiv
wird hier (meiner Meinung nach) im Zusammenhang mit Einbettung in die
Knoten einer Liste verwendet. Eine Liste ist demnach intrusiv, wenn ihre
Elemente die Zielobjekte enthalten, und sie ist nicht intrusiv wenn
lediglich ein Pointer uaf das Objekt verweist. Entspricht das auch
deinem Verständnis von intrusiv?
Warum ist C++ Code langsamer als der entsprechende C Code? Kannst du mir
ein kurzes Beispiel für eine intrusive Liste in C und C++ geben?
Gruß Markus
Falk Tannhäuser
>
> Ursprünglich sollte es das Ziel sein, einen Verweis als key-type in der
> map zu verwenden. Kopien der Objekte sind zu teuer und einfache Zeiger
> haben eigene Vergleichsoperatoren, mit ihnen kann man (zumindest als
> key) nicht die Operatoren des dahinterliegenden Objekts aufrufen.
'key-types' erstellen, welche den gewünschten Vergleich (z.B. der gezeigten
Objekte anstelle der Zeiger) durchführt, und diese bei der Instanzierung
der 'map' als 3. Template-Argument übergeben (bie 'set' wäre es das 2.).
(std::less<key_type> ist an dieser Stelle das Default-Argument, welches im Fall
von Zeigern zum vor dir beschriebenen, unerwünschten Verhalten führt.)
Also z.B.:
template<typename T>
struct ComparePointedObjects
{
bool operator() (T const* p1, T const* p2) const
{
assert(p1 != 0 && p2 != 0); // Optional
return *p1 < *p2;
}
};
class MyKey { ... };
// Hat einen Operator <, welcher die Anforderungen für std::map erfüllt
class MyMappedType { ... };
typedef std::map<MyKey*, MyMappedType, ComparePointedObjects<MyKey> > MyCoolMap;
Hier ist kein Wrapper erforderlich.
Falk
Olaf Krzikalla
Markus Schaaf wrote:
> Ich denke, man hätte das Interface der vorhandenen Container gleich so
> gestalten können, daß es sich für "intrusive" Varianten eignet.
Ich bin mir jetzt nicht sicher, ob ich Dich hier richtig verstehe. IMHO
eignet sich ja der Großteil des allgemeinen STL-Contrainer-Interfaces
auch für intrusive Container. Man hätte allerdings am besten von Anfang
an intrusive Container entwickeln können, auf die dann die
nicht-intrusiven Varianten problemlos hätten aufsetzen können.
MfG
Olaf Krzikalla
Olaf Krzikalla
Markus Breuer wrote:
> Mir ist der Begriff intrusiv nicht geläufig. Beim googeln habe ich
> diverse Seiten gefunden, die intrusive Containern behandeln. Intrusiv
> wird hier (meiner Meinung nach) im Zusammenhang mit Einbettung in die
> Knoten einer Liste verwendet. Eine Liste ist demnach intrusiv, wenn ihre
> Elemente die Zielobjekte enthalten, und sie ist nicht intrusiv wenn
> lediglich ein Pointer uaf das Objekt verweist. Entspricht das auch
> deinem Verständnis von intrusiv?
Ich glaube nicht. Eine intrusive Liste für einen Typ T erwartet in T die
zur Verwaltung notwendigen Elemente (z.B. zwei Zeiger 'prev' und
'next'). Intrusive Container kümmern sich im Allg. nicht um die
Speicherverwaltung.
Im Ggs. dazu akzeptieren nichtintrusive Container beliebige T's. Intern
erzeugen sie dann einen neuen Typ, der neben den Daten von T noch für
den jeweiligen Container notwendigen Verwaltungsinformationen enthält.
Für STL-Listen sähe das z.B. so aus:
template<class T>
struct node
{
node<T> *prev, *next;
T data;
};
Die Anforderungen an T unterscheiden sich sehr stark für nichtintrusive
und intrusive Container. Z.B. muß T nur für nichtintrusive Container
kopierbar sein.
> Warum ist C++ Code langsamer als der entsprechende C Code? Kannst du mir
> ein kurzes Beispiel für eine intrusive Liste in C und C++ geben?
Nehmen wir Dein Problem. Im Prinzip sieht Deine C++-Lösung so aus:
struct Objekt
{
//...
};
std::list<Objekt> geordnete_liste;
std::multiset<std::list<Objekt>::iterator, compare> zweite_ordnung;
D.h., Deine Objekte habe in der List eine determinierte, erhaltenswerte
Ordnung. Außerdem brauchst Du jetzt noch eine zweite Ordnung, die durch
das multiset mit einem entsprechenden Vergleichsobjekt festgelegt wird.
Das multiset braucht zur Verwaltung jetzt natürlich auch Speicher, was
im Endeffekt auch auf weitere Allokationen hinausläuft. Außerdem hast Du
natürlich einige Arbeit, wenn etwas aus 'geordnete_liste' entfernt wird.
Wenn Du nun soundso weißt, dass Deine Objekte noch mindestens eine
zweite Ordnung haben, könnte man die dazu notwendigen
Verwaltungsinformationen auch gleich in den Typ Objekt mit aufnehmen:
struct Objekt
{
intrusive_multiset_info<Objekt, intrusive_trait> info;
//...
};
std::list<Objekt> geordnete_liste;
intrusive_multiset<Objekt, intrusive_trait, compare> zweite_ordnung;
Die Klasse intrusive_multiset bietet das gleiche Interface wie multiset
an. Nur wird intern nichts gespeichert, sondern es werden zur Verwaltung
die info-Felder der Klasse Objekt genutzt (über intrusive_trait). Das
hat zwei Vorteile:
- Es ist effizienter, da die zusätzlichen Allokationen durch
std::multiset wegfallen.
- Es ist sicherer, da intrusive_multiset_info natürlich auch einen
entsprechenden d'tor besitzt, der ein Element beim Ableben automatisch
aus dem multiset entfernt. D.h., Du hast keine Zusatzarbeit, wenn etwas
aus geordnete_liste entfernt wird.
Dem stehen natürlich auch einige Nachteile gegenüber:
- Objekt muß auf die Aufnahme in einen intrusiven Container vorbereitet
sein
- mit Instanzen vom Typ Objekt muß man sehr pfleglich umgehen, da durch
die intrusive_info das Objekt eine Art Identitätssemantik erhält.
Insbesondere ist es schwierig bis unmöglich, einen allgemein
funktionierenden copy-c'tor für
intrusive_info's zu schreiben. Daraus folgt auch, dass Objekt in einem
std::vector nur dann gut aufgehoben ist, wenn in diesem garantiert keine
Reallokationen stattfinden.
In C ist das ganze jetzt einfach nicht so stark gekapselt. Da sieht man
dann häufig soetwas:
struct Objekt
{
Objekt *prev, *next;
Objekt *prev_zweite_ordnung, *next_zweite_ordnung;
//...
};
und entsprechend viel - fast doppelten - Code dazu, der dann über die
jeweilige Ordnung operiert.
Hth
Olaf Krzikalla
Moritz Kaiser
> Ich möchte eine Liste von Objekten Indizieren. Die Objekte sind in einem
> Standardcontainer std::list abgelegt. Zwecks Sortierung sollen einzelne
> Komponenten der Objekte als Schlüssen für eine std::map herangezogen
> werden. Beispiel:
>
> struct Object {
> TYPE1 t1;
> TYPE2 t2;
> TYPE3 t3;
> };
>
> std::list<Object> m_liste;
>
> Da die Objekte sehr teuer sind, möchte ich keine Kopien anlegen. Daher
> folgende Idee:
>
> std::map< Object&, std::list<Object>::iterator > m_dictionary;
>
>
Was du bei all deinen Überlegungen nicht erwähnt hast, ist, was während
ihrer Existenz mit all den "Objekt"en passiert. Ein Grund warum es gar
nicht gut wäre, wenn man in assoziativen Conainern Referenzen als
Schlüssel verwenden würde, ist, dass die Schlüssel konstant sein müssen,
damit die Sortierung des Containers (hier map<>) erhalten bleibt. Aber
selbst, wenn du als Schlüssel eine konstante Referenz verwendest, lässt
sich nicht verhindern, dass das "Originalobjekt" vielleicht nicht
konstant ist und hinterrücks durch Änderung seines Inhalts die
Sortierung deiner map zerstört.
Ich frage mich allerdings, warum du überhaupt zusätzlich zur map noch
die Liste brauchst, oder hab' ich da was übersehen?
Viele Grüße,
Moritz
Markus Schaaf
> Ich bin mir jetzt nicht sicher, ob ich Dich hier richtig verstehe. IMHO
> eignet sich ja der Großteil des allgemeinen STL-Contrainer-Interfaces
> auch für intrusive Container. Man hätte allerdings am besten von Anfang
> an intrusive Container entwickeln können, auf die dann die
> nicht-intrusiven Varianten problemlos hätten aufsetzen können.
So meinte ich's.