对自定义对象的向量进行排序

Question

如何对包含自定义（即用户定义）对象的向量进行排序呢？
可能需要使用标准STL算法sort和一个谓词（一个函数或函数对象），该谓词将操作自定义对象中的一个字段（作为排序的键）。
我走在正确的道路上吗？

- TL36

---

可能是标准库排序和用户定义类型的重复问题。 - MCCCS

Answer 1

使用std::sort的一个简单例子

struct MyStruct
{
    int key;
    std::string stringValue;

    MyStruct(int k, const std::string& s) : key(k), stringValue(s) {}
};

struct less_than_key
{
    inline bool operator() (const MyStruct& struct1, const MyStruct& struct2)
    {
        return (struct1.key < struct2.key);
    }
};

std::vector < MyStruct > vec;

vec.push_back(MyStruct(4, "test"));
vec.push_back(MyStruct(3, "a"));
vec.push_back(MyStruct(2, "is"));
vec.push_back(MyStruct(1, "this"));

std::sort(vec.begin(), vec.end(), less_than_key());

---

编辑：正如Kirill V. Lyadvinsky所指出的那样，您可以实现MyStruct的operator<，而不是提供一个排序谓词：

struct MyStruct
{
    int key;
    std::string stringValue;

    MyStruct(int k, const std::string& s) : key(k), stringValue(s) {}

    bool operator < (const MyStruct& str) const
    {
        return (key < str.key);
    }
};

使用这种方法，您可以按照以下方式简单地对向量进行排序：

std::sort(vec.begin(), vec.end());

编辑2： 正如Kappa所建议的，您还可以通过重载>运算符并稍微更改sort函数的调用来将向量按降序排序：

struct MyStruct
{
    int key;
    std::string stringValue;

    MyStruct(int k, const std::string& s) : key(k), stringValue(s) {}

    bool operator > (const MyStruct& str) const
    {
        return (key > str.key);
    }
};

同时，您应该这样调用排序函数：

std::sort(vec.begin(), vec.end(),greater<MyStruct>());

- Alan

---

你能解释一下为什么在第一个例子中，你将结构体less_than_key中的比较函数compare声明为内联函数吗？ - kluka

另外一个问题/注意事项：如果一个类想要有多个排序方法（针对不同的属性），重载小于号运算符的方式可能不是一个选项，对吗？ - kluka

一个很棒的点子是提供 operator> 方法。这将允许我们进行反向排序，例如：std::sort(vec.begin(), vec.end(), greater<MyStruct>()) 这样既干净又优雅。 - kappa

你需要包含头文件<functional>才能使用"std::greater"。 - Nick Hartung

你可以只定义一个 operator<，然后使用 std::sort(vec.begin(), vec.end()); 或者 std::sort(vec.rbegin(), vec.rend()); 来实现升序或降序排序。 - Pixelchemist

Answer 2

为了更全面的覆盖，我提出了一个使用lambda表达式的实现。

C++11

#include <vector>
#include <algorithm>

using namespace std;

vector< MyStruct > values;

sort( values.begin( ), values.end( ), [ ]( const MyStruct& lhs, const MyStruct& rhs )
{
   return lhs.key < rhs.key;
});

C++14

#include <vector>
#include <algorithm>

using namespace std;

vector< MyStruct > values;

sort( values.begin( ), values.end( ), [ ]( const auto& lhs, const auto& rhs )
{
   return lhs.key < rhs.key;
});

- Ben Crowhurst

---

为了清晰明了，这将得到升序排列；若要得到降序排列，请使用>代替<。 - bhaller

Answer 3

你可以在调用 std::sort 函数时使用一个函数对象作为第三个参数，或者你可以在你的类中定义 operator< 运算符重载。

struct X {
    int x;
    bool operator<( const X& val ) const { 
        return x < val.x; 
    }
};

struct Xgreater
{
    bool operator()( const X& lx, const X& rx ) const {
        return lx.x < rx.x;
    }
};

int main () {
    std::vector<X> my_vec;

    // use X::operator< by default
    std::sort( my_vec.begin(), my_vec.end() );

    // use functor
    std::sort( my_vec.begin(), my_vec.end(), Xgreater() );
}

- Kirill V. Lyadvinsky

---

为什么我们需要在函数签名末尾加上const？ - prongs

该函数不会改变对象，因此它是“const”。 - Kirill V. Lyadvinsky

如果是这种情况，为什么我们要传递 "const X& val"，我认为将值传递为 const 到函数中会使函数认为其值不会被改变。 - Prashant Bhanarkar

