Sortieren eines Vektors benutzerdefinierter Objekte

Wie sortiert man einen Vektor, der benutzerdefinierte (dh benutzerdefinierte) Objekte enthält?
Wahrscheinlich Standard-STL-Algorithmus Sortieren zusammen mit einem Prädikat (einer Funktion oder einem Funktionsobjekt), das auf eines der Felder (als Schlüssel zum Sortieren) im benutzerdefinierten Objekt wirken würde, verwendet werden.
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());

Bearbeiten: Wie Kirill V. Lyadvinsky betonte, können Sie anstelle eines sort-Prädikats das implementieren operator< zum 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 a überladen > Operator und Änderung des Anrufs ein wenig:

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 aufrufen als:

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

Im Interesse der Reichweite. Ich habe eine Implementierung mit vorgeschlagen Lambda-Ausdrücke.

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 Funktor als drittes Argument von verwenden std::sortoder Sie könnten definieren operator< in deiner Klasse.

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

So sortieren vector oder jeder andere anwendbare (veränderliche Eingabe-Iterator) Bereich von benutzerdefinierten Objekten des Typs X kann unter Verwendung verschiedener Methoden erreicht werden, insbesondere einschließlich der Verwendung von Standardbibliotheksalgorithmen wie z

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

Da die meisten Techniken, um eine relative Reihenfolge von zu erhalten X Elemente bereits gepostet wurden, beginne ich mit einigen Anmerkungen zum „Warum“ und „Wann“ der Verwendung der verschiedenen Ansätze.

Der „beste“ Ansatz hängt von verschiedenen Faktoren ab:

1. Sortiert Bereiche von X Objekte eine häufige oder eine seltene Aufgabe (werden solche Bereiche an mehreren verschiedenen 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 Bereichen erfolgen? X Objekte narrensicher sein?

Beim Sortieren von Bereichen von X ist eine gemeinsame Aufgabe und die erzielte Sortierung ist zu erwarten (dh X umschließt nur einen einzelnen fundamentalen Wert), dann würde on wahrscheinlich zum Überladen gehen operator< da es ein Sortieren ohne Fuzz (wie das korrekte Passieren geeigneter Komparatoren) ermöglicht und wiederholt die erwarteten Ergebnisse liefert.

Wenn das Sortieren eine häufige Aufgabe ist oder wahrscheinlich in verschiedenen Kontexten erforderlich ist, es jedoch mehrere Kriterien gibt, die zum Sortieren verwendet werden können X Objekte, würde ich mich für Funktoren entscheiden (überladen operator() Funktionen benutzerdefinierter Klassen) oder Funktionszeiger (dh ein Funktor/eine Funktion für die lexikalische Ordnung und ein anderer für die natürliche Ordnung).

Beim Sortieren von Bereichen des Typs X in anderen Kontexten ungewöhnlich oder unwahrscheinlich ist. Ich neige dazu, Lambdas zu verwenden, anstatt einen Namensraum 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 verstehen, wenn Sie sich ein Lambda ansehen, das an Ort und Stelle angewendet wird, während operator< ist auf den ersten Blick undurchsichtig und Sie müssten die Definition nachschlagen, um zu wissen, welche Ordnungslogik angewendet wird.

Beachten Sie jedoch, dass eine einzelne operator< Definition ist ein einzelner Fehlerpunkt, während mehrere Lambas mehrere Fehlerpunkte sind und mehr Vorsicht erfordern.

Wenn die Definition von operator< nicht verfügbar ist, wo die Sortierung erfolgt / die Sortiervorlage kompiliert ist, kann der Compiler gezwungen sein, beim Vergleichen von Objekten einen Funktionsaufruf durchzuführen, anstatt die Sortierlogik einzufügen, was ein schwerwiegender Nachteil sein könnte (zumindest bei der Linkzeitoptimierung / Codegenerierung wird nicht angewendet).

Wege zur Vergleichbarkeit von class X um Standardbibliotheks-Sortieralgorithmen zu verwenden

Lassen std::vector<X> vec_X; und std::vector<Y> vec_Y;

1. Überlastung T::operator<(T) oder operator<(T, T) und 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 frei 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 Vergleichsfunktor ü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 generischer 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; }
};

die verwendet werden kann, um jeden Typ mit Mitglied zu sortieren i unterstützend <.

4. Übergeben Sie einen Anonymus-Abschluss (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 generischeren Lambda-Ausdruck ermöglicht:

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

was in ein Makro gepackt werden könnte

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

die gewöhnliche Komparator-Erstellung ziemlich reibungslos zu 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::sort wird benutzen operator< als Vergleichsfunktion standardmäßig. Um Ihre Objekte zu sortieren, müssen Sie also entweder überladen bool operator<( const T&, const T& ) oder stellen Sie ein Funktionsobjekt bereit, das den Vergleich durchführt, etwa so:

 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 Funktionsobjekts besteht darin, dass Sie eine Funktion mit Zugriff auf die privaten Member der Klasse verwenden können.

Ich war neugierig, ob es messbare Auswirkungen auf die Leistung zwischen den verschiedenen Aufrufmöglichkeiten von std::sort gibt, also 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 erforderlich ist, um ihn zu kopieren und die Kopie davon zu sortieren (und eine Prüfsumme zu berechnen, um eine zu energische 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 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

Sieht so aus, als wären alle Optionen außer dem Übergeben eines Funktionszeigers sehr ähnlich, und das Übergeben eines Funktionszeigers verursacht eine Strafe von +30 %.

Es sieht auch so aus, als ob die operator<-Version ~ 1 % langsamer ist (ich habe den Test mehrmals wiederholt und der Effekt bleibt bestehen), was etwas seltsam ist, da es darauf hindeutet, dass der generierte Code anders ist (mir fehlt die Fähigkeit, --save- zu analysieren Temp-Ausgabe).

Unten ist der Code mit Lambdas

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