struct C++ tri

Question

• J'ai un vecteur de struct personnalisé qui a besoin d'être triés sur différents critères à chaque fois
• La mise en œuvre opérateur < permettra un seul critère
• Mais je veux être en mesure de préciser les critères de tri chaque temps que j'appelle le tri standard C++.

Comment faire cela?

• S'il vous plaît noter qu'il est préférable d'être efficace dans le temps en cours d'exécution ..

Merci

Answer 1

Vous pouvez définir la fonction de comparaison à utiliser dans chaque exécution de l'algorithme de tri en utilisant le troisième argument :

template <class RandomAccessIterator, class StrictWeakOrdering> 
void sort(RandomAccessIterator first, RandomAccessIterator last, 
      StrictWeakOrdering comp); 

Un exemple simple:

struct person { 
    std::string name; 
    int age; 
}; 
bool sort_by_name(const person & lhs, const person & rhs) 
{ 
    return lhs.name < rhs.name; 
} 
bool sort_by_age(const person & lhs, const person & rhs) 
{ 
    return lhs.age < rhs.age; 
} 
int main() { 
    std::vector<person> people; 
    // fill in the vector 
    std::sort(people.begin(), people.end(), sort_by_name); 
    std::sort(people.begin(), people.end(), sort_by_age); 
} 

Answer 2

Il y a 2 versions de std::sort, la 2ème version accepte un foncteur de comparaison:

template <class RandomAccessIterator, class StrictWeakOrdering> 
void sort(RandomAccessIterator first, RandomAccessIterator last, 
      StrictWeakOrdering comp); 
//--------^^^^^^^^^^^^^^^^^^^^^^^ 

Par exemple:

bool isLessThan(const MyStruct& first, const MyStruct& second) { 
    if (first.name < second.name) return true; 
    else if (first.name == second.name) { 
     if (first.date > second.date) return true; 
     // etc. 
    } 
    return false; 
} 

... 

sort(v.begin(), v.end(), isLessThan); 

Voir aussi http://www.cplusplus.com/reference/algorithm/sort/. Cette variante utilise toujours le même algorithme quicksort, c'est donc en moyenne O (n log n).

Answer 3

Il existe deux versions de std::sort, la première prend simplement les itérateurs et utilise la surcharge < de l'objet, alors que la seconde vous permet de spécifier un objet comparateur pour effectuer la comparaison. Vous devez simplement fournir une classe conforme au concept StrictWeakOrdering en tant que compartiments. L'objet comparateur (ou la fonction) devrait être appelable avec deux paramètres, où chaque paramètre est du type spécifié, et il devrait renvoyer vrai si le premier paramètre est inférieur au deuxième paramètre. Par exemple:

 
bool mycomparator(const T& a, const T&b); // return true if a < b 

OU

 
class MyComparator 
{ 
    public: 
     bool operator()(const T& a, const T& b)const; // return true if a < b 
}; 

Answer 4

Juste pour être complet, voici un exemple en C++ 0x fonctions lambda:

std::vector<Person> v; 
std::sort(v.begin(), v.end(), [](Person a, Person b) { return a.name_ < b.name_; }); 
... 
std::sort(v.begin(), v.end(), [](Person a, Person b) { return a.address_ < b.address_; }); 

Answer 5

Boost.Bind permet dans des cas simples pour définir un comparer la fonction inplace:

#include <iostream> 
#include <algorithm> 

#include <boost/foreach.hpp> 
#include <boost/format.hpp> 
#include <boost/bind.hpp> 

#define P(a) do {              \ 
    BOOST_FOREACH (Struct s, a)           \ 
     std::cout << boost::format("(%d %c) ") % s.i % s.c;    \ 
    std::cout << std::endl;            \ 
    } while(0) 

namespace { 
    struct Struct { int i; char c; }; 
} 

int main() { 
    using boost::bind; 

    Struct a[] = { 1, 'z', 2, 'a' }; P(a); 
    const int N = sizeof(a)/sizeof(*a); 

    std::sort(a, a + N, bind(&Struct::i, _1) > bind(&Struct::i, _2)); P(a); 
    std::sort(a, a + N, bind(&Struct::c, _1) > bind(&Struct::c, _2)); P(a); 
} 

Sortie:

(1 z) (2 a) 
(2 a) (1 z) 
(1 z) (2 a)