@PrashantBhanarkar 在函数签名末尾使用 const 关键字表示 operator() 函数不会修改 Xgreater 结构体的实例（一般情况下此结构体可能具有成员变量），而仅在输入值前加上 const 表示这些输入值是不可变的。 - schester

@PrashantBhanarkar const in 可选，如果需要可以使用。但是使用它可以使排序更安全，因为您正在使用 &。 - Brijesh

Answer 4

对于排序一个vector或其他适用的（可变输入迭代器）范围内的自定义对象类型X，可以使用各种方法，特别是使用标准库算法如：

• sort,
• stable_sort,
• partial_sort或
• partial_sort_copy。

由于大多数技术已经发布，以获取X元素的相对顺序，因此我将从“为什么”和“何时”使用不同方法的一些注释开始。

“最佳”方法将取决于不同的因素：

1. 排序X对象范围是否是常见或罕见任务（这些范围是否在程序中的多个不同位置或库用户中排序）？
2. 所需排序是否“自然”（预期），还是有多种方式可以将类型与自身进行比较？
3. 性能是否成问题，或者应该对X对象范围进行排序？

如果排序X范围是常见任务，并且所获得的排序是预期的（即X仅包装单个基本值），那么可能会重载operator<，因为它使排序无需任何模糊（如正确传递适当的比较器）并反复产生预期结果。

如果排序是常见任务或可能在不同上下文中需要排序X对象，则我会选择Functors（自定义类的重载operator()函数）或函数指针（例如一个Functor/Function用于词法排序，另一个用于自然排序）。

如果类型X的排序范围不常见或不太可能出现在其他上下文中，我倾向于使用lambda而不是使任何命名空间混乱更多函数或类型。

特别是如果排序在某种方式上不“清晰”或“自然”，则可以轻松地通过查看应用于原位的lambda来获取排序逻辑，而operator<在第一眼看起来就是不透明的，您必须查找定义才能知道将应用哪个排序逻辑。

但要注意，单个operator<定义是单点故障，而多个lambda是多个故障点，并且需要更加谨慎。

如果在排序或者编译模板时没有定义operator<的定义，编译器可能会强制调用函数进行比较，而不是内联排序逻辑，这可能会带来严重的缺陷（至少当链接时间优化/代码生成未应用时）。

实现class X的可比性以使用标准库排序算法的方法：

假设有std::vector<X> vec_X;和std::vector<Y> vec_Y; 1. 重载T::operator<(T)或operator<(T, T)并使用标准库模板，但不需要一个比较函数。可以重载成员operator<:

struct X {
  int i{}; 
  bool operator<(X const &r) const { return i < r.i; } 
};
// ...
std::sort(vec_X.begin(), vec_X.end());

或者使用免费的 operator<：

struct Y {
  int j{}; 
};
bool operator<(Y const &l, Y const &r) { return l.j < r.j; }
// ...
std::sort(vec_Y.begin(), vec_Y.end());

2. 使用自定义比较函数的函数指针作为排序函数参数。

struct X {
  int i{};  
};
bool X_less(X const &l, X const &r) { return l.i < r.i; }
// ...
std::sort(vec_X.begin(), vec_X.end(), &X_less);

3. 为自定义类型创建一个bool operator()(T, T)重载函数，该函数可作为比较函数传递。

struct X {
  int i{};  
  int j{};
};
struct less_X_i
{
    bool operator()(X const &l, X const &r) const { return l.i < r.i; }
};
struct less_X_j
{
    bool operator()(X const &l, X const &r) const { return l.j < r.j; }
};
// sort by i
std::sort(vec_X.begin(), vec_X.end(), less_X_i{});
// or sort by j
std::sort(vec_X.begin(), vec_X.end(), less_X_j{});

那些函数对象的定义可以使用C++11和模板更加通用地编写：

struct less_i
{ 
    template<class T, class U>
    bool operator()(T&& l, U&& r) const { return std::forward<T>(l).i < std::forward<U>(r).i; }
};

这可以用于排序任何具有支持<运算符的成员i的类型。

4. 通过将匿名闭包（lambda）作为比较参数传递给排序函数。

struct X {
  int i{}, j{};
};
std::sort(vec_X.begin(), vec_X.end(), [](X const &l, X const &r) { return l.i < r.i; });

C++14使得Lambda表达式更加通用:

std::sort(a.begin(), a.end(), [](auto && l, auto && r) { return l.i < r.i; });

这可以被包装在一个宏中。

#define COMPARATOR(code) [](auto && l, auto && r) -> bool { return code ; }

