Еще одна реализация обобщенных функторов на C++

ОГЛАВЛЕНИЕ

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

Введение

Обобщенные функторы – важные и мощные артефакты конструкции. В статье пересказываются главные идеи, концепции и детали реализации с сильным упором на последнем, что следует из названия статьи.

Сначала выясним назначение обобщенных функторов. Допустим, есть следующий код на C++:

void f2(int, int) {...}
struct A {
void f2(int, int) {...}
};
struct B {
void f2(int, int) {...}
void f2const(int, int) const {...}
};
struct F {
void operator()(int, int) {...}
};
void (*pf2)(int, int) = &f2;
void (A::*paf2)(int, int) = &A::f2;
void (B::*pbf2)(int, int) = &B::f2;
F f;

Общее понятие для pf2 (указатель на статическую функцию), paf2 и pbf2 (указатели на функции-члены), f (экземпляр класса, содержащий соответствующий operator()) – вызываемая сущность C++, означающая сущность, к которой можно применить оператор operator () вызова функтора:

pf2(1, 2);
A a;
B* pb = new B;
(a.*paf2)(1, 2);
(pb->*pbf2)(1, 2);
f(1, 2);

Что если нам нужно обращаться со всеми ними некоторым универсальным образом, например, поместить их в некоторый "контейнер" и выполнить все вышеуказанные вызовы одновременно с помощью единственного вызова метода такого "контейнера"? Первый способ реализации этого – разработать специальный класс "контейнер". Другой способ – разработать специальный класс-адаптер, способный хранить и делать вызовы всех вышеуказанных вызываемых сущностей. Затем экземпляры класса-адаптера можно сохранять в контейнерах std как обычно. Последний способ более универсален, так как данный класс-адаптер можно использовать в других применениях. Такой класс называется обобщенный функтор. Следующий псевдокод вводит его:

typedef Functor<
...

аргументы шаблона, передающие некоторым образом
тип возвращаемой переменной и типы всех параметров
оператора () – void (пустой тип) и int (целый тип), int для данного примера

...
> Functor2; // (0)
Functor2 fun1(&f2); // (1)
Functor2 fun2(&a, &A::f2); // (2)
Functor2 fun3(pb, &B::f2); // (2)
Functor2 fun4(f); // (3)
fun1(1, 2); // (4)
fun2(1, 2); // (4)
fun3(1, 2); // (4)
fun4(1, 2); // (4)
// fun1(1); // (5)
// fun2(1, 2, 3); // (5)
// fun3(1, true); // (5)
// bool r = fun4(1, 2); // (5)
Functor2 fun; // (6)
fun = fun1; // (7)
fun = fun2; // (7)
fun = fun3; // (7)
fun = fun4; // (7)
// -------------------------------------------
class FunSet
{
typedef std::vector FV;
FV fv_;
public:
FunSet& operator+=(Functor2 const& f)
{
fv_.push_back(f); // (8)
return *this;
}
void operator()(int i1, int i2) const
{
FV::const_iterator end(fv_.end());
for(FV::const_iterator i = fv_.begin(); i != end; ++i)
(*i)(i1, i2);
}
};
FunSet fs;
fs += fun1;
fs += fun2;
fs += fun3;
fs += fun4;
fs(1, 2);

Вышеприведенный  пример простой, но имеет несколько важных задач. Во-первых, онпоказываетприменениеобобщенныхфункторовиихмощностьвместесполучаемымудобством. В частности, то, что все функции, fun1-fun4 имеют одинаковый тип (Functor2), дает простой способ решения вышеуказанной проблемы "контейнера" для разных вызываемых сущностей. Во-вторых, данный пример неявно содержит требования к возможной реализации обобщенного функтора. Далее на них часто ссылаемся, поэтому выделим их:

R1.

Строки 1-3 означают универсальную поддержку для всех видов вызываемых сущностей и требует соответствующих функторов.

R2.

