Цепочка упорядочивающих предикатов (например,для std::сортировать)

Question

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

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

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

last name, first name, area code

.В другие времена

first name, last name

- еще в другие разы

age, first name, area code

...и т.д.

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

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

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

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

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

[Обновление]

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

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

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

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

Answer 3

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

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

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 4

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

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

Answer 5

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

Answer 6

Вариационные шаблоны в 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;
    }