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”
[…] consistently. For instance, when I was implementing my own physics code for a game, I ran into a crash bug when sorting my objects, and when I realized what I had done wrong and fixed it, I wrote about […]