Work with heterogeneous containers with C ++ 17

Hi, Habr! Recently, a lot has been said about C ++ 17, especially with the advent of the national standardization working group in Russia. In the open spaces of the network, without any problems, you can find short examples of using the latest C ++ standard. Everything is good, but there is no really extensive transition to new standards. Therefore, we can observe a picture in which any library requiring a minimum of 14 standards is already considered modern after the fact.

In this publication, we will develop a small library (3 functions ( apply , filter , reduce ) and one as “homework” ( map :))) for convenient work with heterogeneous containers in runtime (heterogeneity due to std :: variant of 17 standard).

From the new, in addition to the new library types, let's taste the fold expressions and quite a bit of structured binding

Introduction

First, a small introduction to the topic of heterogeneous containers. As you know, there are no real heterogeneous containers working in runtime on c ++. We have std :: tuple at our disposal, the traces of which almost completely disappear in runtime (not pay for what you don't use) and ... well, everything. Everything else is just the building blocks for building your own library bikes .
')
The building blocks, allowing to make a heterogeneous container, two are std :: any and std :: variant . The first does not remember the type, so its use is very limited. std :: variant remembers the type and is able to match functors to the current type using std :: visit (implemented by generating a table of methods and subsequent transitions on it). The implementation is truly magical, and magic is the only thing that will help to do what is impossible at first glance :) (of course it is possible, because everything is possible with c ++). Inside the std :: variant contains not so much overhead, transferring the boost version to the standard, the developers took care of the performance (relative to what it was). Summarizing, we take std :: variant as a container of types and base unit of a heterogeneous container.

Disclaimer

I warn in advance about the maximum compactness of the code. It is not worthless to copy it without thinking, it was as much as possible lightweight for quick understanding. There are no namespaces, link forwarding and whatnot.

I also do not pretend to be unique, for sure there are similar good libraries :)

Start

For easier understanding and testing of functions let's take a simple example. To do this, we emulate the usual polymorphic structure:

struct Circle { void Print() { cout << "Circle. " << "Radius: " << radius << endl; } double Area() { return 3.14 * radius * radius; } double radius; }; struct Square { void Print() { cout << "Square. Side: " << side << endl; } double Area() { return side * side; } double side; }; struct EquilateralTriangle { void Print() { cout << "EquilateralTriangle. Side: " << side << endl; } double Area() { return (sqrt(3) / 4) * (side * side); } double side; }; using Shape = variant<Circle, Square, EquilateralTriangle>; 

Also for comparison we will keep in mind its simple polymorphic analogue:

 struct Shape { virtual void Print() = 0; virtual double Area() = 0; virtual ~Shape() {}; }; struct Circle : Shape { Circle(double val) : radius(val) {} void Print() override { cout << "Circle. " << "Radius: " << radius << endl; } double Area() override { return 3.14 * radius * radius; } double radius; }; struct Square : Shape { Square(double val) : side(val) {} void Print() override { cout << "Square. Side: " << side << endl; } double Area() override { return side * side; } double side; }; struct EquilateralTriangle : Shape { EquilateralTriangle(double val) : side(val) {} void Print() override { cout << "EquilateralTriangle. Side: " << side << endl; } double Area() override { return (sqrt(3) / 4) * (side * side); } double side; }; 

Let's create a vector and try using standard means to achieve polymorphic behavior. Let's iterate over the vector and call the Print function.

First, let's take a dynamic analog (on virtual functions). As you can think, we have no problems with dynamic polymorphism:

 vector<Shape*> shapes; shapes.emplace_back(new Square(8.2)); shapes.emplace_back(new Circle(3.1)); shapes.emplace_back(new Square(1.8)); shapes.emplace_back(new EquilateralTriangle(10.4)); shapes.emplace_back(new Circle(5.7)); shapes.emplace_back(new Square(2.9)); 

However, it does not look very modern. Bare new calls do not inspire confidence. Rewrite:

 vector<shared_ptr<Shape>> shapes; shapes.emplace_back(make_shared<Square>(8.2)); shapes.emplace_back(make_shared<Circle>(3.1)); shapes.emplace_back(make_shared<Square>(1.8)); shapes.emplace_back(make_shared<EquilateralTriangle>(10.4)); shapes.emplace_back(make_shared<Circle>(5.7)); shapes.emplace_back(make_shared<Square>(2.9)); 

Now it looks better. However, for a beginner, the clarity in the code clearly did not increase. But let's not breed holivar, let's fulfill our task:

 for (shared_ptr<Shape> shape: shapes) { shape->Print(); } // : // Square. Side: 8.2 // Circle. Radius: 3.1 // Square. Side: 1.8 // EquilateralTriangle. Side: 10.4 // Circle. Radius: 5.7 // Square. Side: 2.9 

We will also try to implement similar behavior for a heterogeneous container:

 vector<Shape> shapes; shapes.emplace_back(EquilateralTriangle { 5.6 }); shapes.emplace_back(Square { 8.2 }); shapes.emplace_back(Circle { 3.1 }); shapes.emplace_back(Square { 1.8 }); shapes.emplace_back(EquilateralTriangle { 10.4 }); shapes.emplace_back(Circle { 5.7 }); shapes.emplace_back(Square { 2.9 }); 

