Сортировка вектора пользовательских объектов

Как происходит сортировка вектора, содержащего пользовательские (т. е. определенные пользователем) объекты.

Наверное, стандартный алгоритм STL вроде наряду с предикатом (функция или объект функции), который будет работать на одном из полей (в качестве ключа для сортировки) в пользовательском объекте должны быть использованы.

Я на правильном пути?

1051   13  

13 ответов:

простой пример использования 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: по словам Кирилла В. Lyadvinsky указал, вместо того, чтобы оказывать своего рода предикат, вы можете использовать тег operator< на 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: как предлагает Каппа, вы также можете сортировать вектор в порядке убывания, перегружая a > оператор и немного изменив вызов сортировки:

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>());
303  
2018-03-26 18:30:55

в интересах покрытия. Я выдвинул реализацию с помощью лямбда-выражения.

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;
});
123  
2017-07-14 01:38:31

вы можете использовать функтор в качестве третьего аргумента 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() );
}
52  
2009-09-04 20:16:21

вы на правильном пути. 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 );

преимущество использования функтора заключается в том, что вы можете использовать функцию с доступом к закрытым членам класса.

12  
2016-03-01 23:32:22

сортировка такой vector или любой другой применимый (изменяемый входной итератор) диапазон пользовательских объектов типа X может быть достигнуто с помощью различных методов, особенно в том числе с использованием стандартных библиотечных алгоритмов, таких как

так как большинство методов, чтобы получить относительный порядок X элементы, уже были опубликованы, я начну с некоторых заметок о "почему" и "когда" использовать различные подходы.

"лучший" подход будет зависеть от разных факторов:

  1. - сортировка диапазонов X объекты общая или редкая задача (будут ли такие диапазоны сортироваться в нескольких разных местах в программе или пользователями библиотеки)?
  2. является ли требуемая сортировка "естественной" (ожидаемой) или существует несколько способов тип можно было бы сравнить с самим собой?
  3. является ли производительность проблемой или следует сортировать диапазоны X объекты быть защита от дурака?

если сортировка диапазонов X является общей задачей и достигнутой сортировки следует ожидать (т. е. X просто обертывает одно фундаментальное значение) тогда, вероятно, пойдет на перегрузку operator< поскольку он позволяет сортировать без каких-либо пух (например, правильно передавая правильные компараторы) и неоднократно дает ожидаемые результаты результаты.

если сортировка является общей задачей или может потребоваться в различных ситуациях, но есть несколько критериев, которые могут быть использованы для сортировки X объекты, я бы пошел на функторы (перегружен operator() функции пользовательских классов) или указатели функций (т. е. один функтор/функция для лексического упорядочения и другой для естественного упорядочения).

если сортировка диапазонов типа X является необычным или маловероятным в других контекстах я склонен использовать лямбды вместо загромождение любого пространства имен с большим количеством функций или типов.

это особенно верно, если сортировка не является "ясной" или "естественной" в некотором роде. Вы можете легко получить логику заказа, глядя на лямбду, которая применяется на месте, тогда как 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());

или бесплатные 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; }
};

, который может быть использован для сортировки любого типа С поддержка <.

4. Передайте замыкание Анонимуса (лямбда) в качестве параметра сравнения в функции сортировки.

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 обеспечивает еще более общий лямбда выражение:

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));
10  
2016-08-30 00:44:11

да std::sort() с третьим параметром (функция или объект) было бы проще. Образец: http://www.cplusplus.com/reference/algorithm/sort/

4  
2015-12-31 13:20:36

в вашем классе, вы можете перегрузить оператор" 

class MyClass
{
  bool operator <(const MyClass& rhs)
  {
    return this->key < rhs.key;
  }
}
3  
2014-10-10 21:52:50

Ниже приведен код с помощью лямбда

#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;
}
2  
2016-04-20 10:28:08 
    // 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;
    }
1  
2013-12-24 18:21:36

вы можете использовать определенный пользователем класс компаратора.

class comparator
{
    int x;
    bool operator()( const comparator &m,  const comparator &n )
    { 
       return m.x<n.x;
    }
 }
1  
2017-08-08 14:47:53

для сортировки вектора можно использовать алгоритм sort () in .

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);
0  
2016-08-02 23:38:15 
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);
}

если сравнение ложно, он будет делать "своп".

0  
2017-09-01 06:05:32

мне было любопытно, есть ли какое-либо измеримое влияние на производительность между различными способами, которые можно вызвать 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%.

Он также выглядит как оператор

0  
2018-06-09 09:11:54

Comments

    Ничего не найдено.
Click here to cancel reply.