Sortieren eines Vektors benutzerdefinierter Objekte

Im Interesse der Berichterstattung. Ich habe eine Implementierung mit Lambda-Ausdrücken vorgeschlagen.

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

Sie können functor als drittes Argument von std::sort Verwenden oder operator< In Ihrer Klasse definieren.

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

Du bist auf dem richtigen Weg. std::sort Verwendet standardmäßig operator< Als Vergleichsfunktion. Um Ihre Objekte zu sortieren, müssen Sie entweder bool operator<( const T&, const T& ) überladen oder einen Funktor bereitstellen, der den Vergleich ausführt.

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

Der Vorteil der Verwendung eines Funktors besteht darin, dass Sie eine Funktion mit Zugriff auf die privaten Mitglieder der Klasse verwenden können.

Das Sortieren eines solchen vector oder eines anderen anwendbaren (veränderlichen Eingabe-Iterators) Bereichs von benutzerdefinierten Objekten des Typs X kann mit verschiedenen Methoden durchgeführt werden, insbesondere unter Verwendung von Standard-Bibliotheksalgorithmen wie

• sort ,
• stable_sort ,
• partial_sort oder
• partial_sort_copy .

Da die meisten Techniken zum Erhalten der relativen Reihenfolge von X Elementen bereits veröffentlicht wurden, beginne ich mit einigen Hinweisen zum "Warum" und "Wann", um die verschiedenen Ansätze zu verwenden.

Der "beste" Ansatz hängt von verschiedenen Faktoren ab:

1. Ist das Sortieren von Bereichen von X Objekten eine häufige oder seltene Aufgabe (werden solche Bereiche an mehreren verschiedenen Stellen im Programm oder nach Bibliotheksbenutzern sortiert)?
2. Ist die erforderliche Sortierung "natürlich" (erwartet) oder gibt es mehrere Möglichkeiten, den Typ mit sich selbst zu vergleichen?
3. Ist die Leistung ein Problem oder sollten Sortierbereiche für X Objekte narrensicher sein?

Wenn Sortierbereiche von X eine häufige Aufgabe sind und die erreichte Sortierung zu erwarten ist (dh X umschließt nur einen einzelnen Grundwert), würde on wahrscheinlich eine Überladung auslösen operator< da es das Sortieren ohne Unschärfe ermöglicht (wie das korrekte Übergeben geeigneter Komparatoren) und wiederholt die erwarteten Ergebnisse liefert.

Wenn das Sortieren eine gemeinsame Aufgabe ist oder wahrscheinlich in verschiedenen Kontexten erforderlich ist, es jedoch mehrere Kriterien gibt, die zum Sortieren von X Objekten verwendet werden können, würde ich Functors (überladene operator() -Funktionen wählen von benutzerdefinierten Klassen) oder Funktionszeigern (dh einem Funktor/einer Funktion für die lexikalische Reihenfolge und einem anderen für die natürliche Reihenfolge).

Wenn das Sortieren von Bereichen des Typs X in anderen Zusammenhängen ungewöhnlich oder unwahrscheinlich ist, verwende ich Lambdas, anstatt einen Namespace mit mehr Funktionen oder Typen zu überladen.

Dies gilt insbesondere dann, wenn die Sortierung in irgendeiner Weise nicht "klar" oder "natürlich" ist. Sie können die Logik hinter der Reihenfolge leicht ermitteln, wenn Sie ein Lambda betrachten, das direkt angewendet wird, während operator< Auf den ersten Blick ungeklärt ist und Sie die Definition nachschlagen müssen, um zu wissen, welche Ordnungslogik angewendet wird .

Beachten Sie jedoch, dass eine einzelne operator< - Definition einen einzelnen Fehlerpunkt darstellt, während mehrere Lambas mehrere Fehlerpunkte darstellen und eine größere Vorsicht erfordern.

Wenn die Definition von operator< Nicht verfügbar ist, wo die Sortierung durchgeführt wird/die Sortiervorlage kompiliert wird, muss der Compiler beim Vergleichen von Objekten möglicherweise einen Funktionsaufruf ausführen, anstatt die Sortierungslogik, die a sein kann, zu inlinieren schwerwiegender Nachteil (zumindest wenn die Optimierung der Verbindungszeit/Codegenerierung nicht angewendet wird).

Möglichkeiten zur Vergleichbarkeit von class X, Um Standard-Sortieralgorithmen für Bibliotheken zu verwenden

Sei std::vector<X> vec_X; Und std::vector<Y> vec_Y;

1. Überladen Sie T::operator<(T) oder operator<(T, T) und verwenden Sie Standard-Bibliotheksvorlagen, die keine Vergleichsfunktion erwarten.

Entweder Überladungsmitglied operator<:

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

oder kostenlos 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. Verwenden Sie einen Funktionszeiger mit einer benutzerdefinierten Vergleichsfunktion als Sortierfunktionsparameter.

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. Erstellen Sie eine bool operator()(T, T) -Überladung für einen benutzerdefinierten Typ, der als Vergleichsfunktion übergeben werden kann.

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

Diese Funktionsobjektdefinitionen können mit C++ 11 und Vorlagen etwas allgemeiner geschrieben werden:

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

hiermit kann jeder Typ sortiert werden, wobei das Mitglied i< unterstützt.

4. Übergeben Sie einen Anonymusabschluss (Lambda) als Vergleichsparameter an die Sortierfunktionen.

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

Wobei C++ 14 einen noch allgemeineren Lambda-Ausdruck ermöglicht:

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

das könnte in einem Makro gewickelt werden

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

so wird die normale Komparatorerstellung reibungslos:

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

Ja, std::sort() mit dem dritten Parameter (function oder object) wäre einfacher. Ein Beispiel: http://www.cplusplus.com/reference/algorithm/sort/

In Ihrer Klasse können Sie den Operator "<" überladen.

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

Ich war neugierig, ob es messbare Auswirkungen auf die Leistung zwischen den verschiedenen Möglichkeiten gibt, die man mit std :: sort aufrufen kann. Deshalb habe ich diesen einfachen Test erstellt:

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

Es wird ein zufälliger Vektor erstellt und anschließend gemessen, wie viel Zeit zum Kopieren und Sortieren der Kopie erforderlich ist (und eine Prüfsumme berechnet, um eine zu starke Beseitigung von totem Code zu vermeiden).

Ich habe mit g ++ (GCC) 7.2.1 20170829 (Red Hat 7.2.1-1) kompiliert.

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

Hier sind die Ergebnisse:

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

Es sieht so aus, als ob alle Optionen mit Ausnahme des Übergebens des Funktionszeigers sehr ähnlich sind und das Übergeben eines Funktionszeigers + 30% Strafe verursacht.

Es sieht auch so aus, als ob der Operator <Version ~ 1% langsamer ist (ich habe den Test mehrmals wiederholt und der Effekt bleibt bestehen). temporäre Ausgabe).

Unten ist der Code mit 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;
}

Sie können eine benutzerdefinierte Vergleichsklasse verwenden.

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

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

Um einen Vektor zu sortieren, können Sie den Algorithmus sort () in verwenden.

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

Der dritte verwendete Parameter kann größer oder kleiner sein, oder es kann auch eine beliebige Funktion oder ein beliebiges Objekt verwendet werden. Der Standardoperator ist jedoch <, wenn Sie den dritten Parameter leer lassen.

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

wenn compare false ist, wird "Swap" ausgeführt.