c++ - patron - recorrer list<> java

Combinando múltiples bucles for en un solo iterador

Question

Digamos que tengo un nido para bucle como

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

y quisiera transformarlo en

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

¿Cómo escribiría la clase MyRange para que sea tan eficiente como la anidada para los bucles? La motivación para esto es poder usar algoritmos estándar (como transformar, acumular, etc.) y crear código que sea en gran medida agnóstico a la dimensión.

Al tener un iterador, sería fácil crear funciones de plantilla que funcionen en un rango de puntos 1d, 2d o 3d.

El código base es actualmente C ++ 14.

EDITAR:

Escribir preguntas claras es difícil. Voy a tratar de aclarar. Mi problema no es escribir un iterador, eso puedo hacerlo. En cambio, el problema es uno de rendimiento: ¿es posible hacer un iterador que sea tan rápido como el anidado para bucles?

Answer 1

Aquí hay una implementación básica que no utiliza ninguna función de lenguaje avanzado ni otras bibliotecas. El rendimiento debe estar bastante cerca de la versión de bucle for.

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

Y un ejemplo de uso:

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

He dejado cosas como constadores, posibles operator+= , decremento, post-incremento, etc. Se han dejado como un ejercicio para el lector.

Almacena los valores iniciales, luego incrementa cada valor a su vez, revirtiéndolos e incrementando el siguiente cuando llega al valor final. Es un poco como incrementar un número de varios dígitos.

Answer 2

Con range/v3 , puedes hacer

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

Answer 3

Otra opción, que trasplanta directamente cualquier código de bucle, es usar un Coroutine . Esto emula el yield de Python o C #.

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

Answer 4

Puedes introducir tu propia clase como

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;

}

y luego inicialice un std::vector<myClass> con su triple bucle

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

Finalmente, puedes usar todos los algoritmos std::vector<myClass> myVec agradables con el std::vector<myClass> myVec . Con el azúcar sintáctico.

using MyRange = std::vector<MyClass>;

y

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

puedes escribir

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

Con la nueva semántica de movimientos, esto no creará copias innecesarias. Tenga en cuenta que la interfaz de esta función es bastante mala. Quizás prefiera usar 3 pares de int, que denotan el intervalo x, y, z

Quizás cambies los nombres a algo significativo (por ejemplo, mi clase podría ser Punto).

Answer 5

Solo una versión muy simplificada que será tan eficiente como un bucle 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);
  }

La ventaja sobre 1201ProgramAlarm es la prueba más rápida que se realiza en cada iteración gracias al uso de un centinela.

Answer 6

Usando boost::iterator_facade para simplificar, puedes deletrear todos los miembros requeridos.

Primero tenemos una clase que itera índices N-dimensionales como 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;
}

Luego lo usamos para hacer algo similar a boost::zip_iterator , pero en lugar de avanzar todos juntos, agregamos nuestros índices.

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

Luego lo envolvemos en un 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;
}

Véalo en Godbolt

Answer 7

Ya que te preocupas por el rendimiento, debes olvidarte de combinar iteradores en el futuro inmediato. El problema central es que los compiladores aún no pueden desenredar el desorden y descubrir que hay 3 variables independientes en él, y mucho menos realizar cualquier intercambio de bucle o desenrollarse o fusionarse.

Si debe usar rangos, use unos simples que el compilador pueda ver a través de:

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

Alternativamente, puedes pasar tu functor y los rangos de impulso a una plantilla:

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

Si realmente te importa el rendimiento, entonces no deberías contorsionar tu código con rangos complicados, ya que hacen que sea más difícil de desentrañar más tarde cuando quieras reescribirlos en los intrínsecos AVX.