Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

STL: Listen mit eigenen Datentypen sortieren

  • 1
  • 2

Werbeanzeige

Anonymous

unregistriert

1

13.06.2004, 00:11

STL: Listen mit eigenen Datentypen sortieren

Hallo,

ich habe eine STL Liste (<list>) welche Zeiger auf Klasseninstanzen einer eigenen Klasse beinhaltet. Nun möchte ich die Liste sortieren, jedoch kann ich ja nicht einfach sort() anwenden, sondern muss irgendwie eine eigene Compare-Funktion, eben für meine spezielle Klasse, schreiben.

Meine Klasse beinhaltet einfach nur 3 int Variablen, und ich möchte die Liste nun nach dem 3. int Wert aufsteigend sortieren.

Weiß jemand, wie man solch eine eigene Vergleichfunktion für den Sortieralgorithmus schreibt und verwendet? Ich habe in diverse STL Manuals geschaut, leider ohne Erfolg :(

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

2

13.06.2004, 00:34

Es reicht, den "<"-Operator des Datentyps zu implementieren.
David Scherfgens Website | Konzentrationstest Polizei

Anonymous

unregistriert

3

13.06.2004, 00:55

Danke für die Antwort, leider will es nicht so ganz funktionieren. Ich habe diese einfache Klasse hier:

Quellcode

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class CEdge
{
private:

public:
    CEdge(int iNodeLeft = 0, int iNodeRight = 0, float fEdgeLength = 0.0f)
    {
        this->iNodeLeft = iNodeLeft;
        this->iNodeRight = iNodeRight;
        this->fEdgeLength = fEdgeLength;
    }
    
    ~CEdge() { }

    bool operator < (CEdge &e)  { return (fEdgeLength < e.fEdgeLength); }

    int iNodeLeft;
    int iNodeRight;
    float fEdgeLength;
};


Und ich möchte nach "fEdgeLength" sortieren, wie man in dem Operator "<" auch sehen kann.

Nun mache ich folgendes:

Quellcode

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

// Liste erstellen

list<CEdge*>* pEdgeList = new list<CEdge*>();


// (--- hier ein paar Dinge einlesen ---)


// Liste sortieren

pEdgeList->sort();


// Liste ausgeben

for(list<CEdge*>::iterator I = pEdgeList->begin(); I != pEdgeList->end(); I++)
{
    cout << "Nr. " << x << ":\t" << (*I)->iNodeLeft << " <--" << (*I)->fEdgeLength << "--> " << (*I)->iNodeRight << endl;
}


Heraus kommt z.B. diese Ausgabe:

Quellcode

 
1
2
3
4
5
6

Nr. 1:  0 <--1.41421--> 1
Nr. 2:  0 <--2.82843--> 2
Nr. 3:  1 <--1.41421--> 0
Nr. 4:  1 <--1.41421--> 2
Nr. 5:  2 <--2.82843--> 0
Nr. 6:  2 <--1.41421--> 1


Es sollte aber nach dem float Wert in der mitte sortiert sein, ist es nur leider nicht. Kannst Du mir da weiterhelfen?

Vielen Dank!

DragonMaster

Community-Fossil

Beiträge: 1 603

  • Private Nachricht senden

4

13.06.2004, 10:44

Ich denke das Problem liegt nicht an der Methode sort sondern daran das du einen Pointer als Parameter hast.

Erstelle mal die Liste, gib sie dann aus und dann sortier sie mal und dann gib sie wieder aus. Gib dabei aber auch immer die Adresse deiner Klasse mit aus. Dann wirst du das Problem schnell finden.

Intern benutzt die sort Methode nur den Inhalt des Iterators und nicht den Inhalt des Zeigers der Inhalt des Iterators ist sprich:
(*iter).[Element] und nicht
(*iter)->[Element]

Hat es einen bestimmten Grund das du statt der Instanz selber einen Zeiger auf due Instanz benutzt?
Wichtig! Ich übernehme keinerlei Verantwortung für eventl. Datenverlust oder Schäden am Rechner ;D

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

5

13.06.2004, 11:44

Übrigens solltest Du Deinen "<"-Operator anders definieren.
Es wird doch kein Objekt verändert, also solltest Du ihn "const" deklarieren, dasselbe gilt für das zweite per Referenz übergebene Objekt.
David Scherfgens Website | Konzentrationstest Polizei

Anonymous

unregistriert

6

13.06.2004, 12:52

Zitat


Erstelle mal die Liste, gib sie dann aus und dann sortier sie mal und dann gib sie wieder aus. Gib dabei aber auch immer die Adresse deiner Klasse mit aus. Dann wirst du das Problem schnell finden.


Du vermutest also, er sortiert die Adressen/Zeiger?

Zitat


Intern benutzt die sort Methode nur den Inhalt des Iterators und nicht den Inhalt des Zeigers der Inhalt des Iterators ist sprich:
(*iter).[Element] und nicht
(*iter)->[Element]


Kann man denn irgendwie erreichen, dass die sort() Methode den Inhalt des Zeigers benutzt, oder muss ich jetzt immer, wenn ich eigene Klassen sortieren will, die Objekte selbst in der Liste speichern, anstatt nur Zeiger darauf?

Zitat


Hat es einen bestimmten Grund das du statt der Instanz selber einen Zeiger auf due Instanz benutzt?


Hm, habe mal irgendwo gehört, dass man am besten immer nur Zeiger auf Objekte in Listen speichert, deswegen hatte ich das wohl intuitiv so gemacht...


Zitat


Übrigens solltest Du Deinen "<"-Operator anders definieren.
Es wird doch kein Objekt verändert, also solltest Du ihn "const" deklarieren, dasselbe gilt für das zweite per Referenz übergebene Objekt.


Danke, werde ich gleich mal ändern.

Anonymous

unregistriert

7

13.06.2004, 12:56

Ach und noch ne kleine Frage hinterher :-)
Wenn ich die Objekte selbst in der Liste speicher und keine Zeiger, dann werden die Objekte ja auf den Stack gelegt, und beim Löschen der Liste automatisch freigegeben, ist das richtig?

