C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  problem with C++ sort algorithm          C++Talk.NET Forum Index -> C++ Language (Moderated) View previous topic :: View next topic   Author Message nthali Guest Posted: Sun Aug 13, 2006 4:28 pm    Post subject: problem with C++ sort algorithm Hello all, First i would like to thank the innumerable C++ faithfuls who slammed, castigated, berated and criticized me for trying to java-ize the STL list class :) Currently i have a vector<Obj*> of objects that i sort using sort( vector.begin(), vector.end(), myCompareMethod ) and i get a core dumped in myCompareMethod( obj* obj1, obj* obj2 ) because apparently obj2 is NULL. Now none of the objects in my vector are NULL, so i don't know how it could possibly get a NULL obj2 in the compare method? Any ideas? Thanks, Nilesh [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Howard Hinnant Guest Posted: Sun Aug 13, 2006 8:32 pm    Post subject: Re: problem with C++ sort algorithm In article <1155433654.040482.222510 (AT) i3g2000cwc (DOT) googlegroups.com>, "nthali" <i.am.joatman (AT) gmail (DOT) com> wrote: Quote: Hello all, First i would like to thank the innumerable C++ faithfuls who slammed, castigated, berated and criticized me for trying to java-ize the STL list class :) Currently i have a vector<Obj*> of objects that i sort using sort( vector.begin(), vector.end(), myCompareMethod ) and i get a core dumped in myCompareMethod( obj* obj1, obj* obj2 ) because apparently obj2 is NULL. Now none of the objects in my vector are NULL, so i don't know how it could possibly get a NULL obj2 in the compare method? Any ideas? Once you've confirmed that there are no NULL pointers in your vector, my next best guess would be that your myCompareMethod does not form a strict weak ordering (section 25.3 p3-p4). Specifically: * !myCompareMethod(a, a) must be true for all elements in the sequence. (no element is less than itself) * If myCompareMethod(a, b) && myCompareMethod(b, c) then myCompareMethod(a, c) must be true. (a < b and b < c implies a < c) * If !myCompareMethod(a, b) && !myCompareMethod(b, a) && !myCompareMethod(b, c) && !myCompareMethod(c, b) then !myCompareMethod(a, c) && !myCompareMethod(c, a) must be true. (a == b and b == c implies a == c) Quote: From the above you can also deduce that if myCompareMethod(a, b) is true then myCompareMethod(b, a) must be false (but not vice-versa). Failure to meet the requirements of a strict weak ordering can cause the sorting algorithm to wander beyond the range of your sequence. Some implementations, at least in debug mode, will detect this error. -Howard [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Frederick Gotham Guest Posted: Sun Aug 13, 2006 8:37 pm    Post subject: Re: problem with C++ sort algorithm nthali posted: Quote: Hello all, First i would like to thank the innumerable C++ faithfuls who slammed, castigated, berated and criticized me for trying to java-ize the STL list class :) Currently i have a vector<Obj*> of objects that i sort using sort( vector.begin(), vector.end(), myCompareMethod ) and i get a core dumped in myCompareMethod( obj* obj1, obj* obj2 ) because apparently obj2 is NULL. Confirm this with: assert(p2); Quote: Now none of the objects in my vector are NULL, so i don't know how it could possibly get a NULL obj2 in the compare method? There's a bug somwhere. -- Frederick Gotham [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Thomas Maeder Guest Posted: Sun Aug 13, 2006 8:39 pm    Post subject: Re: problem with C++ sort algorithm { extra line breaks removed. please check your newsreader. -mod } "nthali" <i.am.joatman (AT) gmail (DOT) com> writes: Quote: Currently i have a vector<Obj*> of objects that i sort using sort( vector.begin(), vector.end(), myCompareMethod ) and i get a core dumped in myCompareMethod( obj* obj1, obj* obj2 ) because apparently obj2 is NULL. Now none of the objects in my vector are NULL, so i don't know how it could possibly get a NULL obj2 in the compare method? Any ideas? Please post the minimal program (<50 lines) that has this behavior. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top werasm Guest Posted: Mon Aug 14, 2006 5:44 pm    Post subject: Re: problem with C++ sort algorithm nthali wrote: Quote: Currently i have a vector<Obj*> of objects that i sort using sort( vector.begin(), vector.end(), myCompareMethod ) and i get a core dumped in myCompareMethod( obj* obj1, obj* obj2 ) because apparently obj2 is NULL. Now none of the objects in my vector are NULL, so i don't know how it could possibly get a NULL obj2 in the compare method? How would we know that for sure? A mistake that I've previously seen made was initializing the vector for a given size. Because you are using pointers, they would be default initialized - to NULL, for example: void test() { std::size_t vsize( 50 ); std::vector<Obj*> v( vsize ); //...v now contains 50 NULL pointers. v.push_back( new Obj ); //...v now contains 50 NULL pointers and ... //... one valid pointer. } Ignorance may lead one to believe that v only contains the item that was pushed back. I've seen this mistake made before - it may be yours. If this is the case - rather than initialise the vector with a size, use reserve to prevent allocations after instantiation. Hope it helps - good luck Werner Quote: Any ideas? Thanks, Nilesh [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Ron Natalie Guest Posted: Mon Aug 14, 2006 5:46 pm    Post subject: Re: problem with C++ sort algorithm nthali wrote: Quote: Now none of the objects in my vector are NULL, so i don't know how it could possibly get a NULL obj2 in the compare method? Are you sure? Are you sure you don't "resize" or otherwise introduce default contstucted elements into the vector? [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Ralf Fassel Guest Posted: Mon Aug 14, 2006 9:45 pm    Post subject: Re: problem with C++ sort algorithm * jo_atman (AT) yahoo (DOT) com | Now this file is 710 lines long, so i don't want to paste it here, | and i don't see an attach file functionality. If all else fails, you could try to gzip/uuencode it and see how big that gets. Should be definitely smaller than the above. | Funny thing is, if i comment out any 1 (or more) of the 292 | push_backs, the sort works fine without a core dump. alternatively, | i can add a 293rd element and again it works fine. so i'm not sure | what's happening with the 292 elements. Did you confirm the pointers were non-Zero in your comparison function? Does the core dump happen because of a NULL pointer dereference or because you happen to have pointers to un-/mis-initialized objects in the vector? R' [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Guest Posted: Tue Aug 15, 2006 2:32 am    Post subject: Re: problem with C++ sort algorithm Folks, This strange problem is now solved, thanks to a programming illiterate (but very sharp OR guy) at work. I guess showing you guys my compare method would have helped you point it out too: bool compareByCloseAndAlloc( State* s1, State* s2 ) { int retVal = s2->getPDClose() - s1->getPDClose(); if ( retVal != 0 ) return retVal < 0; return s1->getAllocation() - s2->getAllocation(); } Well, this guy asked me why i'm returning a boolean (retVal < 0) on line 2, but an integer on line 3. I said, well, C++ really uses ints as bool, and that i could change the code to bool compareByCloseAndAlloc( State* s1, State* s2 ) { int retVal = s2->getPDClose() - s1->getPDClose(); if ( retVal != 0 ) return retVal < 0; retVal = s1->getAllocation() - s2->getAllocation(); return retVal < 0; } but it wouldn't make a shred of a difference. And it did. It fixed the problem. I still honestly believe i did no wrong (i thought in C++, 0 was false, every other number in the universe means true). before we close this inane topic, maybe someone could clarify? Thanks again for all your help. Ron Natalie wrote: Quote: nthali wrote: Now none of the objects in my vector are NULL, so i don't know how it could possibly get a NULL obj2 in the compare method? Are you sure? Are you sure you don't "resize" or otherwise introduce default contstucted elements into the vector? [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Joel Eidsath Guest Posted: Tue Aug 15, 2006 5:42 am    Post subject: Re: problem with C++ sort algorithm jo_atman (AT) yahoo (DOT) com wrote: Quote: bool compareByCloseAndAlloc( State* s1, State* s2 ) { int retVal = s2->getPDClose() - s1->getPDClose(); if ( retVal != 0 ) return retVal < 0; return s1->getAllocation() - s2->getAllocation(); } I probably would have written this: bool compareByCloseAndAlloc( State* s1, State*s2) { //compare by Alloc if Close are equal if (s1->getPDClose() == s2->getPDClose()) { return (s1->getAllocation() < s2->getAllocation()); } //otherwise compare by Close return (s1->getPDClose() < s2->getPDClose()); } Notice that it would have made clear the bug in the code (I assume) where you switch s1 and s2 in the 3rd to the 5th line. Quote: Well, this guy asked me why i'm returning a boolean (retVal < 0) on line 2, but an integer on line 3. I said, well, C++ really uses ints as bool, and that i could change the code to bool compareByCloseAndAlloc( State* s1, State* s2 ) { int retVal = s2->getPDClose() - s1->getPDClose(); if ( retVal != 0 ) return retVal < 0; retVal = s1->getAllocation() - s2->getAllocation(); return retVal < 0; } but it wouldn't make a shred of a difference. And it did. It fixed the problem. Possibly because your boolean algebra is faulty. If x is greater than y, then: x - y is true, x - y < 0 is false If x is equal to y, then: x - y is false, x - y < 0 is false If x is less than y, then: x - y is true, x - y < 0 is true Your code may run without bombing out, but I have to wonder whether it actually does what it is supposed to. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Simon Farnsworth Guest Posted: Tue Aug 15, 2006 5:43 am    Post subject: Re: problem with C++ sort algorithm jo_atman (AT) yahoo (DOT) com wrote: Quote: Folks, This strange problem is now solved, thanks to a programming illiterate (but very sharp OR guy) at work. I guess showing you guys my compare method would have helped you point it out too: bool compareByCloseAndAlloc( State* s1, State* s2 ) { int retVal = s2->getPDClose() - s1->getPDClose(); if ( retVal != 0 ) return retVal < 0; return s1->getAllocation() - s2->getAllocation(); } Translated to closer match your later example: bool compareByCloseAndAlloc( State* s1, State* s2 ) { int retVal = s2->getPDClose() - s1->getPDClose(); if ( retVal != 0 ) return retVal < 0; retVal = s1->getAllocation() - s2->getAllocation(); return retVal != 0; } Quote: Well, this guy asked me why i'm returning a boolean (retVal < 0) on line 2, but an integer on line 3. I said, well, C++ really uses ints as bool, and that i could change the code to bool compareByCloseAndAlloc( State* s1, State* s2 ) { int retVal = s2->getPDClose() - s1->getPDClose(); if ( retVal != 0 ) return retVal < 0; retVal = s1->getAllocation() - s2->getAllocation(); return retVal < 0; } but it wouldn't make a shred of a difference. And it did. It fixed the problem. Unless there's domain knowledge of the return values of getAllocation that I'm missing, you've changed the last return from retVal != 0 to retVal < 0. As a result, instead of returning true when s2->getAllocation() is smaller than s1->getAllocation(), you're returning false. -- Simon Farnsworth [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top kevin cline Guest Posted: Wed Aug 16, 2006 4:41 am    Post subject: Re: problem with C++ sort algorithm Greg Herlihy wrote: Quote: ... A more compact implementation would simply be: bool compareByCloseAndAlloc( State* s1, State* s2 ) { return s1->getPDClose() < s2->getPDClose() ? true : s1->getPDClose() > s2->getPDClose() ? false : s1->getAllocation() < s2->getAllocation(); This is just standard memberwise comparison of pairs: return s1->getPDClose() < s2->getPDClose() || (s1->getPDClose() == s2->getPDClose() && s1->getAllocation() < s2->getAllocation()); [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         C++Talk.NET Forum Index -> C++ Language (Moderated) All times are GMT Page 1 of 1   Jump to: Select a forum C/C++----------------C LanguageC Language (Moderated)C++ Language (Moderated)C++ language (comp.lang.c++)C++ language, library and standards Non-English C/C++ Newsgroups----------------C++ (German)C++ (French)  You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum Powered by phpBB © 2001, 2006 phpBB Group SEO toolkit © 2004-2006 webmedic.