Operator-Überladung für sort() bei Struct-Array

Molinman

Hi,

ich habe ein Problem mit der Operator-Überladung von <, die ich für sort() brauche, um Structs zu sortieren.

Wenn ich den Operator mit

bool operator<(const tagundinhalt& a, const tagundinhalt& b) {
	   return a.tag < b.tag;
   }

überlade, so, wie ich das aus http://www.fredosaurus.com/notes-cpp/algorithms/sorting/stl-sort-arrays.html verstanden habe, liefert mir G++ folgende "kompakte" Fehlerausgabe:

/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_iterator_base_types.h: In instantiation of ‘std::iterator_traits<tagundinhalt>’:
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_algo.h:2703:   instantiated from ‘void std::sort(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = tagundinhalt]’
./src/sortieren.cpp:22:   instantiated from here
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_iterator_base_types.h:129: error: no type named ‘iterator_category’ in ‘struct tagundinhalt’
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_iterator_base_types.h:130: error: no type named ‘value_type’ in ‘struct tagundinhalt’
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_iterator_base_types.h:131: error: no type named ‘difference_type’ in ‘struct tagundinhalt’
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_iterator_base_types.h:132: error: no type named ‘pointer’ in ‘struct tagundinhalt’
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_iterator_base_types.h:133: error: no type named ‘reference’ in ‘struct tagundinhalt’
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_algo.h: In function ‘void std::sort(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = tagundinhalt]’:
./src/sortieren.cpp:22:   instantiated from here
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_algo.h:2711: error: no match for ‘operator!=’ in ‘__first != __last’
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_algo.h:2713: error: no match for ‘operator-’ in ‘__last - __first’
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_bvector.h:182: note: candidates are: ptrdiff_t std::operator-(const std::_Bit_iterator_base&, const std::_Bit_iterator_base&)
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_algo.h: In function ‘void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = tagundinhalt]’:
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_algo.h:2714:   instantiated from ‘void std::sort(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = tagundinhalt]’
./src/sortieren.cpp:22:   instantiated from here
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_algo.h:2357: error: no match for ‘operator-’ in ‘__last - __first’
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_bvector.h:182: note: candidates are: ptrdiff_t std::operator-(const std::_Bit_iterator_base&, const std::_Bit_iterator_base&)
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_algo.h:2359: error: no match for ‘operator+’ in ‘__first + 16’
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_bvector.h:267: note: candidates are: std::_Bit_iterator std::operator+(ptrdiff_t, const std::_Bit_iterator&)
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_bvector.h:353: note:                 std::_Bit_const_iterator std::operator+(ptrdiff_t, const std::_Bit_const_iterator&)
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_algo.h:2360: error: no match for ‘operator+’ in ‘__first + 16’
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_bvector.h:267: note: candidates are: std::_Bit_iterator std::operator+(ptrdiff_t, const std::_Bit_iterator&)
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_bvector.h:353: note:                 std::_Bit_const_iterator std::operator+(ptrdiff_t, const std::_Bit_const_iterator&)
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_algo.h: In function ‘void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = tagundinhalt]’:
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_algo.h:2363:   instantiated from ‘void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = tagundinhalt]’
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_algo.h:2714:   instantiated from ‘void std::sort(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = tagundinhalt]’
./src/sortieren.cpp:22:   instantiated from here
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_algo.h:2270: error: no match for ‘operator==’ in ‘__first == __last’
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_algo.h:2273: error: no match for ‘operator+’ in ‘__first + 1’
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_bvector.h:267: note: candidates are: std::_Bit_iterator std::operator+(ptrdiff_t, const std::_Bit_iterator&)
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_bvector.h:353: note:                 std::_Bit_const_iterator std::operator+(ptrdiff_t, const std::_Bit_const_iterator&)
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_algo.h:2273: error: no match for ‘operator!=’ in ‘__i != __last’
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_algo.h:2273: error: no match for ‘operator++’ in ‘++__i’
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_algo.h:2277: error: no match for ‘operator*’ in ‘*__first’
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_algo.h:2279: error: no match for ‘operator+’ in ‘__i + 1’
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_bvector.h:267: note: candidates are: std::_Bit_iterator std::operator+(ptrdiff_t, const std::_Bit_iterator&)
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_bvector.h:353: note:                 std::_Bit_const_iterator std::operator+(ptrdiff_t, const std::_Bit_const_iterator&)
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_algo.h:2276: error: no match for ‘operator*’ in ‘*__first’

Keine schöne Sache, wie ich finde. So, wie ich das interpretiere, zerstört meine Operator-Überladung sämtliche Operator-Definitionen.

