Sortowanie wektora obiektów niestandardowych

W interesie pokrycia. Przedstawiłem implementację wykorzystującą wyrażenia 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;
});

Możesz użyć functora jako Trzeciego argumentu std::sort lub zdefiniować operator< w swojej klasie.

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

Jesteś na dobrej drodze. std::sort domyślnie używa operator< jako funkcji porównawczej. Aby posortować obiekty, musisz albo przeciążyć bool operator<( const T&, const T& ), albo podać funktor, który wykonuje porównanie, podobnie jak to:

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

Zaletą użycia functora jest to, że można używać funkcji z dostępem do prywatnych członków klasy.

Sortowanie takiego vector lub dowolnego innego odpowiedniego (zmiennego iteratora wejściowego) zakresu obiektów niestandardowych typu X może być osiągnięte za pomocą różnych metod, w tym w szczególności przy użyciu standardowych algorytmów bibliotecznych, takich jak

• sort,
• stable_sort,
• partial_sort lub
• partial_sort_copy.

Ponieważ większość technik, aby uzyskać względną kolejność X elementów, zostały już opublikowane, będę zacznij od kilku uwag na temat "dlaczego" i "kiedy", aby korzystać z różnych podejść.

"najlepsze" podejście będzie zależeć od różnych czynników:

1. czy sortowanie zakresów obiektów X jest zadaniem powszechnym lub rzadkim (czy takie zakresy będą sortowane w wielu różnych miejscach w programie lub przez użytkowników biblioteki)?
2. czy wymagane sortowanie jest "naturalne" (oczekiwane), czy istnieje wiele sposobów porównywania tego typu z samym sobą?
3. czy wydajność jest problemem, czy należy sortować zakresy X obiekty są niezawodne?

Jeśli sortowanie zakresów {[10] } jest powszechnym zadaniem i należy się spodziewać osiągniętego sortowania (tj. {[10] } po prostu owija jedną podstawową wartość), to on prawdopodobnie pójdzie na przeciążenie operator<, ponieważ umożliwia sortowanie bez żadnych fuzz (jak prawidłowo przechodząc odpowiednie komparatory) i wielokrotnie daje oczekiwane wyniki.

Jeśli sortowanie jest wspólnym zadaniem lub może być wymagane w różnych kontekstach, ale istnieje wiele kryteriów, które mogą być używane do sortowania X obiektów, wybrałbym funktory (przeciążone operator() funkcje klas niestandardowych) lub Wskaźniki funkcji (tj. jeden funktor/funkcja do porządkowania leksykalnego, a drugi do naturalnego porządkowania).

Jeśli sortowanie zakresów typu X jest rzadkie lub mało prawdopodobne w innych kontekstach, zwykle używam lambda zamiast zaśmiecać dowolną przestrzeń nazw większą ilością funkcji lub typów.

Jest to szczególnie prawdziwe, jeśli sortowanie nie jest "jasne" lub "naturalne" w jakiś sposób. Możesz łatwo uzyskać logika stojąca za porządkowaniem patrząc na lambda, która jest stosowana w miejscu, podczas gdy operator< jest opague na pierwszy rzut oka i trzeba by spojrzeć na definicję, aby wiedzieć, jaka logika porządkowania zostanie zastosowana.

Należy jednak pamiętać, że pojedyncza definicja operator< jest pojedynczym punktem awarii, podczas gdy wiele lambas jest wieloma punktami awarii i wymaga większej ostrożności.

Jeśli definicja operator< Nie jest dostępna, gdzie sortowanie jest wykonywane / szablon sortowania jest kompilowany, kompilator może być zmuszony do wywołania funkcji podczas porównywania obiektów, zamiast wprowadzania logiki porządkowania, co może być poważną wadą (przynajmniej gdy nie stosuje się optymalizacji czasu łącza/generowania kodu).

Sposoby osiągnięcia porównywalności class X w celu użycia standardowych algorytmów sortowania bibliotek

Niech std::vector<X> vec_X; i std::vector<Y> vec_Y;

1. Przeciążenie T::operator<(T) lub operator<(T, T) i użycie standardowych szablonów bibliotecznych, które nie oczekują porównania funkcja.

Albo członek przeciążenia operator<:

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

Lub wolne 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. Użyj wskaźnika funkcji z niestandardową funkcją porównywania jako parametru funkcji sortowania.

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. Tworzy przeciążenie bool operator()(T, T) dla typu niestandardowego, które może być przekazane jako funktor porównawczy.

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

Te definicje obiektów funkcji mogą być napisane nieco bardziej ogólne przy użyciu C++11 i szablonów:

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

Które mogą być używane do sortowania dowolnego typu za pomocą member i wsparcie <.

4. Przekazuje Anonymus closure (lambda) jako parametr porównawczy do funkcji sortowania.

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

Gdzie C++14 umożliwia jeszcze bardziej ogólne wyrażenie lambda:

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

Które mogą być zawinięte w makro

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

Tworzenie zwykłego komparatora jest dość płynne:

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

Tak, {[0] } z trzecim parametrem (funkcją lub obiektem) byłoby łatwiej. Przykład: http://www.cplusplus.com/reference/algorithm/sort/

W klasie możesz przeciążać operator"

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

Poniżej znajduje się kod z użyciem lambda

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

Możesz użyć klasy komparatora zdefiniowanej przez użytkownika.

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

Do sortowania wektora można użyć algorytmu sort ().

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

Trzeci parametr może być większy lub mniejszy lub może być również użyta Dowolna funkcja lub obiekt. Jednak domyślnym operatorem jest

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

Jeśli compare jest false, wykona "swap".

Byłem ciekaw, czy istnieje jakiś mierzalny wpływ na wydajność między różnymi sposobami, które można nazwać std:: sort, więc stworzyłem ten prosty test:

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

Tworzy wektor losowy, a następnie mierzy czas potrzebny na skopiowanie i posortowanie kopii (i oblicza sumę kontrolną, aby uniknąć zbyt intensywnej eliminacji martwego kodu).

Kompilowałem z g++ (GCC) 7.2.1 20170829 (Red Hat 7.2.1-1)

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

Oto wyniki:

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

Wygląda na to, że wszystkie opcje oprócz podania wskaźnika funkcji są bardzo podobne, a podanie wskaźnika funkcji powoduje + 30% kary.

Wygląda również na to, że operator