CODEWITHSUNDEEP
c++sortingc++11vectorsegmentation-fault
Evan Teran
Evan Teran

Reputation: 90422

Bug in std::sort?

OK, I typically default to assuming that the error is in my code, but what I am seeing is making literally no sense to me.

I have a std::vector<DocumentWidget *>, which I want to be sorted by some relatively simple algorithm. Here's what I am seeing.

The code looks like this:

std::vector<DocumentWidget *> documents = DocumentWidget::allDocuments();

// NOTE(eteran): on my system, I have observed a **consistent** crash
// when documents.size() == 17 while using std::sort.
std::sort(documents.begin(), documents.end(), [](const DocumentWidget *a, const DocumentWidget *b) {

    int rc = (a->filenameSet_ == b->filenameSet_) ? 0 : a->filenameSet_ && !b->filenameSet_ ? 1 : -1;
    if (rc != 0) {
        return rc < 0;
    }
    if(a->filename_ < b->filename_) {
        return true;
    }
    return a->path_ < b->path_;
});

Seems simple enough, but it crashes specifically when I have a 17th item in the list! The sorting predicate clearly is not modifying the vector in any way, so I can't see that being an issue. Address sanitizer and valgrind show no errors up until this point.

qSort does not crash, seems to work fine. No other threads that are running are touching this data, and it happens reliably no matter how slowly I step... so it's not a race condition.

When I look in the debugger, the a parameter seems to be where the "one past the end" iterator is pointing. But that shouldn't be happening if std::sort is behaving Crash.

Note There are 17 items in the std::vector, I forced the debugger to display an 18th item to illustrate where a seems to be coming from.

I can't imagine that std::sort is bugged, but I am really struggling to find another explanation. Am I missing some obvious bug here?!

Upvotes: 1

Views: 946

Answers (2)

Paul Floyd
Paul Floyd

Reputation: 6906

@T.C.'s answer is a good one since the question is tagged C++11, but in case future readers are after a C++03 solution, the 'canonical' way to write such a comparison operator (for members m1, m2, .... mn) is

if (a->m1 != b-m1)
    return a->m1 < b->m1;
else if (a->m2 != b->m2)
    return a0>m2 < b->m2;
else ...
else if (a->mn != b->mn)
    return a->mn < b->mn;
else
    return false;

(see here for a discussion, with the question having the above style but avoiding operator!=).

One further thing is that you are using pointers and your code is not bomb-proof. If a or b is NULL you'll get a crash. If you can't avoid pointers and you want to be paranoid then you need to add checks like

if (!a && !b)
    return false;
else if (!a)
    return true;
else if (!b)
    return false;

Upvotes: 1

T.C.
T.C.

Reputation: 137301

if(a->filename_ < b->filename_) {
    return true;
}
return a->path_ < b->path_;

This is known as "not a valid strict weak ordering":

{ "a", "d" } < { "b", "c"}; because "a" < "b"
{ "b", "c" } < { "a", "d"}; because "c" < "d"

The fix is simple: don't reinvent the wheel:

return std::tie(a->filename_, a->path_) < std::tie(b->filename_, b->path_);

Upvotes: 16

Related Questions