C++ Pointer in Container

[Mr.Seymour Buds]

Hallo,

ich habe folgendes Problem:

Ich habe einen Container (std vector) und in diesem Container liegen Pointer auf (dicke) Objekte. Der Container soll nun ziemlich dynamisch arbeiten, also es sollen ständig Pointer aus diesem Container herausgelöscht bzw. neue Pointer hinzugefügt werden.

Zum Löschen der Pointer habe ich eine kurze Funktion geschrieben. In der Parameterliste der Funktion wird der Funktion bekannt gemacht, welcher Pointer denn nun gelöscht werden soll. Dazu wird der Funktion eine Referenz (&DickesObjektA) übergeben, dann iteriere ich über alle Elemente des Containers und Vergleiche die String-ID jedes Objekt-Pointers mit der String-ID der Referenz (die Objekte haben alle eine ID). In genau einem Fall ist diese ID identisch. Dieses Element wird dann einfach mit containerDingsBums.erase(iterator) gelöscht. Damit ist das Löschen erledigt. Funktioniert soweit gut.

Für das Einfügen eines neuen Pointers nutze ich einfach Push-Back.

Meine Frage lautet nun:

Gibt es einen besseren Ansatz für die Löschfunktion. Also die Vorgehensweise im Allgemeinen. Weil meine Sorge ist, dass mein String-ID Vergleich sehr langsam werden kann, wenn ich sehr viele Pointer in dem Container liegen habe. Welche anderen Ansätze gibt es für sowas? Wie kann ich auf performante Art und Weise herausfinden, welcher Pointer für ein vorgegebenes Objekt in dem Vector zu löschen ist?

Beste Grüße

 

[Kagee]

damit ein Eintrag schnell gefunden werden kann, sollte die Datenstruktur, die die Liste der Einträge verwaltet sortiert vorliegen. Da dies ein generisches Problem ist, gibt es dafür bereits Ansätze:

http://en.cppreference.com/w/cpp/container

Da du ausschließlich eindeutige und einzigartige Objekte (Zeiger) verwaltest, ist der direkte Ansatz ein set anzulegen.
http://en.cppreference.com/w/cpp/container/set
Dort gibt es auch Infos zu Implementierung (hier red-black trees) und deren Verhalten gegen große Datenmengen.

 

[SoDaTierchen]

Du könntest eine Int-ID vergeben. Ist zwar weniger Intuitiv, spart aber die String-Operationen. Das ist aber eher Höchstoptimierung und wird zeitkritische Anwendungen nicht vorwärts bringen. Du vergleichst ja nicht permanent. Auch ist der String-Vergleich nicht unbedingt langsam - nur langsamer. Wenn du etwa 2 Milliarden Operationen pro Sekunde ausführen kannst (realistische Untergrenze, toppen schon viele Handys heutzutage), wird ein String-Vergleich über 12 Zeichen nur 13 Operationen fressen - ein lächerlich geringer Anteil.

Auch ist dein Löschen fragwürdig. Soll nur der Pointer verschwinden, oder das ganze Objekt? Letzteren Fall hast du nämlich mit Erase nicht abgedeckt.

Ein Alternativer Ansatz ist eine Art Hashing. Also das Verwaltungsobjekt, was die Pointer vergibt, sucht und entfernt merkt sich einfach jeden Pointer. So kannst du in konstanter Zeit löschen, weil du nur den Pointer selbst entfernen musst, und nicht erst suchen. Du speicherst nicht welchen Pointer du hast, sondern auch wo du ihn hast. Das ist aber theoretisch und hängt sehr vom Kontext ab. Und keine Sorge wegen des zusätzlichen Speichers bei der Merk-Methode: In einen KB Speicher passen 256 Pointer/Positions-Paare, wenn du bei Integer bleibst

 

[the_nobs]

Genau dafür gibt es ja Maps mit einer Key-Value beziehung
der Key ist der String, Value ist der Pointer

 

[Blublah]

Ja, Map mit ID Key und Zeigern auf Objekte. Wenn spezielle Sortierung nötig, dann optional noch mit einem eigenem Komparator (scheint bei dir nicht der Fall zu sein).

Könnte die ID auch ein Integer sein? Das wäre schneller.

Iterieren durch das Set ist allerdings etwas langsamer als beim vector. Suchen allerdings viiiiiiel schneller (je mehr Elemente drin sind desto groösser ist der Geschwindigkeitsvorteil).

