The other day I came across a nice little C++-shoot-yourself-in-the-foot at one of our customers. Let’s see how fast you can spot the problem. The following code crashes with segmentation fault sometime, somewhere in the sort call (line 31).
#include <iostream> #include <vector> #include <boost/shared_ptr.hpp> #include <boost/bind.hpp> using namespace std; using namespace boost; enum SORT_ORDER { SORT_ORDER_ASCENDING, SORT_ORDER_DESCENDING }; bool compareValues(const std::string& valueLeft, const std::string& valueRight, SORT_ORDER order) { const bool compareResult = (valueLeft < valueRight); if (order == SORT_ORDER_DESCENDING) { return !compareResult; } return compareResult; } int main(int argc, char *argv[]) { std::vector<std::string> strValues(300); std::fill(strValues.begin(), strValues.end(), "Hallo"); std::sort(strValues.begin(), strValues.end(), bind(compareValues, _1, _2, SORT_ORDER_DESCENDING)); return EXIT_SUCCESS; }
Any ideas? The tricky thing about this bug is that the stacktrace output in the debugger gives absolutely no hint at all about its cause. And this is a simplified version of the real code which has to sort boost::shared_ptrs instead of strings. Believe me, you don’t want to see that stacktrace. Because of the use of boost::bind together with boost::shared_ptrs it looks, well, let’s say intimidating.
Still no idea?
I’ll give you a hint. If the SORT_ORDER is set to SORT_ORDER_ASCENDING everything is fine. …
Ok, the problem is that std::sort algorithm must be given a comparison function (object) that defines a strict weak ordering on the elements that are to be sorted. In other words the comparison function object must implement the ‘<‘ (less than) relationship on the elements.
Unfortunately, lines 20 to 22 break this ordering when SORT_ORDER_DESCENDING is given. The initial idea of this code was that, well, if compareResult gets returned on ascending sort order, lets just return the negation of it when the “negation” of acscending order is requested. This, of course, destroys the strict weak ordering requirement because whenever valueLeft == valueRight, the function returns true, meaning instead that valueLeft < valueRight. And this somehow wreaks havoc inside std::sort.
A better version of the function could be:
... bool compareValues(const std::string& valueLeft, const std::string& valueRight, SORT_ORDER order) { // solution: return false independent of sort order // whenever valueLeft == valueRight if (valueLeft == valueRight) { return false; } const bool compareResult = (valueLeft < valueRight); if (order == SORT_ORDER_DESCENDING) { return !compareResult; } return compareResult; } ...
The really annoying thing about this whole issue is that std::sort just randomly crashes with a stack trace that shows nothing but some weird memory corruption going on. After the initial shock, this sends you down the complete wrong bug hunting road where you start looking for spots where memory could be overwritten or the like.
So beware of custom comparison functions or function objects. They might look innocent and easy, but they can give you lot’s of headaches.
Pingback: Open Source Love Day October 2010 « Schneide Blog
Thanks, this avoided some severe frustration for me!
Thank God for blogs like this!!
Thank you.You saved me a lot of time.
You rock!!! thank you for sharing this gem. I spent an entire day debugging this and still had no idea. Then decided to do a google search.
Thank you kind sir, I wasted 30 minutes of my afternoon wondering why my sort was suddenly crashing. This solved my problem.
Thank you….Spent half a day as to why it wasn’t working for Descending order…!!
Thanks!
You saved me a lot of debuging time 🙂 I have version with std::vector
std::vector<boost::shared_ptr
I am not sure how comparision semantic is related to illigal memory access(seg fault) here. I changed the objects count to 16 in container and it worked.
Problem is something else.
Just ran into a similar situation when using <= instead of < inside a lambda comparison functor… this is the very essence of foot-self-shooting, indeed.
Thank you so much for this blog entry! I just spent a whole day trying to track down memory corruptions and segfaults, and it turned out it was just my comparator. WOW! I think you just saved my life, or at least my job. 🙂
Thanks, we had exactly the same issue when we first faced a bug in a game called manaplus. See
The author of the game only found the solution after I pointed him to this blog post.