История изменений

Исправление quasimoto, 20.06.13 06:53 (текущая версия) :

Помимо STL-like итераторов есть ещё ranges — в их случае предполагается возвращать из контейнера не пару begin/end, а просто некий range реализующий нужный интерфейс ranges, внутри может быть как begin/end, так и вообще что угодно, интерфейс — от минимального bool empty() / operator* / operator= и далее forward / backward в виде operator++/operator-- и т.п. Плюс, к более общему интерфейсу, — возможность писать find(cont.all(), element) вместо find(cont.begin(), cont.end(), element), более удобные композиционные свойства, как следствие.

Пример с итерацией по 1D массиву кусками с последующими итерациями уже по кускам:

template <typename T>
struct Range {
    virtual ~Range() {}
    virtual bool empty() const = 0;
    virtual const T& operator*() const = 0;
};

template <typename T>
struct ForwardRange : Range<T> {
    virtual ~ForwardRange() {}
    virtual void operator++() = 0;
};

template<typename T, typename AForwardRange>
AForwardRange find(AForwardRange range, T value)
{
    for (; !range.empty(); ++range)
        if (value == *range)
            break;
    return range;
}

template<typename T, typename AForwardRange, typename Functor>
T fold(AForwardRange range, Functor fn)
{
    T res {};
    for (; !range.empty(); ++range)
        res = fn(res, *range);
    return res;
}

template<typename T, typename AForwardRange>
T sum(AForwardRange range)
{
    return fold<T>(range, std::plus<T>());
}

template <typename AForwardRange>
struct SliceForwardRange : ForwardRange<AForwardRange> {
    virtual ~SliceForwardRange() {}
    virtual AForwardRange slice() const = 0;
};

template<typename T, typename ASliceForwardRange, typename AForwardRange, typename Functor>
T async_fold(AForwardRange range, Functor fn, size_t n_steps)
{
    std::vector<std::future<T> > jobs;

    // map/fork
    for (ASliceForwardRange slices(range, n_steps); !slices.empty(); ++slices)
        jobs.push_back(std::async(std::launch::async, [=]() {
            T res {};
            for (auto sub_range = slices.slice(); !sub_range.empty(); ++sub_range)
                res = fn(res, *sub_range);
            return res;
        }));

    // reduce/join
    T res {};
    for (auto &job : jobs)
        res = fn(res, job.get());
    return res;
}

/* In 1D case. */

template <typename T>
struct MemoryForwardRange : public ForwardRange<T> {

    MemoryForwardRange(T *begin_, const T *end_) :
        begin(begin_), end(end_) {}

    bool empty() const { return begin >= end; }

    void operator++() { assert(!empty()); ++begin; }

    const T& operator*() const { assert(!empty()); return *begin; }

    T *begin;
    const T *end;

};

template <typename T>
struct MemorySliceForwardRange : public SliceForwardRange<MemoryForwardRange<T> > {

    MemorySliceForwardRange(const MemoryForwardRange<T> &range_, size_t n_steps_) :
        range(range_), n_steps(n_steps_) {}

    bool empty() const { return range.empty(); }

    void operator++() { assert(!empty()); range.begin += n_steps; }

    const MemoryForwardRange<T>& operator*() const { return range; }

    MemoryForwardRange<T> slice() const {
        assert(!empty());
        return
            range.begin + n_steps >= range.end ?
            MemoryForwardRange<T>(range.begin, range.end) :
            MemoryForwardRange<T>(range.begin, range.begin + n_steps);
    }

    MemoryForwardRange<T> range;
    const std::size_t n_steps;

};

// async_fold<T, MemorySliceForwardRange<T> >(
//     MemoryForwardRange<T>(xs, xs + n), std::plus<T>(), n / threads
// );

Исходная версия quasimoto, 20.06.13 06:45:

Пример с итерацией по 1D массиву кусками с последующими итерациями уже по кускам:

template <typename T>
struct Range {
    virtual ~Range() {}
    virtual bool empty() const = 0;
    virtual const T& operator*() const = 0;
};

template <typename T>
struct ForwardRange : Range<T> {
    virtual ~ForwardRange() {}
    virtual void operator++() = 0;
};

template<typename T, typename AForwardRange>
AForwardRange find(AForwardRange range, T value)
{
    for (; !range.empty(); ++range)
        if (value == *range)
            break;
    return range;
}

template<typename T, typename AForwardRange, typename Functor>
T fold(AForwardRange range, Functor fn)
{
    T res {};
    for (; !range.empty(); ++range)
        res = fn(res, *range);
    return res;
}

template<typename T, typename AForwardRange>
T sum(AForwardRange range)
{
    return fold<T>(range, std::plus<T>());
}

template <typename AForwardRange>
struct SliceForwardRange : ForwardRange<AForwardRange> {
    virtual ~SliceForwardRange() {}
    virtual AForwardRange slice() const = 0;
};

template<typename T, typename ASliceForwardRange, typename AForwardRange, typename Functor>
T async_fold(AForwardRange range, Functor fn, size_t n_steps)
{
    std::vector<std::future<T> > jobs;

    // map/fork
    for (ASliceForwardRange slices(range, n_steps); !slices.empty(); ++slices)
        jobs.push_back(std::async(std::launch::async, [=]() {
            T res {};
            for (auto sub_range = slices.slice(); !sub_range.empty(); ++sub_range)
                res = fn(res, *sub_range);
            return res;
        }));

    // reduce/join
    T res {};
    for (auto &job : jobs)
        res = fn(res, job.get());
    return res;
}

/* In 1D case. */

template <typename T>
struct MemoryForwardRange : public ForwardRange<T> {

    MemoryForwardRange(T *begin_, const T *end_) :
        begin(begin_), end(end_) {}

    bool empty() const { return begin >= end; }

    void operator++() { assert(!empty()); ++begin; }

    const T& operator*() const { assert(!empty()); return *begin; }

    T *begin;
    const T *end;

};

template <typename T>
struct MemorySliceForwardRange : public SliceForwardRange<MemoryForwardRange<T> > {

    MemorySliceForwardRange(const MemoryForwardRange<T> &range_, size_t n_steps_) :
        begin(range_.begin), range(range_), n_steps(n_steps_) {}

    bool empty() const { return begin >= range.end; }

    void operator++() { assert(!empty()); begin += n_steps; }

    const MemoryForwardRange<T>& operator*() const { return range; }

    MemoryForwardRange<T> slice() const {
        assert(!empty());
        return
            begin + n_steps >= range.end ?
            MemoryForwardRange<T>(begin, range.end) :
            MemoryForwardRange<T>(begin, begin + n_steps);
    }

    T *begin;
    const MemoryForwardRange<T> range;
    const std::size_t n_steps;

};

// async_fold<T, MemorySliceForwardRange<T> >(
//     MemoryForwardRange<T>(xs, xs + n), std::plus<T>(), n / threads
// );