Интерфейс для оптимального обхода контейнера

Во-первых, я бы не стал засовывать алгоритм прохода контейнера внутрь, а прилепил функцию for_each сбоку. Под каждый контейнер она затачивается перегрузкой и/или специализацией.

Далее, for_each оптимально, в т.ч. в несколько потоков, проходит весь контейнер и вызывает переданную ей «функцию» с нужными аргументами (элемент, его «координаты» и что ты там еще хочешь). «Функция» разумеется передается через шаблонный тип и может быть как функцией, так и объектом с оператором круглые скобки, конечно лучше воспользоваться абстракцией bind, чтобы можно было передавать и метод некоторого объекта, например из буста. Вроде в самом с++ ввели что-то подобное.

UPD. С петоном скрестить наверное не сложно, нужно только пробросить интерфейс к for_each и колбэку.

Насчет for_each сбоку подумаю, но как то оно пока не смотрится - ей много всего надо знать, а с друзьями связываться не хочется.

А если передавать функтор, как создавать его копии для неск потоков (и как потом сводить вместе результат)?

А если передавать функтор, как создавать его копии для неск потоков (и как потом сводить вместе результат)?

Функтор должен хранить какое-то состояние и сбрасываться? Перед каждым вызовом? Перед первым вызовом в потоке? Вот когда надо сбросить состояние, тогда и копируй его.

Как сводить. Если for_each должен модифицировать контейнер, проще всего в колбэк передавать ссылки на элементы. Кроме того у тебя есть некие координаты элементов, можно ориентироваться на них. Если по результату for_ecch должен получиться новый контейнер (тогда, по идее, и с возможно новым типом хранимых элементов), проще всего было бы в начала for_each создать выходной контейнер, дублирующий структуру оригинала, но с «пустыми» элементами, затем, зная координаты исходных элементов, вставлять в нужные места результаты работы колбэков.

ЗЫ. Я правильно понимаю, что ты разбиваешь контейнер на несколько участков и на каждом из них запускаешь по потоку-обработчику?

STL-подобных итераторов для контейнеров НЕТ (и не будет).

мне надо забивать гвозди. молотка нет и не будет. чем их можно ещё забивать?

Паттерн Visitor.

Посмотри как valarray + slice&gslice организованы.

А чем итераторы-то не устраивают? Это же стандартный интерфейс для всех языков.

