c++ std::sort unexpected behaviour (Runtime Error)

Question

can anyone please tell me why std::sort shows this unexpected behaviour.

This code is giving Runtime Error

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

inline bool compare(string a, string b){
    return a.size() <= b.size();
}

int main(){

        int n = 100;

        string a = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";

        vector<string>v;
        for(int i=0; i<n; i++){
            v.push_back(a);
        }

        sort(v.begin(), v.end(), compare);

}

but when i replace return a.size() <= b.size(); with return a.size() < b.size(); , it is working completely fine.

Answer 1

The compare function does not meet the requirements for ordering objects using std::sort. Change it to

inline bool compare(string a, string b){
    return a.size() < b.size(); // Not <= just <
}

Why does use of <= not work?

All the elements of your vector are strings of equal size. Hence, our sorting works almost identically to sorting a list of numbers.

Given two numbers, std::sort has to figure whether one is less than the other, greater than the other, or they are equal.

Given n1 and n2,

1. If comp(n1, n2) returns true, then n1 is less than n2.
2. If comp(n1, n2) returns false and comp(n2, n1) returns false, then n1 is equal to n2.
3. If comp(n1, n2) returns false and comp(n2, n1) returns true, then n1 is greater than n2.

If you use <= in the compare function, comp(n1, n2) returns true and comp(n2, n1) returns true. Given that, the sorting algorithm simply cannot sort your objects and goes into an infinite recursion in attempting to do so.