[XCode] Problem mit std::vector und std::sort

Programmiersprachen, APIs, Bibliotheken, Open Source Engines, Debugging, Quellcode Fehler und alles was mit praktischer Programmierung zu tun hat.
Antworten
Benutzeravatar
dowhilefor
Moderator
Beiträge: 173
Registriert: 27.02.2009, 15:44
Alter Benutzername: 6SidedDice
Echter Name: Nico Probst
Wohnort: Bochum
Kontaktdaten:

[XCode] Problem mit std::vector und std::sort

Beitrag von dowhilefor »

Hallo zusammen,

ich versuche gerade ein einfaches Kommandozeilentool unter MacOSX in XCode zu schreiben.
Projekt ist ein einfaches C++ Tool. Den Fehler konnte ich nun auf folgendes runterbrechen und reproduzieren, nur nachvollziehen kann ich es nicht.
Vorneweg, im Debugbuild sind 2 zusätzliche Preprocessor Defines gesetzt, die wohl die STL in eine Art Debugmodus versetzen, daher komme ich an die unten stehende Fehlerausgaben.

Code: Alles auswählen

// main.cpp
#include <iostream>
#include <vector>
using namespace std;

class MyClass{
};

bool myCmpr(const MyClass& a, const MyClass& b) {
	return true;
}
int main (int argc, char * const argv[]) {
	std::vector<MyClass> input;
	input.resize(20);
	cout << input.size() << endl;
	std::sort(input.begin(), input.end(), myCmpr);
    return 0;
}
Keine weiteren Codedateien, keine Änderung an den Projekteinstellungen, keine zusätzlichen Abhängigkeiten.
Also im Grunde eine sehr einfache Klasse erzeuge 20 davon und möchte sie gerne sortieren, soweit so unspektakulär. Code produziert folgenden fehler in der sort funktion.
/Developer/SDKs/MacOSX10.5.sdk/usr/include/c++/4.0.0/debug/safe_iterator.h:178:
error: attempt to dereference a past-the-end iterator.

