Verkettung von Ordnungsvergleichselementen (z. B. für std :: sort)

Question

Sie können einen Funktionszeiger, ein Funktionsobjekt (oder Boost-Lambda) an std :: sort übergeben, um eine strenge schwache Reihenfolge der Elemente des zu sortierenden Containers zu definieren.

Aber manchmal (genug, dass ich diese mehrmals getroffen habe), möchten Sie in der Lage sein, "primitive" Vergleiche zu verketten.

Ein triviales Beispiel wäre, wenn Sie eine Sammlung von Objekten sortieren würden, die Kontaktdaten darstellen. Manchmal möchten Sie nach

last name, first name, area code

sortieren. Andere Male

first name, last name

- noch andere Male

age, first name, area code

... usw.

Jetzt können Sie sicherlich ein zusätzliches Funktionsobjekt für jeden Fall schreiben, aber das verstößt gegen das DRY-Prinzip - vor allem, wenn jeder Vergleich weniger trivial ist.

Es scheint, als ob Sie in der Lage sein sollten, eine Hierarchie von Vergleichsfunktionen zu schreiben - die Low-Level-Einsen machen die einfachen, primitiven Vergleiche (zB Vorname < Vorname), dann rufen die höherwertigen die nachfolgenden auf (wahrscheinlich Verkettung mit & &, um die Kurzschlussauswertung zu verwenden), um die zusammengesetzten Funktionen zu erzeugen.

Das Problem mit diesem Ansatz ist, dass Std :: sort ein binäres Prädikat nimmt - das Prädikat kann nur ein Bool zurückgeben. Also, wenn Sie sie komponieren, können Sie nicht sagen, ob ein "false" Gleichheit oder größer als bedeutet. Sie können Ihre niedrigeren Prädikate dazu bringen, ein int mit drei Zuständen zurückzugeben - aber dann müssten Sie diese in höhere Prädikate einbetten, bevor sie mit std :: sort allein verwendet werden könnten.

In allem sind dies keine unüberwindbaren Probleme. Es scheint einfach schwieriger als es sein sollte - und lädt sicherlich eine Helfer Bibliothek Implementierung ein.

Wer weiß also schon von einer bereits vorhandenen Bibliothek (vor allem wenn es sich um eine Standard- oder Boost-Bibliothek handelt), die hier helfen könnte - irgendwelche anderen Gedanken zu haben?

[Update]

Wie in einigen Kommentaren erwähnt - ich habe weitergemacht und geschrieben meine eigene Implementierung einer Klasse diese zu verwalten. Es ist ziemlich minimal und hat wahrscheinlich einige Probleme damit. aber auf dieser Grundlage für alle Interessierten ist die Klasse hier:

http://pastebin.com/f52a85e4f

Und einige Hilfsfunktionen (die Notwendigkeit zu vermeiden Vorlage args angeben) ist hier:

http://pastebin.com/fa03d66e

Answer 1

Sie könnten ein wenig Verkettungssystem bauen etwa so:

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

Dann, es zu benutzen:

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

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

Die letzte Zeile ein wenig ausführlich ist, aber ich denke, es ist klar, was beabsichtigt ist.

Answer 2

One Herkömmliche Weise, dies zu handhaben, besteht darin, in mehreren Durchgängen zu sortieren und eine stabile Sortierung zu verwenden. Beachten Sie, dass std::sort im Allgemeinen nicht stabil ist. Allerdings gibt es std::stable_sort.

Das heißt, ich würde einen Wrapper um Funktoren schreiben, die ein Tristate zurückgeben (das heißt weniger, gleich, größer).

Answer 3

std::sort wird nicht garantiert, stabil zu sein, da stabile Sortierungen normalerweise langsamer als nicht stabile sind ... so dass eine stabile Sortierung mehrere Male wie ein Rezept für Performance-Probleme aussieht ...

Und ja, es ist wirklich eine Schande, dass Art für ein Prädikat fragen: ich keine andere Möglichkeit sehen, als erstellen Funktors einen Vektor von Tri-State-Funktionen akzeptieren ...

Answer 4

Die Verkettungslösung ist ausführlich. Sie könnten auch boost :: bind in Verbindung mit std :: logical_and verwenden, um Ihr Sortierprädikat zu erstellen. Siehe den verlinkten Artikel für weitere Informationen: How the boost bind library can improve your C++ programs

Answer 5

du versuchen:

Verbrauch:

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

Umsetzung:

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

Variadische Vorlagen in C++ 11 eine kürzere Option geben:

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