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

Question

我有矢量类型std::vector<std::pair<int, std::string>>.我只是试图按降序排列(通过使用std::pair对象的第一个int值),同时保持稳定,以便相同的数字保持按插入顺序排列.

Fe:
如果我有:.5,3a,4,3b,6
我想订购它:6,5,4,3a,3b

但它似乎没有正常工作.排序功能按递增顺序对其进行排序.所以我想要做的是排序,然后以相反的顺序采取它们.但是后来我也得到了相反的相反值,它不稳定,对我不利.所以我尝试先颠倒整个矢量,然后才对它进行排序,然后按相反顺序进行排序,但我不知道为什么它不起作用？看起来sort函数按插入顺序改变它,即使我先反转向量.

无论如何,我如何实现我的目标.向量递减的向量,同时保持稳定.

编辑:对所有人说使用稳定排序.这也无济于事.我尝试过这个.我的问题不仅仅是一个稳定的订单,而是一个下降的顺序,而且稳定.他们没有实现它.

Answer 1

的std ::排序

按升序对[first,last]范围内的元素进行排序.不保证保持相等元素的顺序.

因此,相等元素的顺序可能会也可能不会改变.你要找的是std :: stable_sort

按升序对[first,last]范围内的元素进行排序.保证等效元素的顺序.

如果要按降序对向量进行稳定排序,可以选择使用rbegin和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.它在<functional>标题中定义,您将需要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为一个类型别名为std::pair<int, std::string>
2.使用的>,而不是<在lambda是什么原因导致被逆转的矢量.