Строки 4 и 5 означают типизированный вызов функции базового экземпляра вызываемой сущности. Отсюда следует, что если строки (5) незакомментированы, они не должны компилироваться, так как они пытаются сделать вызов с неподобающим числом или типами аргументов или с неподобающим типом возвращаемой переменной.

R3.

Строки 6-8 означают полную поддержку семантики значений, т.е. необходимость правильного стандартного ctor, оператора operator=, копирование ctorи dtor. Это важно и очень удобно, учитывая то, что C++ запрещает присваивание и преобразования для неформатированных вызываемых сущностей разных типов.

Есть дополнительные вопросы, затронутые в строке 0. Они касаются ряда других важных деталей реализации:

D1.

Листинг выше показывает пример функтора для вызываемых сущностей с оператором вызова функции operator (), принимающим два целых параметра и возвращающим void. Другие параметры и типы возвращаемых значений обязательно должны поддерживаться, что приводит к вопросу о способе определения параметров шаблона обобщенного функтора.

D2.

А как быть с разным количеством аргументов базового оператора вызова функции operator ()? Разумеется, это должно поддерживаться, проблема в том, как реализовать это максимально явно. В C++ этонепросто, как будет показано позже.

Известные реализации

Две известные реализации обобщенных функторов предоставлены библиотекой Локи и библиотеками ускорения (последняя представлена для стандарта C++). Предоставляя полную семантику и функциональность обобщенных функторов, они полностью отличаются по внутренней реализации, от принципов до итоговой сложности. Разумеется, есть и другие реализации. Проходя через упомянутые вопросы R1, R2, R3, D1 и D2, мы создадим собственную реализацию.

Сейчас рассмотрим вопросы D1. Есть два главных способа параметризации шаблона обобщенного функтора. Первый использует типы функции, а второй использует пару типов возвращаемого значения и список типов, содержащий типы всех аргументов соответствующего оператора вызова функции operator ():

template <class F> class Functor;              (a)

//и

template <class R, class TList> class Functor; (b)

 чтобы использовать их в качестве:

typedef Functor<void (*)(int, int)> Functor2;            (a)

//и

typedef Functor<void, TYPELIST_2(int, int)> Functor2; (b)

typedef Functor<void, CreateTL<int, int>::Type> Functor2;

Примечание: В варианте (b) TYPELISTи CreateTL- макрос и меташаблон, соответственно, используемые для создания списков типов.

Вариант (a) (используется в ускорении) выглядит более изящно, но имеет несколько недостатков. Функции с одинаковой сигнатурой могут иметь разные модификаторы. Cv-уточнители (constи volatile) – первые важные примеры. Они могут применяться лишь к функциям-членам, таким образом:

typedef Functor<void (*)(int, int) const> Functor2;

объявление будет отвергнуто компилятором C++, так как соответствующий тип функции неправильный. Возникает вопрос – как создать экземпляр обобщенного функтора для функции B::f2constв данном случае? Разумеется, это возможно, но за счет ненужного усложнения кода, уродующего исходное изящество. Другие примеры - __cdecl, __stdcall, __fastcall (для функций-нечленов и функций-членов) и неявные модификаторы __thiscall (для функций-членов). Все это нестандартные расширения, предоставленные производителями компилятора, но некоторые из производителей слишком важны, чтобы их игнорировать. Проблема в том, что типы функций с разными модификаторами имеют разные типы, то же самое можно сказать о функторах, экземпляры которых создаются с их помощью. Обобщая, тип функции – слишком низкоуровневая сущность, чтобы использовать ее для параметризации такой высокоуровневой сущности, как обобщенные функторы.

Варианты (b) не имеют вышеуказанных недостатков, хотя выглядят несколько менее изящно. Но можно бороться за изящество, например, путем создания функций создания функторов. С их помощью можно привести клиентский код к следующему аккуратному синтаксису:

FunSet fs;

fs += MakeFunctor(f2);

fs += MakeFunctor(A::f2, &a);

fs += MakeFunctor(B::f2, &b);

Для реализации функций MakeFunctorнужно преобразование между типом функции и типом возвращаемого ею значения и списком типов, содержащим типы всех ее аргументов, которые можно определить с помощью языка общих черт:

