Inicio > Apunte, Boost, C++, Independiente > Filtrando contenedores mediante boost::filter_iterator

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!

Categorías:Apunte, Boost, C++, Independiente Etiquetas: , ,
  1. Aún no hay comentarios.
  1. marzo 20, 2012 a las 11:20 am
  2. marzo 22, 2012 a las 4:52 pm

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s