Menyortir vektor objek khusus

Bagaimana cara menyortir vektor yang berisi objek kustom (yaitu yang ditentukan pengguna).
Mungkin, algoritma STL standar menyortir bersama dengan predikat (fungsi atau objek fungsi) yang akan beroperasi pada salah satu bidang (sebagai kunci untuk menyortir) dalam objek kustom harus digunakan.
Apakah saya di jalur yang benar?

Contoh sederhana menggunakan 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());

Sunting: Seperti yang ditunjukkan Kirill V. Lyadvinsky, alih-alih memberikan predikat semacam, Anda dapat menerapkan operator<untuk 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);
    }
};

Menggunakan metode ini berarti Anda cukup mengurutkan vektor sebagai berikut:

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

Sunting2: Seperti yang disarankan Kappa, Anda juga dapat mengurutkan vektor dalam urutan menurun dengan membebani >operator dan mengubah sedikit panggilan:

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

Dan Anda harus memanggil sortir sebagai:

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

Untuk kepentingan liputan. Saya mengajukan implementasi menggunakan ekspresi 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;
});

Anda bisa menggunakan functor sebagai argumen ketiga std::sort, atau Anda bisa mendefinisikan operator<di kelas Anda.

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

Menyortir vectorberbagai objek jenis kustom yang Xdapat diterapkan (dapat dimutasikan input) jenis ini dapat dicapai dengan menggunakan berbagai metode, terutama termasuk penggunaan algoritma perpustakaan standar seperti

• sort,
• stable_sort,
• partial_sort atau
• partial_sort_copy.

Karena sebagian besar teknik, untuk mendapatkan urutan relatif Xelemen, telah diposting, saya akan mulai dengan beberapa catatan tentang "mengapa" dan "kapan" untuk menggunakan berbagai pendekatan.

Pendekatan "terbaik" akan tergantung pada berbagai faktor:

1. Apakah menyortir rentang Xobjek merupakan tugas yang umum atau jarang (akankah rentang tersebut diurutkan menjadi beberapa tempat yang berbeda dalam program atau oleh pengguna perpustakaan)?
2. Apakah pemilahan yang diperlukan "alami" (diharapkan) atau apakah ada beberapa cara tipe dapat dibandingkan dengan dirinya sendiri?
3. Apakah kinerja masalah atau haruskah menyortir rentang Xobjek menjadi sangat mudah?

Jika menyortir rentang Xadalah tugas umum dan penyortiran yang dicapai diharapkan (yaitu Xhanya membungkus nilai fundamental tunggal) maka mungkin akan pergi untuk kelebihan operator<karena memungkinkan menyortir tanpa fuzz (seperti melewati pembanding yang tepat dengan benar) dan berulang kali menghasilkan diharapkan hasil.

Jika menyortir adalah tugas umum atau mungkin diperlukan dalam konteks yang berbeda, tetapi ada beberapa kriteria yang dapat digunakan untuk menyortir Xobjek, saya akan mencari Functors ( operator()fungsi kelas kustom yang berlebihan ) atau pointer fungsi (yaitu satu functor / fungsi untuk pemesanan leksikal dan satu lagi untuk pemesanan alami).

Jika menyortir rentang tipe Xjarang atau tidak mungkin dalam konteks lain saya cenderung menggunakan lambdas daripada mengacaukan namespace dengan lebih banyak fungsi atau tipe.

Ini terutama benar jika penyortiran tidak "jelas" atau "alami" dalam beberapa cara. Anda dapat dengan mudah mendapatkan logika di balik pemesanan ketika melihat lambda yang diterapkan di tempat sedangkan operator<buram pada pandangan pertama dan Anda harus melihat definisi untuk tahu apa logika pemesanan akan diterapkan.

Namun perlu dicatat, bahwa operator<definisi tunggal adalah titik kegagalan tunggal sedangkan banyak lambas adalah titik kegagalan ganda dan memerlukan perhatian lebih.

