C++ / Algoritmos y traits

Bienvenidos sean a este post, hoy veremos una aplicacion de los traits.

Trait puede ser una tecnica muy util para optimizar algoritmos. Para entender el concepto vamos a analizar un ejemplo con el algoritmo copy. Veamos como se compone:

template<typename ItEntrada, typename ItSalida> 
ItSalida copy(ItEntrada first, ItEntrada last, ItSalida out);

Tendremos dos tipos genericos que seran nuestros iteradores. El primero sera para que reciba todos los datos que procesaremos, el segundo sera el de salida y es el que usaremos para enviar el resultado. Por lo tanto, el tipo que devolvemos sera de este segundo tipo. Los primeros dos argumentos seran para poder manipular toda la informacion y el ultimo sera para que la reciba y la devuelva. Pero los autores de este algoritmo, bajo ciertas circunstancias recomiendan usar a memcpy para mejorar el rendimiento. Para ello debemos cumplir algunos requerimientos:

• Tanto ItEntrada como ItSalida deben ser punteros
• Ambos deben apuntar al mismo tipo, con excepcion de const y calificadores volátiles
• Un operador de asignacion trivial debe ser provisto por el tipo a que ItEntrada apunta

El ultimo punto significa que es un tipo escalar o uno de los siguientes:

• No hay operador de asignacion definido por el usuario para el tipo
• No hay ningún tipo de referencia de miembros de datos dentro del tipo
• Los operadores de asignación triviales deben definirse en todas las clases base y los objetos miembros de datos.

El tipo escalar incluye a tipos arimeticos, tipo enumeracion, puntero, puntero a miembro, o una constante o una version volatil calificado de algunos de esos tipos. Veamos como es la implementacion original, esta es la primera parte:

namespace detail{

template <bool b>
struct copier {
    template<typename I1, typename I2>
    static I2 do_copy(I1 first, I1 last, I2 out);
};

template <bool b>
template<typename I1, typename I2>
I2 copier<b>::do_copy(I1 first, I1 last, I2 out) {
    while(first != last) {
        *out = *first; 
         ++out;
         ++first;
    }
    return out;
};

template <>
struct copier<true> {
    template<typename I1, typename I2>
    static I2* do_copy(I1* first, I1* last, I2* out){
        memcpy(out, first, (last-first)*sizeof(I2));
        return out+(last-first);
    }
};
}

Este es todo un namespace para la accion de copiar. Primero definimos un template de clase primaria con una funcion estatica. Tenemos un template de tipo bool y un struct con la funcion estatica donde recibe dos tipos genericos para los datos de entrada y el que sera de devolucion, tal como mencionamos anteriormente. Lo siguiente es la definicion de la funcion anterior, en este caso hace copia elemento por elemento en cada posicion del elemento iterable. El condicional se hara mientras el primer y ultimo elemento sean distintos. Y una vez finalizado devolvera el objeto de salida. La siguiente es una especializacion de la funcion estatica. Pero lugar de hacer una copia elemento por elemento, utilizara memcpy para copiar todos los elementos de una vez. Pasemos a la segunda parte que es la interfaz del usuario:

template<typename I1, typename I2>
inline I2 copy(I1 first, I1 last, I2 out) {
    typedef typename boost::remove_cv
    <typename std::iterator_traits<I1>::value_type>::type v1_t;

    typedef typename boost::remove_cv
    <typename std::iterator_traits<I2>::value_type>::type v2_t;

    enum{ can_opt = boost::is_same<v1_t, v2_t>::value
                    && boost::is_pointer<I1>::value
                    && boost::is_pointer<I2>::value
                    && boost::has_trivial_assign<v1_t>::value 
   };

   return detail::copier<can_opt>::do_copy(first, last, out);
}

Como dijimos esta es la interfaz de copy para el usuario. Tenemos el template con los dos tipos genericos y luego un inline con la funcion copy.. Pero por que un inline? Simplemente para que nuestro codigo sea mas rapido y evitar sobrecargas asociadas a esta funcion. En este definiremos dos objetos template remove_cv. Estos se usan para convertir un tipo en no constante/volatil en base a un tipo. Con nuestros dos objetos creados, en el enum evaluaremos las distintas posibilidades de tipos de datos que podemos recibir. Asi como si son punteros o de asignacion trivial. Como usamos un operador AND en todos los casos, solo sera true si todos son true. Si observan, son los requerimientos que mencionamos anteriormente. Por lo tanto, si can_opt es true procede a usar a memcpy, en caso contrario utiliza la mecanica original de copiar elemento por elemento. Esto mejora la performance porque podremos manejar de una manera correcta a los tipos de datos. Para ir finalizando, veamos algunos detalles:

• El trait dara informacion adicional mas alla del tipo y esta es implementada mediante la especializacion
• Por convencion, los traits son struct y estos struct se denominan como clases de trait
• Bjarne Stroustrup dice que debemos pensar a trait como pequeños objetos cuyo proposito es transportar informacion que es usado por otro objeto o algoritmo y sera para determinar detalles de la politica o implementacion
• Scott Meyers tambien comento que podemos usar las clases de trait para recopilar informacion de los tipos
• Y como vimos, trait permite implementar algoritmos genericos en una manera muy optima

En resumen, hoy hemos visto como usar trait en algoritmos, como nos permiten optimizarlos, asi como tambien como se implementa en el algoritmo copy. Espero les haya resultado de utilidad sigueme en tumblr, Twitter o Facebook para recibir una notificacion cada vez que subo un nuevo post en este blog, nos vemos en el proximo post.