Chaînage de prédicats de classement (par exemple pour std :: sort)

Question

Vous pouvez passer un pointeur de fonction, un objet fonction (ou amplifier lambda) à std :: sort pour définir un ordre faible strict des éléments du conteneur que vous voulez trier.

Cependant, parfois (assez que j'ai touché cela plusieurs fois), vous voulez être en mesure d'enchaîner les comparaisons "primitives".

Un exemple trivial serait si vous étiez en train de trier une collection d'objets qui représentent des données de contact. Parfois, vous voudrez trier par

last name, first name, area code

. Autres fois

first name, last name

- encore d'autres fois

age, first name, area code

... etc

Maintenant, vous pouvez certainement écrire un objet fonction supplémentaire pour chaque cas, mais cela viole le principe DRY - surtout si chaque comparaison est moins triviale.

Il semble que vous devriez être capable d'écrire une hiérarchie de fonctions de comparaison - les bas niveau font les comparaisons simples et primitives (par ex. Prénom < prénom), puis celles de niveau supérieur appellent les fonctions de niveau inférieur (chaînage probable avec & & pour utiliser l'évaluation de court-circuit) pour générer les fonctions composites.

Le problème avec cette approche est que std :: sort prend un prédicat binaire - le prédicat ne peut retourner qu'un booléen. Donc, si vous les composez, vous ne pouvez pas dire si un "faux" indique une égalité ou supérieur à. Vous pouvez faire en sorte que vos prédicats de niveau inférieur renvoient un int, avec trois états - mais alors vous devrez envelopper ces prédicats de niveau supérieur avant qu'ils puissent être utilisés avec std :: sort par eux-mêmes.

En tout, ce ne sont pas des problèmes insurmontables. Cela semble juste plus difficile que cela devrait être - et invite certainement une implémentation de bibliothèque auxiliaire.

