Bug hunting fun with std::sort

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.

13 thoughts on “Bug hunting fun with std::sort

  1. Pingback: Open Source Love Day October 2010 « Schneide Blog

  2. 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.

  3. 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.

  4. 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.

  5. 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.πŸ™‚

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s