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

Question

如何排序包含自定义(即用户定义)对象的向量.
可能应该使用标准STL算法与谓词(函数或函数对象)一起排序,该谓词将在自定义对象中的一个字段(作为排序键)上操作.
我是在正确的轨道上吗？

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指出的那样,您可以实现operator<for MyStruct:而不是提供排序谓词.

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());

Edit2:正如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);
    }
};

你应该将sort称为:

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

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;
});

Answer 3

你可以使用functor作为第三个参数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() );
}

Answer 4

你走在正确的轨道上. 默认情况下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 );

使用仿函数的优点是您可以使用一个函数来访问类的私有成员.

Answer 5

可以使用各种方法对这类vector或任何其他适用的(可变输入迭代器)类型的自定义对象进行排序X,尤其是包括使用标准库算法,如

• sort,
• stable_sort,
• partial_sort 要么
• partial_sort_copy.

由于大多数技术,为了获得X元素的相对排序,已经发布,我将从一些关于"为什么"和"何时"使用各种方法的注释开始.

"最佳"方法取决于不同因素:

1. 将X对象的范围排序为常见或罕见的任务(这些范围是在程序中的多个不同位置还是由库用户排序)？
2. 所需的排序是"自然的"(预期的)还是有多种方式可以将类型与自身进行比较？
3. 性能是一个问题还是X对象的排序范围是万无一失的？

如果排序范围X是一个常见的任务,并且预期实现排序(即X只包含一个基本值),那么可能会进行过载,operator<因为它可以在没有任何模糊的情况下进行排序(如正确传递正确的比较器)并反复产生预期结果.

如果排序是一项常见任务或可能在不同的上下文中需要,但有多个标准可用于排序X对象,我会选择Functors(operator()自定义类的重载函数)或函数指针(即一个函数/函数)用于词法排序,另一个用于自然排序).

如果类型的排序范围X在其他上下文中不常见或不太可能,我倾向于使用lambdas而不是使用更多函数或类型来混淆任何名称空间.

如果排序在某种程度上不是"清楚的"或"自然的",则尤其如此.在查看就地应用的lambda时,您可以轻松获得排序背后的逻辑,而operator<初看起来是不明智的,您必须查看定义以了解将应用的排序逻辑.

但请注意,单个operator<定义是单点故障,而多个lambas是多个故障点,需要更加谨慎.

如果在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.将anonymus closure(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));

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;
}

Answer 7

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

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

Answer 8

我很好奇在调用 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% 的惩罚。

看起来 operator< 版本也慢了大约 1%（我多次重复测试并且效果仍然存在），这有点奇怪，因为它表明生成的代码不同（我缺乏分析的技巧--save-温度输出）。

Answer 9

在 C++20 中，可以默认运算符<=>，而无需用户定义的比较器。编译器会处理这个问题。

#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