Цепочка предикатов упорядочения (например, для std :: sort)

Question

Вы можете передать указатель функции, объект функции (или увеличить lambda), в std :: sort, чтобы определить строгий слабый порядок элементов контейнера, который вы хотите отсортировать.

Однако иногда (достаточно, чтобы я ударил это несколько раз), вы хотите иметь возможность связывать «примитивные» сравнения.

Тривиальный пример: если бы вы сортировали коллекцию объектов, представляющих контактные данные. Иногда вам нужно сортировать по

last name, first name, area code

. Другое время

first name, last name

- еще раз

age, first name, area code

... и т. Д.

Теперь вы можете, конечно, написать дополнительный объект функции для каждого случая, но это нарушает принцип DRY - особенно если каждое сравнение менее тривиально.

Похоже, что вы должны иметь возможность написать иерархию функций сравнения - низкоуровневые выполняют одиночные, примитивные, сопоставления (например, имя первого имени <), затем более высокие уровни называют нижние уровни подряд (возможно, с цепью & &, чтобы использовать оценку короткого замыкания) для создания составных функций.

Проблема с этим подходом заключается в том, что std :: sort принимает двоичный предикат - предикат может возвращать только bool. Поэтому, если вы их составляете, вы не можете сказать, означает ли «ложь» равенство или больше. Вы можете заставить предикаты нижнего уровня возвращать int с тремя состояниями - но тогда вам придется обернуть их в предикаты более высокого уровня, прежде чем их можно будет использовать с помощью std :: sort самостоятельно.

В целом, это не непреодолимые проблемы. Это кажется сложнее, чем должно быть - и, конечно же, приглашает реализацию вспомогательной библиотеки.

Таким образом, знает ли кто-нибудь о существовании ранее существовавшей библиотеки (особенно если это библиотека std или boost), которая может помочь здесь - иметь какие-либо другие мысли по этому вопросу?

[Update]

Как уже отмечался в некоторых комментариях - я пошел вперед и написал свою собственную реализацию класса справиться с этим. Он довольно минимален и, вероятно, имеет некоторые проблемы с ним в целом. но на этой основе, для тех, кто заинтересован, класс здесь:

http://pastebin.com/f52a85e4f

И некоторые вспомогательные функции (чтобы избежать необходимости указывать шаблон арг) здесь:

http://pastebin.com/fa03d66e

Answer 1

Вы можете создать небольшую систему СЦЕПЛЕНИЯ следующим образом:

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

Затем, чтобы использовать его:

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

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

последняя строка немного многословным, но я думаю, ясно, что задумано.

Answer 2

One Обычный способ справиться с этим - сортировать в нескольких проходах и использовать стабильный вид. Обратите внимание, что std::sort обычно не стабильный. Однако есть std::stable_sort.

Это, я бы написал обертку вокруг функторов, которые возвращают tristate (представляя меньше, равно, больше).

Answer 3

std::sort не гарантированно стабилен, потому что стабильные сорта обычно медленнее, чем нестабильные ... поэтому использование стабильного сорта несколько раз похоже на рецепт проблемы с производительностью ...

И да, это действительно позор, что-то спросить предикат: Я не вижу другой пути, чем создать функтор принимающего вектор функций трехуровневых ...

Answer 4

Цепочный раствор является подробным. Вы также можете использовать boost :: bind в сочетании с std :: logical_and для создания вашего предиката сортировки. См связанной статьи для получения дополнительной информации: How the boost bind library can improve your C++ programs

Answer 5

Вы можете попробовать это:

Использование:

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

Реализация:

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 шаблоны в C++ 11 дает более короткий вариант:

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