c++ - 为什么必须将std::stable_sort()的比较器函数的参数设置为常量？

Question

各位程序员，您好，我正在解决有关leetcode的问题，该问题需要稳定排序。

问题链接:https://leetcode.com/problems/rearrange-words-in-a-sentence/submissions/

我注意到，必须将std::stable_sort()的比较器函数的参数设置为常量，否则会生成以下编译时错误。

下面是生成编译时错误的代码:

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

void display(vector<string> &a);
bool compare(string &s1, string &s2);

int main() {
    vector<string> a = {"abc", "defgh", "ijk"};

    // sorting vector<string> in stable order
    // error will be generated
    std::stable_sort(a.begin(), a.end(), compare);
    display(a);
    return 0;
}

// argument strings should be made constants???
bool compare(string &s1, string &s2) {
    return s1.length() < s2.length();
}

void display(vector<string> &a) {
    for(int i=0; i<=a.size()-1; i++) {
        cout << a[i] << " ";
    }
    cout << "\n";
    return ;
}

// errors generated
/*
    error: binding reference of type ‘std::__cxx11::basic_string<char>&’ to ‘const 
    std::__cxx11::basic_string<char>’ discards qualifiers
    177 |  { return bool(_M_comp(*__it, __val)); }

    error: binding reference of type ‘std::__cxx11::basic_string<char>&’ to ‘const 
    std::__cxx11::basic_string<char>’ discards qualifiers
    215 |  { return bool(_M_comp(__val, *__it)); }
*/

我尝试了谷歌搜索，但找不到任何东西。我搜索了Stack Overflow，并遇到了一个问题，但无法理解在那里解释的原因。

堆栈溢出答案链接:

https://stackoverflow.com/a/45905608/13331053

任何帮助表示赞赏。提前致谢!

Answer 1

因为这就是功能所需要的。 cppreference对 std::stable_sort (强调我的)的引用:

The signature of the comparison function should be equivalent to the following:

bool cmp(const Type1 &a, const Type2 &b); 

While the signature does not need to have const &, the function must not modify the objects passed to it and must be able to accept all values of type (possibly const) Type1 and Type2 regardless of value category (thus, Type1 & is not allowed[, nor is Type1 unless for Type1 a move is equivalent to a copy (since C++11)]).

您的函数必须接受const参数，并且非const引用类型不满足此要求。因此，您的compare函数应如下所示:

bool compare(const string &s1, const string &s2);

尽管https://godbolt.org/z/S2tL44与std::sort具有完全相同的要求，但GCC仍可接受std::sort中的所有非const版本: std::stable_sort 。我假设根本不检查它，并且std::sort实现不依赖于constness，但是std::stable_sort依赖。为什么？这将是对源代码(或标准库维护者)的一个问题。
在任何情况下，始终在此类函数中使用const&参数将使编译器能够捕获对象的任何意外修改，并确保它可与每个编译器一起使用，这将更安全，更可移植。