Jika definisi operator<tidak tersedia di mana penyortiran dilakukan / template penyortiran dikompilasi, kompiler mungkin dipaksa untuk membuat panggilan fungsi ketika membandingkan objek, alih-alih menguraikan logika pemesanan yang mungkin merupakan kelemahan parah (setidaknya ketika optimisasi waktu taut / pembuatan kode tidak diterapkan).

Cara untuk mencapai keterbandingan class Xuntuk menggunakan algoritma pengurutan perpustakaan standar

Biarkan std::vector<X> vec_X;danstd::vector<Y> vec_Y;

1. Kelebihan T::operator<(T)atau operator<(T, T)dan gunakan templat pustaka standar yang tidak mengharapkan fungsi perbandingan.

Salah satu anggota kelebihan beban operator<:

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

atau gratis 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. Gunakan pointer fungsi dengan fungsi perbandingan khusus sebagai parameter fungsi penyortiran.

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. Buat bool operator()(T, T)kelebihan untuk jenis kustom yang dapat dilewatkan sebagai fungsi perbandingan.

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

Definisi objek fungsi tersebut dapat ditulis sedikit lebih umum menggunakan C ++ 11 dan templat:

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

yang dapat digunakan untuk mengurutkan jenis apa pun dengan anggota ipendukung <.

4. Lewati penutupan anonymus (lambda) sebagai parameter perbandingan ke fungsi penyortiran.

struct X {
  int i{}, j{};
};
std::sort(vec_X.begin(), vec_X.end(), [](X const &l, X const &r) { return l.i < r.i; });

Di mana C ++ 14 memungkinkan ekspresi lambda yang lebih umum:

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

yang bisa dibungkus makro

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

membuat pembuatan pembanding biasa cukup lancar:

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

Anda berada di jalur yang benar. std::sortakan digunakan operator<sebagai fungsi perbandingan secara default. Jadi untuk mengurutkan objek Anda, Anda harus membebani bool operator<( const T&, const T& )atau menyediakan functor yang melakukan perbandingan, seperti ini:

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

Keuntungan penggunaan functor adalah Anda dapat menggunakan fungsi dengan akses ke anggota pribadi kelas.

Saya ingin tahu apakah ada dampak yang dapat diukur pada kinerja antara berbagai cara yang dapat disebut std :: sort, jadi saya telah membuat tes sederhana ini:

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

Apa yang dilakukannya adalah menciptakan vektor acak, dan kemudian mengukur berapa banyak waktu yang diperlukan untuk menyalinnya dan mengurutkan salinannya (dan menghitung beberapa checksum untuk menghindari penghapusan kode mati yang terlalu kuat).

Saya mengkompilasi dengan g ++ (GCC) 7.2.1 20170829 (Red Hat 7.2.1-1)

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

Ini hasilnya:

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

Sepertinya semua opsi kecuali untuk melewatkan pointer fungsi sangat mirip, dan melewatkan pointer fungsi menyebabkan penalti + 30%.

Ini juga terlihat seperti operator <versi ~ 1% lebih lambat (saya mengulangi tes beberapa kali dan efeknya tetap ada), yang agak aneh karena menunjukkan bahwa kode yang dihasilkan berbeda (saya kurang memiliki keterampilan untuk menganalisis - menghemat- temps output).

Ya, std::sort()dengan parameter ketiga (fungsi atau objek) akan lebih mudah. Contoh: http://www.cplusplus.com/reference/algorithm/sort/

Di kelas Anda, Anda mungkin membebani operator "<".

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

Di bawah ini adalah kode menggunakan 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;
}

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

Anda dapat menggunakan kelas pembanding yang ditentukan pengguna.

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

Untuk mengurutkan vektor, Anda dapat menggunakan algoritma sort () di.

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

Parameter ketiga yang digunakan bisa lebih besar atau lebih kecil atau fungsi atau objek apa pun juga bisa digunakan. Namun operator default adalah <jika Anda membiarkan parameter ketiga kosong.

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

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

jika perbandingan salah, itu akan melakukan "swap".