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

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

排序, stable_sort, partial_sort或 partial_sort_copy。

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

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

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

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

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

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

如果排序在某种程度上不“清晰”或“自然”，这尤其正确。您可以很容易地了解排序背后的逻辑，因为lambda是就地应用的，而operator<一看就是opague，您必须查看定义才能知道将应用什么排序逻辑。

但是请注意，单个操作符<定义是单点故障，而多个lambas是多个故障点，需要更加谨慎。

如果操作符<的定义在排序完成/编译排序模板时不可用，编译器可能会在比较对象时强制进行函数调用，而不是内联排序逻辑，这可能是一个严重的缺陷(至少在没有应用链接时间优化/代码生成时)。

实现类X的可比性的方法，以便使用标准库排序算法

让std::vector<X> vec_X;and std::vector<Y> vec_Y;

1. 重载T::operator<(T)或operator<(T, T)，并使用不需要比较函数的标准库模板。

重载成员运算符<:

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

或自由运算符<:

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

2016-05-19 22:11:02

是的，std::sort()与第三个参数(函数或对象)将更容易。一个例子: http://www.cplusplus.com/reference/algorithm/sort/

2009-09-04 17:11:31

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

2014-10-10 08:54:12

在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

2020-12-14 10:38:28

中使用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);

2016-08-02 20:38:15