-
Notifications
You must be signed in to change notification settings - Fork 82
Session: Functional programming with C
Something you might know from variadic macros. Let us use define classes with zero or more template parameters or functions with zero or more arguments.
- http://en.cppreference.com/w/cpp/language/parameter_pack
- https://www.youtube.com/watch?v=VXi0AOQ0PF0&list=PLs3KjaCtOwSZ2tbuV1hx8Xz-rFZTan2J1&index=4
- http://eli.thegreenplace.net/2014/variadic-templates-in-c/
So let's start with implementing a generic zip iterator, which allows us to zip multiple iterators into one and to simultaneously iterate over a set of containers in one iteration loop.
Template code (click to expand)
#include <iostream>
#include <vector>
#include <string>
#include <tuple>
using namespace std;
template <typename first_type, typename ...remaining_type>
class zip_iterator
{
public:
zip_iterator() = delete;
zip_iterator(first_type && first, remaining_type &&... remaining) : _data(std::make_tuple(first, remaining...))
{}
std::tuple< first_type, remaining_types...> _data;
};
int main()
{
vector<int> v{0,1,2,3,4,5};
string s{'a','b','c','d','e','f'};
zip_iterator<vector<int>::iterator, string::iterator> zipper{v.begin(), s.end()};
return 0;
}In this code example we defined a class zip_iterator, which can take 1 ore more iterator types. The ... notation denotes the parameter pack. The STL already gives us a data structure, which can hold 0 or more elements of different types, the tuple class. However, the creation of the zipper is quite tedious, as we have to specify all template arguments, this zipper should be apply for. So we implement a utility function, called zip similar to make_tuple, to not worry about the types that are stored in the zipper.
Template code (click to expand)
...
template <typename first_type, typename ...remaining_types>
inline auto
zip(first_type && first, remaining_types && ...remaining)
{
return zip_iterator<first_type, remaining_types...>{first, std::forward<remaining_types>(remaining)...};
}
int main()
{
vector<int> v{0,1,2,3,4,5};
string s{'a','b','c','d','e','f'};
auto zipper = zip(v.begin(), s.end());
return 0;
}Ok, now we have a generic zipper that can hold one or more iterators. Now let's start implementing the iteration. We will start with the ++operator.
Template code (click to expand)
...
namespace impl
{
template <typename tuple_type, size_t ...index>
inline void
increment(tuple_type & data,
std::index_sequence<Is...> const & /*idx*/)
{
(void) std::initializer_list<int>{(++std::get<Is>(tuple), 0)...};
}
}
template <typename ...iter_types>
inline zip_iterator<iter_types...>&
operator++(zip_iterator<iter_types...> & me /*pre-increment*/)
{
impl::increment(me._data, std::make_index_sequence<sizeof...(iter_types)>());
return me;
}
...
int main()
{
vector<int> v{0,1,2,3,4,5};
string s{'a','b','c','d','e','f'};
auto zipper = zip(v.begin(), s.end());
return 0;
}When we call ++ we somehow need to access all the elements in the tuple and increment the contained iterator.
We could loop over the tuple, but there is a more efficient way to do it utilising pack expansion.
With [std::make_index_sequence<SIZE>()](http://en.cppreference.com/w/cpp/utility/integer_sequence), we can get all the indices that are available for the tuple using the sizeof...() operator.
We than can expand all elements of the tuple via: std::get<index>(tuple)....
Now we also want to apply a function to all expanded elements. This can be achieved in C++14 with the initializer_list trick. Here we kind of create an initialiser list of integers and create it with an comma-separated expression. C++ will evaluate all expressions and return the last one. This means in our example, that c++ first calls ++ on the iterator at the corresponding expanded index of the tuple and then returns 0, to fill the initialiser list. Thus we can apply a function to all elements in the tuple with expansion semantics.
- http://en.cppreference.com/w/cpp/language/lambda
- http://www.cprogramming.com/c++11/c++11-lambda-closures.html
Now we are going to implement multiple operators on the zip iterator. Since we want to reuse the initialiser trick, we will write a utility function called for_each, which takes an arbitrary function and invokes it on each element in the tuple. We then can rewrite ++operator to also submit a lambda function which implements the ++operation on the expanded tuple elements.
In the same fashion we can now implement the --operator.
Template code (click to expand)
...
namespace impl
{
template <typename tuple_type,
typename func_type,
size_t ...Is>
inline void
for_each(tuple_type && tuple,
func_type && func,
std::index_sequence<Is...> const &/*idx*/)
{
(void) std::initializer_list<int>{(func(std::get<Is>(tuple)), 0)...};
}
}
template <typename tuple_type,
typename func_type>
inline void
for_each(tuple_type && tuple,
func_type && callable)
{
constexpr auto N = tuple_size<typename std::decay<tuple_type>::type>::value;
impl::for_each(forward<tuple_type>(tuple), forward<func_type>(callable), make_index_sequence<N>());
}
template <typename ...iter_types>
inline zip_iterator<iter_types...>&
operator++(zip_iterator<iter_types...> & me /*pre-increment*/)
{
for_each(me._data, [](auto & it){ ++it; });
return me;
}
template <typename ...iter_types>
inline zip_iterator<iter_types...>&
operator--(zip_iterator<iter_types...> & me /*pre-decrement*/)
{
for_each(me._data, [](auto & it){ --it; });
return me;
}
...
int main()
{
vector<int> v{0,1,2,3,4,5};
string s{'a','b','c','d','e','f'};
auto zipper = zip(v.begin(), s.end());
++zipper;
--zipper;
return 0;
}Implementing the comparison operators is fairly easy:
Template code (click to expand)
...
template <typename ...iter_types>
inline bool
operator==(zip_iterator<iter_types...> const & lhs,
zip_iterator<iter_types...> const & rhs)
{
return std::get<0>(lhs._data) == std::get<0>(rhs._data);
}
template <typename ...iter_types>
inline bool
operator!=(zip_iterator<iter_types...> const & lhs,
zip_iterator<iter_types...> const & rhs)
{
return !(lhs == rhs);
}
...
int main()
{
vector<int> v{0,1,2,3,4,5};
string s{'a','b','c','d','e','f'};
auto zipper = zip(v.begin(), s.begin());
auto zipperEnd = zip(v.end(), s.end());
for (; zipper != zipperEnd; ++zipper)
{
// print the values
}
return 0;
}The last trick is to print the elements, for which we need to implement the *operator.
Therefor, we write a second helper function which we call apply. This function invokes a callable and passes all elements of the tuple as a parameter.
Template code (click to expand)
namespace impl
{
template <typename tuple_type, typename func_type,
size_t ...index>
inline auto
apply(tuple_type & tuple,
func_type && func,
std::index_sequence<index...> const &/*idx*/)
{
return func(std::get<index>(tuple)...);
}
}
template <typename ...types, typename func_type>
inline auto
apply(std::tuple<types...> & tuple,
func_type && func)
{
return impl::apply(tuple, std::forward<func_type>(func), std::make_index_sequence<sizeof...(types)>());
}
...
template <typename ...iter_types>
inline auto
operator*(zip_iterator<iter_types...> & me)
{
return impl::apply(me._data, [](auto && ... iters){
return std::forward_as_tuple(*iters...);
});
}
...
int main()
{
vector<int> v{0,1,2,3,4,5};
string s{'a','b','c','d','e','f'};
auto zipper = zip(v.begin(), s.begin());
auto zipperEnd = zip(v.end(), s.end());
for (; zipper != zipperEnd; ++zipper)
{
impl::apply_each(*zipper, [](auto const & val) { std::cout << val << ", "; });
std::cout << "\n";
}
return 0;
}Many things are added to C++ or the STL with the upcoming C++17 release, which makes the helper functions apply and apply_each obsolete. Here are some links for reading. You can try to replace the initialiser_list trick with a fold expression.
Here is the complete code with C++17 features. Note that we replaced our apply function with the one from the STL and that we used fold expressions to get rid of the initialiser list trick.
Template code (click to expand)
```cpp #include #include #include #include
using namespace std;
template <typename ...TIters> class Zip_iterator { public: Zip_iterator() = delete;
Zip_iterator(TIters &&... iterators) : _data(std::make_tuple(iterators...)) {}
std::tuple<TIters...> _data; };
namespace impl { template <typename tuple_type, typename func_type, size_t ...Is> inline void for_each(tuple_type && tuple, func_type && func, std::index_sequence<Is...> const &/idx/) { (func(std::get(tuple)), ...); }
} // namespace impl
template <typename tuple_type, typename func_type> inline void for_each(tuple_type && tuple, func_type && callable) { constexpr auto N = tuple_size<typename std::decay<tuple_type>::type>::value; impl::for_each(forward<tuple_type>(tuple), forward<func_type>(callable), make_index_sequence()); }
template <typename ...iter_types> inline Zip_iterator<iter_types...>& operator++(Zip_iterator<iter_types...> & me /pre-increment/) { for_each(me._data, [](auto & iter){++iter;}); return me; }
template <typename ...iter_types> inline Zip_iterator<iter_types...>& operator--(Zip_iterator<iter_types...> & me /pre-increment/) { for_each(me._data, [](auto & iter){--iter;}); return me; }
template <typename ...iter_types> inline auto operator*(Zip_iterator<iter_types...> & me) { return std::apply([](auto && ... iters){ return std::forward_as_tuple(*iters...); }, me._data); }
template <typename ...iter_types> inline bool operator==(Zip_iterator<iter_types...> const & lhs, Zip_iterator<iter_types...> const & rhs) { return std::get<0>(lhs._data) == std::get<0>(rhs._data); }
template <typename ...iter_types> inline bool operator!=(Zip_iterator<iter_types...> const & lhs, Zip_iterator<iter_types...> const & rhs) { return !(lhs == rhs); }
template <typename ...TIters> inline auto zip_iterator(TIters && ...iters) { return Zip_iterator<TIters...>{std::forward(iters)...}; }
int main() { vector v{0,1,2,3,4,5}; string s{'a','b','c','d','e','f'};
auto zip = zip_iterator(std::begin(v), std::begin(s));
auto zip_end = zip_iterator(std::end(v), std::end(s));
for (; zip != zip_end; ++zip)
{
for_each(*zip, [](auto const & val) { std::cout << val << ", "; });
std::cout << "\n";
}
return 0;
}
</p></detail>