Объединение нескольких циклов в один итератор - программирование
Подтвердить что ты не робот

Объединение нескольких циклов в один итератор

Скажем, у меня есть гнездо для циклы, как

for (int x = xstart; x < xend; x++){
    for (int y = ystart; y < yend; y++){
        for (int z = zstart; z < zend; z++){
            function_doing_stuff(std::make_tuple(x, y, z));
        }
    }
}

и хотел бы превратить его в

MyRange range(xstart,xend,ystart,yend, zstart,zend);
for (auto point : range){
    function_doing_stuff(point);
}

Как бы написать класс MyRange таким же эффективным, как вложенные для циклов? Мотивация заключается в том, чтобы иметь возможность использовать std-алгоритмы (такие как преобразование, накопление и т.д.) И создавать код, который в значительной степени агностик.

Имея итератор, было бы легко создать шаблонные функции, которые работают в диапазоне 1d, 2d или 3-х точек.

В настоящее время база кода С++ 14.

РЕДАКТИРОВАТЬ:

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

4b9b3361

ОТВЕТЫ

Ответ 1

Поскольку вы заботитесь о производительности, вы должны забыть о объединении итераторов в обозримом будущем. Основная проблема заключается в том, что компиляторы еще не могут распутать беспорядок и выяснить, что в нем есть 3 независимые переменные, а тем более не выполняются любые обмены циклами или разворачивание или слияние.

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

for (int const x : boost::irange<int>(xstart,xend))
    for (int const y : boost::irange<int>(ystart,yend))
        for (int const z : boost::irange<int>(zstart,zend))
            function_doing_stuff(x, y, z);

Кроме того, вы можете передать свой функтор и диапазоны повышения в шаблон:

template <typename Func, typename Range0, typename Range1, typename Range2>
void apply_ranges (Func func, Range0 r0, Range1 r1, Range2 r2)
{
     for (auto const i0 : r0)
         for (auto const i1 : r1)
             for (auto const i2 : r2)
                 func (i0, i1, i2);
}

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

Ответ 2

С диапазоном /v3 вы можете делать

auto xs = ranges::view::iota(xstart, xend);
auto ys = ranges::view::iota(ystart, yend);
auto zs = ranges::view::iota(zstart, zend);
for (const auto& point : ranges::view::cartesian_product(xs, ys, zs)){
    function_doing_stuff(point);
}

Ответ 3

Вы можете представить свой собственный класс как

class myClass {
  public:
    myClass (int x, int y, int z):m_x(x) , m_y(y), m_z(z){};
  private: 
    int m_x, m_y, m_z;

}

и затем инициализируйте std::vector<myClass> с помощью тройной циклы

std::vector<myClass> myVec;
myVec.reserve((xend-xstart)*(yend-ystart)*(zend-zstart)); // alloc memory only once;
for (int x = ystart; x < xend; x++){
    for (int y = xstart; y < yend; y++){ // I assume you have a copy paste error here
        for (int z = zstart; z < zend; z++){
            myVec.push_back({x,y,z})
        }
    }
}

Наконец, вы можете использовать все хорошие std-алгоритмы с помощью std::vector<myClass> myVec. С синтаксическим сахаром

using MyRange = std::vector<MyClass>;

а также

MyRange makeMyRange(int xstart, int xend, int ystart, int yend, int zstart,int zend) {
    MyRange myVec;
    // loop from above
    return MyRange;
}

ты можешь написать

const MyRange range = makeMyRange(xstart, xend, ystart, yend, zstart, zend);
for (auto point : range){
    function_doing_stuff(point);
}

С новой семантикой перемещения это не создаст ненужные копии. Обратите внимание, что интерфейс к этой функции довольно плох. Возможно, вместо этого используйте 3 пары int, обозначающих интервал x, y, z.

Возможно, вы измените имена на что-то значимое (egmyClass может быть точкой).

Ответ 4

Другой вариант, который непосредственно пересаживает любой код цикла, заключается в использовании Coroutine. Это эмулирует yield из Python или С#.

using point = std::tuple<int, int, int>;
using coro = boost::coroutines::asymmetric_coroutine<point>;