template <typename F> struct FunTraits;

//... частичные специализации для разных количеств

// аргументов типов функции ...

template <typename R, typename P1, P2>

struct FunTraits<R (*)(P1, P2)>

{

typedef NullType ObjType;

typedef R ResultType;

typedef P1 Parm1;

typedef P2 Parm2;

typedef TYPELIST_2(P1, P2) TypeListType;

};

//... специализации для типов с модификаторами __cdecl,

// __stdcallи т.д. можно разместить здесь ...

template <class O, typename R, P1, P2>

struct FunTraits<R (O::*)(P1, P2)>

{

typedef O ObjType;

typedef R ResultType;

typedef P1 Parm1;

typedef P2 Parm2;

typedef TYPELIST_2(P1, P2) TypeListType;

};

//... специализациидлявсех комбинаций

// cv-уточненных типов должны быть здесь ...

Теперь очень просто реализовать вспомогательные функции создания функтора:

template <typename F> inline 

Functor<typename FunTraits<F>::ResultType,

typename FunTraits<F>::TypeListType> MakeFunctor(F fun)

{

return Functor<typename FunTraits<F>::ResultType,

typename FunTraits<F>::TypeListType>(fun);

}

template <typename MF, class P> inline

Functor<typename FunTraits<MF>::ResultType,

typename FunTraits<MF>::TypeListType>

MakeFunctor(MF memfun, P const& pobj)

{

return Functor<typename FunTraits<MF>::ResultType,

typename FunTraits<MF>::TypeListType>(pobj, memfun);

}

Перейдем к рассмотрению требования R1. Можно легко заметить, что шаблон класса обобщенного функтора параметризован типами, абсолютно не связанными с типами объектов, передаваемыми их функторам. Отсюда следует, что эти функторы должны быть определены как шаблоны членов:

template <class R, class TList> 

class Functor

{

public:

// функтор для функций-нечленов и произвольные функторы

template <typename F> Functor(F const& fun) { ... }

// функтор для функций-членов

template <typename P, typename MF> Functor(P const& pobj,

MF memfn)

{ ... }

...

};

Только функторы знают тип вызываемой сущности, и он теряются после завершения работы функторов. Но некоторые операции все еще требуют сведения о типе вызываемой сущности, например, операции копирования, присваивания и уничтожения функтора. Оператор operator() также должен перенаправлять вызов базовому экземпляру вызываемой сущности в соответствии с его реальным типом. Поэтому шаблонные функторы должны хранить информацию о типе вызываемой сущности в некоторой "универсальной форме", позволяющей обращаться с ними позже некоторым самоизменяющимся способом.

Самое простое решение следующее:

template <class R, class TList> 

class Functor

{

struct FunImplBase

{

virtual R call_(...params evaluated from TList...) = 0;

...

};

template <typename F>

class FunctorImpl : public FunImplBase

{

F fun_;

public:

FunctorImpl(F const& fun) : fun_(fun) {}

virtual R call_(...params evaluated from TList...)

{ ... use params to make a call to fun_ ... }

...

};

template <typename P, typename MF>

class MemberFnImpl : public FunImplBase

{

P pobj_;

MF memfun_;

public:

MemberFnImpl(P const& pobj, MF memfun) : pobj_(pobj),

memfun_(fun) {}

virtual R call_(...params evaluated from TList...)

{ ... use params to make a call to memfun_ of pobj_ ... }

...

};

FunImplBase *pimpl_;

public:

// функтор для функций-нечленов и произвольных функторов

template <typename F> Functor(F const& fun)

{

pimpl_ = new FunctorImpl<F>(fun);

}

// функтор дляфункций-членов

template <typename P, typename MF> Functor(P const& pobj,

MF memfn)

{

pimpl_ = new MemberFnImpl<P, MF>(pobj, memfn);

}

...

R operator(...params evaluated from TList...)

{

return pimpl_->call_(... params ...);

}

...

};

