Archivo

Posts Tagged ‘Boost’

Filtrando contenedores mediante boost::filter_iterator


Cuando creamos nuestro modelo de datos, a veces nos encontramos con que necesitamos crear clases que actúan como contenedores. En estos casos lo natural que expongamos una forma a través de la cual podamos acceder a los objetos contenidos. Pero la mayoría de las veces (a menos que se trate de un contenedor trivial) también querremos exponer una forma para filtrar el contenido por criterios definidos.

En el caso de que el contenedor sea trivial y sólo necesites acceder al contenido, nos basta entonces con usar alguno de los contenedores estándares que la librería estándar de C++ pone a nuestra disposición, como std::list o std::vector. Pero ¿y cuando queremos añadir filtros? Por supuesto que hay varias formas de hacerlo, pero eso lo veremos más adelante. Comencemos por armar nuestro ejemplo base.

Pensemos en una clase empleado que tiene algunos atributos: nombre, edad, salario y un puntero hacia el jefe (o nulo si no lo tiene); y un método que nos permita imprimir el nombre del empleado hacia la consola. Nothing too fancy:


class employee
{
    public:
        employee()
            : income(0.0), age(0), manager(nullptr)
        { }
        employee(const string& name, double income, int age, employee* manager)
            : name(name), income(income), age(age), manager(manager)
        { }
        employee(const employee& copy)
            : name(copy.name), income(copy.income), age(copy.age), 
              manager(copy.manager)
        { }

        string manager_name() const { 
            return manager != nullptr ? manager->name : "[Sin jefe]"; 
        }

        void print() const { cout << name << endl; }

        string name;
        double income;
        int age;
        employee* manager;
};

Nada del otro mundo. Ahora pensemos en cómo sería nuestra clase contenedora. La librería estándar de C++ nos provee los contenedores de la STL, como std::list o std::vector. Todos estos contenedores se basan en la idea de separar el acceso a los datos del algoritmo empleado para almacenarlos. En otras palabras, la forma en la que obtenemos los objetos no varía respecto de la forma en la que éstos se almacenan (en nodos, en bloques de memoria adyacentes, etc.).

La forma de acceder a los objetos se hace mediante iteradores. El concepto de un iterador es el de un puntero hacia el siguiente elemento de un contenedor (iterador de avance), hacia el siguiente y el anterior (iterador bidireccional), o hacia un elemento particular (iterador de acceso aleatorio). De esta forma, dado un elemento cualquiera dentro de la colección siempre será posible acceder al que le sigue, sin importar la forma en la que esté implementado el algoritmo interno.

Dado lo anterior, es una buena idea seguir el mismo patrón para nuestra clase contenedora. Aunque internamente usaremos un std::list para almacenar el contenido.



class catalog
{
    public:
        typedef list<employee> employee_list;
        typedef employee_list::size_type size_type;
        typedef employee_list::iterator iterator;
        typedef employee_list::const_iterator const_iterator;

    private:
        employee_list _employees;
        
    public:

        catalog() { }

        size_type size() const { return _employees.size(); }
        void clear() { _employees.clear(); }

        void add(const employee& emp) { _employees.push_back(emp); }
        void add(const string& name, double income, int age, employee* mgr) {
            add(employee(name, income, age, mgr));
        }
};

Bueno, sólo son algunos typedefs y algunos métodos comúnmente encontrados en este tipo de clases. Ahora bien, queremos exponer los elementos del catálogo, así que bien haríamos con añadir un método begin_all y end_all que nos devuelva el iterador inicial y el final.


        iterator begin_all() { return _employees.begin(); }
        iterator end() { return _employees.end(); }

Bueno, ahora sí. ¿Cómo le hacemos para añadir filtros? Por ejemplo, ¿cómo le hacemos si quisiéramos, de alguna forma, exponer a aquellos empleados cuyo nombre contiene alguna letra o cuya edad se encuentra en un rango determinado?

Una forma, por supuesto, sería crear un método similar a este:

...

