c++ - patron - recorrer un arraylist de objetos en java




Combinando múltiples bucles for en un solo iterador (5)

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.

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?


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

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


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.


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.







c++14