使普通比较器的创建变得非常顺畅：

// sort by i
std::sort(v.begin(), v.end(), COMPARATOR(l.i < r.i));
// sort by j
std::sort(v.begin(), v.end(), COMPARATOR(l.j < r.j));

- Pixelchemist

---

在第二种情况下，您编写了 bool X_less(X const &l, X const &r) const { return l.i < r.i; } 作为比较器，但应该删除 const 关键字（因为它不是成员函数）。 - PolGraphic

@PolGraphic：正确 - 在情况1下也是如此。 - Pixelchemist

@Pixelchemist 如果我不使用std::sort或类似的方法，但需要一个Compare实例，例如在实例化std::set时，我该如何使用(4.) lambda方法？ - azrdev

@azrdev：一个函数模板，它捕获闭包的类型并将其作为模板参数传递给set：template<class T, class C> std::set<T, C> make_set(C const& compare) { return std::set<T, C>{ compare }; }，可以像这样使用：auto xset = make_set<X>([](auto && l, auto && r) { return l.i < r.i; });。 - Pixelchemist

Answer 5

你已经走在了正确的道路上。std::sort默认会使用operator<作为比较函数。因此，如果要对你的对象进行排序，你需要重载bool operator<( const T&, const T& )或提供一个函数对象来执行比较，就像这样：

 struct C {
    int i;
    static bool before( const C& c1, const C& c2 ) { return c1.i < c2.i; }
 };

 bool operator<( const C& c1, const C& c2 ) { return c1.i > c2.i; }

 std::vector<C> values;

 std::sort( values.begin(), values.end() ); // uses operator<
 std::sort( values.begin(), values.end(), C::before );

使用函数对象的优点是可以使用访问类的私有成员的函数。

- xtofl

---

错过了这个：提供一个成员函数 operator<。 - xtofl

最好将operator<作为类（或结构体）的成员，因为全局的操作符可能会使用受保护或私有的成员。或者你可以将其设置为结构体C的友元函数。 - Kirill V. Lyadvinsky

Answer 6

以下是使用lambda表达式的代码：（点击此处查看更多信息）

#include <vector>
#include <algorithm>

using namespace std;

struct MyStruct
{
    int key;
    std::string stringValue;

    MyStruct(int k, const std::string& s) : key(k), stringValue(s) {}
};

int main()
{
    std::vector < MyStruct > vec;

    vec.push_back(MyStruct(4, "test"));
    vec.push_back(MyStruct(3, "a"));
    vec.push_back(MyStruct(2, "is"));
    vec.push_back(MyStruct(1, "this"));

    std::sort(vec.begin(), vec.end(), 
        [] (const MyStruct& struct1, const MyStruct& struct2)
        {
            return (struct1.key < struct2.key);
        }
    );
    return 0;
}

- Sathwick

Answer 7

我很好奇在不同的std::sort函数调用方式之间是否存在可衡量的性能影响，因此我创建了这个简单的测试：

$ cat sort.cpp
#include<algorithm>
#include<iostream>
#include<vector>
#include<chrono>

#define COMPILER_BARRIER() asm volatile("" ::: "memory");

typedef unsigned long int ulint;

using namespace std;

struct S {
  int x;
  int y;
};

#define BODY { return s1.x*s2.y < s2.x*s1.y; }

bool operator<( const S& s1, const S& s2 ) BODY
bool Sgreater_func( const S& s1, const S& s2 ) BODY

struct Sgreater {
  bool operator()( const S& s1, const S& s2 ) const BODY
};

void sort_by_operator(vector<S> & v){
  sort(v.begin(), v.end());
}

void sort_by_lambda(vector<S> & v){
  sort(v.begin(), v.end(), []( const S& s1, const S& s2 ) BODY );
}

void sort_by_functor(vector<S> &v){
  sort(v.begin(), v.end(), Sgreater());
}

void sort_by_function(vector<S> &v){
  sort(v.begin(), v.end(), &Sgreater_func);
}

const int N = 10000000;
vector<S> random_vector;

ulint run(void foo(vector<S> &v)){
  vector<S> tmp(random_vector);
  foo(tmp);
  ulint checksum = 0;
  for(int i=0;i<tmp.size();++i){
     checksum += i *tmp[i].x ^ tmp[i].y;
  }
  return checksum;
}