Kann mir jemand helfen?
Danke schonmal für eure Mühen!

CStoll

Zeig doch mal den Code, wo dieser Operator (bzw. die sort()-Funktion) verwendet wird. Die Fehlermeldungen deuten darauf hin, daß du die struct 'tagundinhalt' als Iterator verwendet hast.

Molinman

Servus, danke für die Antwort und sorry, dass ich jetzt erst antworte.
Ich habe mir bei dem Versuch, in mehreren Schritten meien FAt32-Partition auf ext3 umzustellen, meine Partitionstabelle zerschossen und konnte jetzt einige Tage nicht ins Internet

Hier die Funktion, die aber wohl nicht gerade viel hilft, ich fürchte, ich habe nicht ganz verstanden, was du gerne sehen würdest:

sort( tag[0], tag[MAX_STRUCT+1] );

Tatsächlich treten die beschriebenen Fehlermeldungen nicht auf, wenn ich diese sort-Anweisung auskommentiere.
Was habe ich denn bei diesem eigentlich simplen Aufruf falsch gemacht?

Edit: Falls du irgendwelche Erklärungen brauchst, was zum Beispiel die Bedeutungen und dahinterstehenden Werte von MAX_STRUCT angeht, einfach fragen. Ich weiß nicht, inwiefern sich die Daten selbst erklären oder ohnehin unwichtig sind.

.filmor

sort( &tag[0], &tag[MAX_STRUCT+1] );

Das sollte es tun. Falls tag ein Zeiger ist gehts sogar noch simpler:

sort (tag, tag + MAX_STRUCT + 1);

Falls tag ein Standardcontainer ist, solltest du folgendes verwenden:

sort (tag.begin (), tag.end ());

sort nimmt als Parameter Iteratoren. Du hast aber stattdessen ein struct übergeben (der Indexzugriff liefert immer ein Objekt zurück).

Molinman

Ah, verstehe.
Danke, das Programm läuft erstmal durch!
Das Problem ist: Nach der Sortierung ist mein Struct-Array leer.

Was sowieso meiner Meinung nach so nicht stimmen kann, ist, dass ich sort ja Adressen übergebe, von der Operator-Überladung aber keine Pointervariablen entgegengenommen werden.

Müsste die Überladung dann nicht eigentlich so aussehen:

bool operator<(const tagundinhalt *a, const tagundinhalt *b) {
	   return a.tag < b.tag;
   }

Ich komme leider mit Pointern im Zusammenhang mit Arrays und zusätzlich noch Structs noch nicht ganz klar (weswegen ich in meinem Programm statt Pointern globale Variablen verwende )

Dass es nicht so heißen muss, wie oben beschreiben, hat mir G++ mit einer ziemlichen Kraut-und-Rüben-Mitteilung klar gemacht, die in etwa so lautet:

./src/header.h:52: error: ‘bool operator<(const tagundinhalt*, const tagundinhalt*)’ must have an argument of class or enumerated type
./src/header.h: In function ‘bool operator<(const tagundinhalt*, const tagundinhalt*)’:
./src/header.h:53: error: request for member ‘tag’ in ‘a’, which is of non-class type ‘const tagundinhalt*’
./src/header.h:53: error: request for member ‘tag’ in ‘b’, which is of non-class type ‘const tagundinhalt*’
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_algo.h: In function ‘void std::partial_sort(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = tagundinhalt*]’:
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_algo.h:2630:   instantiated from ‘void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size) [with _RandomAccessIterator = tagundinhalt*, _Size = int]’
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_algo.h:2713:   instantiated from ‘void std::sort(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = tagundinhalt*]’
./src/sortieren.cpp:17:   instantiated from here

Das geht noch weiter, dies schien mir aber der wichtigste Teil zu sein.
Offensichtlich möchte die Überladung eine Klasse (bzw. einen "enumerated type", das wäre doch ein Array, oder?) sehen, mit der ich natürlich nicht dienen kann, da mein C-C++-Mischmasch ja noch Structs verwendet.

Wie komme ich hier weiter? Danke schonmal!

CStoll

Molinman schrieb:

Ah, verstehe.
Danke, das Programm läuft erstmal durch!
Das Problem ist: Nach der Sortierung ist mein Struct-Array leer.

Was sowieso meiner Meinung nach so nicht stimmen kann, ist, dass ich sort ja Adressen übergebe, von der Operator-Überladung aber keine Pointervariablen entgegengenommen werden.