В примере выше абстрактный базовый класс FunImplBaseопределяет все операции в зависимости от разных типов вызываемой сущности. FunctorImplи MemberFnImpl– ее конкретные потомки, реализующие данные операции для функций-нечленов вместе с произвольными функторами и функциями-членами, соответственно. Шаблон обобщенного функтора сам включает в себя указатель на FunImplBase, инициализирует его соответствующими функторами и использует его там, где он нужен. Нужно отметить, что пример выше в принципе похож на шаблон функтора Локи.

Теперь рассмотрим вопросы R2 и D2. Используя списки типов, можно объединить любое число разных типов в один тип, что полезно для многих универсальных алгоритмов. Но само произвольное число типов должно быть зафиксировано в конструкции списков типов (и обычно выбирается достаточно большим, подходящим для всех применений). Похожая проблема - C++ не имеет средства управления подсчетом параметров функции, поэтому нельзя обращаться с ними общим способом. В нашем случае наличие нескольких типов TypeList<T1,T2,T3,...Tn> произвольной длины помогло бы создать соответствующую функцию, например, operator()(T1,T2,T3,...Tn). Это могло бы полностью решить проблему типизированного вызова функции. Но, как было сказано, на C++ такое нельзя сделать, поэтому нужно найти обходные пути. Естьдвапути. Первый путь – можно объявить шаблон класса Functor и затем определить частичные специализации для всех возможных количеств типов в операторе operator():

template <class R, class TList> class Functor;

template <class R> class Functor<R, TYPELIST_0(P1)> { ... };

template <class R, class P1> class Functor<R, TYPELIST_1(P1)>

{ ... };

template <class R, class P1, class P2>

class Functor<R, TYPELIST_2(P1, P2)> { ... };

...

Но в данном случае каждая специализация также содержит весь код, независимо от количества аргументов оператора operator(). Можно попытаться некоторым образом факторизовать данный код в базовые классы (как делает ускорение). Однакорезультатнекажетсяхорошим.

Второй способ – определить единственный внешний шаблон функтора и перегрузить все возможные операторы operator():

template <class R, class TList> class Functor 

{

...

operator()()

operator()(T1)

operator()(T1,T2)

...

operator()(T1,T2,...Tn)

...

operator()(T1,T2,T3,...Tmax)

};

Это решает проблему, но вводит некоторые вероятные ошибки. Если попытаться использовать получившийся шаблон обобщенного функтора, как в первых листингах кода, и убрать комментарий из закомментированной строки 5, компилятор весело скомпилирует их, обеспечив фатальный сбой времени выполнения! Решение – убрать объявления FunImplBase, FunctorImpl и MemberFnImpl из шаблона Functor и определить специализации для всех возможных количеств типов в функциях call_. СмотритепримердляFunImplBase:

template <class R, class TList> struct FunImplBase;

... частичные специализации для разных количеств аргументов ...

template <class R, typename P1, P2>

struct FunImplBase<R, TYPELIST_2(P1, P2)>

{

virtual R call_(P1 p1, P2 p2) = 0;

...

};

Здесь есть несколько специализаций, но каждая в отдельности содержит только одну подходящую функцию call_. Поэтому код для строки 5 в первом листинге кода теперь не компилируется. Хотя компилятор может найти подходящий оператор operator() в шаблоне Functor, он не находит подходящую функцию call_ в соответствующей специализации FunImplBase. Мы вернулись к необходимости частичных специализаций – не для самого шаблона Functor, а для некоторых вспомогательных классов. Этоплохиеновости. Хорошие и более важные новости в том, что специализации содержат минимальный объем лишнего кода (независимо от количества аргументов функции call_). Реализация Локи следует данному пути и достигает очень хорошего разложения кода на элементарные операции.

Мы рассмотрели, как требования обобщенных функторов и проблемы деталей реализации (R1, R2, D1 и D2) могут быть решены, и как они решены в существующих библиотеках. Проблемы требования R3 не затрагивались, так как они не вносят никаких новых идей и довольно просты в реализации.