Jumping Jack

Treue Seele

Beiträge: 142

Wohnort: Hamburg

Beruf: Schüler

  • Private Nachricht senden

8

13.06.2004, 13:55

Zitat


dann werden die Objekte ja auf den Stack gelegt

AFAIK:
Nein, das geht eigentlich garnicht. Die Listnodes werden ja nach bedarf hinzugefügt. Das geht nur über den Heap.
Was sich ändert ist, dass in den Listnodes kein zeiger auf die instanz des objektes gespeichert ist, sondern die instanz selbst als Member im Listnode ist.

DragonMaster

Community-Fossil

Beiträge: 1 603

  • Private Nachricht senden

9

13.06.2004, 15:18

Das ist nicht nur AFIK so, das ist so ;)

Zitat

Hm, habe mal irgendwo gehört, dass man am besten immer nur Zeiger auf Objekte in Listen speichert, deswegen hatte ich das wohl intuitiv so gemacht...
Wieso sollte man denn nur Zeiger als Template Parameter verwenden? Das ist nicht Sinn und Zweck der Sache. Es macht lediglich nur dann Sinn wenn man sehr große Objekte hat. Allerdings gilt das nur für std::vector da hier die Daten oft umgeschichtet werden, was bei std::list nicht der Fall ist.

Wie auch immer bei drei Variablen a 32Bit fällt das überhaupt nicht ins Gewicht. Da ist ein Zeiger sogar schon eher nachteilig ;)
Wichtig! Ich übernehme keinerlei Verantwortung für eventl. Datenverlust oder Schäden am Rechner ;D

Jonathan_Klein

Community-Fossil

Beiträge: 3 820

  • Private Nachricht senden

10

13.06.2004, 16:15

Aber ich hatte mal Probleme damit Objekte zu speicerhn, die sich selbst anzeigen sollten. Das Objekt hatte eine Render Methode die eine Oberfläche anzeigte die die Initmethode erstellte. Das hat aber irgendwie nicht geklappt. Irgendjemand hat gemeint man müsste der Klasse so ne besondere Methode hinzufügen so was ähnliches wie ein Konstruktor oder so. Weil ich davon aber nicht so viel Ahnung hab, hab ich die Objekte mit new erstellt und die Zeiger dann in der Liste gespeichert. Dann hat ales ganz einfach funktioniert

Werbeanzeige

  • 1
  • 2