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

Sorting a vector of custom objects

提问by Ankur

How does one go about sorting a vector containing custom (i.e. user defined) objects.
Probably, standard STL algorithm sortalong with a predicate (a function or a function object) which would operate on one of the fields (as a key for sorting) in the custom object should be used.
Am I on the right track?

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

回答by Alan

A simple example using std::sort

一个简单的例子使用 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());

---

---

Edit:As Kirill V. Lyadvinsky pointed out, instead of supplying a sort predicate, you can implement the operator<for MyStruct:

编辑：正如 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);
    }
};

Using this method means you can simply sort the vector as follows:

使用此方法意味着您可以简单地按如下方式对向量进行排序：

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

Edit2:As Kappa suggests you can also sort the vector in the descending order by overloading a >operator and changing call of sort a bit:

编辑 2：正如 Kappa 建议的那样，您还可以通过重载>运算符并稍微更改排序调用来按降序对向量进行排序：

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

And you should call sort as:

您应该将 sort 称为：

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

回答by Ben Crowhurst

In the interest of coverage. I put forward an implementation using lambda expressions.

为了覆盖的利益。我提出了一个使用lambda 表达式的实现。

C++11

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

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

回答by Kirill V. Lyadvinsky

You could use functor as third argument of std::sort, or you could define operator<in your class.

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

回答by Pixelchemist

Sorting such a vectoror any other applicable (mutable input iterator) range of custom objects of type Xcan be achieved using various methods, especially including the use of standard library algorithms like

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

• sort,
• stable_sort,
• partial_sortor
• partial_sort_copy.

• sort,
• stable_sort,
• partial_sort或者
• partial_sort_copy.

Since most of the techniques, to obtain relative ordering of Xelements, have already been posted, I'll start by some notes on "why" and "when" to use the various approaches.

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

The "best" approach will depend on different factors:

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

1. Is sorting ranges of Xobjects a common or a rare task (will such ranges be sorted a mutiple different places in the program or by library users)?
2. Is the required sorting "natural" (expected) or are there multiple ways the type could be compared to itself?
3. Is performance an issue or should sorting ranges of Xobjects be foolproof?

1. 对X对象范围进行排序是一项常见任务还是一项罕见任务（此类范围是否会在程序或库用户的多个不同位置进行排序）？
2. 所需的排序是“自然的”（预期）还是可以通过多种方式将类型与其自身进行比较？
3. 性能是一个问题还是X对象的排序范围应该是万无一失的？

If sorting ranges of Xis a common task and the achieved sorting is to be expected (i.e. Xjust wraps a single fundamental value) then on would probably go for overloading operator<since it enables sorting without any fuzz (like correctly passing proper comparators) and repeatedly yields expected results.

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

If sorting is a common task or likely to be required in different contexts, but there are multiple criteria which can be used to sort Xobjects, I'd go for Functors (overloaded operator()functions of custom classes) or function pointers (i.e. one functor/function for lexical ordering and another one for natural ordering).

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

If sorting ranges of type Xis uncommon or unlikely in other contexts I tend to use lambdas instead of cluttering any namespace with more functions or types.

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

This is especially true if the sorting is not "clear" or "natural" in some way. You can easily get the logic behind the ordering when looking at a lambda that is applied in-place whereas operator<is opague at first sight and you'd have to look the definition up to know what ordering logic will be applied.

如果排序在某些方面不是“清晰”或“自然”，则尤其如此。在查看就地应用而operator<乍一看不透明的 lambda 时，您可以轻松获得排序背后的逻辑，您必须查看定义才能知道将应用什么排序逻辑。

Note however, that a single operator<definition is a single point of failure whereas multiple lambas are multiple points of failure and require a more caution.

但是请注意，单个operator<定义是单点故障，而多个 labas 是多个故障点，需要更加小心。

If the definition of operator<isn't available where the sorting is done / the sort template is compiled, the compiler might be forced to make a function call when comparing objects, instead of inlining the ordering logic which might be a severe drawback (at least when link time optimization/code generation is not applied).

如果在operator<完成排序/编译排序模板的地方定义不可用，则编译器在比较对象时可能会被迫进行函数调用，而不是内联排序逻辑，这可能是一个严重的缺点（至少当不应用链接时间优化/代码生成）。

Ways to achieve comparability of class Xin order to use standard library sorting algorithms

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

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

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

1. Overload T::operator<(T)or operator<(T, T)and use standard library templates that do not expect a comparison function.

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

Either overload member operator<:

任一重载成员operator<：

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

or free operator<:

或免费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. Use a function pointer with a custom comparison function as sorting function parameter.

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. Create a bool operator()(T, T)overload for a custom type which can be passed as comparison functor.

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

Those function object definitions can be written a little more generic using C++11 and templates:

这些函数对象定义可以使用 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; }
};

which can be used to sort any type with member isupporting <.

可用于对具有成员i支持的任何类型进行排序<。

4. Pass an anonymus closure (lambda) as comparison parameter to the sorting functions.

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

Where C++14 enables a even more generic lambda expression:

C++14 支持更通用的 lambda 表达式：

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

which could be wrapped in a macro

可以包裹在宏中

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

making ordinary comparator creation quite smooth:

使普通比较器的创建非常流畅：

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

回答by xtofl

You are on the right track. std::sortwill use operator<as comparison function by default. So in order to sort your objects, you will either have to overload bool operator<( const T&, const T& )or provide a functor that does the comparison, much like this:

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

The advantage of the usage of a functor is that you can use a function with access to the class' private members.

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

回答by swatkat

Yes, std::sort()with third parameter (function or object) would be easier. An example: http://www.cplusplus.com/reference/algorithm/sort/

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

回答by qbolec

I was curious if there is any measurable impact on performance between the various ways one can call std::sort, so I've created this simple test:

我很好奇在调用 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;
}

What it does is it creates a random vector, and then measures how much time is required to copy it and sort the copy of it (and compute some checksum to avoid too vigorous dead code elimination).

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

I was compiling with g++ (GCC) 7.2.1 20170829 (Red Hat 7.2.1-1)

我用 g++ (GCC) 7.2.1 20170829 (Red Hat 7.2.1-1) 编译

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

Here are results:

以下是结果：

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

Looks like all the options except for passing function pointer are very similar, and passing a function pointer causes +30% penalty.

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

It also looks like the operator< version is ~1% slower (I repeated the test multiple times and the effect persists), which is a bit strange as it suggests that the generated code is different (I lack skill to analyze --save-temps output).

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

回答by BobbyShaftoe

In your class, you may overload the "<" operator.

在您的课程中，您可能会重载“<”运算符。

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

回答by Sathwick

Below is the code using lambdas

下面是使用lambdas的代码

#include "stdafx.h"
#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;
}

回答by Amin Alomaisi

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