如果非原始数据类型的 std::sort 包含比较器的重复项，则它是否始终返回相同的排序数组

Question

假设我有一个非原始数据类型，根据比较器有重复项，并且我尝试使用...对其进行排序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);
    }
}

Answer 1

如果我没理解错的话，你是在问，尽管缺乏稳定性，std::sort是否能保证可重复性；如果以相同的顺序提供相同的输入，并且比较组件上的元素相等，但其他组件上的元素不相等，那么所述元素是否总是相对于彼此进行相同的排序？

\n

答案是否定的，std::sort不做这样的保证。这样做会对实现施加限制，可能导致它们的性能更差（例如，基于快速排序的实现不能使用随机主元来最大限度地减少快速排序病态情况的发生，其中性能高于O(n\xc2\xb2)平均情况O(n log n)）。虽然这种设计的普通快速排序在 C++11 中被禁止（现在std::sort需要O(n log n)比较周期，而不仅仅是O(n log n)平均情况），但它仍然可以为基于 introsort 的实现形成顶级排序std::sort（当输入为从可能的恶意来源收到的数据，并且您希望降低它们强制过度递归，然后进行较慢的堆排序的能力），因此要求可重复性将阻止实现使用随机枢轴（或具有随机组件的任何其他排序策略），其好处几乎没有一个人关心。

\n

std::sort 方法您不关心根据比较器比较相等的不相等元素的顺序；他们不会限制潜在的优化来提供无用的保证。实际上，在这种情况下，许多实现可能具有可重复的排序顺序，但这不是代码应该依赖的东西；如果您需要重复性，可以：

\n

\n

1. 使用(并获得可在实现之间std::stable_sort重复的相同输入的排序，其中std::sort，其中，由不同供应商以不同方式实现，几乎肯定不会在选择不同算法的实现中重复），或者

   \n
\n

2. 扩展您的自定义比较器以执行包含输入元素中所有字段的回退排序，因此不可能有任何不确定性，除非字段 100% 相等，而不仅仅是基于主要比较的等效，这不仅使您能够获得相等输入的可重复性，但具有不同顺序的相同元素的输入的可重复性。实际结果可能会以不同的顺序放置两个完全相等的元素（例如，您可能能够检查.data()a std::string，并发现具有相同字符的两个字符串最终以不同的顺序排序），但这几乎从来都不重要（如果它再次使用std::stable_sort)。在这种情况下，您可以将比较器更改为（添加#include <tuple>如果不使用则添加）：

   \n

   struct {\n        bool operator()(const Data& a, const Data& b) const {\n            return std::tie(a.data, a.str) > std::tie(b.data, b.str);\n        }\n} customLess;\n

   \n

   所以所有字段都会进行比较。请注意，我将参数更改为const引用（因此您不必Data为每次比较复制两个对象），并且我曾经std::tie使后备比较高效且易于编码（std::tie允许您使用std::tuple的词典排序，而不必重新实现词典排序草稿，一个容易出错的过程，同时仍然坚持引用语义以避免复制）。

   \n
\n

\n