void fill_by_age(list& lst, int min, int max)
{
    for (auto i = employees.begin(); i != employees.end(); ++i)
    {
        if (min <= age && i->age <= max)
            lst.push_back(*i);
    }
}
...

Aunque correcto, este código presenta ciertas deficiencias de diseño. Para empezar tenemos que pasar una referencia al contenedor donde se guardarán. Para seguir, tenemos que especificar el tipo de contenedor que usaremos (std::list). Si mañana quisiéramos cambiar de un list a un vector o a un map, rompería código ya escrito y habría que rehacerlo. Y por último, aquí estamos rompiendo la regla de separar implementación del acceso.

No hay mucho qué hacer para el primer problema. Pero para resolver el segundo, podríamos crear un método plantilla y que ahí se decida el tipo de contenedor. Y aun si obviáramos los problemas de estar manejando plantillas, no resolveríamos el tercer problema.

¿Qué podemos hacer? Bueno, una alternativa es regresar iteradores, similares al begin_all y end_all que hicimos hace rato. Pero en aquel momento simplemente pasamos los iteradores del contenedor interno (std::list). ¿Qué hacer ahora? ¿Crear nuestros propios iteradores, unos que hagan el filtro en automático?

Evidentemente es una opción, aunque es cierto que es una un tanto compleja y laboriosa. Y aquí el estándar de C++ nos deja sin opciones. Afortunadamente aquí es donde entra Boost. Esta biblioteca cuenta con una clase que nos ayuda, precísamente, a hacer esto que queremos. Estamos hablando de boost::filter_iterator<P, I>.

No voy a entrar en una discusión completa sobre esta clase (para eso, mejor revisar la documentación de Boost). Pero sí diré que es una clase que toma un predicado o functor (de tipo P), y un iterador de tipo I. La clase recorre el iterador, de inicio a fin, y para cada elemento ejecuta el predicado / functor en cuestión. Si éste regresa verdadero, filter_iterador añade el elemento a un iterador temporal. Si no, lo deja fuera. Luego, puede recorrerse este iterador temporal y todo lo que obtendremos serán los elementos filtrados.

¡Yay! ¡Suena como a algo que necesitamos! ¿Cómo lo implementamos?

Lo primero que necesitamos es un functor. Es decir, una clase con el operador () sobrecargado, y que tome como parámetro un objeto del contenedor, es decir, de tipo employee. Esta sobrecarga deberá regresar true para cuando queramos que el objeto pasado como parámetro sea incluido en el filtro. Así que podemos probar con un functor para filtrar la edad por un rango mínimo (ésto último pasados como parámetros al constructor del functor).

struct range_func
{
    range_func()
        : _min(0), _max(0)
    { }
    range_func(const range_func& copy)
        : _min(copy._min), _max(copy._max) 
    { }
    range_func(int min, int max)
        : _min(min), _max(max) 
    { }

    bool operator()(const employee& emp) const {
        return _min <= emp.age && emp.age <= _max;
    }

    int _min;
    int _max;
};

Sencillo, ¿no? Bueno, ahora lo que haremos es crear nuestro boost::filter_iterator para devolver un iterador de inicio y uno de fin. Para ello, usaremos la función boost::make_filter_iterator, en donde le pasaremos el functor ya creado y luego el iterador. Para el begin(), le pasamos begin() y end() de la lista, y para el end(), pasamos dos veces el end() de la lista. Algo así.

typedef filter_iterator range_filter_iterator;
...

range_filter_iterator begin_age_range(int min, int max)  {
	return begin_age_range(range_func(min, max));
}
		