Objects involved in the operation:
iterator "this" @ 0x0xbffff3b4 {
type = N11__gnu_debug14_Safe_iteratorIN9__gnu_cxx17__normal_iteratorIP7MyClassN10__gnu_norm6vectorIS3_SaIS3_EEEEEN15__gnu_debug_def6vectorIS3_S7_EEEE (mutable iterator);
state = past-the-end;
references sequence with type `N15__gnu_debug_def6vectorI7MyClassSaIS1_EEE' @ 0x0xbffff3b4
}
Program received signal: “SIGABRT”.
kill
quit
Ich kann mir das überhaupt nicht erklären. Klar verstehe ich was das problem ist, angeblich würde ich den end() iterator dereferenzieren, aber da das in der sort methode passiert hab ich darauf ja keinen Einfluss. Ist vielleicht was an meiner Compare Methode falsch? Denn das Ausgeben der 20 Objekte geht ohne Probleme. Noch etwas merkwürdiges, füge ich bis zu 16 Objekte ein, funktioniert der Code, sobald ich 17 oder mehr einfüge geht es nicht.
Also ich hoffe jemand kann das bestätigen oder mir noch besser sagen, was ich da falsch mache. Auch wäre es nett wenn es mal jemand in einem anderen Compiler probieren könnte.

Danke im vorraus
Nico
Mein Gehirn besteht nur noch aus einem hash-index, ich weiss was ich kenn aber kenn nicht was ich weiss
Benutzeravatar
Schrompf
Moderator
Beiträge: 4855
Registriert: 25.02.2009, 23:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Re: [XCode] Problem mit std::vector und std::sort

Beitrag von Schrompf »

Das klingt in der Tat nach einem spannenden Problem :-)

Dein Code ist korrekt, soweit ich das beurteilen kann. Geht ja auch kaum anders. Egal, wie man es dreht - es klingt nach einem Bug in der std::sort()-Implementation.

Der std::vector wird (beim ersten Hinzufügen) mit einer Standardkapazität von 16 erzeugt - zumindest unter Visual Studio ist das so, evtl. ist das sogar eine vom C++-Standard vorgegebene Startgröße. Daher kommt evtl. diese seltsame Verhaltensänderung ab 17 Elementen. Du kannst ja mal versuchen, reinzudebuggen. Aber das wird im Normalfall ein ziemlicher Kampf... zumindest bei VC hat die Lib irgendjemand geschrieben, der dichtgedrängte Sonderzeichenwüsten mögen muss.
Früher mal Dreamworlds. Früher mal Open Asset Import Library. Heutzutage nur noch so rumwursteln.
Benutzeravatar
dowhilefor
Moderator
Beiträge: 173
Registriert: 27.02.2009, 15:44
Alter Benutzername: 6SidedDice
Echter Name: Nico Probst
Wohnort: Bochum
Kontaktdaten:

Re: [XCode] Problem mit std::vector und std::sort

Beitrag von dowhilefor »

Danke schonmal für deine Antwort Schrompf,

ich dachte mir schon das es was mit der Granularität des Containers zu tun hat. Debuggen möcht ich das ganze äusserst ungerne weil die STL eben so ein Krampf ist und ich VS verwöhnt bin der nun mit XCode frickeln muss. Vorallem aber muss das Tool was ich hier schreibe fertig werden, da es für ein weiteres Projekt benötigt wird. Ärgerlich das ich mich nun mit sowas rumschlagen muss.
Alternativen sehe ich bisher nur in STL komplett verwerfen und Arrays und qsort verwenden, wogegen ich mich arg sträube, oder mal STLPort auszuprobieren.
Alles keine zufriedenstellenden Lösungen, ich hoffe vielleicht weiß noch jemand Rat und ich verweise solange auf meine Signatur :(

Nachtrag: Es ist nicht direkt XCode, der Fehler lässt sich mit dem gcc bzw. g++ auf dem Terminal reproduzieren. Bzw. dort gibt es keinen Fehler, aber das Programm bleibt in sort hängen, ohne Fehlerausgaben, was demselben Verhalten entspricht, wie unter XCode in Release(wo die Debugausgaben der STL abgeschaltet sind).
Mein Gehirn besteht nur noch aus einem hash-index, ich weiss was ich kenn aber kenn nicht was ich weiss
Benutzeravatar
eXile
Establishment
Beiträge: 1136
Registriert: 28.02.2009, 13:27

Re: [XCode] Problem mit std::vector und std::sort

Beitrag von eXile »

Visual Studio springt hier raus:

Code: Alles auswählen

template<class _Pr, class _Ty1, class _Ty2> inline
	bool __CLRCALL_OR_CDECL _Debug_lt_pred(_Pr _Pred, _Ty1& _Left, _Ty2& _Right,
		const wchar_t *_Where, unsigned int _Line)
	{	// test if _Pred(_Left, _Right) and _Pred is strict weak ordering
	if (!_Pred(_Left, _Right))
		return (false);
	else if (_Pred(_Right, _Left))
		_DEBUG_ERROR2("invalid operator<", _Where, _Line); // Hier Abbruch
	return (true);
	}
Die Betonung liegt auf "test if _Pred(_Left, _Right) and _Pred is strict weak ordering". Das ist bei deinem Code natürlich nicht der Fall. Wenn man einfach mal einen Vergleich der Speicheradressen schreibt:

Code: Alles auswählen

bool myCmpr(const MyClass& a, const MyClass& b) {
	return (&a < &b);
}
Ist alles in Ordnung ;)
Benutzeravatar
dowhilefor
Moderator
Beiträge: 173
Registriert: 27.02.2009, 15:44
Alter Benutzername: 6SidedDice
Echter Name: Nico Probst
Wohnort: Bochum
Kontaktdaten:

Re: [XCode] Problem mit std::vector und std::sort

Beitrag von dowhilefor »

die Compare Methode ist natürlich bei mir nur so einfach weil ich immer mehr Code entfernt habe um zu gucken wo der Fehler liegt. Das return true macht natürlich keinen Sinn.
Im eigentlich projekt waren das Verschiedene Vergleichsmethoden für Klassen mit Rechtecken, zum sortieren nach Breite, Höhe oder Fläche. Das Beispiel was ich hier gepostet habe, war das einfachste womit sich der Fehler reproduzieren lies. Wie Schrompf aber auch schon sagte, ist das ganze so einfach, das der Fehler nicht auftreten dürfte.
Mein Gehirn besteht nur noch aus einem hash-index, ich weiss was ich kenn aber kenn nicht was ich weiss
Benutzeravatar
eXile
Establishment
Beiträge: 1136
Registriert: 28.02.2009, 13:27

Re: [XCode] Problem mit std::vector und std::sort

Beitrag von eXile »

D.h. auch mit obigen Änderung der Compare-Methode treten die gleichen Fehler bei dir auf? Ich glaube, ohne Debuggen kommt man da nicht weiter ... :?
Benutzeravatar
dowhilefor
Moderator
Beiträge: 173
Registriert: 27.02.2009, 15:44
Alter Benutzername: 6SidedDice
Echter Name: Nico Probst
Wohnort: Bochum
Kontaktdaten:

Re: [XCode] Problem mit std::vector und std::sort

Beitrag von dowhilefor »

Naja ich kann Debuggen, aber mehr Informationen als die im ersten Post gepostete Debug ausgabe der Debug STL, kommt da auch nicht bei raus. Dafür ist der Code einfach zu kryptisch für mich.
Hier noch der Callstack, von unten nach oben gelesen.
#2 0x9452a23a in raise
#3 0x94536679 in abort
#4 0x90e6f6f9 in __gnu_debug::_Error_formatter::_M_error
#5 0x0000366f in __gnu_debug::_Safe_iterator<__gnu_cxx::__normal_iterator<MyClass*, __gnu_norm::vector<MyClass, std::allocator<MyClass> > >, __gnu_debug_def::vector<MyClass, std::allocator<MyClass> > >::operator* at safe_iterator.h:176
#6 0x0000412d in std::__unguarded_partition<__gnu_debug::_Safe_iterator<__gnu_cxx::__normal_iterator<MyClass*, __gnu_norm::vector<MyClass, std::allocator<MyClass> > >, __gnu_debug_def::vector<MyClass, std::allocator<MyClass> > >, MyClass, bool (*)(MyClass const&, MyClass const&)> at stl_algo.h:2056
#7 0x000080ae in std::__introsort_loop<__gnu_debug::_Safe_iterator<__gnu_cxx::__normal_iterator<MyClass*, __gnu_norm::vector<MyClass, std::allocator<MyClass> > >, __gnu_debug_def::vector<MyClass, std::allocator<MyClass> > >, int, bool (*)(MyClass const&, MyClass const&)> at stl_algo.h:2536
#8 0x00008887 in std::sort<__gnu_debug::_Safe_iterator<__gnu_cxx::__normal_iterator<MyClass*, __gnu_norm::vector<MyClass, std::allocator<MyClass> > >, __gnu_debug_def::vector<MyClass, std::allocator<MyClass> > >, bool (*)(MyClass const&, MyClass const&)> at stl_algo.h:2606
#9 0x00001a5e in main at main.cpp:25
Mein Gehirn besteht nur noch aus einem hash-index, ich weiss was ich kenn aber kenn nicht was ich weiss
Benutzeravatar
CodingCat
Establishment
Beiträge: 1857
Registriert: 02.03.2009, 21:25
Wohnort: Student @ KIT
Kontaktdaten:

Re: [XCode] Problem mit std::vector und std::sort

Beitrag von CodingCat »

Nico Probst hat geschrieben:die Compare Methode ist natürlich bei mir nur so einfach weil ich immer mehr Code entfernt habe um zu gucken wo der Fehler liegt. Das return true macht natürlich keinen Sinn.
Im eigentlich projekt waren das Verschiedene Vergleichsmethoden für Klassen mit Rechtecken, zum sortieren nach Breite, Höhe oder Fläche. Das Beispiel was ich hier gepostet habe, war das einfachste womit sich der Fehler reproduzieren lies. Wie Schrompf aber auch schon sagte, ist das ganze so einfach, das der Fehler nicht auftreten dürfte.
Aber wie eXile schon sagte ist das Beispiel so einfach, dass es schlichtweg falsch ist. Was soll sort denn machen wenn ein Element erst mit true umsortiert wird und dann bei Vergleich mit demselben wieder zurücksortiert wird, weil beide Male true zurückgegeben wird? Zwar dürfte sort das Programm eigentlich nicht crashen, aber das heißt noch lange nicht, dass der Fehler nicht auch bei dir liegt. Jedenfalls erfüllt dein "vereinfachtes" Predicate nicht die folgenden Voraussetzungen, und der Fehler deines eigentlichen Programms könnte eben genau darin bestehen, dass das vollständige Predicate, gerade wenn es etwas komplizierter ist, diese Bedingungen ebenfalls nicht erfüllt:
MSDN hat geschrieben:Several algorithms make use of a predicate that must impose a strict weak ordering on pairs of elements from a sequence. For the predicate pr(X, Y):
  • Strict means that pr(X, X) is false.
  • Weak means that X and Y have an equivalent ordering if !pr(X, Y) && !pr(Y, X) (X == Y does not need to be defined).
  • Ordering means that pr(X, Y) && pr(Y, Z) implies pr(X, Z).
alphanew.net (last updated 2011-07-02) | auf Twitter | Source Code: breeze 2 | lean C++ library | D3D Effects Lite
Dirk Schulz
Establishment
Beiträge: 130
Registriert: 01.03.2009, 14:21
Alter Benutzername: frittentuete

Re: [XCode] Problem mit std::vector und std::sort

Beitrag von Dirk Schulz »

hi,

jepp, das Programm kompiliert mit dem gcc unter windows fehlerfrei, führt mit "return true;" aber zu einer Endlosschleife. Wenn man "return false;" nimmt, terminiert das Programm. Kenne jetzt den Mac-Compiler nicht, kann es sein, dass der das rausfindet und abbricht?

frittentuete
Benutzeravatar
dowhilefor
Moderator
Beiträge: 173
Registriert: 27.02.2009, 15:44
Alter Benutzername: 6SidedDice
Echter Name: Nico Probst
Wohnort: Bochum
Kontaktdaten:

Re: [XCode] Problem mit std::vector und std::sort

Beitrag von dowhilefor »

Ah solangsam verstehe ich ... Das macht natürlich Sinn. Ich hatte nämlich, wie schon erwähnt ein Compare für Höhe, Breite und Fläche.
Ich hatte erstmal eine Version die nur Breite < Breite gemacht hat und später dann noch zusätzlich wenn Breite == Breite war, nach Höhe zu vergleichen. Das letztere führte zu einem Fehler, lies ich den Code weg, ging es.
Irreführend bleibt aber das es mit bis zu 16 Elementen funktioniert.
Mein Gehirn besteht nur noch aus einem hash-index, ich weiss was ich kenn aber kenn nicht was ich weiss
Benutzeravatar
CodingCat
Establishment
Beiträge: 1857
Registriert: 02.03.2009, 21:25
Wohnort: Student @ KIT
Kontaktdaten:

Re: [XCode] Problem mit std::vector und std::sort

Beitrag von CodingCat »

Naja, die Tatsache, dass das Programm crasht, weist ja irgendwie darauf hin, dass in deiner STL Implementierung auf diesen Sonderfall keine Rücksicht genommen wurde - ob das so legitim ist, ist eine andere Frage - jedenfalls darf es sich bei Nicht-Einhalten der Vorgaben durchaus "undefiniert" verhalten. ;-)
alphanew.net (last updated 2011-07-02) | auf Twitter | Source Code: breeze 2 | lean C++ library | D3D Effects Lite
Antworten