void measure(void foo(vector<S> & v)){

ulint check_sum = 0;

  // warm up
  const int WARMUP_ROUNDS = 3;
  const int TEST_ROUNDS = 10;

  for(int t=WARMUP_ROUNDS;t--;){
    COMPILER_BARRIER();
    check_sum += run(foo);
    COMPILER_BARRIER();
  }

  for(int t=TEST_ROUNDS;t--;){
    COMPILER_BARRIER();
    auto start = std::chrono::high_resolution_clock::now();
    COMPILER_BARRIER();
    check_sum += run(foo);
    COMPILER_BARRIER();
    auto end = std::chrono::high_resolution_clock::now();
    COMPILER_BARRIER();
    auto duration_ns = std::chrono::duration_cast<std::chrono::duration<double>>(end - start).count();

    cout << "Took " << duration_ns << "s to complete round" << endl;
  }

  cout << "Checksum: " << check_sum << endl;
}

#define M(x) \
  cout << "Measure " #x " on " << N << " items:" << endl;\
  measure(x);

int main(){
  random_vector.reserve(N);

  for(int i=0;i<N;++i){
    random_vector.push_back(S{rand(), rand()});
  }

  M(sort_by_operator);
  M(sort_by_lambda);
  M(sort_by_functor);
  M(sort_by_function);
  return 0;
}

它的功能是创建一个随机向量，然后测量复制并对其排序所需的时间（同时计算一些校验和以避免过度的死代码消除）。

我使用的编译器是g++（GCC）7.2.1 20170829（Red Hat 7.2.1-1）。

$ g++ -O2 -o sort sort.cpp && ./sort

这里是结果：

Measure sort_by_operator on 10000000 items:
Took 0.994285s to complete round
Took 0.990162s to complete round
Took 0.992103s to complete round
Took 0.989638s to complete round
Took 0.98105s to complete round
Took 0.991913s to complete round
Took 0.992176s to complete round
Took 0.981706s to complete round
Took 0.99021s to complete round
Took 0.988841s to complete round
Checksum: 18446656212269526361
Measure sort_by_lambda on 10000000 items:
Took 0.974274s to complete round
Took 0.97298s to complete round
Took 0.964506s to complete round
Took 0.96899s to complete round
Took 0.965773s to complete round
Took 0.96457s to complete round
Took 0.974286s to complete round
Took 0.975524s to complete round
Took 0.966238s to complete round
Took 0.964676s to complete round
Checksum: 18446656212269526361
Measure sort_by_functor on 10000000 items:
Took 0.964359s to complete round
Took 0.979619s to complete round
Took 0.974027s to complete round
Took 0.964671s to complete round
Took 0.964764s to complete round
Took 0.966491s to complete round
Took 0.964706s to complete round
Took 0.965115s to complete round
Took 0.964352s to complete round
Took 0.968954s to complete round
Checksum: 18446656212269526361
Measure sort_by_function on 10000000 items:
Took 1.29942s to complete round
Took 1.3029s to complete round
Took 1.29931s to complete round
Took 1.29946s to complete round
Took 1.29837s to complete round
Took 1.30132s to complete round
Took 1.3023s to complete round
Took 1.30997s to complete round
Took 1.30819s to complete round
Took 1.3003s to complete round
Checksum: 18446656212269526361

看起来除了传递函数指针以外，所有选项都非常相似，而传递函数指针会导致+30%的惩罚。

此外，运算符<版本似乎慢了约1％（我多次重复测试，效果仍然存在），这有点奇怪，因为它表明生成的代码不同（我缺乏分析--save-temps输出的技能）。

- qbolec

Answer 8

在你的类中，你可以重载"<"运算符。

class MyClass
{
  bool operator <(const MyClass& rhs)
  {
    return this->key < rhs.key;
  }
}

- BobbyShaftoe

Answer 9

在C++20中，可以默认使用operator<=>运算符而无需用户定义比较器。编译器会自动处理此过程。

#include <iostream>
#include <compare>
#include <vector>
#include <algorithm>

struct MyInt
{
    int value;
    MyInt(int val) : value(val) {}
    auto operator<=>(const MyInt& other) const = default;
};


int main()
{
    MyInt Five(5);
    MyInt Two(2);
    MyInt Six(6);
    
    std::vector V{Five, Two, Six};
    std::sort(V.begin(), V.end());
    
    for (const auto& element : V)
        std::cout << element.value << std::endl;
}

输出：

2
5
6

- Tony Tannous

Answer 10

是的，使用第三个参数（函数或对象）的std::sort()会更容易。例如：http://www.cplusplus.com/reference/algorithm/sort/

- swatkat

---

不完全是一个仅包含链接的答案，但至少提供一个单行示例会很有用。 - Manos Nikolaidis