C++: Wie kann ich einen Vector mit Strukturen sortieren? [gelöst]

[dakuan]

Ich erzeuge eine Datenstruktur und füge diese in einen Vecctor ein. Anschließend möchte ich diese Strukturen sortieren. Dabei stürzt mein Programm ab. Der Absturz passiert irgendwo in der Sortiermethode, sagt nemiver:

Code: Alles auswählen

  template<typename _RandomAccessIterator, typename _Compare>
    _RandomAccessIterator
    __unguarded_partition(_RandomAccessIterator __first,
			  _RandomAccessIterator __last,
			  _RandomAccessIterator __pivot, _Compare __comp)
    {
>>    while (true)
	{
	  while (__comp(__first, __pivot))
	    ++__first;
	  --__last;
	  while (__comp(__pivot, __last))
	    --__last;
	  if (!(__first < __last))
	    return __first;
	  std::iter_swap(__first, __last);
	  ++__first;
	}
    }

Das ">>" ist die Cursorposition des Debuggers. Der Absturz passiert nicht sofort.

Hier mal einige Ausschnitte aus dem umfangreichen Programmcode in der Hoffnung dass das ausreicht:

Code: Alles auswählen

typedef struct {
    char  * name;
    short   type;
    short   flags;
    long    size;
    time_t  mtime;
} fbdata_t;
...
    std::vector<fbdata_t*> name_list;
...
    static int  s_cmp( fbdata_t * dp0, fbdata_t * dp1 );

// ...

    std::sort( name_list.begin(), name_list.end(), s_cmp );
    for( unsigned it = 0; it < name_list.size(); it++ )
        add( name_list[it]->name ); // Einfügen in Fl_Browser (Ok)
...

int File_Browser::s_cmp( fbdata_t * dp0, fbdata_t * dp1 ) {
    char * s0 = dp0->name;
    char * s1 = dp1->name;
    return strcmp( s0, s1 );
}

In der Vergleichsfunktion kann ich die Strings und die komplette Struktur noch sehen. Wenn ich die Zeile mit sort() auskommentiere, werden die Namen in der Fl_Browser Klasse (von der ich abgeleitet habe) angezeigt. Dann natürlich unsortiert.

Wo könnte der Fehler liegen?

[JTH]

Wie bei allen Fragen : Wie ist die genaue „Fehlermeldung“, also was heißt für dich Absturz? Segfault, hängt dein Programm in einer Endlosschleife oder …? Das hilft auch hier beim Eingrenzen einer Fehlerursache.

Die Vergleichsfunktion, die man std::sort übergibt, soll einen boolschen Wert zurückgeben, keinen dreiwertigen wie es strcmp macht. Der Rückgabewert soll wahr sein, wenn das erste Vergleichsargument vor dem zweiten einsortiert werden soll (bzw. korrekt: das erste kleiner ist als das zweite). Das könntest du hier z.B. so machen:

Code: Alles auswählen

int File_Browser::s_cmp( fbdata_t * dp0, fbdata_t * dp1 ) {
    …
    return strcmp( s0, s1 ) < 0;
}

So wie du es geschrieben hast, wird der int-Rückgabewert von strcmp zwar auch implizit zu einem bool konvertiert. Du hast damit als Vergleichsfunktion aber nur einen Vergleich auf Gleichheit (<0 und >0 werden zu true, ==0 wird zu false) von fbdata_t::name, keinen Vergleich auf „kleiner als“. Sortieren nur mit Vergleich auf Gleichheit klappt aber nicht, reicht nicht für eine Ordnung. Eventuell – ohne wie gesagt den genauen „Absturz“ zu kennen – bringt das also den Sortieralgorithmus durcheinander bzw. führt zu einer Endlosschleife.

[dakuan]

Danke für die schnelle Antwort.

Wie bei allen Fragen : Wie ist die genaue „Fehlermeldung“, also was heißt für dich Absturz?

Der Absturz sieht so aus:

Code: Alles auswählen

manfred@samurai:~/prog/img/vted2$ ./vted
Speicherzugriffsfehler (Speicherabzug geschrieben)
manfred@samurai:~/prog/img/vted2$

