"schnelle" Datenstruktur

[Dawen]

Guten Abend/Morgen zusammen,

ich suche eine Datenstruktur zum speichern von Objekten und zwar in der Form :

Datenstruktur d;

d.add(1,object);
d.add(2,object);
d.add(3,object);

Erstes Feld soll dabei aber nicht ein eindeutiger Schlüssel oder ähnliches sein ( bei mir wird es die Anzahl an einträgen in einem object representieren ). In der Datenstruktur darf das erste Feld mehrmals vorkommen, dies ist kein Problem, die Felder sollen aber sortiert sein, wenn ich z.B. nun ein Object der Länge 2 einfüge, soll es automatisch an die richtige stelle plaziert werden.

Datenstruktur d;

d.add(1,object);
d.add(2,object);
d.add(2,object); // neues Objekt am Ende oder Anfang oder wo auch immer, wo die Felder der Länge 2 sind
d.add(3,object);

Es wird häufig eingefügt ( an jeder beliebigen Stelle ) und gelöscht ( an jeder belieben Stelle ). Die Datenstruktur ist nun mal das "Herz" von meinem Programm und vielleicht kann ich noch etwas performance rausholen, bis jetzt habe ich "nur" einen STL vector,den ich jedesmal durchlaufe, die länge von object jedem prüfe und falls es passt dann an die Stelle einfüge.

Kennt einer etwas, es muss nicht STL sein, es gibt ja noch Sachen wie boost ( und mehr ? ). Es ist ein C/C++ Programm.

Einer einen Vorlschlag ?

 

[cr]

Moins.

std::multimap ist wohl das was du suchst und ist auch automatisch sortiert. Der Unterschied zur normalen std::map ist das der erste Wert wie von dir gefordert mehrmals vorkommen darf.

http://www.cppreference.com/cppmultimap/index.html

 

[Dawen]

Multimap, sehr gut :-D das sollte erstmal ausreichen. THX

 

[mauralix]

Prinzipiell brauchst du eine Datenstruktur die mit Hashcodes arbeitet, aber auch eine Baumstruktur oder Heaps könnten geigenet sein.