c++ - libreria - Encadenamiento de predicados de ordenamiento(p. Ej. Para std:: sort)

sort vector c++ ascending

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), quiere poder encadenar comparaciones "primitivas".

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

last name, first name, area code . Otros tiempos

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 viola el principio DRY, especialmente si cada comparación es menos trivial.

Parece que debería poder escribir una jerarquía de funciones de comparación: las de bajo nivel hacen las comparaciones simples, primitivas (por ejemplo, nombre y apellido), luego las de nivel más alto llaman sucesivamente a las de nivel inferior (probablemente encadenándose 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 general, 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 alguna biblioteca preexistente (especialmente si es una biblioteca estándar o de refuerzo) que puede ayudar aquí, de tener alguna otra opinión al respecto?

[Actualizar]

Como mencioné en algunos de los comentarios, he avanzado y he escrito mi propia implementación de una clase para gestionar 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) están aquí:

http://pastebin.com/fa03d66e

Answer 1

Podrías construir un pequeño sistema de encadenamiento así:

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

Entonces para usarlo:

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 prolija, pero creo que está claro lo que se pretende.

Answer 2

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

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

Answer 3

La solución de encadenamiento es prolija. También podría usar boost :: bind junto con std :: logical_and para construir su predicado de clasificación. Consulte el artículo vinculado para obtener más información: cómo la biblioteca de enlace reforzado puede mejorar sus programas en C ++

Answer 4

Puedes 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 5

Las plantillas variables 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;
    }

Answer 6

std::sort no está garantizado para ser estable porque los géneros estables son generalmente más lentos que los no estables ... así que usar un tipo estable varias veces parece una receta para problemas de rendimiento ...

Y sí, es realmente una pena que ese tipo pida un predicado: no veo otra manera que crear un functor que acepte un vector de funciones triestado ...