Простая реализация Stream из Java 8 в С++

Всем привет! В статье будет представлена упрощенная реализацию Stream из Java 8 на С++. Скажу сразу, что:

• в отличии от Java не используются отложенные вычисления;
• нет параллельных версий;
• местами совмещает Stream и Collectors;
• используются простые и готовые решения от STL, здесь нету чистого ФП, где только рекурсия;
• не используются техники оптимизации.

В этой версии основной упор сделан на то, чтобы быстро и просто сделать велосипед). Про ФП упомянуто по-минимуму (комбинаторам внимание не уделено :)).

Интерфейс

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

Stream работает с контейнерами или контейнероподобными типами (типа QString, QByteArray и т.п). Контейнеры в свою очередь могут состоять из контейнеров. Контейнер с неконтейнерными данными будет терминален для функций типа flatMap

Определяем 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:

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 терминальна, а базовый класс выводится метафункцией 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 выглядит следующим образом:

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

Рассмотрев детали, перейдем к базе.

StreamBase

Давайте рассмотрим простой базовый интерфейс. StreamBase работает с контейнерами, элементы которых могут быть контейнерами.

Для большей простоты реализации StreamBase копирует исходные данные или перемещает их к себе.

Нетерминальные функции возвращают Stream. Вызовы нетерминальных функций можно объединять цепочки и получить что-то вроде монад в ФП.

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. Аппликатору можно передать дополнительные параметры.

    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 (здесь используется свертка слева) более интересна. reduce "сворачивает" контейнер в одно значение, двигаясь слева-направо, применяя функцию-оператор к текущему элементу, в качестве первого операнда, а в качестве второго — начальное значение 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 вызывается для каждого нового выведенного значения 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();

    }

Поиск минимума и максимума без optional не представялет интереса:

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

Разбиение элементов: берем два списка – в один кладем, то что удовлетворяет предикату, а в другой, то что нет, а потом в духе оригинала все это помещаем в 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 – для разбиения на группы, а потом над каждым элементом группы выполняется (если задана) функция-finisher.

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

Сложности только в определении типов: для определения типов возвращаемым значений clasterizator и finisher используется invoke (который будет в С++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> превратится в QString с содержимым: "functionalprogramming".

С простым контейнером ничего не случится (здесь std::initalizer_list<int> превратится в QVector<int>)

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

А вот с "непростым" случится QVector<QVector<int>> превратится в QVector<int> с содержимым (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();
    }

Проверим с лямбда-функциями, функциональными объектами и с указателями на функции:

    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-ов превращается в список строк, представляющих 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: простите за такие примеры… На ночь ничего лучше не придумалось)