void MyContainer::ForEach(std::function<void(const Item &item)> func) { //...implementation }

Функция вызывается для каждого элемента.

функтор должен хранить состояние, которое изменяется по мере прохода. После окончания прохода состояния функторов надо свести вместе.

Новый контейнер не создается. Изменения элементов контейнера возможны, но не обязательны (скорее они таки не изменяются).

Обход в неск потоков - да, можно считать что контейнер разбивается на неск областей в каждой из которых пасется свой поток. Как после это сост. функторов сводить (напр если считалась сумма элементов) - ХЗ

спасибо КО. Как мне с таким подходом найти минимальный элент например?

итераторы STL вовсе не вершина мысли. Они стандартны, но для таких задач далеко не оптимальны. Напр для обхода многомерного массива итератор должен знать границы массива и еще кучу всякой фигни.

итератор должен знать границы массива и еще кучу всякой фигни.

И? Что запрещает хранить это в итераторе? Если контейнер не будут изменять, не вижу проблемы.

Ничего не запрещает. А теперь представьте неск итераторов каждый в своем потоке. А етперь представьте что итервторы динамически балансируются. А теперь представьте, что это нужно формить как обычные итераторы.

Ничего не запрещает так делать, просто это неудобно.

А теперь представьте неск итераторов каждый в своем потоке. А етперь представьте что итервторы динамически балансируются. А теперь представьте, что это нужно формить как обычные итераторы.

Не понял полёта твоей мысли. Объясни на пальцах, что значит «динамически балансируются» и чем тебе будут мешать итераторы в разных потоках?

Если контейнер не будут изменять, не вижу проблемы.

--

просто это неудобно.

Неудобно спать на потолке, одеяло спадает. Имхо, если хочешь забивать гвозди - возьми молоток. Самое оно для этой цели. А мне отвечают, что молоток тяжёлый и можно попасть по пальцу, да.

представьте

Я польщён, можно на ты, спасибо.

Напр для обхода многомерного массива итератор должен знать границы массива и еще кучу всякой фигни.

зачем ему знать границы массива? Если эл-ты нумеруются с нуля до N, то пусть себе перебирает, пока не встретит NULL или NaN, или ещё чего-нить.

Ничего не запрещает. А теперь представьте неск итераторов каждый в своем потоке. А етперь представьте что итервторы динамически балансируются. А теперь представьте, что это нужно формить как обычные итераторы.

...а теперь представьте, что вместо обычных итераторов какие-то мутные функторы... Жуть...

А кто и как, кроме итератора (если есть только итераторы) узнает координаты элемента в многомерном массиве?

Я и беру узкозаточенный специальный безоткатный молоток. А Вы привыкли стучать кирпичом, аргументируя это тем что кирпичи это стандартно и есть у всех.

Вообще, тред не о нужности/ненужности итераторов. Если нечего сказать по теме треда, давайтедосвиданья. Можете создать свой тред, где будете обосновывать нужность итераторов для всего сущего.

Вы не знаете что есть динамическая балансировка?

А кто и как, кроме итератора (если есть только итераторы) узнает координаты элемента в многомерном массиве?

не понял вопроса: зачем кому-то, кого нет, узнавать координаты? У тебя только итераторы, и они знают координаты. В чём проблема?

Вы не знаете что есть динамическая балансировка?

балансировка ЧЕГО? Сам по себе итератор не может быть не сбалансирован, ибо на нём ничего не висит. И он висит в одной точке коллекции. Может вы про два итератора? Или про нагрузку, создаваемую итераторами? Или ещё про что-то?

Вообще, тред не о нужности/ненужности итераторов. Если нечего сказать по теме треда

вообще-то, хреновина, которая обходит коллекцию, называется «итератор». Вы про них и спрашиваете. Даже три примера итераторов привели. Давайте не будем в середине темы говорить про не нужность итераторов? А то прикрутили к палке кирпич, забиваете этим кирпичом на палке гвоздь, и рассказываете тут, как в не любите молотки...

Помимо 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
// );

У тебя только итераторы, и они знают координаты. В чём проблема?

КАК они знают координаты? Вот у меня обычный 3Д массив 10х10х10. Итератор указывает на 19й элемент (от начала) и знает координаты. Инкрементируем. Как он узнает новые координаты не зная границ массива?

А теперь допустим массив устроен гораздо сложнее. Итератору для нормальной работы нужно знать все детали устройства массива. Т.е. итератору нужно либо держать ссылку на объект массива и постоянно по ней лазить, либо держать в себе копию всех деталей устройства массива.

вообще-то, хреновина, которая обходит коллекцию, называется «итератор».

Вообще то нет. for_each что угодно, но только не итератор. Итератор м.б. спрятан внутри for_each, как деталь реализации, но конкретно реализация обхода меня не интересует - меня интересует интерфейс, т.е. как сообщить for_each какие действия нужно делать над каждым элементом. И где тут итераторы?

Мне казалось я довольно ясно объяснил что меня интересует, привел примеры, и это еще раз доказывает как вредно курить, даже если ты кислотный пони;-)

Вы про них и спрашиваете. Даже три примера итераторов привели. Давайте не будем в середине темы говорить про не нужность итераторов?

Про них я не спрашиваю. Ок, под итератором в данной теме лично я (и наск я понял nanoolinux) понимаем STL-подобные итераторы. Вот их нет, не будет, и я не хочу и не буду обсуждать почему их нет и не будет.

балансировка ЧЕГО?

Потоков же.

Спасибо. Т.е. фактически range отличается от итератора только тем, что сама проверяет не дошла ли до конца?

В данном случае, мне неинтересна реализация обхода. Мне интересно, как сообщить «обходчику» что ему делать с каждым элементом и как вернуть итоговый результат.

В этом смысле конечно концепция итераторов (или range) выглядит соблазнительно, можно написать обычный цикл и вперед. Проблема во первых в реализации итератора/range (обход может быть например рекурсивным, разворачивать рекурсию ручками по ряду причин не хочется и не можется), во вторых в параллельной реализации этого цикла (ну допустим под каждый тред можно сваять свой range).

Т.е. мы считаем, что сам эффективная реализация обхода в общем случае настолько сложна, что не может быть эффективно записана в виде простой конструкции (типа for) и должна быть от пользователя скрыта в недрах for_each. Вопрос в том, как туда передать действия (тело цикла) и получить назад результат.

Я дико извиняюсь, а можно для идиота объяснить, о чем идет речь? Есть контейнер, от содержимого абстрагируемся путем некоего интерфейса для обхода или редукции. Публикуем метод, принимающий фукнциеподобное значение и диапазон/масштаб для параллельности и готово, нет?

Да-да, все именно так. Но дьявол кроется в деталях.

Детали это управление ресурсами? Если так, то передавай заранее выделенный void * вместе с функцией-итератором, и в конце просто free() его. Туда как раз запишешь все, что собрал в итераторе.