Falls oft schnelles iterieren ohne Änderung an dem Containerinhalt wichtig ist, dann könnte man auch noch extra einen temporären Vektor (Grösse ist schon bekannt) mit Zeigern nur zum durchiterieren anlegen und bei der nächsten Änderung wieder löschen.

 

[Mr.Seymour Buds]

Damit ein Eintrag schnell gefunden werden kann, sollte die Datenstruktur, die die Liste der Einträge verwaltet sortiert vorliegen. Da dies ein generisches Problem ist, gibt es dafür bereits Ansätze:

http://en.cppreference.com/w/cpp/container

Da du ausschließlich eindeutige und einzigartige Objekte (Zeiger) verwaltest, ist der direkte Ansatz ein set anzulegen.
http://en.cppreference.com/w/cpp/container/set
Dort gibt es auch Infos zu Implementierung (hier red-black trees) und deren Verhalten gegen große Datenmengen.

Okay, Danke für den Input. Ich habe bisher nur den std::vector benutzt. Ich werde mir mal die anderen Container ansehen und das mit dem Set ausprobieren. Sets habe ich allerdings bisher noch nie verwendet.

Du könntest eine Int-ID vergeben. Ist zwar weniger Intuitiv, spart aber die String-Operationen. Das ist aber eher Höchstoptimierung und wird zeitkritische Anwendungen nicht vorwärts bringen. Du vergleichst ja nicht permanent. Auch ist der String-Vergleich nicht unbedingt langsam - nur langsamer. Wenn du etwa 2 Milliarden Operationen pro Sekunde ausführen kannst (realistische Untergrenze, toppen schon viele Handys heutzutage), wird ein String-Vergleich über 12 Zeichen nur 13 Operationen fressen - ein lächerlich geringer Anteil.

Ich entnehme dem Text mal, dass der Stringvergleich auch schon relativ schnell ist. Zeitlich hochkritisch ist die Anwendung nicht.

Auch ist dein Löschen fragwürdig. Soll nur der Pointer verschwinden, oder das ganze Objekt? Letzteren Fall hast du nämlich mit Erase nicht abgedeckt.

Nur der Pointer in dem Container soll gelöscht werden. Hintergrund ist, dass ich in regelmäßigen Abständen den Inhalt des Containers abfrage, damit ich weiss, welche Pointer gerade "zu besuch" sind (bzw. welche Objekte). Die Objekte selbst sollen nicht gelöscht werden. Das passiert in einer speziellen Verschrottungsroutine die den Standard-Destruktor aufruft. Ich bewege die Objekte mit Absicht nicht, weil die Pointer leichter sind, als die Objekte selbst.

Ein Alternativer Ansatz ist eine Art Hashing. Also das Verwaltungsobjekt, was die Pointer vergibt, sucht und entfernt merkt sich einfach jeden Pointer. So kannst du in konstanter Zeit löschen, weil du nur den Pointer selbst entfernen musst, und nicht erst suchen. Du speicherst nicht welchen Pointer du hast, sondern auch wo du ihn hast. Das ist aber theoretisch und hängt sehr vom Kontext ab. Und keine Sorge wegen des zusätzlichen Speichers bei der Merk-Methode: In einen KB Speicher passen 256 Pointer/Positions-Paare, wenn du bei Integer bleibst

Verwaltungsobjekt, was die Pointer vergibt. Das habe ich so noch gar nicht, klingt aber sehr gut. Vielleicht sollte ich so ein Objekt entwerfen...

Ergänzung (6. November 2013)

Genau dafür gibt es ja Maps mit einer Key-Value beziehung
der Key ist der String, Value ist der Pointer

Gut, die Map werde ich auch ausprobieren.

Ja, Map mit ID Key und Zeigern auf Objekte. Wenn spezielle Sortierung nötig, dann optional noch mit einem eigenem Komparator (scheint bei dir nicht der Fall zu sein).

Spezielle Sortierung muss erstmal nicht sein.

Könnte die ID auch ein Integer sein? Das wäre schneller.

Ja, die ID könnte auch ein Interger sein. Ich würde die Basisklasse der Objekte dann um einen ID-Stempel für jedes Objekt ergänzen.