There are already no pointers. No problem, you can work with objects on the stack. Also, instead of a costructor, you can use aggregate initialization for as “simple” types.

However, just to iterate and call the function will not succeed. Let's try to do this with the tools provided by the std :: variant. For this we have the function std :: visit , we also need to create a class of functors.

Everything will look like this:

 struct Visitor { void operator()(Circle& c) { c.Print(); } void operator()(Square& c) { c.Print(); } void operator()(EquilateralTriangle& c) { c.Print(); } }; ... ... ... for (Shape& shape: shapes) { visit(Visitor{}, shape); } 

The conclusion is the same. You can also emulate the same behavior with constexpr if. Here is someone who likes more.

Acquainted with the functionality that the standard library provides us with, we will try to simplify a bit the work with heterogeneous sequences.

We implement the most frequent and comprehensive functions: apply , filter , reduce .

Step 1

To begin with, simplify your task. The first step is quite primitive - it has been described more than once.
Take the variadic templates, the inheritance mechanism, and the knowledge that lambda functions are deployed into ordinary structures - functors. We follow the set of freebies and create a function that will help us derive the template types:

 template < typename... Func > class Visitor : Func... { using Func::operator()...; } template < class... Func > make_visitor(Func...) -> Visitor < Func... >; 

Now, instead of creating classes with functors, we can use a set of lambdas that will match according to their signatures:

 for (Shape& shape: shapes) { visit(make_visitor( [](Circle& c) { c.Print(); }, [](Square& c) { c.Print(); }, [](EquilateralTriangle& c) { c.Print(); } ), shape); } 

We can also use type inference with a generic parameter:

 for (Shape& shape: shapes) { visit(make_visitor([](auto& c) { c.Print(); }), shape); } 

It turned out quite nice and fairly short.

Apply

It remains to put everything together and get the apply function for heterogeneous sequences:

 template < typename InputIter, typename InputSentinelIter, typename... Callable > void apply(InputIter beg, InputSentinelIter end, Callable... funcs) { for (auto _it = beg; _it != end; ++_it) visit(make_visitor(funcs...), *_it); }; 

Is done. The shown technique does not pretend to be new, any developer who somehow worked with boost :: variant has long implemented something similar for itself http://en.cppreference.com/w/cpp/utility/variant/visit , https: // habrahabr .ru / post / 270689 / ).

Now we can use the function like this:

 apply(shapes.begin(), shapes.end(), [](auto& shape) { shape.Print(); }); 

or

 apply(shapes.begin(), shapes.end(), [] (Circle& shape) { shape.Print(); }, [] (Square& shape) { shape.Print(); }, [] (EquilateralTriangle& shape) { shape.Print(); }); 

As you can see, it turned out pretty nepokho. However, if we pass the functors not for all types that are in the std :: variant , we get a compilation error. To avoid this, in the likeness of SFINAE, we make a functor with elipsis, which will be called in the absence of any other alternative, and in the order of the call it will be the most recent version.

 template < typename InputIter, typename InputSentinelIter, typename... Callable > void apply(InputIter beg, InputSentinelIter end, Callable... funcs) { for (auto _it = beg; _it != end; ++_it) visit(make_visitor(funcs..., [](...){}), *_it); }; 

Now we can pass the functors not for all types, for the absent, the empty lambda will be called:

 //      Circle apply(shapes.begin(), shapes.end(), [] (Circle& shape) { shape.Print(); }); 

For a good example, just show you how to do this using dynamic polymorphism:

 //      Circle for_each(shapes.begin(), shapes.end(), [] (shared_ptr<Shape> shape) { if (dynamic_pointer_cast<Circle>(shape)) shape->Print(); }); 

Far from the most pleasant view.

Filter

By analogy, we will make the filter function. Sense loading practically does not differ except that the lambda, having elipsis in the signature has to return value like bool. We assume that if we have not passed a functor processing some particular type, then we do not want to see its instances in the filtered container.

 template < typename InputIter, typename InputSentinelIter, typename OutputIter, typename... Callable > void filter(InputIter beg, InputSentinelIter end, OutputIter out, Callable... funcs) { for (auto _it = beg; _it != end; ++_it) { if (visit(make_visitor(funcs..., [] (...) { return false; }), *_it)) *out++ = *_it; } }; 

You can use the implemented function as follows:

 vector<Shape> filtered; filter(shapes.begin(), shapes.end(), back_inserter(filtered), [] (Circle& c) { return c.radius > 4.; }, [] (Square& s) { return s.side < 5.; }); apply(filtered.begin(), filtered.end(), [](auto& shape) { shape.Print(); }); // : // Square. Side: 1.8 // Circle. Radius: 5.7 // Square. Side: 2.9 

