Why can't I use a non-const parameter function with stable_sort()?

Question

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

bool foo(string&s1, string&s2);

int main(int args, char *argv[])
{
    istringstream istrm("counts elements for which predicate p returns");
    vector<string> vec;
    string word;
    while (istrm >> word) {
        vec.push_back(word);
    }

    stable_sort(vec.begin(), vec.end(), foo); //Conversion Error
    //sort(vec.begin(), vec.end(), foo); //Using sort is also OK.

    //Below is OK.
    //int size_num = 7;
    //auto num = count_if(vec.begin(), vec.end(), [size_num](string &s1) {
    //  return s1.size() > size_num;
    //});
    //cout << num;
} 

bool foo(string&s1, string&s2) {
    return s1.size() < s2.size();
}

I got a conversion error while passing a non-const parameter function to stable_sort, but count_if is fine.

From cppreference, it seems that using a non-const parameter function is totally fine.

The signature of the comparison function should be equivalent to the following:
bool cmp(const Type1 &a, const Type2 &b);
The signature does not need to have const &, but the function object must not modify the objects passed to it.

What am I doing wrong here?

PS: So what type of objects do functions in algorithm pass to a predicate? Only const? Only non-const? Or could it be both?

Answer 1

This is currently a defect in the Standard, see LWG 3031.

The existing major implementations don't work with such a comparator in some cases and the Standard is unclear about whether it is supposed to work or not.

Similar question: Is Comp comparator used in STL required to never change compared objects in STL?