Tri d'un vecteur d'objets personnalisés

248

Comment procéder pour trier un vecteur contenant des objets personnalisés (c'est-à-dire définis par l'utilisateur).
Il est probable que le tri standard de l'algorithme STL avec un prédicat (une fonction ou un objet fonction) qui fonctionnerait sur l'un des champs (comme clé de tri) dans l'objet personnalisé devrait être utilisé.
Suis-je sur la bonne voie?

c++ stl sorting Ankur
la source

Copie

365

Un exemple simple utilisant 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: Comme l'a souligné Kirill V. Lyadvinsky, au lieu de fournir un prédicat de tri, vous pouvez implémenter le operator<pour 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);
    }
};

En utilisant cette méthode, vous pouvez simplement trier le vecteur comme suit:

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

Edit2: Comme Kappa le suggère, vous pouvez également trier le vecteur dans l'ordre décroissant en surchargeant un >opérateur et en changeant un peu l'appel de tri:

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

Et vous devez appeler sort comme:

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

Alan
la source

2

Pourriez-vous expliquer pourquoi vous avez fait la fonction de comparaison dans la structure less_than_key (dans le premier) exemple en ligne?

kluka

2

et une autre question / note: si l'on souhaite avoir plusieurs méthodes de tri (pour différents attributs) dans une classe, la manière de surcharger l'opérateur <n'est probablement pas une option, non?

kluka

5

Une chose intéressante est de fournir également une méthode opérateur. Cela nous permettra de trier dans l'ordre inverse comme:, std::sort(vec.begin(), vec.end(), greater<MyStruct>())qui est propre et élégant.

kappa

3

@Bovaz Vous devez #include <functional>utiliser "std :: supérieur".

Nick Hartung

4

@kappa: Où vous pouvez simplement avoir operator<et utiliser soit std::sort(vec.begin(), vec.end());ou std::sort(vec.rbegin(), vec.rend());selon que vous souhaitez avoir un ordre croissant ou décroissant.

Pixelchemist

182

Dans l'intérêt de la couverture. J'ai proposé une implémentation utilisant des expressions 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;
});

Ben Crowhurst
la source

21

+1 supplémentaire pour inclure le #includes

Anne

3

Pour être clair, cela se traduit par ordre croissant; utilisez >au lieu de <pour obtenir l'ordre décroissant.

bhaller

56

Vous pouvez utiliser functor comme troisième argument de std::sort, ou vous pouvez définir operator<dans votre classe.

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

Kirill V. Lyadvinsky
la source

4

pourquoi devons-nous ajouter constà la fin de la signature de fonction?

broches

4

La fonction ne change pas l'objet ainsi const.

Kirill V. Lyadvinsky

Si tel est le cas, alors pourquoi nous passons "const X & val", je suppose que le passage de la valeur comme const à une fonction fait penser à la fonction que sa valeur ne va pas être modifiée.

Prashant Bhanarkar

1

@PrashantBhanarkar Le constmot-clé à la fin de la signature spécifie que la operator()fonction ne change pas l'instance de la Xgreaterstructure (qui en général pourrait avoir des variables membres), alors constqu'indiquer pour les valeurs d'entrée spécifie seulement que ces valeurs d'entrée sont immuables.

schester

15

Le tri d'une telle vectorou de toute autre plage applicable (itérateur d'entrée mutable) d'objets personnalisés de type Xpeut être réalisé à l'aide de diverses méthodes, notamment en utilisant des algorithmes de bibliothèque standard comme

Comme la plupart des techniques, pour obtenir un ordre relatif des Xéléments, ont déjà été postées, je commencerai par quelques notes sur "pourquoi" et "quand" pour utiliser les différentes approches.

La "meilleure" approche dépendra de différents facteurs:

Le tri des plages d' Xobjets est-il une tâche courante ou rare (ces plages seront-elles triées à plusieurs endroits différents dans le programme ou par les utilisateurs de la bibliothèque)?
Le tri requis est-il «naturel» (attendu) ou existe-t-il plusieurs façons de comparer le type à lui-même?
Les performances posent-elles un problème ou le tri des plages d' Xobjets doit-il être infaillible?

