Simple Stream implementation from Java 8 to C ++

Hello! The article will present a simplified implementation of Stream from Java 8 in C ++. I will say right away that:

Unlike Java, deferred calculations are not used.
no parallel versions;
sometimes combines Stream and Collectors ;
simple and ready-made solutions from STL are used, there is no pure OP, where only recursion is present;
optimization techniques are not used.

In this version, the main focus is on making a bicycle quickly and simply). About FP is mentioned to a minimum (attention is not paid to combinators :)).

Interface

 template <typename Type> class Stream : private StreamImpl<Type> { private: typedef StreamImpl<Type> Parent; public: using Parent::Parent; //   using Parent::data; using Parent::isEmpty; using Parent::count; using Parent::flatMap; using Parent::map; using Parent::reduce; using Parent::filter; using Parent::allMatch; using Parent::noneMatch; using Parent::groupingBy; using Parent::partitionBy; using Parent::minElement; using Parent::maxElement; ~Stream() = default; };

Here you can add simple static type checks:

  static_assert( std::is_copy_assignable<Type>::value, "Type is not copy assignable"); static_assert( std::is_default_constructible<Type>::value, "Type is not default constructible"); static_assert( std::is_copy_constructible<Type>::value, "Type is not"); static_assert(!std::is_volatile<Type>::value, "volatile data can't be used in Stream"); static_assert(!std::is_same<Type, std::nullptr_t>::value, "Stream can't used with nullptr");

Actually, it remains to consider what StreamImpl .

Streamreaml

Stream works with containers or container-like types (such as QString , QByteArray , etc.). Containers in turn may consist of containers. The container with non-container data will be terminal for functions of type flatMap

Define StreamImpl :

 template <typename ContainerType, bool isContainer = Private::is_nested_stl_compatible_container<ContainerType>::value> class StreamImpl;

Where is_nested_stl_compatible_container is an auxiliary is_nested_stl_compatible_container - is_nested_stl_compatible_container for defining the container's “container” (SFINAE helps with this):

 namespace Private { template <typename ContainerType> class is_iterator { DECLARE_SFINAE_TESTER(Unref, T, t, *t) DECLARE_SFINAE_TESTER(Incr, T, t, ++t) DECLARE_SFINAE_TESTER(Decr, T, t, --t) public: typedef ContainerType Type; static const bool value = GET_SFINAE_RESULT(Unref, Type) && (GET_SFINAE_RESULT(Incr, Type) || GET_SFINAE_RESULT(Decr, Type)); }; template <typename ContainerType> class is_stl_compatible_container { DECLARE_SFINAE_TESTER(Begin, T, t, std::cbegin(t)) DECLARE_SFINAE_TESTER(End, T, t, std::cend(t)) DECLARE_SFINAE_TESTER(ValueType, T, t, sizeof(typename T::value_type)) public: typedef ContainerType Type; static const bool value = GET_SFINAE_RESULT(Begin, Type) && GET_SFINAE_RESULT(End, Type) && GET_SFINAE_RESULT(ValueType, Type); }; template <typename ContainerType> struct is_nested_stl_compatible_container { DECLARE_SFINAE_TESTER(ValueType, T, t, sizeof(typename T::value_type::value_type)) typedef ContainerType Type; static const bool value = is_stl_compatible_container<Type>::value && GET_SFINAE_RESULT(ValueType, Type); }; }

Consider the organization of the SFINAE tester:

 #define DECLARE_SFINAE_BASE(Name, ArgType, arg, testexpr) \ typedef char SuccessType; \ typedef struct { SuccessType a[2]; } FailureType; \ template <typename ArgType> \ static decltype(auto) test(ArgType &&arg) \ -> decltype(testexpr, SuccessType()); \ static FailureType test(...); #define DECLARE_SFINAE_TESTER(Name, ArgType, arg, testexpr) \ struct Name { \ DECLARE_SFINAE_BASE(Name, ArgType, arg, testexpr) \ }; #define GET_SFINAE_RESULT(Name, Type) (sizeof(Name::test(std::declval<Type>())) == \ sizeof(typename Name::SuccessType))

The SFINAE tester uses SFINAE by type and SFINAE by expression.

Suppose that the SFINAE tester has determined that we have a container with container data.

Container with container data

StreamImpl for a container with container data simply inherits from StreamBase - an interface with basic functionality that will be discussed later.

Container data container interface

 template <typename Tp> class StreamImpl<Tp, true> : private StreamBase<Tp> { public: typedef StreamBase<Tp> Parent; typedef Tp ContainerType; using Parent::Parent; using Parent::data; using Parent::flatMap; using Parent::isEmpty; using Parent::count; using Parent::map; using Parent::reduce; using Parent::filter; using Parent::allMatch; using Parent::noneMatch; using Parent::groupingBy; using Parent::partitionBy; using Parent::minElement; using Parent::maxElement; };

Container with non-container data

StreamImpl for a container with non-container data is intended for working with data of type QVector<int> , as well as for pseudo-containers of type QString , but for working with std::initalizer :

 template <typename Tp> class StreamImpl<Tp, false> : private StreamBase<typename Private::select_type<Tp>::type> { public: typedef StreamBase<typename Private::select_type<Tp>::type> Parent; typedef typename Private::select_type<Tp>::type ContainerType; using Parent::Parent; using Parent::data; using Parent::isEmpty; using Parent::count; using Parent::map; using Parent::reduce; using Parent::filter; using Parent::allMatch; using Parent::noneMatch; using Parent::groupingBy; using Parent::partitionBy; using Parent::minElement; using Parent::maxElement; //    flatMap, . StreamBase::flatMap() auto flatMap() const { return Stream<Tp>(data()); } };

As you can see, the implementation is identical to StreamImpl<Tp, true> , except that flatMap terminal and the base class is inferred by the select_type<Tp>::type flatMap :

 template <typename Tp> struct type_to_container; namespace Private { template <typename Tp> struct select_type { using type = std::conditional_t< is_stl_compatible_container<Tp>::value, Tp, typename type_to_container<Tp>::type >; }; }

Which turns a non-container into a container using an open type_to_container , which is then passed to std::initalizer_list . For pseudo-container no "magic" is used. The default implementation of the type_to_container metafunction is as follows:

 template <typename Tp> struct type_to_container { using type = QVector<Tp>; };

Having considered the details, go to the base.

Streambase

Let's look at a simple basic interface. StreamBase works with containers whose elements can be containers.

For greater ease of implementation, StreamBase copies source data or moves it to itself.

Non-terminal functions return Stream . Calls to non-terminal functions can join chains and get something like monads in the OP.

 template <typename Container> class StreamBase { Container m_data; public: typedef typename Container::value_type value_type; ~StreamBase() = default; StreamBase(const StreamBase &other) = default; explicit StreamBase(StreamBase &&other) noexcept : m_data(std::move<Container>(other.m_data)) { } explicit StreamBase(const Container &data) : m_data(data) { } explicit StreamBase(Container &&data_) noexcept : m_data(std::move(data_)) { }

You can add a static check for the container:

  static_assert( std::is_copy_assignable<Container>::value, "..."); static_assert( std::is_default_constructible<Container>::value, "..."); static_assert( std::is_copy_constructible<Container>::value, "...");

Service functions are very simple:

  Container data() const { return m_data; } auto cbegin() const noexcept(noexcept(std::cbegin(m_data))) { return std::cbegin(m_data); } auto cend() const noexcept(noexcept(std::cend(m_data))) { return std::cend(m_data); } bool isEmpty() const noexcept(noexcept(cbegin() == cend())) { return cbegin() == cend(); } auto count() const noexcept(noexcept(m_data.size())) { return m_data.size(); }

Consider the implementation of the map . The essence of the operation is that an applicator function is applied to each element of the container, and the result is placed in another container. The applicator function can return values of another type. Actually, all the work is done in an auxiliary function, which returns a new container. This container will be transferred to Stream . The applicator can pass additional parameters.

  template<typename F, typename ...Params> auto map(F &&f, Params&& ...params) const { auto result = map_helper(data(), f, params...); using result_type = decltype(result); return Stream<result_type>(std::forward<result_type>(result)); }

The filter operation calls the predicate function for each element of the container element, and if true , the element is copied to another container.

  template<typename F, typename ...Params> Stream<Container> filter(F &&f, Params&& ...params) const { Container result; std::copy_if(cbegin(), cend(), std::back_inserter(result), std::bind(f, std::placeholders::_1, params...)); return Stream<decltype(result)>(std::forward<Container>(result)); }

The reduce operation (the convolution on the left is used here) is more interesting. reduce "collapses" the container into one value, moving from left to right, applying the operator function to the current element, as the first operand, and as the second - the initial initial value, with which the previous elements are collapsed:

  template<typename F, typename ...Params> value_type reduce(F &&f, const value_type &initial, Params&& ...params) { using namespace std::placeholders; return std::accumulate(cbegin(), cend(), initial, std::bind(f, _1, _2, params...)); }

If we have a container of containers with elements of type T, then as a result of using flatMap will be a container with elements of type T. In the return value, flatMap is called for each new Stream value displayed until it reaches the terminal version of flatMap .

  auto flatMap() const { value_type result; std::for_each(cbegin(), cend(), std::bind(append, std::ref(result), std::placeholders::_1)); return Stream<value_type>(std::forward<value_type>(result)).flatMap(); }

Finding the minimum and maximum without optional is of no interest:

Min / Max

  template<typename F, typename ...Params> value_type maxElement(F &&f, Params ...params) const { auto it = std::max_element(cbegin(), cend(), std::bind(f, std::placeholders::_1, params...)); return it != cend() ? *it : value_type(); } value_type maxElement() const { auto it = std::max_element(cbegin(), cend()); return it != cend() ? *it : value_type(); } template<typename F, typename ...Params> value_type minElement(F &&f, Params ...params) const { auto it = std::min_element(cbegin(), cend(), std::bind(f, std::placeholders::_1, params...)); return it != cend() ? *it : value_type(); } value_type minElement() const { auto it = std::min_element(cbegin(), cend()); return it != cend() ? *it : value_type(); }

The analog of distinct also very simple:

  template<typename F, typename ...Params> Stream<value_type> unique(F &&f, Params ...params) const { QList<value_type> result; std::unique_copy(cbegin(), cend(), std::back_inserter(result), std::bind(f, std::placeholders::_1, params...)); return Stream<value_type>(std::forward<value_type>(result)); }

If there is a search for all matching items:

  template<typename F, typename ...Params> Stream<value_type> allMatch(F &&f, Params ...params) const { return filter(f, params...); }

Just do a search for all inappropriate (through denial):

  template<typename F, typename ...Params> Stream<value_type> noneMatch(F &&f, Params ...params) const { return allMatch(std::bind(std::logical_not<>(), std::bind(f, std::placeholders::_1, params...)) ); }

Breaking up the elements: we take two lists - we put in one, what satisfies the predicate, and in the other, what doesn't, and then in the spirit of the original we put all this in QMap :

  template<typename F, typename ...Params> QMap<bool, QList<value_type>> partitionBy(F &&f, Params&& ...params) const { QList<value_type> out_true; QList<value_type> out_false; std::partition_copy(cbegin(), cend(), std::back_inserter(out_true), std::back_inserter(out_false), std::bind(f, std::placeholders::_1, params...)); QMap<bool, QList<value_type>> result { { true, out_true } , { false, out_false } }; return result; }

Clustering (splitting into groups): two functions of the clasterizator are clasterizator - for splitting into groups, and then a clasterizator function is performed (if specified) on each group element.

  template<typename F, typename ...Params> auto groupingBy(F &&f, Params&& ...params) const { return clasterize(m_data, f, params...); }

Difficulties only in the definition of types: invoke (which will be in C ++ 17) is used to determine the types returned by the clasterizator and finisher , until it is legalized using the implementation presented at the very end:

  template<typename Claserizer, typename Finisher> auto groupingBy(Claserizer &&clasterizator, Finisher &&finisher) const { using claster_type = decltype(Private::invoke(clasterizator, std::declval<value_type>())); QMap<claster_type, QList<value_type>> clasters = clasterize(data(), clasterizator); using item_type = decltype(Private::invoke( finisher, std::declval<typename decltype(clasters)::mapped_type>())); QMap<claster_type, item_type> result; for(auto it = clasters.cbegin(); it != clasters.cend(); ++it) result[it.key()] = finisher(it.value()); return result; } private: template<typename ContainerType, typename F, typename ...Params> static auto map_helper(const ContainerType &c, F &&f, Params&& ...params) { using ret_type = decltype(Private::invoke(f, std::declval<value_type>(), params...)); using result_type = typename make_templated_type<ContainerType, ret_type>::type; result_type result; std::transform(std::cbegin(c), std::cend(c), std::back_inserter(result), std::bind(f, std::placeholders::_1, params...)); return result; }

The cluster device looks awful, but does a simple job:

  template<typename ContainerType, typename F, typename ...Params> static auto clasterize(const ContainerType &c, F &&f, Params&& ...params) { using ret_type = decltype(Private::invoke(f, std::declval<value_type>(), params...)); QMap<ret_type, QList<value_type>> result; auto applier = std::bind(f, std::placeholders::_1, params...); auto action = [&result, &applier](const value_type &item) mutable { result[applier(item)].push_back(item); }; std::for_each(c.cbegin(), c.cend(), action); return result; } static value_type& append(value_type &result, const value_type &item) { std::copy(item.cbegin(), item.cend(), std::back_inserter(result)); return result; } };

std :: invoke

  template<typename _Functor, typename... _Args> inline typename enable_if< (!is_member_pointer<_Functor>::value && !is_function<_Functor>::value && !is_function<typename remove_pointer<_Functor>::type>::value), typename result_of<_Functor&(_Args&&...)>::type >::type invoke(_Functor& __f, _Args&&... __args) { return __f(std::forward<_Args>(__args)...); } template<typename _Functor, typename... _Args> inline typename enable_if< (is_member_pointer<_Functor>::value && !is_function<_Functor>::value && !is_function<typename remove_pointer<_Functor>::type>::value), typename result_of<_Functor(_Args&&...)>::type >::type invoke(_Functor& __f, _Args&&... __args) { return std::mem_fn(__f)(std::forward<_Args>(__args)...); } template<typename _Functor, typename... _Args> inline typename enable_if< (is_pointer<_Functor>::value && is_function<typename remove_pointer<_Functor>::type>::value), typename result_of<_Functor(_Args&&...)>::type >::type invoke(_Functor __f, _Args&&... __args) { return __f(std::forward<_Args>(__args)...); }

Total

Let's try to apply our works:

  { QStringList x = {"functional", "programming"}; Stream<QList<QStringList>> stream(QList<QStringList>{x}); qDebug() << stream.flatMap().data(); }

QList<QStringList> turns into a QString with the contents: "functionalprogramming".

Nothing happens to a simple container (here std::initalizer_list<int> will turn into QVector<int> )

  { Stream<int> is({1, 2, 3, 4}); qDebug() << is.flatMap().data(); }

But with the "difficult" happens QVector<QVector<int>> will turn into QVector<int> with the contents (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 , 14, 15, 16, 17, 18, 19, 100, 111, 112, 113, 114, 115, 116, 117, 118, 119):

  { QVector<QVector<int>> x = { {0,1,2,3,4,5,6,7,8,9}, {10,11,12,13,14,15,16,17,18,19}, {100,111,112,113,114,115,116,117,118,119}, }; Stream<decltype(x)> t(x); qDebug() << t.flatMap().data(); }

Check with lambda functions, functional objects and pointers to functions:

  Stream<int> t{{1, 20, 300, 4000, 50000}}; qDebug() << t.map(static_cast<QString(*)(int, int)>(&QString::number), 2) .filter(std::bind( std::logical_not<>(), std::bind(QString::isEmpty, std::placeholders::_1)) ) .map(&QString::length) .filter(std::greater<>(), 1) .filter(std::bind( std::logical_and<>(), std::bind(std::greater_equal<>(), std::placeholders::_1, 1), std::bind(std::less_equal<>(), std::placeholders::_1, 100) ) ) .reduce(std::multiplies<>(), 1);

Here, the list of ints turns into a list of strings representing ints in the binary number system, then the lengths of the strings are calculated, from which those that are greater than 1 are selected, and then using the functional composition created with std::bind , elements are selected in range [1, 100], and then these elements are multiplied.

Horror!

And finally, in the first part of the example, we divide the elements into digits / non-digits and independently group them by a significant byte ( QChar::cell ), and then, again, we independently group the elements x by a significant byte and count their number.

  { QStringList x = {"flat 0","Map 1","example"}; Stream<decltype(x)> t(x); Stream<QString> str(t.flatMap().data()); qDebug() << str.partitionBy(static_cast<bool(QChar::*)()const>(&QChar::isDigit)); qDebug() << str.groupingBy(&QChar::cell); auto count = [](const auto &x) { return x.size(); }; qDebug() << str.groupingBy(&QChar::cell, count); }

PS: sorry for such examples ... At night, nothing better was invented)

Source: https://habr.com/ru/post/322924/

All Articles