Раздел «Образование».FIVTLecturesTerm2Lecture10:
<<Лекции ФИВТ, 2-й семестр

Следующая лекция
Предыдущая лекция?

Лекция 10. Функторы less и less_than

Функтор less

#include <algorithm>
#include <iostream>

using std::cout;
using std::endl;

template<class T>
class less {
public:
    bool operator ()(const T &a, const T &b) const
    {
        return a < b;
    }
};

int main() {
    less<int> a;

    cout << a(2,1) << endl;
    return 0;
}

%CODE{cpp}%
#include <algorithm>
#include <iostream>

using std::cout;
using std::endl;

template<class T>
class greater {
public:
    bool operator ()(const T &a, const T &b) const
    {
        return a > b;
    }
};

int main() {
    // есть возможность задать функцию сравнения для ключей
    // в дереве поиска в контейнере map
    map<int, string, greater<int>()>  c;
    // ....
    for(it = s.begin(); it != s.end(); it++) {
       // .. 
       // итерирование будет происходить от пары с большим ключем
       // к паре с наименьшим ключём
    }
    return 0;
}

Функтор less_than

#include <algorithm>
#include <iostream>

using std::cout;
using std::endl;
using std::remove_if;

template<class T>
class less_than {
private:
    T threshold;
public:
    less_than(const T &threshold): threshold(threshold) {};

    bool operator ()(const T &a) const
    {
        return a <= threshold;
    }
};

int main(void)
{
    int a[] = { 0, 1, 10, 99, -11, 4, 5, 1, 2, 3 };
    int size = sizeof(a) / sizeof(*a);
    int *end = remove_if(a, a + size, less_than<int>(4));
    int *begin = a;
    while(begin < end) {
        cout << *begin << ' ';
        ++begin;
    }
    cout << endl;
    return 0;
}

Функция создания функтора less_than

#include <algorithm>
#include <iostream>

using std::cout;
using std::endl;
using std::remove_if;


template<class T>
class less_than_functor {
private:
    T threshold;
public:
    less_than_functor(const T &threshold): threshold(threshold) {};

    bool operator ()(const T &a) const
    {
        return a <= threshold;
    }
};

template<class T>
less_than_functor<T> less_than(const T &arg)
{
    return less_than_functor<T>(arg);
}

int main(void)
{
    int a[] = { 0, 1, 10, 99, -11,  4,  5, 1, 2, 3 };
    int size = sizeof(a) / sizeof(*a);
    // можно не писать параметр для шаблоной функции less_than, так как
    // тип T будет автоматически выведен из типа аргумента
    int *end = remove_if(a, a + size, less_than(4));
    int *begin = a;
    while (begin < end) {
        cout << *begin << ' ';
        ++begin;
    }
    cout << endl;
    return 0;
}

#include <algorithm>
#include <iostream>

using std::cout;
using std::endl;
using std::remove_if;


template<class T>
class less {
public:
    bool operator ()(const T &a, const T &b) const
    {
        return a < b;
    }
};

template<class T>
class less_than_functor {
private:
    T threshold;
public:
    less_than_functor(const T &threshold): threshold(threshold) {};

    bool operator ()(const T &a) const
    {
        return a <= threshold;
    }
};

template<class T>
less_than_functor<T> less_than(const T &arg)
{
    return less_than_functor<T>(arg);
}

int main(void)
{
    double a[] = { 0, 1, 10, 99, -11, 4.1, 4, 3.9, 5, 1, 2, 3 };
    int size = sizeof(a) / sizeof(*a);

    // почему здесь обязательно нужно явно указывать тип T?
    double *end = remove_if(a, a + size, less_than<int>(4));
    double *begin = a;
    while(begin < end) {
        cout << *begin << ' ';
        ++begin;
    }
    cout << endl;
    return 0;
}

Шаблон функтора memoise

Кэширование значений функций — достаточно общий функционал. Несложно написать кеширование значений определенной функции. Но если вам требуется кешировать множество функции, правильнее написать реализацию функционала кеширования общего назначения.

#include <iostream>
#include <map>
using std::cout;
using std::endl;
using std::map;

struct square {
    int operator () (int value) const
    {
        return value * value;
    }
};

int cube(int value) {
    return value * value * value;
}


template<class R, class A, class F, int SIZE=100>
class memoizer {
    map<A, R> cache;
    F f;
public:
    memoizer(const F &f): f(f) {};

    R operator () (const A &arg)
    {
        time++;
        if (cache.find(arg) == cache.end()) {
            cerr << "caching!" << endl;
            return cache[arg] = f(arg);
        } else {
            return cache[arg];
        }
    }
};

int main(void) {
    square s;
    memoizer<int, int, square> m(s);
    cout << m(10) << endl;
    cout << m(15) << endl;
    cout << m(10) << endl;

    memoizer<int, int, int (*) (int)> n(cube);
    cout << n(10) << endl;
    cout << n(15) << endl;
    cout << n(10) << endl;
    cout << n(15) << endl;

    return 0;
}

Шаблон функтора memoise с максимальным значением размера кеша

Параметром шаблона могут быть и числа. Для примера покажем как для шаблона функтора memoise можно добавить новый параметр — максимальный размер кеши.

#include <iostream>
#include <map>
using std::cout;
using std::endl;
using std::map;

struct square {
    int operator () (int value) const
    {
        return value * value;
    }
};

int cube(int value) {
    return value * value * value;
}


template<class R, class A, class F, int SIZE=100>
class memoizer {
    map<A, R> cache;
    map<A, int> arg_to_time;
    map<int, A> time_to_arg;
    int time;
    F f;
public:
    memoizer(const F &f): f(f) {};

    R operator () (const A &arg)
    {
        time++;
        if (cache.find(arg) == cache.end()) {
            cout << "caching!" << endl;
            arg_to_time[arg] = time;
            time_to_arg[time] = arg;
            
            if (cache.size() > SIZE) {
                A old_arg = time_to_arg.begin()->second;
                time_to_arg.erase(time_to_arg.begin());
                arg_to_time.erase(old_arg);
                cache.erase(old_arg);
            }

            return cache[arg] = f(arg);
        } else {
            return cache[arg];
        }
    }
};

// функция для осздания кеширующих функторов
template<class R, class A, class F, int SIZE=100>
memoizer<R, A, F, SIZE> make_memoizer(const F &f) {
    return memoizer<R, A, F, SIZE>(f);
}

int main(void) {
    square s;
    memoizer<int, int, square> m(s);
    cout << m(10) << endl;
    cout << m(15) << endl;
    cout << m(10) << endl;

    memoizer<int, int, int (*) (int)> n(cube);
    cout << n(10) << endl;
    cout << n(15) << endl;
    cout << n(10) << endl;
    cout << n(15) << endl;

    // при вызове шаблонной функции make_memoizer параметр F
    // можно опустить, так как он выводится из типа аргумента
    memoizer<int, int, square> v = make_memoizer<int, int>(s);
    cout << v(20) << endl;
    return 0;
}

-- ArtemVoroztsov - 27 Apr 2010