http://ru.wikipedia.org/wiki/MapReduce

Делай две функции: фильтр отдельно (параллелится внутри for_each как угодно), свёртка отдельно (опять же join внутри реализации for_each).

Т.е. фактически range отличается от итератора только тем, что сама проверяет не дошла ли до конца?

В первом приближении это пара «обычных» итераторов, так что, да, всё есть — можно реализовать empty() и прочие вещи. Но вообще суть в том что это именно единственный объект для каждого вида обхода для данного контейнера — с любым подходящим интерфейсом для обобщённого кода в виде свободных шаблонных функций. И то что это единственный объект позволяет, например, делать вещи вроде ReversedRange<ARange> reverse(ARange), SequentialRange<ARange, BRange> seq(ARange, BRange), ParallelRange<ARange, BRange> par(ARange, BRange) и т.п.

Мне интересно, как сообщить «обходчику» что ему делать с каждым элементом и как вернут итоговый результат.

http://www.cplusplus.com/reference/algorithm/ и http://www.cplusplus.com/reference/numeric/ это не то? Если обощённость не нужна, то для конкретного класса можно тогда стереть итераторы из шаблонов и заменить функторы на обычные ссылки на функции, вроде

template <typename R, typename A, typename ...As>
using AccumulateFunction = R(&)(R, A, As...);

template <typename R, typename A, typename ...As>
R accumulate(ThisClass<A> &obj, AccumulateFunction<R, A, As...> fn)
{
    // traverse, parallelize, prepeare As... from obj for user's callback (including "context", "hints" and so on)
}

template <typename R, typename A, typename ...As>
R accumulate(ThisClass<A> &obj, AccumulateFunction<R, A, As...> fn, R init)

// min = accumulate(obj, *[](T acc, T el) { return el < acc ? el : acc; });
// sum = accumulate(obj, std::plus<T>(), 0);

также с for_each, find_if и т.п. Только будучи свободными функциям им всем всё равно нужно опираться на какие-то методы обхода ThisClass, или просто на его кишки (будучи выделенными в отдельные сущности они превращаются, собственно, в итераторы и ко).

обход может быть например рекурсивным, разворачивать рекурсию ручками по ряду причин не хочется и не можется

Это да, если структура данных неудобная в итеративном смысле то без её «прошивания» (то есть дополнения связями) может не получиться эффективного обхода.

ну допустим под каждый тред можно сваять свой range

Выше у меня в async_fold как раз в лямбду для async копируется ([=]) range элементов массива полученный как срез из range срезов массива.

А вот, кстати, — http://threadingbuildingblocks.org/docs/help/reference/algorithms.htm.

Детали это управление ресурсами?

Нет.

вообще суть в том что это именно единственный объект для каждого вида обхода для данного контейнера

Все, понял, спасибо. Это интересная концепция, но если относить ее к многомерным массивам, то сразу появляется желание в частности задавать области произвольной формы. А эта задача в общем случае хорошего решения не имеет... но подумать можно, тут чувствуется некоторое благородное безумие;-)

http://www.cplusplus.com/reference/algorithm/ и http://www.cplusplus.com/reference/numeric/ это не то?

