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

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

10 голосов
/ 08 ноября 2008

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

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

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

last name, first name, area code
. В другое время 
first name, last name
- но в другое время 
age, first name, area code
... и т. Д.

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

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

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

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

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

[Update]

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

http://pastebin.com/f52a85e4f

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

http://pastebin.com/fa03d66e

Ответы [ 6 ]

8 голосов
/ 08 ноября 2008

Вы можете построить небольшую систему цепочек, например, так: 

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

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

2 голосов
/ 23 июня 2012

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

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

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;
};
2 голосов
/ 08 ноября 2008

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

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

2 голосов
/ 08 ноября 2008

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

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

1 голос
/ 22 февраля 2013

Шаблоны 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;
    }
1 голос
/ 09 ноября 2008

Цепное решение многословно. Вы также можете использовать boost :: bind в сочетании с std :: logic_and для создания предиката сортировки. См. Связанную статью для получения дополнительной информации: Как библиотека boost bind может улучшить ваши программы на C ++

...