Geek / Technical

Why std::sort Crashes on My Collection of Objects

I’m working on the physics of my game, and I’m trying to sort the collidable object data on the X axis, then on the Y axis. Sorting should help my implementation of Sweep and Prune work faster, and so I wrote my own less than operator.

bool CollidableObject::operator<(const CollidableObject & rhs) const
    bool lessThan = (this->m_position.X() - this->m_radius) < (rhs.m_position.X() - rhs.m_radius);
    if (!lessThan)
        lessThan = (this->m_position.Y() - this->m_radius) < (rhs.m_position.Y() - rhs.m_radius);

    return lessThan;

Yet, when I call std::sort(beginIter, endIter), I get a seg fault in the bowels of the sorting algorithm.

Looking online, I find that the problem other people are running into is with their custom comparators. std::sort requires a strict weak ordering, meaning that if a < b, then you can't also say a == b, or else the sort algorithm's assumptions are invalid. Ok, but what was wrong with my code? It must be something else...oh, wait. I wanted to sort on the Y axis only if I couldn't sort on the X axis. My implementation checks the X axis, then if a.X() is not less than b.X(), it checks the Y axis, which means if a.X() == b.X(), or worse, if I know for sure that a.X() > b.X(), then I’m doing further sorting when I don’t want to do so.

I made this change:

if (!lessThan && this->m_position.X() == rhs.m_position.X())

And now everything is sorting properly and without a crash.

One reply on “Why std::sort Crashes on My Collection of Objects”

Comments are closed.