coro::pull_type points(
    [&](coro::push_type& yield){
        for (int x = xstart; x < xend; x++){
            for (int y = ystart; y < yend; y++){
                for (int z = zstart; z < zend; z++){
                    yield(std::make_tuple(x, y, z));
                }
            }
        }
    });

for(auto p : points)
    function_doing_stuff(p);

Ответ 5

Здесь реализована реализация bare-bones, которая не использует никаких дополнительных языковых функций или других библиотек. Производительность должна быть очень близка к версии for loop.

#include <tuple>

class MyRange {
public:
    typedef std::tuple<int, int, int> valtype;
    MyRange(int xstart, int xend, int ystart, int yend, int zstart, int zend): xstart(xstart), xend(xend), ystart(ystart), yend(yend), zstart(zstart), zend(zend) {
    }

    class iterator {
    public:
        iterator(MyRange &c): me(c) {
            curvalue = std::make_tuple(me.xstart, me.ystart, me.zstart);
        }
        iterator(MyRange &c, bool end): me(c) {
            curvalue = std::make_tuple(end ? me.xend : me.xstart, me.ystart, me.zstart);
        }
        valtype operator*() {
            return curvalue;
        }
        iterator &operator++() {
            if (++std::get<2>(curvalue) == me.zend) {
                std::get<2>(curvalue) = me.zstart;
                if (++std::get<1>(curvalue) == me.yend) {
                    std::get<1>(curvalue) = me.ystart;
                    ++std::get<0>(curvalue);
                }
            }
            return *this;
        }
        bool operator==(const iterator &other) const {
            return curvalue == other.curvalue;
        }
        bool operator!=(const iterator &other) const {
            return curvalue != other.curvalue;
        }
    private:
        MyRange &me;
        valtype curvalue;
    };

    iterator begin() {
        return iterator(*this);
    }

    iterator end() {
        return iterator(*this, true);
    }

private:
    int xstart, xend;
    int ystart, yend;
    int zstart, zend;
};

И пример использования:

#include <iostream>

void display(std::tuple<int, int, int> v) {
    std::cout << "(" << std::get<0>(v) << ", " << std::get<1>(v) << ", " << std::get<2>(v) << ")\n";
}

int main() {
    MyRange c(1, 4, 2, 5, 7, 9);
    for (auto v: c) {
        display(v);
    }
}

Я operator+= от таких вещей, как operator+= итераторы, возможно operator+=, декремент, приращение постов и т.д. Они остались в качестве упражнения для читателя.

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

Ответ 6

Используя boost::iterator_facade для простоты, вы можете указать всех необходимых членов.

Сначала у нас есть класс, который выполняет итерации N-мерных индексов как std::array<std::size_t, N>

template<std::size_t N>
class indexes_iterator : public boost::iterator_facade<indexes_iterator, std::array<std::size_t, N>>
{
public:
    template<typename... Dims>
    indexes_iterator(Dims... dims) : dims{ dims... }, values{} {}

private:
    friend class boost::iterator_core_access;

    void increment() { advance(1); }
    void decrement() { advance(-1); }

    void advance(int n) 
    { 
        for (std::size_t i = 0; i < N; ++i)
        { 
            int next = ((values[i] + n) % dims[i]); 
            n = (n \ dims[i]) + (next < value); 
            values[i] = next;
        }
    }

    std::size_t distance(indexes_iterator const & other) const
    {
        std::size_t result = 0, mul = 1;
        for (std::size_t i = 0; i < dims; ++i)
        {
             result += mul * other[i] - values[i];
             mul *= ends[i];
        }
    }

    bool equal(indexes_iterator const& other) const
    {
        return values == other.values;
    }

    std::array<std::size_t, N> & dereference() const { return values; }

    std::array<std::size_t, N> ends;
    std::array<std::size_t, N> values;
}

Затем мы используем это, чтобы сделать что-то похожее на boost::zip_iterator, но вместо того, чтобы продвигаться вместе, мы добавляем наши индексы.