Analogue implemented using dynamic polymorphism:

 vector<shared_ptr<Shape>> filtered; copy_if(shapes.begin(), shapes.end(), back_inserter(filtered), [] (shared_ptr<Shape> shape) { if (auto circle = dynamic_pointer_cast<Circle>(shape)) { return circle->radius > 4.; } else if (auto square = dynamic_pointer_cast<Square>(shape)) { return square->side < 5.; } else return false; }); for_each(filtered.begin(), filtered.end(), [](shared_ptr<Shape> shape) { shape->Print(); }); // : // Square. Side: 1.8 // Circle. Radius: 5.7 // Square. Side: 2.9 

Reduce

It remains to implement reduce (analog std :: accumulate ) and map (analog std :: transform ). The implementation of these functions is somewhat more complicated than it was with the apply and filter . To reduce, we use functors with two parameters (the value of the battery and the object itself). In order to implement a similar behavior, you can partially apply the lambda functions in such a way that the functions of one argument remain for the std :: variant . There is no beautiful solution for c ++ for partial application, a quick way is to capture the necessary context with the help of another lambda. Considering that we are working not with one lambda, but with the variadic pack , the code swells up and starts to be poorly readable. Processing of variadics using fold expressions saves us. Veterans know what crutches they used to fold lists of types earlier.

 template < typename InputIter, typename InputSentinelIter, typename AccType, typename... Callable > struct reduce < InputIter, InputSentinelIter, AccType, false, Callable... > { constexpr auto operator()(InputIter beg, InputSentinelIter end, AccType initial_acc, Callable... funcs) { for (auto _it = beg; _it != end; ++_it) { initial_acc = visit(utility::make_overloaded_from_tup( tup_funcs(initial_acc, funcs...), make_index_sequence<sizeof...(Callable)>{}, [&initial_acc] (...) { return initial_acc; } ), *_it); } return initial_acc; } }; 

In order to do something similar, it was decided to use the good old tuple ( std :: tuple ). Processing its elements is not too complicated, at any time you can write your own. And so, I create a lambda tuple, which is transformed into a new tuple by wrapping each lambda into another with the capture of the value of the battery. Benefit transformation of the tuple, using the new standard, is written relatively easily:

 template < typename... Types, typename Func, size_t... I > constexpr auto tuple_transform_impl(tuple<Types...> t, Func func, index_sequence<I...>) { return make_tuple(func(get<I>(t)...)); } template < typename... Types, typename Func > constexpr auto tuple_transform(tuple<Types...> t, Func f) { return tuple_transform_impl(t, f make_index_sequence<sizeof...(Types)>{}); } 

In order to create a comprehensive lyabda, I need to know the type of the second argument of the incoming lambda. With the help of helper'ov, found on the Internet, you can skip lambda to the structure, having a call operator and by the match to get the desired type.

It looks like this:

 template < typename Func, typename Ret, typename _, typename A, typename... Rest > A _sec_arg_hlpr(Ret (Func::*)(_, A, Rest...)); template < typename Func > using second_argument = decltype(_sec_arg_hlpr(&Func::operator())); template < typename AccType, typename... Callable > constexpr auto tup_funcs(AccType initial_acc, Callable... funcs) { return tuple_transform(tuple<Callable...>{ funcs... }, [&initial_acc](auto func) { return [&initial_acc, &func] (second_argument<decltype(func)> arg) { return func(initial_acc, arg); }; }); } 

Everything is good, but these wonders do not work with generic functions, the types of input arguments of which we cannot get by definition. Therefore, using tag dispatching and creating a simple treit to test the function, we create our own implementation for this case.
Summarizing, we obtain for reduce the following possibilities for use:

 using ShapeCountT = tuple<size_t, size_t, size_t>; auto result = reduce(shapes.begin(), shapes.end(), ShapeCountT{}, [] (ShapeCountT acc, Circle& item) { auto [cir, sq, tr] = acc; return make_tuple(++cir, sq, tr); }, [] (ShapeCountT acc, Square& item) { auto [cir, sq, tr] = acc; return make_tuple(cir, ++sq, tr); }, [] (ShapeCountT acc, EquilateralTriangle& item) { auto [cir, sq, tr] = acc; return make_tuple(cir, sq, ++tr); }); auto [cir, sq, tr] = result; cout << "Circle count: " << cir << "\tSquare count: " << sq << "\tTriangle count: " << tr << endl; // : // Circle count: 2 Square count: 3 Triangle count: 2 

The map function is implemented on the basis of similar ideas, omitting the description of its implementation and the implementation itself. To train your meta skills, I propose to implement it yourself :)

What's next?

A bit of error. Take a step aside and see a similar message:


The text of this error cannot be disassembled, even if you use a very simple code (the error lies in the incorrect use of the generic parameter of the functor). Imagine what happens if you use the classes much more difficult than the ones presented.

There are several approaches, how you can elegantly or not really say about the true nature of the error.
Next time we dilute what is written with Concepts TS from gcc-7.1.

Summarizing, we can say that such an approach can be very useful for working with libraries that have had to use TypeErasure techniques, for template classes with different specializations, for primitive emulation of polymorphism, ...

How would you add / use this functionality? Write in the comments, it will be interesting to read

The above code is available here .