std::sort对含比较器判定重复的非原生类型排序是否具确定性？

先看你给出的代码场景：

struct Data {
  std::string str;
  int data;
};

struct {
        bool operator()(Data a, Data b) const { return a.data > b.data; }
} customLess;

int main() {
    std::vector v = {
       {"Rahul", 100},
       {"Sachin", 200},
       {"Saurav", 200},
       {"Rohit", 300},
       // .....

    };

    for(uint k = 0; k < 1000; k++) {
       auto v2 = v;
       std::sort(v2.begin(), v2.end(), customLess);
    }
}

答案是：在同一编译器、同一编译选项、同一运行环境下，相同输入数组每次调用std::sort的结果是确定且可复现的，但自定义比较器判定为相等的元素，它们的相对顺序可能和原数组不同；换不同环境/编译器的话，相等元素的相对顺序可能变化，但单次环境内多次运行结果一致。

具体解释： #

• C++标准没有规定std::sort的具体实现细节（比如用快速排序、归并排序还是IntroSort这类混合算法），但明确要求这类排序算法是确定性的——不会引入随机化操作（比如像std::shuffle那样依赖随机数生成器）。因此只要输入完全一致，同一实现下每次排序的结果必然完全相同。
• 你的代码中，customLess仅通过data字段比较元素，所以{"Sachin", 200}和{"Saurav", 200}会被判定为“等价”（因为customLess(a,b)和customLess(b,a)都返回false）。std::sort是不稳定排序，不会保留这两个元素在原数组中的相对顺序，但每次排序后它们的相对位置是固定的（比如每次都是"Saurav"排在"Sachin"前面，或者反过来，具体取决于编译器的sort实现逻辑）。
• 如果需要严格保留等价元素的原始相对顺序，应该使用std::stable_sort，它是稳定排序算法，会保证自定义比较器判定等价的元素，排序后的相对位置与原数组完全一致。

额外注意： #

• 不同编译器（比如GCC、Clang、MSVC）的std::sort实现可能存在差异，因此跨编译器运行时，等价元素的相对顺序可能不同，但同一编译器下多次运行结果完全一致。
• 同一编译器的不同版本，或者修改优化级别、编译选项等，也可能导致sort实现的细节变化，进而改变等价元素的相对顺序，但在同一配置下多次运行，结果始终稳定。

内容的提问来源于stack exchange，提问作者cryptickey