sort() übernimmt Iteratoren (eine Art Verallgemeinerung von Zeigern) auf den Anfang und das Ende des zu sortierenden Bereiches. An seine Vergleichsfunktion übergibt es aber die Inhalte der zu sortierenden Elemente (Iterator- nzw. Pointer-Vergleiche würden da wenig Sinn machen). Deshalb benötigt dein operator< auch zwei Referenzen als Parameter (eigentlich klappt auch Wert-Übergabe, aber die ist bei großen Objekten wenig sinnvoll).

Ich komme leider mit Pointern im Zusammenhang mit Arrays und zusätzlich noch Structs noch nicht ganz klar (weswegen ich in meinem Programm statt Pointern globale Variablen verwende )

In Kurzform: In einem Array stehen die Objekte hintereinander. Und wenn es die Umstände erfordern, kannst du den Array-Namen implizit als Zeiger (auf das erste Element) verwenden. Beim Index-Zugriff bekommst du dagegen das n-te Element heraus.

Dass es nicht so heißen muss, wie oben beschreiben, hat mir G++ mit einer ziemlichen Kraut-und-Rüben-Mitteilung klar gemacht, die in etwa so lautet:

./src/header.h:52: error: ‘bool operator<(const tagundinhalt*, const tagundinhalt*)’ must have an argument of class or enumerated type
./src/header.h: In function ‘bool operator<(const tagundinhalt*, const tagundinhalt*)’:
./src/header.h:53: error: request for member ‘tag’ in ‘a’, which is of non-class type ‘const tagundinhalt*’
./src/header.h:53: error: request for member ‘tag’ in ‘b’, which is of non-class type ‘const tagundinhalt*’
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_algo.h: In function ‘void std::partial_sort(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = tagundinhalt*]’:
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_algo.h:2630:   instantiated from ‘void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size) [with _RandomAccessIterator = tagundinhalt*, _Size = int]’
/usr/lib/gcc/i486-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_algo.h:2713:   instantiated from ‘void std::sort(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = tagundinhalt*]’
./src/sortieren.cpp:17:   instantiated from here

Und die Fehlermeldung in deinem Eröffnungspost teilt dir genauso unmissverständlich mit, daß dein Ansatz sort(tag[0],tag[n]); Unfug ist

Du mußt den STL-Algorithmen Iteratoren übergeben, damit sie arbeiten können, daran führt kein Weg vorbei. (und wenn du dir das Beispiel ansiehst, auf dem dein Code aufbaut - dort steht auch nicht sort(a[0],a[7]); )

Das geht noch weiter, dies schien mir aber der wichtigste Teil zu sein.
Offensichtlich möchte die Überladung eine Klasse (bzw. einen "enumerated type", das wäre doch ein Array, oder?) sehen, mit der ich natürlich nicht dienen kann, da mein C-C++-Mischmasch ja noch Structs verwendet.

Zur Operator-Überladung benötigst du mindestens einen User-definierten Typ (das sind struct, class, enum, union) - die Redefinition der Operatoren für Build-ins (inklusive Zeigern) ist nicht erlaubt.

Molinman

Eieiei, ok, verstehe. Danke.
Da war ich zu strikt programmiert auf "wenn ich einer Funktion Adressen übergebe, dann muss sie auch Pointervariablen annehmen".

Gut, dann verstehe ich jetzt, wie sort funktioniert - allerdings leider immer noch nicht, warum nach dem Sortiervorgang mein Struct komplett leer ist.

Mein Struct sieht folgendermaßen aus:

struct tagundinhalt{
	   int inhaltzaehler;
	   std::string tag;
	   std::string inhalt[MAX_INHALT_ANZAHL];
   };

Sowohl die int inhaltzaehler als auch tag und inhalt sind auf 0 gesetzt bzw. komplett leer.
(Besonders, dass alle inhaltzaehler ausgerechnet auf 0 gesetzt sind, macht mich stutzig, denn das klingt nicht gerade nach einem seltsamen Willkür-Fehler)
Auch wenn ich beispielsweise nach inhaltzaehler sortieren lasse, bekomme ich dasselbe leere Array.
An welcher Stelle könnte hier der Fehler liegen?

Wenn ich statt

return a.tag < b.tag

einfach immer true zurückgeben lasse, bekomme ich ein Segmentation fault.
Wenn ich immer false zurückgeben lasse, bekomme ich dasselbe Ergebnis wie bei dem echten Vergleich von a.tag und b.tag (Nur für den Fall, dass das von irgendeiner Bedeutung ist bzw. weiterhilft)

Und: ist es normal, dass sich nach der Sortierung mein Array an derselben Stelle im Speicher befindet? (Ich nehme schon an, schließlich kann sort nicht eigenhändig dauerhaft Speicher reservieren, oder kann es das? Ich wollte das jedenfalls erwähnt haben )