Sortowanie wektora niestandardowych obiektów

Jak można posortować wektor zawierający obiekty niestandardowe (tj. Zdefiniowane przez użytkownika).
Prawdopodobnie należy użyć standardowego algorytmu sortowania STL wraz z predykatem (funkcją lub obiektem funkcji), który działałby na jednym z pól (jako klucz do sortowania) w obiekcie niestandardowym.
Czy jestem na dobrej drodze?

Prosty przykład użycia 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: Jak Kirill V. Lyadvinsky wskazał, zamiast dostarczania predykat sortowania, można wdrożyć operator<na 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);
    }
};

Dzięki tej metodzie możesz po prostu posortować wektor w następujący sposób:

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

Edycja2: Jak sugeruje Kappa, możesz również sortować wektor w malejącej kolejności, przeciążając >operatora i zmieniając nieco sortowanie wywołania:

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

I powinieneś nazywać sort jako:

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

W interesie pokrycia. Przedstawiłem implementację przy użyciu wyrażeń 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ć funktora jako trzeciego argumentu std::sortlub 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() );
}

Sortowanie takiego vectorlub dowolnego stosownego (niestandardowego iteratora wejściowego) typu obiektów niestandardowych Xmożna osiągnąć za pomocą różnych metod, w tym w szczególności za pomocą standardowych algorytmów bibliotecznych, takich jak

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

Ponieważ większość technik mających na celu uzyskanie względnego uporządkowania Xelementów została już opublikowana, zacznę od kilku uwag na temat „dlaczego” i „kiedy”, aby zastosować różne podejścia.

Podejście „najlepsze” będzie zależeć od różnych czynników:

1. Czy sortowanie zakresów Xobiektów jest powszechnym czy rzadkim zadaniem (czy takie zakresy będą sortowane na wiele różnych miejsc w programie czy przez użytkowników biblioteki)?
2. Czy wymagane sortowanie jest „naturalne” (oczekiwane), czy też istnieje wiele sposobów na porównanie tego typu z samym sobą?
3. Czy wydajność stanowi problem, czy też zakresy sortowania Xobiektów powinny być niezawodne?

Jeśli zakresy sortowania Xsą powszechnym zadaniem i należy oczekiwać osiągniętego sortowania (tj. Po Xprostu otacza jedną podstawową wartość), to prawdopodobnie przejdzie on do przeciążenia, operator<ponieważ umożliwia sortowanie bez żadnych zakłóceń (jak prawidłowe przekazywanie odpowiednich komparatorów) i wielokrotne oczekiwane wyniki wyniki.

Jeśli sortowanie jest częstym zadaniem lub prawdopodobnie będzie wymagane w różnych kontekstach, ale istnieje wiele kryteriów, które można zastosować do sortowania Xobiektów, wybrałbym Functors (przeciążone operator()funkcje klas niestandardowych) lub wskaźniki funkcji (tj. Jeden funktor / funkcja dla porządku leksykalnego i innego dla porządku naturalnego).

Jeśli zakresy sortowania typów Xsą rzadkie lub mało prawdopodobne w innych kontekstach, zwykle używam lambdów zamiast zaśmiecać przestrzeń nazw większą liczbą funkcji lub typów.

Jest to szczególnie prawdziwe, jeśli sortowanie nie jest w jakiś sposób „jasne” lub „naturalne”. Możesz łatwo zrozumieć logikę operator<związaną z porządkowaniem, patrząc na lambda, która jest stosowana w miejscu, podczas gdy na pierwszy rzut oka jest niejasna i trzeba by sprawdzić definicję, aby wiedzieć, która logika porządkowania zostanie zastosowana.

Zauważ jednak, że jedna operator<definicja 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 w miejscu, w którym odbywa się sortowanie / kompilowany jest szablon sortowania, kompilator może zostać zmuszony do wywołania funkcji podczas porównywania obiektów, zamiast wprowadzania logiki porządkowania, co może być poważną wadą (przynajmniej gdy optymalizacja czasu łącza / generowanie kodu nie jest stosowane).

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

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

1. Przeciąż T::operator<(T)lub operator<(T, T)użyj standardowych szablonów bibliotek, które nie oczekują funkcji porównania.

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 za darmo 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ównania 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. Utwórz bool operator()(T, T)przeciążenie dla typu niestandardowego, który można przekazać 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 można zapisać nieco bardziej ogólnie, używając 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żyte do sortowania dowolnego typu z iobsługą elementów <.

4. Przekaż zamknięcie anonimowe (lambda) jako parametr porównawczy do funkcji sortujących.

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 można zawinąć w makro

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

dzięki czemu 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));

Jesteś na dobrej drodze. std::sortbędzie operator<domyślnie używał jako funkcji porównania. Aby więc posortować obiekty, będziesz musiał albo przeładować, bool operator<( const T&, const T& )albo podać funktor , który dokona porównania, 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 funktora jest to, że można użyć funkcji z dostępem do prywatnych członków klasy.

Byłem ciekawy, czy istnieje jakiś wymierny wpływ na wydajność między różnymi sposobami nazywania std :: sort, dlatego 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 losowy wektor, a następnie mierzy, ile czasu potrzeba na jego skopiowanie i posortowanie jego kopii (i obliczenie pewnej sumy kontrolnej, aby uniknąć zbyt energicznej eliminacji martwego kodu).

Kompilowałem przy użyciu 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 z wyjątkiem przekazywania wskaźnika funkcji są bardzo podobne, a przekazanie wskaźnika funkcji powoduje + 30% kary.

Wygląda również na to, że operator <wersja jest ~ 1% wolniejszy (powtórzyłem test wiele razy, a efekt utrzymuje się), co jest nieco dziwne, ponieważ sugeruje, że wygenerowany kod jest inny (brak umiejętności analizy - zapisywania - wyjście temps).

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

W swojej klasie możesz przeciążać operatora „<”.

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

Poniżej znajduje się kod używający 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;
    }

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

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

Aby posortować wektor, możesz użyć algorytmu sort ().

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

Trzeci użyty parametr może być większy lub mniejszy lub można również użyć dowolnej funkcji lub obiektu. Jednak domyślnym operatorem jest <jeśli pozostawisz trzeci parametr pusty.

// 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 porównanie jest fałszywe, wykona „zamianę”.