range_filter_iterator begin_age_range(const range_func& func) {
	return make_filter_iterator<range_func>((func, 
        _employees.begin(), _employees.end());
}

range_filter_iterator end_age_range(int min, int max) {
    return end_age_range(range_func(min, max));
}

range_filter_iterator end_age_range(const range_func& func) {
    return make_filter_iterator<range_func>((func, 
        _employees.end(), _employees.end());
}

Un typedef al inicio para facilitar las cosas. Por lo demás, make_filter_iterator se encarga del resto. Ahora podemos usar nuestra clase de una forma similar a esta.

int main(int argc, char* argv[])
{
    catalog cat;
    employee fer("Fernando", 10000, 29, nullptr);
    cat.add(fer);
    cat.add("Gabriela", 13500, 26, &fer);
    employee jime("Jimena", 9500, 22, &fer);
    cat.add(jime);
    cat.add("Mario", 4300, 37, &jime);
    employee caty("Catalina", 15000, 31, nullptr);
    cat.add(caty);
    employee gis("Gisela", 14750, 30, &caty);
    cat.add(gis);
    cat.add("Omar", 12700, 30, &gis);

    auto func = [](const employee& emp) { 
        emp.print(); 
    };

    cout << "Edad entre 25 y 30" << endl;
    for_each(cat.begin_age_range(25, 30), cat.end_age_range(25, 30), func);
    cout << endl;

    ...
    return 0;
}

Como podemos ver, filter_iterator es una forma fácil de generar filtros y de paso resolver los tres problemas planteados hace un momento: no se expone el tipo del contenedor, y mantenemos separada la implementación.

Ya para terminar, dejo un programita de ejemplo completo: filtros por edad, nombre y jefe.



#include <iostream>
#include <string>
#include <list>
#include <functional>
#include <algorithm>
#include <boost/iterator/filter_iterator.hpp>

using std::string;
using std::cout;
using std::endl;
using std::list;
using std::function;
using std::for_each;
using std::shared_ptr;
using boost::filter_iterator;
using boost::make_filter_iterator;

class employee;

class employee
{
    public:
        employee()
            : income(0.0), age(0), manager(nullptr)
        { }
        employee(const string& name, double income, int age, employee* manager)
            : name(name), income(income), age(age), manager(manager)
        { }
        employee(const employee& copy)
            : name(copy.name), income(copy.income), age(copy.age), 
                manager(copy.manager)
        { }

        string manager_name() const { 
            return manager != nullptr ? manager->name : "[Sin jefe]"; 
        }

        void print() const { cout << name << endl; }

        string name;
        double income;
        int age;
        employee* manager;
};

struct range_func
{
    range_func()
        : _min(0), _max(0)
    { }
    range_func(const range_func& copy)
        : _min(copy._min), _max(copy._max) 
    { }
    range_func(int min, int max)
        : _min(min), _max(max) 
    { }

    bool operator()(const employee& emp) const {
        return _min <= emp.age && emp.age <= _max;
    }

    int _min;
    int _max;
};

struct substr_func
{
    substr_func() 
    { }
    substr_func(const string& str) 
        : _str(str)
    { }
    substr_func(const substr_func& copy)
        : _str(copy._str)
    { }

    bool operator()(const employee& emp) const {
        return emp.name.find(_str) != string::npos;
    }

    string _str;
};

struct mgr_func
{
    mgr_func()
        : _ptr(nullptr)
    { }
    mgr_func(employee* ptr)
        : _ptr(ptr)
    { }
    mgr_func(const mgr_func& copy)
        : _ptr(copy._ptr)
    { }

    bool operator()(const employee& emp) const {
        bool val = false;
        if (_ptr == nullptr)
            val = emp.manager == nullptr;
        else 
            val = emp.manager_name() == _ptr->name;
        return val;
    }

    employee* _ptr;
};


class catalog
{
    public:
        typedef list<employee> employee_list;
        typedef employee_list::size_type size_type;
        typedef employee_list::iterator iterator;
        typedef employee_list::const_iterator const_iterator;
        typedef filter_iterator<range_func, iterator> range_filter_iterator;
        typedef filter_iterator<substr_func, iterator> substr_filter_iterator;
        typedef filter_iterator<mgr_func, iterator> mgr_filter_iterator;

    private:
        employee_list _employees;
        
    public:

        catalog() { }

        size_type size() const { return _employees.size(); }
        void clear() { _employees.clear(); }

        void add(const employee& emp) { _employees.push_back(emp); }
        void add(const string& name, double income, int age, employee* mgr) {
            add(employee(name, income, age, mgr)); 
        }

        iterator begin_all() { return _employees.begin(); }
        iterator end() { return _employees.end(); }

        range_filter_iterator begin_age_range(int min, int max)  {
			return begin_age_range(range_func(min, max));
		}
		
		range_filter_iterator begin_age_range(const range_func& func) {
			return make_filter_iterator<range_func>(func, _employees.begin(), 
                _employees.end());
		}

        range_filter_iterator end_age_range(int min, int max) {
            return end_age_range(range_func(min, max));
        }

        range_filter_iterator end_age_range(const range_func& func) {
            return make_filter_iterator<range_func>(func, _employees.end(), 
                _employees.end());
        }

        substr_filter_iterator begin_substr(const string& value) {
            return begin_substr(substr_func(value));
        }

        substr_filter_iterator begin_substr(const substr_func& func) {
            return make_filter_iterator(func, _employees.begin(), 
                _employees.end());
        }

        substr_filter_iterator end_substr(const string& value) {
            return end_substr(substr_func(value));
        }

        substr_filter_iterator end_substr(const substr_func& func) {
            return make_filter_iterator(func, _employees.end(),
                 _employees.end());
        }

        mgr_filter_iterator begin_mgr(employee* mgr) {
            return begin_mgr(mgr_func(mgr));
        }

        mgr_filter_iterator begin_mgr(const mgr_func& func) {
            return make_filter_iterator(func, _employees.begin(), 
                _employees.end());
        }

        mgr_filter_iterator end_mgr(employee* mgr) {
            return end_mgr(mgr_func(mgr));
        }

        mgr_filter_iterator end_mgr(const mgr_func& func) {
            return make_filter_iterator(func, _employees.end(), 
                _employees.end());
        }
};

int main(int argc, char* argv[])
{
    catalog cat;
    employee fer("Fernando", 10000, 29, nullptr);
    cat.add(fer);
    cat.add("Gabriela", 13500, 26, &fer);
    employee jime("Jimena", 9500, 22, &fer);
    cat.add(jime);
    cat.add("Mario", 4300, 37, &jime);
    employee caty("Catalina", 15000, 31, nullptr);
    cat.add(caty);
    employee gis("Gisela", 14750, 30, &caty);
    cat.add(gis);
    cat.add("Omar", 12700, 30, &gis);

    auto func = [](const employee& emp) { 
        emp.print(); 
    };

    cout << "*** Todos los empleados *** " << endl;
    for_each(cat.begin_all(), cat.end(), func);
    cout << endl;

    cout << "***** POR EDAD *****" << endl;

    cout << "Edad entre 25 y 30" << endl;
    for_each(cat.begin_age_range(25, 30), cat.end_age_range(25, 30), func);
    cout << endl;

    cout << "Edad menor a 25" << endl;
    for_each(cat.begin_age_range(0, 25), cat.end_age_range(0, 25), func);
    cout << endl;

    cout << "Edad mayor a 30" << endl;
    for_each(cat.begin_age_range(30, 100), cat.end_age_range(30, 100), func);
    cout << endl;

    cout << "***** POR NOMBRE *****" << endl;

    cout << "Nombre que contenga 'na'" << endl;
    for_each(cat.begin_substr("na"), cat.end_substr("na"), func);
    cout << endl;

    cout << "Nombre que contenga 'ri'" << endl;
    for_each(cat.begin_substr("ri"), cat.end_substr("ri"), func);
    cout << endl;

    cout << "***** POR JEFE *****" << endl;

    cout << "Le reportan a Fernando" << endl;
    for_each(cat.begin_mgr(&fer), cat.end_mgr(&fer), func);
    cout << endl;

    cout << "Le reportan a Caty" << endl;
    for_each(cat.begin_mgr(&caty), cat.end_mgr(&caty), func);
    cout << endl;

    system("pause");
    return 0;
}


Y al ejecutarlo, tenemos este resultado:

*** Todos los empleados ***
Fernando
Gabriela
Jimena
Mario
Catalina
Gisela
Omar

***** POR EDAD *****
Edad entre 25 y 30
Fernando
Gabriela
Gisela
Omar

Edad menor a 25
Jimena

Edad mayor a 30
Mario
Catalina
Gisela
Omar

***** POR NOMBRE *****
Nombre que contenga 'na'
Fernando
Jimena
Catalina

Nombre que contenga 'ri'
Gabriela
Mario

***** POR JEFE *****
Le reportan a Fernando
Gabriela
Jimena

Le reportan a Caty
Gisela

Press any key to continue . . .

Ahora, intenta hacer algo similar sin functores, sino con lambdas… o mediante std::function. ¡Disfruta!

Anuncios
Categorías:Apunte, Boost, C++, Independiente Etiquetas: , ,

Boostificando mi vida


Vaya cosas de la vida. La gente que me conoce sabe que soy C++ boy desde hace años: no por nada mis sobrenombres son Fer++ o F++.

Aunque no fue el primer lenguaje que aprendí (ese fue QBASIC y luego Visual Basic 6, cuando iba en la preparatoria), fue mi primer lenguaje profesional. Antes de salir de la preparatoria ya había hecho trabajos con HTML, JavaScript y CSS, pero mi primer trabajo para una empresa de desarrollo fue como programador de C++: cuando apenas tenía 19 años en marzo de 2002. Desde ahí nunca he dejado de programar con este lenguaje.

Seguro, el boom de .NET llegó a México alrededor del 2004, y hubo altibajos, pero en general creo que fui bastante constante. En 2008 fue cuando ahora sí mi trabajo se volvió puro .NET con algo de SharePoint. Sin embargo, ahora que el código no administrado viene de vuelta, con todo, me emociona volver a usar este lenguaje y de hecho ya estoy aprendiendo Metro, la nueva API de Microsoft para Windows 8. Y no soy el único: justo hoy se está llevando a cabo la conferencia Going Native 2012.

¿Cuántos libros de C++ no habré leído con entusiasmo? The Standard C++ Library, de Nicolai Josuttis, o qué tal Modern C++ Design de Andrei Alexandrescu… He probado varias librerías: obviamente MFC, pero también la Windows Template Library, Qt o incluso wxWidgets. Y sin embargo… nunca había utilizado Boost.

Boost, para quien no sepa, es una librería, o conjunto de librerías de C++, diseñadas para integrarse bien con el estándar de C++. Proveen mucha funcionalidad que el estándar todavía no contempla, y éstas son revisadas por mucha gente de la comunidad, incluídos participantes del comité de estandarización de C++. Es más, muchos componentes de Boost suelen terminar en el estándar. Pero no dejes que te lo cuente, entra a este enlace y entérate por tí mismo.

Ahora, no es que no supiera de la existencia de Boost. Hace algunos años intenté instalarlo pero la verdad que fue un poco engorroso el construirlo. La mayoría de los componentes de Boost son puros encabezados, perohay ciertaspartes que requieren enlazar con librerías estáticas, y ahí es donde estaba el problema.

Y sucede que con todo este fervor por regresar al mundo nativo, en parte promovido por Microsoft y su Windows 8, ahora sí decidí echarle un ojo. Me encontré conque ya tenían un instalador, así que ésta fue bien fácil. Sólo tuve que agregar el directorio de instalación a

image

Y ahora sí, estamos listos para usar Boost. Probemos algo sencillo.


#include <iostream>
#include <boost/array.hpp>

int main(int argc, char* argv[])
{
    boost::array a;
    for (auto i = 0; i < a.size(); i++)
        a[i] = i * i;

    for (auto i = a.begin(); i != a.end(); ++i)
        std::cout << *i << std::endl;

    system("pause");
    return 0;
}

 

La clase boost::array en realidad es un simple envoltorio de un array natural, pero provee ciertas características adicionales como el contar con iteradores begin() y end(). En fin, no importa. Como estas clases, Boost cuenta con muchísimas más.

Y he de decir que hasta donde he podido explorar he encontrado muchas clases muuuuuuucho muy útiles. De hecho poco a poco las iré exponiendo por aquí. Pero venga, anímate tú también y boostifica tu vida.

¡Nos vemos!

Categorías:Boost, C++, Noticias Etiquetas: ,