Der Coredump ist übrigens nicht vorhanden. Den müsste ich erst mit ulimit aktivieren, was ich mir aber schenke, da nemiver den nicht wirklich brauchbar auswerten kann. ddd ist da besser, funktioniert in der aktuellen Version aber nicht wirklich gut.

Aber die Änderung auf:

Code: Alles auswählen

    return strcmp( s0, s1 ) < 0;

scheint tatsächlich den Fehler zu beheben. Den Trick kannte ich noch nicht. Suchmaschinen haben mir immer nur Beispiele mit Integer Variablen angeboten, die einfacher gestaltet sind.

Ich werde das mal mit den geplanten weiteren Sortiekriterien testen. Außerdem muss ich jetzt untersuchen, warum ein vorheriges Programm funktioniert. Möglicherweise tickt da eine Zeitbombe.

[Meillo]

Der Absturz sieht so aus:

Code: Alles auswählen

manfred@samurai:~/prog/img/vted2$ ./vted
Speicherzugriffsfehler (Speicherabzug geschrieben)
manfred@samurai:~/prog/img/vted2$

Der Coredump ist übrigens nicht vorhanden. Den müsste ich erst mit ulimit aktivieren, was ich mir aber schenke, da nemiver den nicht wirklich brauchbar auswerten kann. ddd ist da besser, funktioniert in der aktuellen Version aber nicht wirklich gut.

Warum ist der Coredump nicht vorhanden, wenn der Kernel ausgibt, dass der ``Speicherabzug geschrieben'' worden ist? Oder ist die Meldung von nachdem du Coredumps mit ulimit aktiviert hast?

Warum soll der Coredump nicht brauchbar sein? Den kann man doch mit dem Debugger einlesen und dann sieht man an welcher Stelle genau der Segfault passiert. Dafuer reicht gdb aus. (Oder uebersehe ich etwas?)

[dakuan]

Warum ist der Coredump nicht vorhanden, wenn der Kernel ausgibt, dass der ``Speicherabzug geschrieben'' worden ist?

Ich habe hier einige PCs am laufen. Und das war auf einem Ubuntu PC. Ich dachte das ist überall gleich. Jedenfalls kann ich die Binaries, wenn sie überhaupt funktionieren, zwischen beiden Systemen ohne Probleme lustig hin und her schieben.

Warum soll der Coredump nicht brauchbar sein?

Ich habe nicht gesagt, dass er nicht brauchbar ist. Aber nemiver hat Probleme damit, wenn der Coredump nicht im selben Verzeichnis liegt wie der Quelltext. Und mit gdb "barfuß" tue ich mich schwer. Ich bin nicht so der Konsolen Junkie.

[eggy]

Versuch mal qtcreator als IDE, die haben ne großartige grafische GDB Einbettung.

[Meillo]

Warum soll der Coredump nicht brauchbar sein?

Ich habe nicht gesagt, dass er nicht brauchbar ist. Aber nemiver hat Probleme damit, wenn der Coredump nicht im selben Verzeichnis liegt wie der Quelltext. Und mit gdb "barfuß" tue ich mich schwer. Ich bin nicht so der Konsolen Junkie.

Es geht gar nicht darum, gross viel zu debuggen. Es reicht schon, wenn du dir mit gdb einen Stacktrace ausgeben laesst, anhand dessen du siehst, wo genau der Segfault passiert ist. Dazu rufst du gdb nur so auf:

Code: Alles auswählen

gdb <dein-programm> <corefile>

Am Prompt gibst du dann `bt' (fuer backtrace) ein. Das zeigt dir den Aufrufstack und die genaue Abbruchstelle (natuerlich musst du mit Debuggingsymbolen kompiliert haben, um lesbare Namen zu sehen, aber das sollte klar sein). Dann kannst du mit `q' beenden.

Wenn du interaktiv debuggen willst, kannst du ja ein grafisches Tool verwenden.

[dakuan]

Danke für den Tipp mit gdb. Das sollte ich mir auch ohne Spickzettel merken können.

Aber wie man oben sieht, hat Nemiver mir die ungefähre Stelle auch gezeigt, was mich anfangs gewundert hat, bis mir klar wurde, dass das ja STL ist.

Ja, und die Debuggingsymbole habe ich eigentlich immer an, wenn die Projekte so groß sind dass ich Make brauche.