Si le tri des plages de Xest une tâche courante et que le tri obtenu est à prévoir (c'est- Xà- dire qu'il n'enveloppe qu'une seule valeur fondamentale), alors irait probablement en surcharge operator<car il permet un tri sans fuzz (comme passer correctement les comparateurs appropriés) et donne à plusieurs reprises les résultats attendus résultats.

Si le tri est une tâche courante ou susceptible d'être requise dans différents contextes, mais qu'il existe plusieurs critères qui peuvent être utilisés pour trier les Xobjets, je choisirais des foncteurs ( operator()fonctions surchargées de classes personnalisées) ou des pointeurs de fonction (c'est-à-dire un foncteur / fonction pour l'ordre lexical et un autre pour l'ordre naturel).

Si le tri des plages de type Xest rare ou peu probable dans d'autres contextes, j'ai tendance à utiliser des lambdas au lieu d'encombrer tout espace de noms avec plus de fonctions ou de types.

Cela est particulièrement vrai si le tri n'est pas "clair" ou "naturel" d'une manière ou d'une autre. Vous pouvez facilement obtenir la logique derrière la commande lorsque vous regardez une lambda qui est appliquée en place alors qu'elle operator<est opague à première vue et vous devez rechercher la définition pour savoir quelle logique de commande sera appliquée.

Notez cependant qu'une seule operator<définition est un point de défaillance unique alors que plusieurs lambas sont de multiples points de défaillance et nécessitent une plus grande prudence.

Si la définition de operator<n'est pas disponible là où le tri est effectué / le modèle de tri est compilé, le compilateur peut être contraint d'effectuer un appel de fonction lors de la comparaison d'objets, au lieu d'inclure la logique de classement qui pourrait être un grave inconvénient (au moins lorsque optimisation du temps de liaison / génération de code n'est pas appliquée).

Façons d'obtenir la comparabilité de `class X`afin d'utiliser des algorithmes de tri de bibliothèque standard

Soit std::vector<X> vec_X;etstd::vector<Y> vec_Y;

1. Surcharger `T::operator<(T)`ou `operator<(T, T)`utiliser des modèles de bibliothèque standard qui n'attendent pas de fonction de comparaison.

Soit membre de surcharge operator<:

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

ou gratuit 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. Utilisez un pointeur de fonction avec une fonction de comparaison personnalisée comme paramètre de fonction de tri.

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. Créez une `bool operator()(T, T)`surcharge pour un type personnalisé qui peut être passé comme foncteur de comparaison.

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

Ces définitions d'objets de fonction peuvent être écrites un peu plus génériques à l'aide de C ++ 11 et de modèles:

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

qui peut être utilisé pour trier n'importe quel type avec le isupport des membres <.

4. Passez une fermeture anonyme (lambda) comme paramètre de comparaison aux fonctions de tri.

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

Où C ++ 14 permet une expression lambda encore plus générique:

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

qui pourrait être enveloppé dans une macro

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

rendre la création d'un comparateur ordinaire assez fluide:

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

Pixelchemist
la source

Dans le cas 2. vous avez écrit bool X_less(X const &l, X const &r) const { return l.i < r.i; }pour le comparateur mais les constmots clés doivent être supprimés (car ce n'est pas une fonction membre).

PolGraphic

@PolGraphic: Correct - dans le cas 1 également.

Pixelchemist

@Pixelchemist comment pourrais-je utiliser l'approche lambda (4.) lorsque je n'utilise pas std::sortou similaire, mais que j'ai besoin d'une instance de Compare, par exemple lors de l'instanciation d'un std::set?

azrdev

1

@azrdev: Un modèle de fonction qui capture le type de fermeture pour le passer comme paramètre de modèle à définir: template<class T, class C> std::set<T, C> make_set(C const& compare) { return std::set<T, C>{ compare }; }qui pourrait être utilisé comme auto xset = make_set<X>([](auto && l, auto && r) { return l.i < r.i; });.

Pixelchemist

14

Tu es sur la bonne piste. std::sortutilisera operator<comme fonction de comparaison par défaut. Donc, pour trier vos objets, vous devrez soit surcharger, bool operator<( const T&, const T& )soit fournir un foncteur qui fait la comparaison, un peu comme ceci:

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

L'avantage de l'utilisation d'un foncteur est que vous pouvez utiliser une fonction avec accès aux membres privés de la classe.

xtofl
la source

Manqué celui-là: fournir un opérateur de fonction membre <.

xtofl

1

Il est préférable de faire operator<un membre de classe (ou struct), car un global peut utiliser des membres protégés ou privés. Ou vous devriez en faire un ami de la structure C.

Kirill V. Lyadvinsky

5

J'étais curieux de savoir s'il y avait un impact mesurable sur les performances entre les différentes façons d'appeler std :: sort, j'ai donc créé ce test simple:

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

Ce qu'il fait, c'est qu'il crée un vecteur aléatoire, puis mesure le temps nécessaire pour le copier et le trier (et calculer une somme de contrôle pour éviter une élimination trop vigoureuse du code mort).

Je compilais avec g ++ (GCC) 7.2.1 20170829 (Red Hat 7.2.1-1)

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

Voici les résultats:

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

Il semble que toutes les options, à l'exception du passage du pointeur de fonction, soient très similaires, et le passage d'un pointeur de fonction entraîne une pénalité de + 30%.

Il semble également que l'opérateur <version soit ~ 1% plus lent (j'ai répété le test plusieurs fois et l'effet persiste), ce qui est un peu étrange car cela suggère que le code généré est différent (je manque de compétences pour analyser - enregistrer - sortie temps).

qbolec
la source

4

Oui, std::sort()avec un troisième paramètre (fonction ou objet) serait plus facile. Un exemple: http://www.cplusplus.com/reference/algorithm/sort/

swatkat
la source

Pas exactement une réponse de lien seulement mais au moins un exemple d'une seule ligne serait utile.

Manos Nikolaidis

3

Dans votre classe, vous pouvez surcharger l'opérateur "<".

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

BobbyShaftoe
la source

3

Voici le code utilisant 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;
}

Sathwick
la source

1

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

Amin Alomaisi
la source

1

Vous pouvez utiliser une classe de comparaison définie par l'utilisateur.

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

la source

0

Pour trier un vecteur, vous pouvez utiliser l'algorithme sort () dans.

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

Le troisième paramètre utilisé peut être supérieur ou inférieur ou n'importe quelle fonction ou objet peut également être utilisé. Cependant, l'opérateur par défaut est <si vous laissez le troisième paramètre vide.

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

Prashant Shubham
la source

0

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

si compare est faux, il fera "swap".

Bruce
la source

En aucune langue, cela ne sera compilé.

LF

Tri d'un vecteur d'objets personnalisés

Réponses:

Façons d'obtenir la comparabilité de class Xafin d'utiliser des algorithmes de tri de bibliothèque standard

1. Surcharger T::operator<(T)ou operator<(T, T)utiliser des modèles de bibliothèque standard qui n'attendent pas de fonction de comparaison.

2. Utilisez un pointeur de fonction avec une fonction de comparaison personnalisée comme paramètre de fonction de tri.

3. Créez une bool operator()(T, T)surcharge pour un type personnalisé qui peut être passé comme foncteur de comparaison.

4. Passez une fermeture anonyme (lambda) comme paramètre de comparaison aux fonctions de tri.

Façons d'obtenir la comparabilité de `class X`afin d'utiliser des algorithmes de tri de bibliothèque standard

1. Surcharger `T::operator<(T)`ou `operator<(T, T)`utiliser des modèles de bibliothèque standard qui n'attendent pas de fonction de comparaison.

3. Créez une `bool operator()(T, T)`surcharge pour un type personnalisé qui peut être passé comme foncteur de comparaison.