Не до конца. Точнее оно то, если делать, что то простое. Вот допустим есть массив размерности D из элементов типа T. Координаты элемента задаются структурой indx<D>. Нужно за один проход найти минимальный и максимальный элементы, а так же их координаты. При вызове чего то внутрях for_each (или называйте это как хотите) передается элемент и его координаты. Я че то не соображу как accumulate тут присобачить;-(

monk прав, ну и я с-но вначале писал, что для reduce нужна отдельная функция. Для каких то тривиальных вещей типа суммы или минимума (без координат) можно обойтись и функцией которая применяется ко всем элементам, но в общем случае нет.

template <typename Elt, typename Idx, typename Iter>
struct MinMaxPlace {

    EltWithIdx<Elt, Idx> min, max;

    MinMaxPlace(const Iter &begin, const Iter &end) :
        min(*begin), max(*begin)
    {
        std::for_each(
            begin, end,
            [&](EltWithIdx<Elt, Idx> curr) {
                if (curr.elt < min.elt)
                    min = curr;
                else if (curr.elt > max.elt)
                    max = curr;
            }
        );
    }

};

или

    auto min_max = std::accumulate(
        xs.begin(), xs.end(),
        std::make_pair(*xs.begin(), *xs.begin()),
        [](Pair acc, EltWithIdx<Elt, Idx> curr) {
            if (curr.elt < acc.first.elt)
                acc.first = curr;
            else if (curr.elt > acc.second.elt)
                acc.second = curr;
            return acc;
        }
    );

это предполагает наличия у Iter EltWithIdx<Elt, Idx> operator*() — текущий элемент в данном состоянии итератора + его позиция в структуре, то есть за индексами итератор должен сам следить.

Не понял, чем первый вариант отличатся от третьего, кроме того, что в первом случае join() реализуется автором for_each, а во втором --- автором функтора.

Мне кажется, здесь уместны ключевые слова «reduce» (или «fold») и «замыкание». reduce обходит контейнер и применяет к нему функцию от двух аргументов: текущее состояние обхода и элемент контейнера. Функция возвращает состояние. В простейшем случае состоянием может быть один из элементов контейнера. Например, поиск минимума в Common Lisp можно записать так:

(reduce #'min container)

В CL у reduce есть ещё ряд вспомогательных параметров, которые облегчают её использование. Подробнее см. http://www.lispworks.com/documentation/HyperSpec/Body/f_reduce.htm. В данном случае, наверное, интереснее всего будет initial-element.

reduce можно сделать через аналог первого варианта for_each и замыкание, например, так:

(defun reduce (function container state)
  (for-each (lambda (element)
              (setf state (funcall function state element)))
            container))

Здесь в reduce явно передаётся state, но его можно сделать неявным, описав как следует поступить с первыми двумя элементами. В C++11 замыкание подобного рода можно сделать через функтор. Удобство в том, что, во-первых, в простых случаях можно воспользоваться лямбда-функциями C++11, и, во-вторых, интерфейс получатся многоуровневый: есть низкоуровневая функция обхода for_each, и есть reduce, который может принимать на вход чистые функции. При желании на основе for_each можно построить другие функции высшего порядка, например, map.

КАК они знают координаты? Вот у меня обычный 3Д массив 10х10х10. Итератор указывает на 19й элемент (от начала) и знает координаты. Инкрементируем. Как он узнает новые координаты не зная границ массива?

спросит. Нужна например функция внутри массива, доступная итератору. Которая отдаёт координату сл. эл-та.

Вообще то нет. for_each что угодно, но только не итератор. Итератор м.б. спрятан внутри for_each, как деталь реализации, но конкретно реализация обхода меня не интересует - меня интересует интерфейс, т.е. как сообщить for_each какие действия нужно делать над каждым элементом. И где тут итераторы?

здесь нет итераторов. И нет ООП. В ООП итератором является объект с методами. А у тебя функция, как в обычном неООП программировании. Естественно, в C++ это выглядит через задницу.

понимаем STL-подобные итераторы.

STL или ООП?

Потоков же.

ты-бы с парадигмой сначала разобрался.

Да, спасибо.Но все же, в многопоточном варианте для слияния результатов нужна в общем случае отдельная функция.

Но все же, в многопоточном варианте для слияния результатов нужна в общем случае отдельная функция.

Я хотел сказать, что в, допустим

template <class InputIterator, class T, class BinaryOperation>
T accumulate(InputIterator first, InputIterator last, T init, BinaryOperation binary_op)
{
    while (first != last)
        init = binary_op(init, *first++)
    return init;
}

у нас в callback binary_op попадает то что возвращает operator* итератора, соответсвенно, без переписывания кода accumulate и прочих можно сделать так чтобы в callback попадало всё что нам нужно просто написанием соответсвующего итератора с нужным operator* (в т.ч. обвёрткой над существующим итератором).

Теперь пусть у нас будут свои параллельные/конкурентные accumulate и т.п. (типа как в TBB, только для конкретного контейнера) большими портянками без итераторов или ranges — чтобы в callback попадали индексы и прочее нам просто нужно сделать

template <...>
ResultType accumulate(Array<ElementType, ...> array, Accumulator<ResultType, ...> accumulator, ..., Function callback)
{
    // обходим array, в т.ч. многопоточно

        // в каждой точке обхода вызываем callback который принимает весь нужный контекст обхода
        // и обновляет сложный accumulator (то есть юзер может смотреть весь контекст и менять accumulator
        // как ему нужно). Дальше обходчик смотрит в (сложный) accumulator -- не решил ли юзер остановить
        // обход (если это scan/find-like) и т.п.

        // функции обхода ведь известны текущие индексы?
        accumulator = callback(accumulator, current_element, indexes, neighborhood, whatever, ...)

        if (accumulator.user_want_to_stop) {
            ...
        } else if (accumulator.any_other_condition_in_acumulator_structure_setted_by_user) {
            ...
        } else {
            ...
        }

    return accumulator.result;
}

через такую функцию выражаются остальные for_each, scan, find, min/max, any/all, map и т.п.