Iterieren durch das Set ist allerdings etwas langsamer als beim vector. Suchen allerdings viiiiiiel schneller (je mehr Elemente drin sind desto groösser ist der Geschwindigkeitsvorteil).

Falls oft schnelles iterieren ohne Änderung an dem Containerinhalt wichtig ist, dann könnte man auch noch extra einen temporären Vektor (Grösse ist schon bekannt) mit Zeigern nur zum durchiterieren anlegen und bei der nächsten Änderung wieder löschen.

Vector schnell im Iterieren, Set/Map schnell im Suchen. Okay.

Ich programmieren noch nicht so lange C++. Und bisher habe ich "nur" Simulationen programmiert, da waren Objekte *relativ* unwichtig. Da gings mehr um die eigentlich numerische Berechnung (99,9999% der Laufzeit). Jetzt will ich halt mehr zu Objektinteraktion lernen und programmieren, deswegen diese Pointerfrage.

 

[Blublah]

Set hat nur ein Datenelement und wird verwendet wenn Schlüssel und Daten identisch sind. Wenn der Schlüssel verschieden ist, dann braucht man eine Map die ein 'Pair' aus Schlüssel+Daten aufnimmt. Dies ist bei dir der Fall denn dein Schlüssel ist die ID und das Datenelement ist der Objektzeiger.

Intern verwenden Set und Map den gleichen Algorythmus (normalerweise Red-Black Tree in STL) zum einsortieren und suchen der Daten.

 

[Mr.Seymour Buds]

Gut, die Map werde ich implementieren. Allerdings schaffe ich das heute nicht mehr und am Wochenende bin ich auf Reise. Besten Dank für die Ideen. Wenn noch jemand andere Vorschläge hat, kann er die ja posten. Grüßle

 

[antred]

Ich würde dir erst mal dazu raten, den intuitivsten Ansatz zu implementieren und dich eventuellen Optimierungen erst dann zuzuwenden, wenn sich zeigt, daß dein Programm Performance-Probleme zeigt (und du mittels Profiling nachweisen kannst, daß es auch wirklich an deinem Pointer-Container liegt).

Einen kleinen Tipp möchte ich dir aber nach zum Entfernen eines Pointers aus deinem vector geben. Sei dir bewußt, daß das Entfernen eines Elements aus einer Position ungleich dem hinteren Ende des vectors suboptimal sein kann. Schließlich müssen dazu alle Elemente, die hinter dieser Position liegen, um eine Position "nach vorn geshiftet" werden. Da kann es bessern sein, erst das hinterste Element des vectors an die Position zu schieben, die eigentlich entfernt werden sollte, und dann einfach mit pop_back() das hinterste Element fallen zu lassen.

Und natürlich wäre es eventuell gut (wie bereits erwähnt), den vector immer im sortierten Zustand zu halten ... dann könnte das Suchen schneller gehen.

 

[the_nobs]

Ich würde dir erst mal dazu raten, den intuitivsten Ansatz zu implementieren und dich eventuellen Optimierungen erst dann zuzuwenden, wenn sich zeigt, daß dein Programm Performance-Probleme zeigt (und du mittels Profiling nachweisen kannst, daß es auch wirklich an deinem Pointer-Container liegt).

Das kann ich nur bestätigen
nicht das du Tage an Aufwand in Optimierung reinsteckst die überhaupt gar nicht das Probelm waren.

Unterschätz nicht wie schnell computer heutzutage sind. Falls du also nur dutzend oder hunderte Pointer hast, und dur nicht gerade 1000x pro sekunde suchen musst. ist der Unterschied zwischen Vector und Map messbar, aber für einen Menschen nicht merkbar.

Das lässt sich aber recht gut profilen, durch die Ticks Messungen.

 

[Blublah]

Statt einem Vector eine Map zu verwenden ist eine kleine Änderung die vielleicht 1 Stunde Arbeit macht je nachdem wie viel man sie benutzt.

Und egal ob die Performance jetzt an der Stelle eine grosse Rolle spielt, sollte man für ein Problem immer möglichst die passendste Lösung verwenden denke ich, jedenfalls solange der Implementierungsaufwand praktisch identisch ist wie in diesem Fall.

Der eigentlich Code dürfte sogar verständlicher und kürzer werden da z.B. statt der Sucherei im Vector eine simple Map-Abfrage verwendet werden kann.

 

[geisterfahrer]

