Java 8からC ++への単純なストリーム実装

みなさんこんにちは！ この記事では、Java 8からC ++へのStream



簡素化された実装を紹介します。 すぐに言います：

• Javaとは異なり、遅延計算は使用されません。
• 並列バージョンはありません。
• 場所では、 Stream
  
  
  
  とCollectors
  
  
  
  組み合わせます。
• STLのシンプルで既製のソリューションが使用されます。純粋なFPはなく、再帰のみが使用されます。
• 最適化手法は使用されません。

このバージョンでは、自転車をすばやく簡単に作成することに主な重点が置かれています）。 FPについては少なくとも言及されています（コンビネーターへの注意は支払われません:)）。

インターフェース

 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; };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここで、単純な静的型チェックを追加できます。

  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");
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

実際には、 StreamImpl



何であるかを検討するStreamImpl



ます。

StreamImpl

Stream



は、コンテナまたはコンテナに似たタイプ（ QString



、 QByteArray



など）で機能します。 コンテナは、コンテナで構成される場合があります。 flatMap



ような関数の場合、コンテナ以外のデータコンテナは終了します

StreamImpl



定義しStreamImpl



。

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

is_nested_stl_compatible_container



は、コンテナの「コンテナ」を決定するための補助メタ関数です（SFINAEはこれに役立ちます）。

 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); }; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

SFINAEテスターを整理する方法を考えてみましょう。

 #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))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

SFINAEテスターは、タイプごとのSFINAEと式ごとのSFINAEの両方を使用します。

SFINAEテスターが、コンテナデータを含むコンテナがあると判断したとします。

コンテナデータを含むコンテナ

コンテナデータを含むコンテナのStreamImpl



は、後で説明する基本機能を備えたインターフェイスであるStreamBase



継承するだけです。

 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; };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

非コンテナデータコンテナ

非コンテナデータを含むコンテナのStreamImpl



は、タイプQVector<int>



データ、およびタイプQString



擬似コンテナを操作するためのものですが、 std::initalizer



QVector<int>



するためのものです。

 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()); } };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ご覧のとおり、実装はStreamImpl<Tp, true>



と同じです。ただし、 flatMap



端末であり、基本クラスはflatMap



select_type<Tp>::type



によって表示されます。

 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 >; }; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これは、オープンtype_to_container



を使用して非コンテナをコンテナに変換し、次にstd::initalizer_list



type_to_container



に渡されます。 擬似コンテナの場合、「マジック」は使用されません。 デフォルトでは、 type_to_container



メタ関数の実装は次のとおりです。

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

詳細を確認したら、ベースに進みます。

ストリームベース

シンプルで基本的なインターフェースを見てみましょう。 StreamBase



は、要素をコンテナにすることができるコンテナで動作します。

実装をより簡単にするために、 StreamBase



はソースデータをコピーするか、それ自体に移動します。

非端末関数はStream



返しStream



。 非終端関数を呼び出すと、FPで連鎖してモナドのようなものを取得できます。

 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_)) { }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

コンテナの静的チェックを追加できます。

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

サービス機能は非常に簡単です。

  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(); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

map



実装を検討してください。 操作の本質は、アプリケータ機能がコンテナの各要素に適用され、結果が別のコンテナに配置されることです。 アプリケーター関数は、異なるタイプの値を返す場合があります。 実際、すべての作業は、新しいコンテナを返す補助関数で実行されます。 このコンテナはStream



に転送されStream



。 追加のパラメーターをアプリケーターに渡すことができます。

  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)); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

filter



操作は、コンテナー要素の各要素に対して述語関数を呼び出し、 true



受け取ると、要素は別のコンテナーにコピーされます。

  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)); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

reduce



操作（左側の畳み込みがここで使用されています）はより興味深いものです。 コンテナを1つの値に「崩壊」させ、左から右に移動し、演算子関数を現在の要素に第1オペランドとして、第2として初期値initial



として適用し、前の要素を「崩壊」させる：

  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...)); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

タイプTの要素を持つコンテナコンテナがある場合、 flatMap



を使用した結果、タイプTの要素を持つコンテナflatMap



ます。戻り値では、 flatMap



の端末バージョンに達するまで、 Stream



新しい表示値ごとに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(); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

オプションなしで最小値と最大値を見つけることは重要ではありません。

  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(); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

distinct



アナログも非常に簡単です。

  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)); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

一致するすべてのアイテムを検索した場合：

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

すべての不適切なものを検索するだけです（否定を使用）。

  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...)) ); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

要素の分割：2つのリストを取りますQMap



つは述部を満たすものを入れ、もう1つは満たさないものを入れ、元の精神でこれをすべて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; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

クラスタリング（グループへの分割）： clasterizator



2つの機能-グループへの分割にclasterizator



、グループの各要素でfinisher



機能（指定されている場合）が実行されます。

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

難しさは型を決定することのみです： clasterizator



とfinisher



戻り値の型を決定するために、 invoke



使用され（C ++ 17にあります）、合法化されるまで、最後に示された実装を使用します：

  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; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

クラスタリングはひどいように見えますが、簡単な仕事をしています：

  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; } };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

  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)...); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

まとめ

私たちの作品を適用してみましょう：

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

QList<QStringList>



は、内容が「functionalprogramming」のQStringに変わります。

単純なコンテナでは何も起こりstd::initalizer_list<int>



（ここでstd::initalizer_list<int>



QVector<int>



はQVector<int>



）

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

しかし、「難しい」 QVector<QVector<int>>



では、内容（ QVector<int>



を持つQVector<int>



になります。 、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(); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ラムダ関数、関数オブジェクト、および関数へのポインターで確認しましょう。

  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);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここで、intのリストは2進数システムのintを表す文字列のリストになり、文字列の長さが計算され、そこから1より大きいものが選択され、 std::bind



で作成された機能構成を使用して、要素が選択されます範囲[1、100]で、これらの要素が乗算されます。

ホラー！

そして最後に、例の最初の部分では、要素を数字/非数字に分割し、有効バイト（ QChar::cell



）で独立してグループ化し、再び、有効バイトでx



要素を独立してグループ化し、その数をカウントします。

  { 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：そのような例でごめんなさい...夜になると、それ以上良いものは思いつかなかった）