Introduction to the magic of patterns

Patterns in C ++ are metaprogramming tools and implement a compile-time polymorphism. What it is?
This is when we write code with polymorphic behavior, but the behavior itself is determined at the compilation stage - that is, in contrast to the polymorphism of virtual functions, the resulting binary code will already have constant behavior.

What for?

We use templates for beauty. Every C ++ developer knows what beauty is, beauty is when the code is compact , clear and fast .

Meta-magic and implicit interfaces

What is a program? A metoprogram is a program whose result will be another program. For C ++, the compiler deals with the execution of metaprograms, and the result is a binary file.


')
Templates are used for writing metaprograms.
What else is different polymorphism of templates from the polymorphism of virtual functions? If a class has an explicit interface that we defined in the class declaration, then later in the program objects of this type can be used in accordance with this very interface. But for templates, we use implicit interfaces, i.e. using a type object, we define an implicit type interface that the compiler will display when building a metaprogram.

First spells: magic club

Let us make our template specific and see what types we have obtained for various template parameters:

typedef char CHAR; int main() { B<int> b; B<char> c; B<unsigned char> uc; B<signed char> sc; B<CHAR> C; B<char, 1> c1; B<char, 2-1> c21; cout << "b=" << typeid(b).name() << endl; cout << "c=" << typeid(c).name() << endl; cout << "C=" << typeid(C).name() << endl; cout << "sc=" << typeid(sc).name() << endl; cout << "uc=" << typeid(uc).name() << endl; cout << "c1=" << typeid(c1).name() << endl; cout << "c21=" << typeid(c21).name() << endl; return 0; } 

The output of the program shows that the types of template instantiations are different even for equivalent types - unsigned char & char. However, they are identical for char & CHAR, since typedef does not create a type, but only gives it a different name. They are identical for expressions 1 and 2-1, since the compiler evaluates expressions and instead of 2-1 uses 1.

From this it follows that we cannot use separate compilation for templates without additional problems:



In general, the C ++ standard has the export keyword for this, but this feature is too hard to implement and is missing in most compilers. There are compilers that support it, but I do not advise it to be used in portable code.

In addition to classes, there are also function templates:

 template<typename T> T func(T t, T d) { cout << "func" << endl; }; int main() { func('1', 2); } 

If the compiler can deduce the type of the parameter of the template from the type of the parameters - it will do so, and we do not need to specify it in the code. If not, we can define an enable function:

  inline int func(char c, int i) { return func<int>(c, i); }; 

It does not incur any overhead.

Specialization is a new level.

Usually using patterns we want to write a universal code, but in some cases we may lose in performance. To solve the problem, there is a special spell - template specialization. Specialization is a redefinition of a template with a specific type or type class :

 #include <iostream> using namespace std; template<typename T> T func(T t) { cout << "func" << endl; }; template<typename T> T * func(T *t) { cout << "func with pointer!" << endl; }; int main() { func(2); int i = 2; func(&i); } 

The compiler will choose the most appropriate specialization, in the example it is the type class “pointer to type”.

Sinister Magic: Recursion

The specializations and the fact that we can use templates in templates will give one very interesting opportunity - recursion of compile time.



The simplest and most popular example is the calculation of a series or a polynomial, say, the sum of a series of natural numbers:

 #include <iostream> using namespace std; template <int i> int func() { return func<i-1>()+i; }; template <> int func<0>() { return 0; }; int main () { cout << func<12>() << endl; return 0; }; 

We look ... It works! Cool? Increase the number of iterations to 500:

 cout << func<500>() << endl; 

Now compilation takes more time, while the program execution time is constant! Miracles!

Do not make a goat if you wanted a thunderstorm

There are a couple of moments.



The default recursion depth is limited by default to the implementation, for the new gcc it is 900, for older versions it is less. Parameter

 $ g++ recursion.cpp -ftemplate-depth=666666666 

removes this restriction.

The second pitfall - do not wait for error reports. Change the amount by factorial:

 int func() { return func<i-1>() * i; }; template <> int func<0>() { return 1; }; ... cout << func<500>() << endl; 

We get an incorrect result, and no warning.

The third point is obvious: we can create too many almost identical template instantiations and, instead of a performance boost, get a gain of a binary code .

Powerful spells of the ancients

Is it possible to combine the magic of inheritance with patterned magic?



The ancients used for this spell CRTP . The idea is simple: apply non-virtual inheritance and provide polymorphic behavior by explicitly casting the heir type to the parent type. Let's look at an example of use :

 template<typename Filtrator> class FiltratorImpl { inline void find_message(...) { Filtrator* filtrator = static_cast<Filtrator* >(this); … filtrator->find_and_read_message(info, collection); } }; ... class CIFSFiltrator : public FiltratorImpl<CIFSFiltrator> { ... inline void find_and_read_message(PacketInfo& info) {...} ... }; class RPCFiltrator : public FiltratorImpl<RPCFiltrator> { ... inline void find_and_read_message(PacketInfo& info) {...} ... }; 

We get inherited inline methods with polymorphic behavior! Who will say that this is not cool - my enemy forever.

The ancients also advise adding something like this to the parent constructor:

 static_assert(std::is_member_function_pointer<decltype(&Filtrator::find_and_read_message)>::value) 

So that the demons, awakened by a powerful spell, could not harm the mage that caused them.



There are still many secret techniques, ancient and not so. I hope not to meet soon / * in hell * /, and may the power of the ancients be with you.