...

суббота, 11 января 2014 г.

Идиомы С++. Static visitor

Паттерн Visitor предлагает еще один способ отделить алгоритм обработки данных от самих данных. В этой статье я кратко опишу идею, стоящую за оригинальным паттерном, его С++ специфическую вариацию и приведу несколько простых примеров использования.



Visitor




Для начала вспомним как устроен классический Visitor. Мотивация этого паттерна довольно проста. Представьте себе, что нам в программе нужно обработать контейнер (дерево, граф) полиморфных указателей и выполнить для каждого объекта какой-то набор операций, причем этот набор должен быть разным для каждого конкретного типа. Также стоит отметить, что сами объекты ничего не должны знать об алгоритмах их обработки кроме того, что их может “навестить” обработчик.

Например, объекты файловой системы: файлы, папки:

class abstract_file_t
{
public:
virtual std::string name() const = 0;
virtual void accept(visitor_t& v) = 0;
virtual ~abstract_file_t(){}
};

////////////////////////////////////////////////////////////////////////////

class regular_file_t : public abstract_file_t
{
public:
std::string name() const;
void accept(visitor_t& v);
size_t size();
};

////////////////////////////////////////////////////////////////////////////

typedef std::vector<abstract_file_t*> file_vector_t;
class directory_t : public abstract_file_t
{
public:
void accept(visitor_t& v);
std::string name() const;
file_vector_t& files();
};





Как видите, знание объектов файловой системы о том как с ними будут работать состоит лишь в том, что их может “навестить” объект с базовым типом visitor_t. В функции accept мы просто “впускаем посетителя”:

void regular_file_t::accept(visitor_t& v) {v.visit(*this);}




В случае с каталогом, в accept может быть добавлен код для “посещения” всех находящихся в нем файлов.

“Посетитель” устроен следующим образом:

class visitor_t
{
public:
virtual void visit(regular_file_t& f) = 0;
virtual void visit(directory_t& f) = 0;
virtual ~visitor_t(){}
};

class print_info_visitor_t : public visitor_t
{
public:
void visit(regular_file_t& f);
{
std::cout << "visiting concrete file. file name: " << f.name() <<
" file size: " << f.size() << std::endl;
}
void visit(directory_t& dir)
{
std::cout << "visiting directory. directory name: " << dir.name() <<
". contains " << dir.files().size() << “files” << std::endl;
}
};


Static visitor




Суть Static visitor’а также заключается в отделении данных от алгоритмов обработки этих данных. Основное отличие заключается в том, что динамический полиморфизм классического Visitor’а заменяется на статический (отсюда, собственно, и название идиомы). С одной реализацией этого паттерна мы встречаемся практически каждый раз когда используем алгоритмы STL. Действительно, предикаты STL — отличный пример static visitor’а. Чтобы это стало совершенно очевидно рассмотрим следующий небольшой пример:

class person_t
{
public:
person_t(const std::string& name, size_t age)
: name_(name), age_(age){}

template<typename Visitor>
void accept(Visitor& v) {v.visit(*this);}
size_t age() const {return age_;}
private:
std::string name_;
size_t age_;
};
////////////////////////////////////////////////////////////////////////////////
struct person_visitor_t
{
person_visitor_t(size_t age_limit) : age_limit_(age_limit){}
bool operator()(const person_t& p) {return visit(p);}
bool visit(const person_t& p) {return p.age() < age_limit_;}
size_t age_limit_;
};

////////////////////////////////////////////////////////////////////////////////
int main()
{
std::vector<person_t> person_vec;
person_vec.push_back(person_t("Person 1", 43));
person_vec.push_back(person_t("Person 2", 20));

auto it = std::find_if(
person_vec.begin(), person_vec.end(), person_visitor_t(30));
if(it != person_vec.end())
std::cout << it->age() << std::endl;
return 0;
}




Очень похоже на то, что мы видели в первой главе, не правда ли?

Примеры использования




Boost Graph Library