Par conséquent, est-ce que quelqu'un sait d'une bibliothèque préexistante (en particulier s'il s'agit d'une bibliothèque std ou boost) qui peut aider ici - d'avoir d'autres idées sur le sujet?

[Mise à jour]

Comme mentionné dans certains commentaires - je suis allé de l'avant et écrit ma propre mise en œuvre d'une classe pour gérer cela. C'est assez minime, et a probablement quelques problèmes avec cela en général. mais sur cette base, pour toute personne intéressée, la classe est ici:

http://pastebin.com/f52a85e4f

Et certaines fonctions d'aide (pour éviter la nécessité de préciser args modèle) est ici:

http://pastebin.com/fa03d66e

Answer 1

Vous pouvez construire un petit système de chaînage comme ceci:

struct Type { 
    string first, last; 
    int age; 
}; 

struct CmpFirst { 
    bool operator() (const Type& lhs, const Type& rhs) { return lhs.first < rhs.first; } 
}; 

struct CmpLast { 
    bool operator() (const Type& lhs, const Type& rhs) { return lhs.last < rhs.last; } 
}; 

struct CmpAge { 
    bool operator() (const Type& lhs, const Type& rhs) { return lhs.age < rhs.age; } 
}; 

template <typename First, typename Second> 
struct Chain { 
    Chain(const First& f_, const Second& s_): f(f_), s(s_) {} 

    bool operator() (const Type& lhs, const Type& rhs) { 
    if(f(lhs, rhs)) 
     return true; 
    if(f(rhs, lhs)) 
     return false; 

    return s(lhs, rhs); 
    } 

    template <typename Next> 
    Chain <Chain, Next> chain(const Next& next) const { 
    return Chain <Chain, Next> (*this, next); 
    } 

    First f; 
    Second s; 
}; 

struct False { bool operator() (const Type& lhs, const Type& rhs) { return false; } }; 

template <typename Op> 
Chain <False, Op> make_chain(const Op& op) { return Chain <False, Op> (False(), op); } 

ensuite l'utiliser:

vector <Type> v; // fill this baby up 

sort(v.begin(), v.end(), make_chain(CmpLast()).chain(CmpFirst()).chain(CmpAge())); 

La dernière ligne est un peu bavard, mais je pense qu'il est clair ce qui est prévu.

Answer 2

One manière classique de gérer cela est de trier en plusieurs passes et d'utiliser un tri stable. Notez que std::sort est généralement pas stable. Cependant, il y a std::stable_sort. Cela dit, j'écrirais un wrapper autour des foncteurs qui retournent un tristate (représentant moins, égal, plus grand).

Answer 3

std::sort n'est pas garanti stable parce que les tris stables sont généralement plus lents que les tris non stables ... donc utiliser un tri stable plusieurs fois ressemble à une recette pour des problèmes de performance ...

Et oui, il est vraiment dommage que ask sort un prédicat: Je ne vois pas d'autre moyen que de créer un foncteur accepter un vecteur de fonctions de trois états ...

Answer 4

La solution de chaînage est verbeuse. Vous pouvez aussi utiliser boost :: bind en conjonction avec std :: logical_et créer votre prédicat de tri. Voir l'article lié pour plus d'informations: How the boost bind library can improve your C++ programs

Answer 5

Vous pouvez essayer ceci:

Utilisation:

struct Citizen { 
    std::wstring iFirstName; 
    std::wstring iLastName; 
}; 

ChainComparer<Citizen> cmp; 
cmp.Chain<std::less>(boost::bind(&Citizen::iLastName, _1)); 
cmp.Chain<std::less>(boost::bind(&Citizen::iFirstName, _1)); 

std::vector<Citizen> vec; 
std::sort(vec.begin(), vec.end(), cmp); 

Mise en œuvre:

template <typename T> 
class ChainComparer { 
public: 

    typedef boost::function<bool(const T&, const T&)> TComparator; 
    typedef TComparator EqualComparator; 
    typedef TComparator CustomComparator; 

    template <template <typename> class TComparer, typename TValueGetter> 
    void Chain(const TValueGetter& getter) { 

     iComparers.push_back(std::make_pair( 
      boost::bind(getter, _1) == boost::bind(getter, _2), 
      boost::bind(TComparer<TValueGetter::result_type>(), boost::bind(getter, _1), boost::bind(getter, _2)) 
     )); 
    } 

    bool operator()(const T& lhs, const T& rhs) { 
     BOOST_FOREACH(const auto& comparer, iComparers) { 
      if(!comparer.first(lhs, rhs)) { 
       return comparer.second(lhs, rhs); 
      } 
     } 

     return false; 
    } 

private: 
    std::vector<std::pair<EqualComparator, CustomComparator>> iComparers; 
}; 

Answer 6

VARIADIC modèles dans 11 C++ donnent une option plus courte:

#include <iostream> 
    using namespace std; 

    struct vec { int x,y,z; }; 

    struct CmpX { 
     bool operator() (const vec& lhs, const vec& rhs) const 
     { return lhs.x < rhs.x; } 
    }; 

    struct CmpY { 
     bool operator() (const vec& lhs, const vec& rhs) const 
     { return lhs.y < rhs.y; } 
    }; 

    struct CmpZ { 
     bool operator() (const vec& lhs, const vec& rhs) const 
     { return lhs.z < rhs.z; } 
    }; 

    template <typename T> 
    bool chained(const T &, const T &) { 
     return false; 
    } 

    template <typename CMP, typename T, typename ...P> 
    bool chained(const T &t1, const T &t2, const CMP &c, P...p) { 
     if (c(t1,t2)) { return true;   } 
     if (c(t2,t1)) { return false;   } 
     else   { return chained(t1, t2, p...); } 
    } 

    int main(int argc, char **argv) { 
     vec x = { 1,2,3 }, y = { 2,2,3 }, z = { 1,3,3 }; 
     cout << chained(x,x,CmpX(),CmpY(),CmpZ()) << endl; 
     return 0; 
    }