Sortieren eines Vektors von benutzerdefinierten Objekten

Wie sortiert man einen Vektor, der benutzerdefinierte (dh benutzerdefinierte) Objekte enthält?
Wahrscheinlich sollte eine Standard-STL-Algorithmus- Sortierung zusammen mit einem Prädikat (einer Funktion oder einem Funktionsobjekt) verwendet werden, das in einem der Felder (als Schlüssel zum Sortieren) im benutzerdefinierten Objekt ausgeführt wird.
Bin ich auf dem richtigen Weg?

Ein einfaches Beispiel mit 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: Wie Kirill V. Lyadvinsky darauf hingewiesen, statt eine Art Prädikat liefert, können Sie das Gerät operator<für 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);
    }
};

Mit dieser Methode können Sie den Vektor einfach wie folgt sortieren:

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

Edit2: Wie Kappa vorschlägt, können Sie den Vektor auch in absteigender Reihenfolge sortieren, indem Sie einen >Operator überladen und den Sortieraufruf ein wenig ändern:

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

Und Sie sollten sort wie folgt nennen:

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

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önnten functor als drittes Argument verwenden std::sortoder 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() );
}

Das Sortieren eines solchen vectoroder eines anderen anwendbaren Bereichs (Iterator für veränderbare Eingaben) von benutzerdefinierten Objekten des Typs Xkann unter Verwendung verschiedener Methoden erreicht werden, insbesondere unter Verwendung der Verwendung von Standardbibliotheksalgorithmen wie

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

Da die meisten Techniken, um eine relative Reihenfolge der XElemente zu erhalten, bereits veröffentlicht wurden, beginne ich mit einigen Anmerkungen 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 XObjektbereichen eine häufige oder seltene Aufgabe (werden solche Bereiche an mehreren Stellen im Programm oder von 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 sollte das Sortieren von XObjektbereichen kinderleicht sein?

Wenn das Sortieren von Bereichen Xeine häufige Aufgabe ist und die erreichte Sortierung zu erwarten ist (dh Xnur einen einzelnen Grundwert umschließt), würde on wahrscheinlich überladen, operator<da es das Sortieren ohne Fuzz ermöglicht (wie das korrekte Übergeben geeigneter Komparatoren) und wiederholt erwartete Ausbeuten ermöglicht Ergebnisse.

Wenn das Sortieren eine gemeinsame Aufgabe ist oder wahrscheinlich in verschiedenen Kontexten erforderlich ist, es jedoch mehrere Kriterien gibt, anhand derer XObjekte sortiert werden können, würde ich mich für Functors (überladene operator()Funktionen benutzerdefinierter Klassen) oder Funktionszeiger (dh einen Funktor / eine Funktion) entscheiden für die lexikalische Bestellung und eine andere für die natürliche Bestellung).

Wenn das Sortieren von XTypbereichen in anderen Kontexten ungewöhnlich oder unwahrscheinlich ist, verwende ich eher 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 Bestellung leicht erkennen, wenn Sie ein Lambda betrachten, das an Ort operator<und Stelle angewendet wird, während es auf den ersten Blick opag ist, und Sie müssten die Definition nachschlagen, um zu wissen, welche Ordnungslogik angewendet wird.

Beachten Sie jedoch, dass eine einzelne operator<Definition ein einzelner Fehlerpunkt ist, während mehrere Lambas mehrere Fehlerpunkte sind 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, kann der Compiler gezwungen sein, beim Vergleichen von Objekten einen Funktionsaufruf auszuführen, anstatt die Ordnungslogik einzuschleusen, was ein schwerwiegender Nachteil sein kann (zumindest wenn) Verbindungszeitoptimierung / Codegenerierung wird nicht angewendet).

Möglichkeiten zur Vergleichbarkeit class X, um Standard-Bibliothekssortieralgorithmen zu verwenden

Lass std::vector<X> vec_X;undstd::vector<Y> vec_Y;

1. Überladen T::operator<(T)oder operator<(T, T)verwenden Sie Standardbibliotheksvorlagen, die keine Vergleichsfunktion erwarten.

Entweder Überlastungsmitglied 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; }
};

Dies kann verwendet werden, um jeden Typ mit iunterstützendem Element zu sortieren <.

4. Übergeben Sie einen Anonymus-Verschluss (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; });

die in ein Makro eingewickelt werden könnte

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

gewöhnliche Komparatorerstellung ganz reibungslos machen:

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

Du bist auf dem richtigen Weg. std::sortwird operator<standardmäßig als Vergleichsfunktion verwendet. Um Ihre Objekte zu sortieren, müssen Sie entweder überladen bool operator<( const T&, const T& )oder einen Funktor bereitstellen, der den Vergleich durchführt, ähnlich wie folgt:

 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.

Ich war neugierig, ob es messbare Auswirkungen auf die Leistung zwischen den verschiedenen Möglichkeiten gibt, wie man 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 erstellt einen zufälligen Vektor und misst dann, wie viel Zeit zum Kopieren und Sortieren der Kopie erforderlich ist (und berechnet eine Prüfsumme, um eine zu starke Eliminierung 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 außer dem Übergeben 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), was etwas seltsam ist, da dies darauf hindeutet, dass der generierte Code anders ist (mir fehlt die Fähigkeit, --save- zu analysieren). temporäre Ausgabe).

Ja, std::sort()mit dem dritten Parameter (Funktion oder Objekt) wäre es 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;
  }
}

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

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

Sie können eine benutzerdefinierte Komparatorklasse verwenden.

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

Um einen Vektor zu sortieren, können Sie den sort () -Algorithmus 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 falsch ist, wird "swap" ausgeführt.