Position in list

Hallo,
ich habe da folgendes Problem: Ich hab eine Liste die ich ordne (mit list::sort()) und dann habe ich ein iterator auf ein Object in diesrer list. Nun muss ich möglichst schnell die Position dieses Objectes heraus finden.

Ich habe ein wenig nachgedacht und bin zum Schluss gekommen, dass der schnellst Weg wäre meinem Object ein int hinzuzufügen das beim einfügen am Ende die Position des Objects erhalten würde (also size()-1). Beim orden müsste dann allerdings wenn 2 Object die Position wechseln auch die Positionen gewechselt werden. Gibt es da irgend ein Trick in der STL um eine art Austausch Funktion zu schreiben? oder muss ich die sort Funktion selber schreiben?

CarstenJ

Ich raffe Null...was genau willst du machen? Bist du dir sicher, dass eine Liste das Optimale ist? Hast du dir evtl. mal Vector angeguckt?

Entyl_Sa

Wenn du die Funktion zum Tauschen der Objekte selber schreibst dann sollte das ganze ja kein Problem sein. Wenn nicht, dann lass doch einfach direkt nach dem sortieren eine Funktion über die Liste laufen die die Elemente wieder richtig nummeriert, das sollte ja auch einfach sein.

Gruß Entyl Sa

Ich raffe Null...was genau willst du machen?

Also ich habe eine unbestimmte Anzahl von Objecten des gleichen Types. Für diesen Typ habe ich den operator< überladen. Nun muss ich ganz schnell feststellen können welches Object das kleinste ist, welches an Stelle 2, Stelle 3, etc. So nun hatte ich mir folgendes gedacht: Ich würde pointer auf diese Objecte in eine list packen und jedes Object erhält ein iterator auf den Pointer der auf es zeigt. Jetzt würde ich die Liste sortiren. Nun muss ich einen weg finden um die Position des Pointers in der List herauszufinden. Ich brauch keinen random Zugriff auf die Pointer in der List, sondern ich habe ein iterator auf den Pointer und muss herausfinden an welcher Position in der list er steht.

Bist du dir sicher, dass eine Liste das Optimale ist? Hast du dir evtl. mal Vector angeguckt?

Ein Vector hat a) keine sort Funktion und b) kann man auch nicht wenn man nur den iterator hat die Position im Vector feststellen.
map, set, deque gehen nicht da die Position nach dem einfügen verändert werden kann (wenn ich die list geordnet habe werden die Positionen nicht verändert, bis, dass ich sie nicht mehr brauche).

Wenn du die Funktion zum Tauschen der Objekte selber schreibst dann sollte das ganze ja kein Problem sein.

Wie geht das? Das wäre genau was ich brauche.

Wenn nicht, dann lass doch einfach direkt nach dem sortieren eine Funktion über die Liste laufen die die Elemente wieder richtig nummeriert, das sollte ja auch einfach sein.

Wäre auch ne Möglichkeit, hätte ich selber drauf kommen können. Danke

Taurin

std::vector vec;
// vec füllen
std::sort(vec.begin(), vec.end());

Das geht schon mal.

Und warum nicht nach dem sortieren einmal die Liste / den Vector von vorne
nach hinten durchlaufen und jedes Element mit dem Iterator vergleichen. Unter
Umständen könnte auch std::find dein Freund werden.

Entyl_Sa

Irgendwer schrieb:

Wenn du die Funktion zum Tauschen der Objekte selber schreibst dann sollte das ganze ja kein Problem sein.

Wie geht das? Das wäre genau was ich brauche.

Wird dir nicht gefallen was ich mir dabei gedacht habe, ich ging naemlich davon aus das man das machen kann wen man die sort Funktion selber schreibt.

Wird dir nicht gefallen was ich mir dabei gedacht habe, ich ging naemlich davon aus das man das machen kann wen man die sort Funktion selber schreibt.

Trotzdem danke auch wenn es nicht geht.

Wenn nicht, dann lass doch einfach direkt nach dem sortieren eine Funktion über die Liste laufen die die Elemente wieder richtig nummeriert, das sollte ja auch einfach sein.

Dann werde ich es so machen.

Ok Problem gelöst danke.

RHBaum

vielleicht solltest dir mal std::set anschauen ?

das dritte element z.B. holst da recht einfach in dem das erste holst (begin() ) und 2 mal weiterrueckst.
Ausserdem ist die suche nach bestimmten elementen sehr schnell.
Da die sortierung beim hinzufuegen/entfernen erledigt wird, einfuegen / loeschen natuerlic klein wenig langsamer, du ersparst dir aber dadurch den explizieten sortiervorgang.

Nen vector wuerd ich da vielleicht nicht nehmen, den Index nur wegen der Soerierung halten ? Ausserdem ist speicherverwaltung bisserl anders beim vector. kann bei groesseren mengen hinzufuegen etc zu performanceverlust fuehren !

Ciao ...