Encadenamiento de predicados de ordenamiento (por ejemplo, para std :: sort)

Question

Puede pasar un puntero de función, objeto de función (o impulsar lambda) a std :: sort para definir un ordenamiento débil estricto de los elementos del contenedor que desea ordenar.

Sin embargo, algunas veces (basta con que haya golpeado esto varias veces), desea poder encadenar comparaciones "primitivas".

Un ejemplo trivial sería si estuviera ordenando una colección de objetos que representan datos de contacto. Algunas veces querrá ordenar por

last name, first name, area code

. Otras veces

first name, last name

- otras veces

age, first name, area code

... etc

Ahora, ciertamente puede escribir un objeto de función adicional para cada caso, pero eso infringe el principio DRY, especialmente si cada comparación es menos trivial.

Parece que debe poder escribir una jerarquía de funciones de comparación: las de bajo nivel hacen las comparaciones simples, primitivas (por ejemplo, nombre del primer nombre <), luego las de nivel superior llaman a las de nivel inferior en sucesión (probablemente encadenando con & & para hacer uso de la evaluación de cortocircuito) para generar las funciones compuestas.

El problema con este enfoque es que std :: sort toma un predicado binario: el predicado solo puede devolver un bool. Entonces, si los estás componiendo no puedes decir si un "falso" indica igualdad o más que. Puede hacer que sus predicados de nivel inferior devuelvan un int, con tres estados, pero luego debería envolverlos en predicados de nivel superior antes de que puedan ser utilizados con std :: sort por sí mismos.

En total, estos no son problemas insuperables. Simplemente parece más difícil de lo que debería ser, y ciertamente invita a una implementación de biblioteca auxiliar.

Por lo tanto, ¿alguien sabe de cualquier biblioteca preexistente (especialmente si se trata de una biblioteca std o boost) que puede ayudar aquí - de tener alguna otra idea al respecto?

[Actualización]

como se menciona en algunos de los comentarios - He ido adelante y escrito mi propia implementación de una clase para manejar esto. Es bastante mínimo, y probablemente tenga algunos problemas con él en general. pero sobre esa base, para cualquier persona interesada, la clase está aquí:

http://pastebin.com/f52a85e4f

Y algunas funciones auxiliares (para evitar la necesidad de especificar argumentos de plantilla) es aquí:

http://pastebin.com/fa03d66e

Answer 1

Se puede construir un pequeño sistema de encadenamiento de este modo:

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

después utilizarla:

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

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

La última línea es un poco prolijo, pero yo creo que está claro lo que se pretende.

Answer 2

Uno La forma convencional de manejar esto es ordenar múltiples pasadas y usar una clasificación estable. Observe que std::sort generalmente es no estable. Sin embargo, está std::stable_sort.

Dicho esto, escribiría un envoltorio alrededor de los funtores que devuelven un estado triestado (representa menos, igual, mayor).

Answer 3

std::sort no se garantiza que sea estable porque los géneros estables son generalmente más lentos que los no estables ... por lo que usar un tipo estable varias veces parece una receta para problemas de rendimiento ...

Y sí que es realmente una pena que una especie pedir un predicado: no veo otra manera de crear un funtor aceptar un vector de funciones de tres estados ...

Answer 4

La solución de encadenamiento es detallada. También podría usar boost :: bind junto con std :: logical_and para construir su predicado de clasificación. Ver el artículo enlazado para más información: How the boost bind library can improve your C++ programs

Answer 5

Usted puede intentar esto:

Uso:

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

Implementación:

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 plantillas en C++ 11 dan una opción más corta:

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