为什么排序函数会改变相同值的顺序？

Question

我有 std::vector<std::pair<int, std::string>> 类型的向量。我只是试图按降序排列它（通过使用 std::pair 对象的第一个 int 值），同时保持它稳定，以便相等的数字保持在它们插入的顺序中。

铁：
如果我有：。 5 , 3a , 4 ,3b , 6
我想要订购：6、5、4、3a、3b

但是好像不太好用。排序函数按递增顺序对其进行排序。所以我想做的是排序，然后以相反的顺序处理它们。但是后来我也以相反的顺序获得相同的值，这不稳定并且对我不利。所以我试着先反转整个向量，然后才对它进行排序，然后再按相反的顺序取它们，但我不知道为什么它不起作用？看起来排序函数会按插入顺序更改它，即使我先反转向量也是如此。

无论如何，我是如何实现我的目标的。一个降序向量，同时保持其稳定。

编辑：致所有说要使用稳定排序的人。这也无济于事。我尝试过这个。我的问题不仅仅是一个稳定的顺序，而是一个降序但稳定的顺序。他们都没有做到。

Answer 1

Why does the sort function change the order of same values?

因为 documentation 对于 std::sort() 是这样说的：

Sorts the elements in the range [first, last) in ascending order. The order of equal elements is not guaranteed to be preserved.

重点是我的。如果您需要保留顺序，请使用 std::stable_sort()

Sorts the elements in the range [first, last) in ascending order. The order of equivalent elements is guaranteed to be preserved.

注：

Sort function sorts it in increasing order. So what I am trying to do is to sort and then take them in reverse order.

这是一种错误的方法 - 你松散顺序不是因为 std::stable_sort() "does not work" 而是因为你在排序后反转你的向量，只需使用 std::stable_sort() 接受自定义比较器并提供一个（使用 lambda 的最佳选择）按降序对其进行排序。然后 std::stable_sort() 将保留相等元素的顺序，您不需要反转向量。

Answer 2

std::sort

Sorts the elements in the range [first, last) in ascending order. The order of equal elements is not guaranteed to be preserved.

因此，相等元素的顺序可能会改变，也可能不会改变。您要找的是std::stable_sort

Sorts the elements in the range [first, last) in ascending order. The order of equivalent elements is guaranteed to be preserved.

如果你想按降序对向量进行稳定排序，你的选择之一是使用 rbegin and rend。顺序将被颠倒；这是一个示例实现：

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

class A {
 public:
  A(int d = 0, const std::string& n = "a"): data(d), name(n) {}
  friend bool operator< (const A& par1, const A& par2) {
    return par1.data < par2.data;
  }
  A& operator= (const A& other) {
    data = other.getData();
    name = other.getName();
    return *this;
  }
  std::string getName() const {
    return name;
  }

  int getData() const {
    return data;
  }

 private:
  int data = 0;
  std::string name;
};

int main()
{
  A a(7, "a"), b(2, "b"), c(3, "c"), d(2, "d"), e(3, "e"), f(6, "f");
  std::vector<A> iv {a, b, c, d, e, f};
  std::stable_sort(iv.rbegin(), iv.rend());

  for (const auto e : iv) {
    std::cout << e.getName() << " ";
  }

  std::cout << std::endl;
  return 0;
}

输出：

a f c e b d

可以看出，相同元素的顺序得以保留，向量以相反的顺序排序。

另一个选项是使用 std::greater. It is defined in the <functional> header, and you will need operator>。这是一个示例实现：

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>


class A {
 public:
  A(int d = 0, const std::string& n = "a"): data(d), name(n) {}
  friend bool operator< (const A& par1, const A& par2) {
    return par1.data < par2.data;
  }
  friend bool operator> (const A& par1, const A& par2) {
    return par1.data > par2.data;
  }
  A& operator= (const A& other) {
    data = other.getData();
    name = other.getName();
    return *this;
  }
  std::string getName() const {
    return name;
  }

  int getData() const {
    return data;
  }

 private:
  int data = 0;
  std::string name;
};

int main()
{
  A a(7, "a"), b(2, "b"), c(3, "c"), d(2, "d"), e(3, "e"), f(6, "f");
  std::vector<A> iv {a, b, c, d, e, f};
  std::stable_sort(iv.begin(), iv.end(), std::greater<A>());

  for (const auto e : iv) {
    std::cout << e.getName() << " ";
  }
  std::cout << std::endl;
  return 0;
}

输出：

a f c e b d

编辑：

如果你想根据第一个元素对std::vector<std::pair<int, std::string>>类型的对象进行反向和稳定排序（这里似乎就是这种情况），你可以使用lambda：

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <functional>

using pis = std::pair<int, std::string>;


int main()
{
  pis a{5, "a"}, b{3, "b"}, c{4, "c"}, d{3, "d"}, e{3, "e"};
  std::vector<pis> iv {a, b, c, d, e};
  std::stable_sort(iv.begin(), iv.end(), [](const pis p1, const pis p2) {return p1.first > p2.first;});




  for (const auto e : iv) {
    std::cout << e.second << "(" << e.first << ")" << " ";
  }
  std::cout << std::endl;
  return 0;
}

输出：

a(5) c(4) b(3) d(3) e(3)

亮点
1. 注意 pis 是 type alias for std::pair<int, std::string>
2. 在 lambda 中使用 > 而不是 < 是导致向量反转的原因。

为什么排序函数会改变相同值的顺序？

Why does the sort function change the order of same values?

c++

sorting

programming-languages

std::sort

编辑：