Zum Löschen der Pointer habe ich eine kurze Funktion geschrieben. In der Parameterliste der Funktion wird der Funktion bekannt gemacht, welcher Pointer denn nun gelöscht werden soll. Dazu wird der Funktion eine Referenz (&DickesObjektA) übergeben, dann iteriere ich über alle Elemente des Containers und Vergleiche die String-ID jedes Objekt-Pointers mit der String-ID der Referenz (die Objekte haben alle eine ID). In genau einem Fall ist diese ID identisch. Dieses Element wird dann einfach mit containerDingsBums.erase(iterator) gelöscht. Damit ist das Löschen erledigt. Funktioniert soweit gut.

Du hast eine Referenz auf das zu suchende Objekt? Dann vergleich doch lieber die Speicheradressen! Also einfach den Pointer löschen, der auf die gleiche Adresse zeigt, wie die Adresse der übergebenen Referenz. Dein komliziertes Vorgehen wäre ja nur nötig, wenn man nur die ID des zu löschenden Objektes hättest, aber wenn du eine Referenz auf das richtige Objekt hast, spricht nichts dagegen die Speicheradressen zu nehmen.

Ansonsten: Um halbwegs vernünftige Vermutungen anstellen zu können, was für Performance Auswirkungen irgendeine bestimmte Veränderung hat, braucht man eine Menge Wissen. Da dieses bei dir aber begrenzt vorhanden zu sein scheint, würde ich von Optimierungen dringend abraten.

 

[Mr.Seymour Buds]

Den Vergleich der Speicheradressen hatte ich auch schon programmiert. Ich erinnere mich, dass dabei ein Compilerfehler geworfen worden ist. Als ich es heute wieder probiert habe, gings...

Naja wie dem auch sei, wenns interessiert hier nochmal der (einfache) Code (RegisterA, DickesObjekt = Klassen; std::vector<class DickesObjekt *> _ObjekteInRegister = Public Member von RegisterA):

void RegisterA::ObjektAbgeben(class DickesObjekt &raus)
{
	for (std::vector<DickesObjekt *>::iterator it(_ObjekteInRegister.begin()); 
		it != _ObjekteInRegister.end(); ++it)
	{
		cout << " Speicheradresse Referenz: " << &raus << endl;
		cout << " Speicheradresse Pointer: "  << *it   << endl;
		cin.get();

                // Vergleich Referenz mit jedem Pointer
		if ( &raus == *it )
		{
			_ObjekteInRegister.erase(it);
			break;
		}
	}
}

Danke für die Anregungen,
Beste Grüße

 

[antred]

Den Vergleich der Speicheradressen hatte ich auch schon programmiert. Ich erinnere mich, dass dabei ein Compilerfehler geworfen worden ist. Als ich es heute wieder probiert habe, gings...

Naja wie dem auch sei, wenns interessiert hier nochmal der (einfache) Code (RegisterA, DickesObjekt = Klassen; std::vector<class DickesObjekt *> _ObjekteInRegister = Public Member von RegisterA):

void RegisterA::ObjektAbgeben(class DickesObjekt &raus)
{
	vector <DickesObjekt *>::iterator it = _ObjekteInRegister.begin();
	for (std::vector<DickesObjekt *>::iterator it(_ObjekteInRegister.begin()); 
		it != _ObjekteInRegister.end(); ++it)
	{
		cout << " Speicheradresse Referenz: " << &raus << endl;
		cout << " Speicheradresse Pointer: "  << *it   << endl;
		cin.get();

                // Vergleich Referenz mit jedem Pointer
		if ( &raus == *it )
		{
			_ObjekteInRegister.erase(it);
			break;
		}
	}
}

Danke für die Anregungen,
Beste Grüße

• Das "class" in der Paramterliste kannst du dir sparen.
• Das DickesObjekt würde ich per const reference übergeben ... die Funktion nimmt ja schließlich keine Änderung an dem Objekt vor.
• Wieso hast du 2 Iteratoren namens it definiert? Die Definition außerhalb der Schleife kann weg.

Ergänzung (13. November 2013)

Oh, und sei vorsichtig mit Bezeichnern mit führenden underscores. Der C++ Standard sagt, daß globale Bezeichner mit führenden underscores für Compilerhersteller reserviert sind. Da dies aber häufig Prärprozessor-#defines sind und sich der Präprozessor einen feuchten Dreck um die Unterscheidung zwischen globalen und lokalen Symbolen kümmert, ist es ratsam, Bezeichner mit führenden underscores prinzipiell zu meiden.

 