template <typename... Iterators>
class product_iterator : public boost::iterator_facade<product_iterator<Iterators...>, const std::tuple<decltype(*std::declval<Iterators>())...>, boost::random_access_traversal_tag>
{
    using ref = std::tuple<decltype(*std::declval<Iterators>())...>;
public:
    product_iterator(Iterators ... ends) : indexes() , iterators(std::make_tuple(ends...)) {}
    template <typename ... Sizes>
    product_iterator(Iterators ... begins, Sizes ... sizes) 
      : indexes(sizes...), 
        iterators(begins...) 
    {}
private:
    friend class boost::iterator_core_access;

    template<std::size_t... Is>
    ref dereference_impl(std::index_sequence<Is...> idxs) const
    {
        auto offs = offset(idxs);
        return { *std::get<Is>(offs)... };
    }

    ref dereference() const
    { 
        return dereference_impl(std::index_sequence_for<Iterators...>{}); 
    }

    void increment() { ++indexes; }
    void decrement() { --indexes; }
    void advance(int n) { indexes += n; }

    template<std::size_t... Is>
    std::tuple<Iterators...> offset(std::index_sequence<Is...>) const
    {
        auto idxs = *indexes;
        return { (std::get<Is>(iterators) + std::get<Is>(idxs))... };
    }

    bool equal(product_iterator const & other) const 
    {
        return offset(std::index_sequence_for<Iterators...>{}) 
            == other.offset(std::index_sequence_for<Iterators...>{}); 
    }

    indexes_iterator<sizeof...(Iterators)> indexes;
    std::tuple<Iterators...> iterators;
};

Затем мы завершаем его в boost::iterator_range

template <typename... Ranges>
auto make_product_range(Ranges&&... rngs)
{
    product_iterator<decltype(begin(rngs))...> b(begin(rngs)..., std::distance(std::begin(rngs), std::end(rngs))...);
    product_iterator<decltype(begin(rngs))...> e(end(rngs)...);
    return boost::iterator_range<product_iterator<decltype(begin(rngs))...>>(b, e);
}

int main()
{
    using ranges::view::iota;
    for (auto p : make_product_range(iota(xstart, xend), iota(ystart, yend), iota(zstart, zend)))
        // ...
    return 0;
}

Смотрите на godbolt

Ответ 7

Просто очень упрощенная версия, которая будет такой же эффективной, как цикл for:

#include <tuple>

struct iterator{
  int x;
  int x_start;
  int x_end;
  int y;
  int y_start;
  int y_end;
  int z;
  constexpr auto
  operator*() const{
    return std::tuple{x,y,z};
    }
  constexpr iterator&
  operator++ [[gnu::always_inline]](){
    ++x;
    if (x==x_end){
      x=x_start;
      ++y;
      if (y==y_end) {
        ++z;
        y=y_start;
        }
      }
    return *this;
    }
  constexpr iterator
  operator++(int){
    auto old=*this;
    operator++();
    return old;
    }
  };
struct sentinel{
  int z_end;
  friend constexpr bool
  operator == (const iterator& x,const sentinel& s){
    return x.z==s.z_end;
    }
  friend constexpr bool
  operator == (const sentinel& a,const iterator& x){
    return x==a;
    }
  friend constexpr bool
  operator != (const iterator& x,const sentinel& a){
    return !(x==a);
    }
  friend constexpr bool
  operator != (const sentinel& a,const iterator& x){
    return !(x==a);
    }
  };

struct range{
  iterator start;
  sentinel finish;
  constexpr auto
  begin() const{
    return start;
    }
  constexpr auto
  end()const{
    return finish;
    }
  };

void func(int,int,int);

void test(const range& r){
  for(auto [x,y,z]: r)
    func(x,y,z);
  }
void test(int x_start,int x_end,int y_start,int y_end,int z_start,int z_end){
  for(int z=z_start;z<z_end;++z)
    for(int y=y_start;y<y_end;++y)
      for(int x=x_start;x<x_end;++x)
        func(x,y,z);
  }

Преимущество перед ответом 1201ProgramAlarm - более быстрое испытание, выполняемое на каждой итерации благодаря использованию дозорного устройства.