Łańcuchy predykatów porządkowania (np. Dla std :: sort)

Question

Możesz przekazać wskaźnik funkcji, obiekt funkcji (lub zwiększyć lambda) do std :: sort, aby zdefiniować ścisłe słabe porządkowanie elementów kontenera, które chcesz posortować.

Jednak czasami (na tyle, że uderzyłem to kilka razy), chcesz mieć możliwość łączenia "prymitywnych" porównań.

Trywialnym przykładem byłoby sortowanie kolekcji obiektów reprezentujących dane kontaktowe. Czasami chcesz sortować według

last name, first name, area code

. Inne czasy:

first name, last name

- jeszcze innym razem

age, first name, area code

... itd.

Teraz z pewnością można napisać dodatkowy obiekt funkcji dla każdego przypadku, ale narusza to zasadę DRY - szczególnie, jeśli każde porównanie jest mniej trywialne.

Wygląda na to, że powinieneś być w stanie napisać hierarchię funkcji porównawczych - te o niskim poziomie wykonują pojedyncze, prymitywne, porównania (np. Imię < pierwsze imię), następnie wyższe poziomy wywołują kolejne niższego poziomu (prawdopodobnie w połączeniu z & &, aby skorzystać z oceny zwarcia) w celu wygenerowania funkcji złożonych.

Problem z tym podejściem polega na tym, że std :: sort przyjmuje predykat binarny - predykat może jedynie zwrócić wartość bool. Więc jeśli je komponujesz, nie możesz powiedzieć, czy "fałsz" oznacza równość lub więcej niż. Możesz sprawić, by predykaty na niższym poziomie zwracały int, z trzema stanami - ale wtedy musiałbyś zawijać te w wyższych predykatach poziomu, zanim mogłyby zostać użyte z std :: sort na własną rękę.

W sumie nie są to nieprzezwyciężone problemy. Wydaje się, że jest trudniejsze, niż powinno być - i na pewno zachęca do wdrożenia biblioteki pomocniczej.

W związku z tym, czy ktoś wie o istniejącej wcześniej bibliotece (szczególnie jeśli jest to biblioteka standardowa lub wspomagająca), która może w tym pomóc? Czy mają Państwo inne zdanie na ten temat?

[Aktualizacja]

Jak wspomniano w niektórych komentarzach - Poszedłem do przodu i napisany własną implementację klasy zarządzać tym. Jest to dość minimalne i prawdopodobnie ma pewne problemy z nim w ogóle. ale na tej podstawie dla każdego zainteresowanego, klasa jest tutaj:

http://pastebin.com/f52a85e4f

a niektóre funkcje pomocnicze (aby uniknąć konieczności zdefiniowanych szablonów args) jest tutaj:

http://pastebin.com/fa03d66e

Answer 1

Można zbudować mały systemu łańcuchowego tak:

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

Potem go używać:

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

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

Ostatnia linia jest trochę rozwlekły, ale myślę, że to jasne, co się ma.

Answer 2

One konwencjonalnym sposobem radzenia sobie z tym jest sortowanie w wielu przejściach i używanie stabilnego sortowania. Zauważ, że std::sort jest ogólnie niezabezpieczony , a nie. Jest jednak std::stable_sort.

Powiedziałbym, że napisałbym wrapper wokół funktorów, które zwracają tristate (reprezentujący less, equals, greater).

Answer 3

std::sort nie może być stabilny, ponieważ sortowanie stabilne jest zwykle wolniejsze niż niestabilne ... więc używanie wielokrotnego sortowania stabilnego wygląda jak przepis na problemy z wydajnością ...

I tak to naprawdę wstyd, że porządek poprosić o orzecznika: nie widzę innego sposobu niż stworzenie funktor zaakceptowaniem wektor funkcji trójstanowych ...

Answer 4

Rozwiązanie łączenia jest pełne gadżetów. Możesz także użyć boost :: bind w połączeniu ze std :: logical_and i zbudować swój predykat sortowania. Zobacz powiązany artykuł, aby uzyskać więcej informacji: How the boost bind library can improve your C++ programs

Answer 5

Można spróbować to:

Zastosowanie:

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

Realizacja:

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

o zmiennej liczbie argumentów szablony w C++ 11 dają krótszą opcję:

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