Sorting vector of smart pointers: mysterious crash

Question

I am trying to sort a vector of smart pointers to a class. I use a struct as the third parameter to std::sort with operator():

struct PhraseSmartPtrParseCreationComparer
{
    bool operator()(const std::shared_ptr<Phrase>& a, const std::shared_ptr<Phrase>& b)
    {
        if (a.get() == nullptr)
            return b.get() != nullptr;
        if (b.get() == nullptr)
            return a.get() != nullptr;
        return *a < *b;
    }
};

Once in a while, I get a segmentation fault where one of the pointers inside the comparing method points to an invalid structure; always one. The interesting bit is, just before the sort, all the objects are intact; I also tried modifying the function to remove the reference bit: const std::shared_ptr<Phrase> a, and it crashed elsewhere.

The call is nothing fancy:

std::sort(_detectedPhrases.begin(), _detectedPhrases.end(), PhraseSmartPtrParseCreationComparer());

Is there something I'm missing or I should be looking elsewhere?

It seems your comparator doesn't meet the requirements of a [Strict Weak Ordering](https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings), because you `return true;` for a `nullptr` before **or after** a valid pointer. You need to pick one - do you want to sort all `nullptr`s to the front, or to the back? If this could be the cause of your crash, I have no idea. — BoBTFish, Jul 20 '18 at 07:19
Thanks, @BoBTFish. I want it at the back - but regardless, what I get is not a nullptr. Honestly, this was added after I started indulging in a voodoo programming. What I get is always the same value, `0xfeeefeeefeeefeee`. — Vadim Berman, Jul 20 '18 at 07:21
@VadimBerman Undefined Behaviour is a strange beast - it could be possible that the sorting algorithm thinks it has sorted something into a position when it hasn't, resulting in garbage in that slot. Fix one problem at a time, then narrow down the next one. — BoBTFish, Jul 20 '18 at 07:24
@DanielLangr In this code they are only compared against `nullptr`, which is always legal. — BoBTFish, Jul 20 '18 at 07:24
The value `0xfeeefeeefeeefeee` suggests that you are reading memory that has been freed previously => undefined behaviour — Jabberwocky, Jul 20 '18 at 07:26
@Jabberwocky Is this some magic flag value set by a particular implementation? — BoBTFish, Jul 20 '18 at 07:27
@BoBTFish yes, Visual Studio does this in debug builds. https://stackoverflow.com/a/127404/898348 — Jabberwocky, Jul 20 '18 at 07:28
So in a nutshell, it appears that my comparison may have caused an item to be sorted and again, and I need to make sure it's consistent - this is at least the working hypothesis. @Jabberwocky, I'm sorry I can't post the entire comparison algorithm because it's huge and involves different modules. But it sounds plausible. I'll check and get back with results. — Vadim Berman, Jul 20 '18 at 07:29
@VadimBerman maybe MinGW does the same thing: https://stackoverflow.com/a/127404/898348 — Jabberwocky, Jul 20 '18 at 07:30

score 4 · Accepted Answer · edited Jul 20 '18 at 09:57

4

I can't believe how fast it was resolved. Here is the explanation - thank you for your guidance and cues, @BoBTFish and @Jabberwocky.

Indeed, the reason was that the sorter was having it both ways. The result was not symmetric. That is, the same two items, when swapped, could sometimes produce the same answer. Unfortunately, because of the business logic, it was actually valid. It's basically a tree, and one of the comparison components was whether one item is allowed to be a parent of the other - and a situation when both could theoretically be parents of the other is valid. So I did not change that. What I did (and hopefully it's not bad taste) was to add this workaround (never mind the nullptr checks, they are not relevant):

struct PhraseSmartPtrParseCreationComparer
{
    bool operator()(const std::shared_ptr<Phrase>& a, const std::shared_ptr<Phrase>& b)
    {
       return *a < *b && !(*b < *a);    
    }
};

edited Jul 20 '18 at 09:57

Passer By

19,325
6
49
96

answered Jul 20 '18 at 07:41

Vadim Berman

1,932
1
20
39

2

Would/should this not work without the inverted check? Because this seems to imply your `operator<` for `Phrase` does not satisfy the usual requirements – rubenvb Jul 20 '18 at 07:52
But I'm not using `operator<` as a sorter. I am using `operator()` which happens to make some use of `operator<` internally. If `operator<` was the only one and I were sorting structures, then yes. – Vadim Berman Jul 20 '18 at 07:56
but then a sorter would have enough to just to `*a < *b` without the `&& !(*b < *a)`. – rubenvb Jul 20 '18 at 07:57
No, and that was the issue. The sorter would return (say) true for either `operator(a, b)` and `operator(b, a)`. Now it doesn't. – Vadim Berman Jul 20 '18 at 07:59
4

Right, so your `Phrase`'s `operator<` does not satisfy the usual requirements anyone would expect from a less than operator in C++. Fix that instead of layering workarounds on top. – rubenvb Jul 20 '18 at 08:00
That's kinda clear. I explained why I can't in the post. So I can rename the underlying logic to "CanBeParent" or "CanBeConstruedAsLess" for aesthetic purposes - what difference would it make to me? – Vadim Berman Jul 20 '18 at 08:02
It wouldn't, of course. Even in my wildest dreams I would not imagine that `std::sort` will feed a junk entry into my comparer. That was the crux of my problem. – Vadim Berman Jul 21 '18 at 08:49

Sorting vector of smart pointers: mysterious crash

1 Answers1