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

你可以使用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() );
}

在类中，可以重载“<”操作符。

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

你的思路是对的。默认情况下，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 );

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

一个使用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());

正如Kappa所建议的那样，你也可以通过重载>操作符并更改sort调用来对vector进行降序排序:

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

    // sort algorithm example
#include <iostream>     // std::cout
#include <algorithm>    // std::sort
#include <vector>       // std::vector
using namespace std;
int main () {
char myints[] = {'F','C','E','G','A','H','B','D'};
vector<char> myvector (myints, myints+8);               // 32 71 12 45 26 80 53 33
// using default comparison (operator <):
sort (myvector.begin(), myvector.end());           //(12 32 45 71)26 80 53 33
// print out content:
cout << "myvector contains:";
for (int i=0; i!=8; i++)
cout << ' ' <<myvector[i];
cout << '\n';
system("PAUSE");
return 0;
}

为了覆盖范围。我使用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;
});

下面是使用λ的代码

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

这样的vector或任何其他适用的(可变输入迭代器)X类型的自定义对象范围的排序可以使用各种方法来实现，特别是包括使用标准库算法，如

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

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

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

1. X对象的排序范围是常见的还是罕见的任务(这样的范围将在程序中多个不同的地方排序或由库用户排序)?
2. 所需的排序是“自然的”(预期的)还是有多种方法可以将类型与自身进行比较?
3. 性能是一个问题，还是X对象的排序范围应该是万无一失的?

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

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

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

如果排序在某种程度上不“清晰”或“自然”，这尤其正确。你可以很容易地得到排序背后的逻辑，当你看到一个被应用的lambda，而operator<是opague第一眼，你必须查看定义，知道什么排序逻辑将被应用。

但是请注意，单个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());

或free 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));

中使用sort()算法对向量进行排序。

sort(vec.begin(),vec.end(),less<int>());

使用的第三个参数可以是更大或更小，也可以使用任何函数或对象。但是默认操作符是<如果第三个参数为空。

// using function as comp
std::sort (myvector.begin()+4, myvector.end(), myfunction);
bool myfunction (int i,int j) { return (i<j); }


// using object as comp
std::sort (myvector.begin(), myvector.end(), myobject);

您可以使用用户定义的比较器类。

class comparator
{
int x;
bool operator()( const comparator &m,  const comparator &n )
{
return m.x<n.x;
}
}

typedef struct Freqamp{
double freq;
double amp;
}FREQAMP;


bool struct_cmp_by_freq(FREQAMP a, FREQAMP b)
{
return a.freq < b.freq;
}


main()
{
vector <FREQAMP> temp;
FREQAMP freqAMP;


freqAMP.freq = 330;
freqAMP.amp = 117.56;
temp.push_back(freqAMP);


freqAMP.freq = 450;
freqAMP.amp = 99.56;
temp.push_back(freqAMP);


freqAMP.freq = 110;
freqAMP.amp = 106.56;
temp.push_back(freqAMP);


sort(temp.begin(),temp.end(), struct_cmp_by_freq);
}

如果compare为false，它将执行“swap”。

我很好奇在调用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输出)。

在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