[Mr.Seymour Buds]

• Das "class" in der Paramterliste kannst du dir sparen. (Okay)
• Das DickesObjekt würde ich per const reference übergeben ... die Funktion nimmt ja schließlich keine Änderung an dem Objekt vor. (Angepasst)
• Wieso hast du 2 Iteratoren namens it definiert? Die Definition außerhalb der Schleife kann weg. (Stimmt, habe ich übersehen. Editiert.)

Ergänzung (13. November 2013)

Oh, und sei vorsichtig mit Bezeichnern mit führenden underscores. Der C++ Standard sagt, daß globale Bezeichner mit führenden underscores für Compilerhersteller reserviert sind. Da dies aber häufig Prärprozessor-#defines sind und sich der Präprozessor einen feuchten Dreck um die Unterscheidung zwischen globalen und lokalen Symbolen kümmert, ist es ratsam, Bezeichner mit führenden underscores prinzipiell zu meiden.

Das mit den Unterstrichen habe ich bei Stackoverflow so gesehen und übernommen. Wo genau weiss ich nicht mehr. Damit klar wird, dass es sich bei den Variablen um Membervariablen handelt, habe ich den Unterstrich immer davor. Ich habe auch schon Code gesehen, wo er hinter der Variablen stand. Also z.B. int GanzeZahl_...

 

[antred]

Das mit den Unterstrichen habe ich bei Stackoverflow so gesehen und übernommen. Wo genau weiss ich nicht mehr. Damit klar wird, dass es sich bei den Variablen um Membervariablen handelt, habe ich den Unterstrich immer davor. Ich habe auch schon Code gesehen, wo er hinter der Variablen stand. Also z.B. int GanzeZahl_...

Dann lies noch mal hier, warum es keine gute Idee ist. http://stackoverflow.com/questions/...s-about-using-an-underscore-in-a-c-identifier

 

[Mr.Seymour Buds]

Ich entnehme dem Link mal, dass der Unterstrich an der ersten Stelle zwar legal ist, aber es wird empfohlen, dass man es so nicht machen sollte ("reserved").

17.4.3.2.1 Global names [lib.global.names]

Certain sets of names and function signatures are always reserved to the implementation:

Each name that contains a double underscore (_ _) or begins with an underscore followed by an uppercase letter (2.11) is reserved to the implementation for any use.
Each name that begins with an underscore is reserved to the implementation for use as a name in the global namespace.165

165) Such names are also reserved in namespace ::std (17.4.3.1).

Werde die Membervariablen dann einfach anpassen und den Unterstrich an erster Stelle löschen.

 

[antred]

Ich entnehme dem Link mal, dass der Unterstrich an der ersten Stelle zwar legal ist, aber es wird empfohlen, dass man es so nicht machen sollte ("reserved").

So isses. Genau genommen ist es zwar etwas komplexer, aber mit dieser Regel fährt man am sichersten.

 

[Mr.Seymour Buds]

Noch eine Anmerkung zu den Unterstrichen. Ich habe heute QT installiert und dabei folgendes Codestück gefunden:

#include <math.h>

class Complex
{
public:
    Complex(double re, double im)
        : _re(re), _im(im)
    {}
    double modulus() const
    {
        return sqrt(_re * _re + _im * _im);
    }
private:
    double _re;
    double _im;
};

Es gibt noch wirklich viele Quellen im Internet, in FAQs und in Programmen selbst, wo diese Unterstriche auch vor den Membervariablen eingefügt werden. Sehr Anfänger unfreundlich das Ganze und best practice sieht irgendwie auch anders aus.

 

[antred]

Ja, das ist leider so. Ich zähl schon gar nicht mehr mit, wie oft ich Header-Files sehe, die so anfangen

#ifndef __UNDERSCORES_ARE_AWESOME__I_PUT_THEM_EVERYWHERE__________
#define __UNDERSCORES_ARE_AWESOME__I_PUT_THEM_EVERYWHERE__________

...

Und es wimmelt nur so von Tutorials, die es anscheinend zum Ziel gesetzt haben, worst practice zu vermitteln (und das Unterstrich-Thema ist da häufig noch das kleinste Problem).