Идею предиката можно развить. Почему бы нам не дать возможность пользователю изменять поведение наших алгоритмов в некоторых ключевых точках с помощью предоставленного пользователем же “посетителя”? Допустим мы пишем библиотеку для работы с графами, состоящую из структур данных для хранения узлов и ребер и алгоритмов для обработки этих структур (Boost Graph Library). Для максимальной гибкости мы можем предоставлять два варианта каждого алгоритма. Один выполняющий действия по умолчанию и другой — позволяющий пользователю влиять на некоторые шаги алгоритма. Упрощенно это можно представить так:

template<typename T>
struct node_t
{
node_t(){}
// Аналог функции accept
template<typename V>
void on_init(V& v) {v.on_init(t_);}
// Еще один accept
template<typename V>
void on_print(V& v) {v.on_print(t_);}
T t_;
};





Алгоритмы. Одна версия по умолчанию и одна с использованием Visitor’a

template<typename T, typename Graph>
void generate_graph(Graph& g, size_t size);

template<typename T, typename Graph, typename Visitor>
void generate_graph(Graph& g, Visitor& v, size_t size)
{
for(size_t i = 0; i < size; ++i)
{
node_t<T> node;
node.on_init(v);
g.push_back(node);
}
}

////////////////////////////////////////////////////////////////////////////////

template<typename Graph>
void print_graph(Graph& g);

template<typename Graph, typename Visitor>
void print_graph(Graph& g, Visitor& v)
{
for(size_t i = 0; i < g.size(); ++i)
{
g[i].on_print(v);
}
}





Теперь код пользователя.

struct person_t
{
std::string name;
int age;
};

////////////////////////////////////////////////////////////////////////////////
// visitor
struct person_visitor_t
{
// visit()
void on_init(person_t& p)
{
p.name = "unknown";
p.age = 0;
}
// visit()
void on_print(const person_t& p)
{
std::cout << p.name << ", " << p.age << std::endl;
}
};

////////////////////////////////////////////////////////////////////////////////

int main()
{
person_visitor_t person_visitor;

typedef std::vector<node_t<person_t> > person_vec_t;
person_vec_t graph;

generate_graph<person_t>(graph, person_visitor, 10);
print_graph(graph, person_visitor);
}





Variant



Еще один крайне интересный пример применения идиомы static visitor можно найти в boost::variant. Variant представляет собой статически типизированный union. Данные любого допустимого типа хранятся в одном и том же массиве байт. И “посещаем” мы по сути всегда этот, хранящийся внутри variant, массив, но “смотрим” на него каждый раз с точки зрения разных типов. Реализовать это можно как-то так (код максимально упрощен и передает лишь основную идею):

template<
typename T1 = default_param1,
typename T2 = default_param2,
typename T3 = default_param3
>
class variant
{
...
public:

// Хорошо уже знакомый нам accept()
template<typename Visitor>
void apply_visitor(const Visitor& v)
{
switch(type_tag_) // Тэг хранящегося в данный момент типа
{
case 1:
apply1(v, T1());
break;
case 2:
apply2(v, T2());
break;
case 3:
apply3(v, T3());
break;
default:
break;
}
}
};





Функции apply могут выглядеть следующим образом

template<typename Visitor, typename U>
void apply1(
const Visitor& v, U u, typename std::enable_if<
!std::is_same<U, default_param1>::value>::type* = 0)
{
// data_ - массив байт.
// В качестве visit() используется operator()
v(*(T1*)(&data_[0]));
}

// Перегрузка для типа по умолчанию.
template<typename Visitor, typename U>
void apply1(
const Visitor& v, U u, typename std::enable_if<
std::is_same<U, default_param1>::value>::type* = 0)
{
}


Здесь мы используем SFINAE, чтобы “включить” корректную функцию для текущего типа и “выключить” для параметров класса по умолчанию. Пользовательский же код совсем простой:



struct visitor_t
{
void operator()(int i)const ;
void operator()(double d)const;
void operator()(const std::string& s)const;
};

variant<int, double> test_v(34);
test_v.apply_visitor(visitor_t());


This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at fivefilters.org/content-only/faq.php#publishers.


Комментариев нет:

Отправить комментарий