Maneras limpias de escribir múltiples bucles 'for'

98

Para una matriz con múltiples dimensiones, generalmente necesitamos escribir un forbucle para cada una de sus dimensiones. Por ejemplo:

vector< vector< vector<int> > > A;

for (int k=0; k<A.size(); k++)
{
    for (int i=0; i<A[k].size(); i++)
    {
        for (int j=0; j<A[k][i].size(); j++)
        {
            do_something_on_A(A[k][i][j]);
        }
    }
}

double B[10][8][5];
for (int k=0; k<10; k++)
{
    for (int i=0; i<8; i++)
    {
        for (int j=0; j<5; j++)
        {
            do_something_on_B(B[k][i][j]);
        }
    }
}

Ves este tipo de for-for-forbucles en nuestro código con frecuencia. ¿Cómo utilizo macros para definir los for-for-forbucles para no tener que volver a escribir este tipo de código cada vez? ¿Hay una mejor manera de hacer esto?

C. Wang
fuente
62
La respuesta obvia es que no es así. No crea un nuevo idioma usando macros (o cualquier otra técnica); la persona que viene después de usted no podrá leer el código.
James Kanze
17
Cuando tienes un vector de un vector de un vector, eso es una señal de mal diseño.
Maroun
5
@Nim: Puede hacerlo con 1 matriz plana (no estoy seguro de que sea mejor).
Jarod42
16
Creo que no querrás ocultar el O(n) = n^3código potencial ...
poy
36
@ TC1: Y luego me resultará más difícil leer. Todo es una cuestión de preferencias personales y en realidad no ayuda con la pregunta en cuestión aquí.
ereOn

Respuestas:

281

Lo primero es que no usa esa estructura de datos. Si necesita una matriz tridimensional, defina una:

class Matrix3D
{
    int x;
    int y;
    int z;
    std::vector<int> myData;
public:
    //  ...
    int& operator()( int i, int j, int k )
    {
        return myData[ ((i * y) + j) * z + k ];
    }
};

O si desea indexar usando [][][], necesita un operator[] que devuelva un proxy.

Una vez que haya hecho esto, si descubre que tiene que iterar constantemente como ha presentado, expone un iterador que lo admitirá:

class Matrix3D
{
    //  as above...
    typedef std::vector<int>::iterator iterator;
    iterator begin() { return myData.begin(); }
    iterator end()   { return myData.end();   }
};

Entonces solo escribe:

for ( Matrix3D::iterator iter = m.begin(); iter != m.end(); ++ iter ) {
    //  ...
}

(o solo:

for ( auto& elem: m ) {
}

si tiene C ++ 11.)

Y si necesita los tres índices durante tales iteraciones, es posible crear un iterador que los exponga:

class Matrix3D
{
    //  ...
    class iterator : private std::vector<int>::iterator
    {
        Matrix3D const* owner;
    public:
        iterator( Matrix3D const* owner,
                  std::vector<int>::iterator iter )
            : std::vector<int>::iterator( iter )
            , owner( owner )
        {
        }
        using std::vector<int>::iterator::operator++;
        //  and so on for all of the iterator operations...
        int i() const
        {
            ((*this) -  owner->myData.begin()) / (owner->y * owner->z);
        }
        //  ...
    };
};
James Kanze
fuente
21
Esta respuesta debería ser mucho más votada, ya que es la única que se ocupa del origen real del problema.
ereOn
5
Puede que sea la respuesta correcta, pero no estoy de acuerdo en que sea buena. muchos códigos de plantilla crípticos con un tiempo de compilación probablemente x10 veces más lento y probablemente x10 código de depuración lenta (puede ser más). Para mí, definitivamente el código original es mucho más claro para mí ...
Gorkem
10
@beehorf ... y también mucho, mucho más lento. Porque las matrices multidimensionales en C y C ++ son en realidad matrices anidadas en el sentido de que las dimensiones externas almacenan punteros a las matrices anidadas. Luego, estas matrices anidadas se dispersan arbitrariamente en la memoria, lo que elimina de manera efectiva cualquier captura previa y almacenamiento en caché. Conozco ejemplos en los que alguien escribió un código utilizando vector<vector<vector<double> > >para representar un campo tridimensional. Reescribir el código, el equivalente a la solución anterior, resultó en una aceleración de 10.
Michael Wild
5
@beehorf ¿Dónde ves algún código de plantilla? (En la práctica, Matrix3Dprobablemente debería ser una plantilla, pero es una plantilla muy sencilla). Y solo tiene que depurar Matrix3D, no siempre que necesite una matriz 3D, por lo que ahorra una enorme cantidad de tiempo en la depuración. En cuanto a la claridad: ¿cómo es std::vector<std::vector<std::vector<int>>>más claro que Matrix3D? Sin mencionar que Matrix3Drefuerza el hecho de que tiene una matriz, mientras que los vectores anidados podrían ser irregulares, y que lo anterior probablemente sea significativamente más rápido.
James Kanze
10
@MichaelWild Pero, por supuesto, la ventaja real de mi enfoque es que puede cambiar la representación, dependiendo de lo que sea más rápido en su entorno, sin tener que modificar el código del cliente. La clave para un buen rendimiento es la encapsulación adecuada, de modo que pueda realizar los cambios que el generador de perfiles dice que necesita sin tener que volver a escribir toda la aplicación.
James Kanze
44

Usar una macro para ocultar los forbucles puede ser muy confuso, solo para guardar algunos caracteres. En su lugar, usaría bucles de rango para :

for (auto& k : A)
    for (auto& i : k)
        for (auto& j : i)
            do_something_on_A(j);

Por supuesto, puede reemplazar auto&con const auto&si, de hecho, no está modificando los datos.

Zapato
fuente
3
Suponiendo que OP pueda usar C ++ 11.
Jarod42
1
@herohuyongtao En el caso de iteradores. Lo que puede ser más idiomático aquí, pero hay casos en los que querrías las tres intvariables.
James Kanze
1
¿Y no debería ser así do_something_on_A(*j)?
James Kanze
1
@Jefffrey Ah, sí. Otra razón para deletrear el tipo. (Supongo que el uso de autofor ky ipuede estar justificado. Excepto que todavía resuelve el problema en el nivel incorrecto; el problema real es que está usando los vectores anidados.)
James Kanze
2
@Dhara kes un vector completo de vectores (bueno, una referencia a él), no un índice.
Yakk - Adam Nevraumont
21

Algo como esto puede ayudar:

 template <typename Container, typename Function>
 void for_each3d(const Container &container, Function function)
 {
     for (const auto &i: container)
         for (const auto &j: i)
             for (const auto &k: j)
                 function(k);
 }

 int main()
 {
     vector< vector< vector<int> > > A;     
     for_each3d(A, [](int i){ std::cout << i << std::endl; });

     double B[10][8][5] = { /* ... */ };
     for_each3d(B, [](double i){ std::cout << i << std::endl; });
 }

Para hacerlo N-ary, necesitamos algo de magia de plantilla. En primer lugar debemos crear la estructura SFINAE para distinguir si este valor o contenedor. La implementación predeterminada para valores y especializaciones para matrices y cada uno de los tipos de contenedor. Como señala @Zeta, podemos determinar los contenedores estándar por el iteratortipo anidado (idealmente deberíamos verificar si el tipo se puede usar con range-base foro no).

 template <typename T>
 struct has_iterator
 {
     template <typename C>
     constexpr static std::true_type test(typename C::iterator *);

     template <typename>
     constexpr static std::false_type test(...);

     constexpr static bool value = std::is_same<
         std::true_type, decltype(test<typename std::remove_reference<T>::type>(0))
     >::value;
 };

 template <typename T>
 struct is_container : has_iterator<T> {};

 template <typename T>
 struct is_container<T[]> : std::true_type {};

 template <typename T, std::size_t N>
 struct is_container<T[N]> : std::true_type {}; 

 template <class... Args>
 struct is_container<std::vector<Args...>> : std::true_type {};

La implementación de for_eaches sencilla. La función predeterminada llamará function:

 template <typename Value, typename Function>
 typename std::enable_if<!is_container<Value>::value, void>::type
 rfor_each(const Value &value, Function function)
 {
     function(value);
 }

Y la especialización se llamará a sí misma de forma recursiva:

 template <typename Container, typename Function>
 typename std::enable_if<is_container<Container>::value, void>::type
 rfor_each(const Container &container, Function function)
 {
     for (const auto &i: container)
         rfor_each(i, function);
 }

Y voilá:

 int main()
 {
     using namespace std;
     vector< vector< vector<int> > > A;
     A.resize(3, vector<vector<int> >(3, vector<int>(3, 5)));
     rfor_each(A, [](int i){ std::cout << i << ", "; });
     // 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,

     std::cout << std::endl;
     double B[3][3] = { { 1. } };
     rfor_each(B, [](double i){ std::cout << i << ", "; });
     // 1, 0, 0, 0, 0, 0, 0, 0, 0,
 }

Además, esto no funcionará para punteros (matrices asignadas en el montón).

fasked
fuente
@herohuyongtao con restricciones podemos implementar dos especializaciones para Containery para otros.
enviado el
1
@herohuyongtao Hice un ejemplo de K-ary foreach.
Fasked
1
@fasked: Use is_container : has_iterator<T>::valuede mi respuesta y no necesita escribir una especialización para cada tipo, ya que cada contenedor debe tener un iteratortypedef. Siéntase libre de usar completamente cualquier cosa de mi respuesta, la suya ya es mejor.
Zeta
@Zeta +1 para esto. Además, como mencioné, el Containerconcepto ayudará.
enviado el
::iteratorno hace un rango iterable. int x[2][3][4]es perfectamente iterable, ya struct foo { int x[3]; int* begin() { return x; } int* end() { return x+3; } }; que no estoy seguro de qué T[]se supone que debe hacer la especialización.
Yakk - Adam Nevraumont
17

La mayoría de las respuestas simplemente demuestran cómo C ++ se puede convertir en extensiones sintácticas incomprensibles, en mi humilde opinión.

Al definir cualquier plantilla o macros, simplemente obliga a otros programadores a comprender fragmentos de código ofuscado diseñados para ocultar otros fragmentos de código ofuscado.
Obligará a cada persona que lea su código a tener experiencia en plantillas, solo para evitar hacer su trabajo de definir objetos con una semántica clara.

Si decidió utilizar datos sin procesar como matrices tridimensionales, simplemente viva con ellos o defina una clase que dé un significado comprensible a sus datos.

for (auto& k : A)
for (auto& i : k)
for (auto& current_A : i)
    do_something_on_A(current_A);

es simplemente consistente con la definición críptica de un vector de vector de vector de int sin semántica explícita.

kuroi neko
fuente
10
#include "stdio.h"

#define FOR(i, from, to)    for(int i = from; i < to; ++i)
#define TRIPLE_FOR(i, j, k, i_from, i_to, j_from, j_to, k_from, k_to)   FOR(i, i_from, i_to) FOR(j, j_from, j_to) FOR(k, k_from, k_to)

int main()
{
    TRIPLE_FOR(i, j, k, 0, 3, 0, 4, 0, 2)
    {
        printf("i: %d, j: %d, k: %d\n", i, j, k);
    }
    return 0;
}

ACTUALIZACIÓN: Sé que lo solicitó, pero es mejor que no lo use :)

FreeNickname
fuente
5
Sé que eso es lo que pidió el OP, pero en serio ... Esto parece un maravilloso ejemplo de ofuscación. Suponiendo que TRIPLE_FORse definieran en algún encabezado, ¿qué debo pensar cuando vea `TRIPLE_FOR aquí?
James Kanze
2
Sí, supongo que tienes razón :) Creo que lo dejaré aquí solo como un ejemplo de que esto se puede hacer usando macros, pero agregue una nota de que es mejor no hacerlo así :) Acabo de despertar y decidió utilizar esta pregunta como un pequeño calentamiento de la mente.
FreeNickname
5

Una idea es escribir una clase de pseudocontenedor iterable que "contenga" el conjunto de todas las tuplas de índices múltiples sobre las que indexará. No hay implementación aquí porque tomará demasiado tiempo, pero la idea es que debería poder escribir ...

multi_index mi (10, 8, 5);
  //  The pseudo-container whose iterators give {0,0,0}, {0,0,1}, ...

for (auto i : mi)
{
  //  In here, use i[0], i[1] and i[2] to access the three index values.
}
Steve314
fuente
la mejor respuesta aquí en mi opinión.
Davidhigh
4

Veo muchas respuestas aquí que funcionan de forma recursiva, detectando si la entrada es un contenedor o no. En cambio, ¿por qué no detectar si la capa actual es del mismo tipo que la función? Es mucho más simple y permite funciones más potentes:

//This is roughly what we want for values
template<class input_type, class func_type> 
void rfor_each(input_type&& input, func_type&& func) 
{ func(input);}

//This is roughly what we want for containers
template<class input_type, class func_type>
void rfor_each(input_type&& input, func_type&& func) 
{ for(auto&& i : input) rfor_each(i, func);}

Sin embargo, esto (obviamente) nos da errores de ambigüedad. Entonces usamos SFINAE para detectar si la entrada actual encaja en la función o no

//Compiler knows to only use this if it can pass input to func
template<class input_type, class func_type>
auto rfor_each(input_type&& input, func_type&& func) ->decltype(func(input)) 
{ return func(input);}

//Otherwise, it always uses this one
template<class input_type, class func_type>
void rfor_each(input_type&& input, func_type&& func) 
{ for(auto&& i : input) rfor_each(i, func);}

Esto ahora maneja los contenedores correctamente, pero el compilador aún lo considera ambiguo para input_types que se pueden pasar a la función. Entonces usamos un truco estándar de C ++ 03 para hacer que prefiera la primera función sobre la segunda, de pasar también un cero, y hacer que la que preferimos acepte e int, y la otra tome ...

template<class input_type, class func_type>
auto rfor_each(input_type&& input, func_type&& func, int) ->decltype(func(input)) 
{ return func(input);}

//passing the zero causes it to look for a function that takes an int
//and only uses ... if it absolutely has to 
template<class input_type, class func_type>
void rfor_each(input_type&& input, func_type&& func, ...) 
{ for(auto&& i : input) rfor_each(i, func, 0);}

Eso es. Seis líneas de código relativamente simples, y puede iterar sobre valores, filas o cualquier otra subunidad, a diferencia de todas las demás respuestas.

#include <iostream>
int main()
 {

     std::cout << std::endl;
     double B[3][3] = { { 1.2 } };
     rfor_each(B[1], [](double&v){v = 5;}); //iterate over doubles
     auto write = [](double (&i)[3]) //iterate over rows
         {
             std::cout << "{";
             for(double d : i) 
                 std::cout << d << ", ";
             std::cout << "}\n";
         };
     rfor_each(B, write );
 };

Prueba de compilación y ejecución aquí y aquí

Si desea una sintaxis más conveniente en C ++ 11, puede agregar una macro. (Lo siguiente no está probado)

template<class container>
struct container_unroller {
    container& c;
    container_unroller(container& c_) :c(c_) {}
    template<class lambda>
    void operator <=(lambda&& l) {rfor_each(c, l);}
};
#define FOR_NESTED(type, index, container) container_unroller(container) <= [](type& index) 
//note that this can't handle functions, function pointers, raw arrays, or other complex bits

int main() {
     double B[3][3] = { { 1.2 } };
     FOR_NESTED(double, v, B) {
         std::cout << v << ", ";
     }
}
Pato morando
fuente
3

Advierto esta respuesta con la siguiente declaración: esto solo funcionaría si estuviera operando en una matriz real ; no funcionaría para su ejemplo usando std::vector.

Si está realizando la misma operación en cada elemento de una matriz multidimensional, sin preocuparse por la posición de cada elemento, puede aprovechar el hecho de que las matrices se colocan en ubicaciones de memoria contiguas y tratar todo como una gran matriz unidimensional. Por ejemplo, si quisiéramos multiplicar cada elemento por 2.0 en su segundo ejemplo:

double B[3][3][3];
// ... set the values somehow
double* begin = &B[0][0][0];     // get a pointer to the first element
double* const end = &B[3][0][0]; // get a (const) pointer past the last element
for (; end > begin; ++begin) {
    (*begin) *= 2.0;
}

Tenga en cuenta que el uso del enfoque anterior también permite el uso de algunas técnicas de C ++ "adecuadas":

double do_something(double d) {
    return d * 2.0;
}

...

double B[3][3][3];
// ... set the values somehow
double* begin = &B[0][0][0];  // get a pointer to the first element
double* end = &B[3][0][0];    // get a pointer past the last element

std::transform(begin, end, begin, do_something);

Yo no aconsejo este enfoque general (prefiriendo algo así como la respuesta de Jefffrey), ya que se basa en tener tamaños definidos para sus matrices, pero en algunos casos puede ser útil.

icabod
fuente
Esto es ilegal: stackoverflow.com/questions/6015080/…
ecatmur
@ecatmur: Interesante: acabo de empezar a trabajar, así que revisaré esto y actualizaré / eliminaré la respuesta en consecuencia. Gracias.
icabod
@ecatmur: He examinado el estándar C ++ 11 (sección 8.3.4), y lo que he escrito debería funcionar y no me parece ilegal (para mí). El enlace que proporcionó se relaciona con el acceso a miembros fuera del tamaño de matriz definido. Si bien es cierto que obtengo la dirección de justo después de la matriz, no está accediendo a los datos; esto es para proporcionar un "final", de la misma manera que puede usar punteros como iteradores, siendo "final" uno pasado el último elemento.
icabod
Estás efectivamente el acceso B[0][0][i]a i >= 3; esto no está permitido ya que está accediendo fuera de la matriz (interna).
ecatmur
1
En mi opinión, una forma más clara de asignar el final SI tuviera que hacer esto es end = start + (xSize * ySize * zSize)
noggin182
2

Me sorprendió un poco que nadie propusiera algún bucle basado en aritmética-magia para hacer el trabajo. Dado que C. Wang está buscando una solución sin bucles anidados , propondré una:

double B[10][8][5];
int index = 0;

while (index < (10 * 8 * 5))
{
    const int x = index % 10,
              y = (index / 10) % 10,
              z = index / 100;

    do_something_on_B(B[x][y][z]);
    ++index;
}

Bueno, este enfoque no es elegante y flexible, por lo que podríamos empaquetar todo el proceso en una función de plantilla:

template <typename F, typename T, int X, int Y, int Z>
void iterate_all(T (&xyz)[X][Y][Z], F func)
{
    const int limit = X * Y * Z;
    int index = 0;

    while (index < limit)
    {
        const int x = index % X,
                  y = (index / X) % Y,
                  z = index / (X * Y);

        func(xyz[x][y][z]);
        ++index;
    }
}

Esta función de plantilla también se puede expresar en forma de bucles anidados:

template <typename F, typename T, int X, int Y, int Z>
void iterate_all(T (&xyz)[X][Y][Z], F func)
{
    for (auto &yz : xyz)
    {
        for (auto &z : yz)
        {
            for (auto &v : z)
            {
                func(v);
            }
        }
    }
}

Y se puede utilizar proporcionando una matriz 3D de tamaño arbitrario más el nombre de la función, dejando que la deducción del parámetro haga el trabajo duro de contar el tamaño de cada dimensión:

int main()
{
    int A[10][8][5] = {{{0, 1}, {2, 3}}, {{4, 5}, {6, 7}}};
    int B[7][99][8] = {{{0, 1}, {2, 3}}, {{4, 5}, {6, 7}}};

    iterate_all(A, do_something_on_A);
    iterate_all(B, do_something_on_B);

    return 0;
}

Hacia más genérico

Pero una vez más, carece de flexibilidad porque solo funciona para matrices 3D, pero usando SFINAE podemos hacer el trabajo para matrices de una dimensión arbitraria, primero necesitamos una función de plantilla que itera matrices de rango 1:

template<typename F, typename A>
typename std::enable_if< std::rank<A>::value == 1 >::type
iterate_all(A &xyz, F func)
{
    for (auto &v : xyz)
    {
        func(v);
    }
}

Y otro que itera matrices de cualquier rango, haciendo la recursividad:

template<typename F, typename A>
typename std::enable_if< std::rank<A>::value != 1 >::type
iterate_all(A &xyz, F func)
{
    for (auto &v : xyz)
    {
        iterate_all(v, func);
    }
}

Esto nos permite iterar todos los elementos en todas las dimensiones de una matriz de tamaño arbitrario de dimensiones arbitrarias.


Trabajando con std::vector

Para el vector anidado múltiple, la solución se asemeja a la de una matriz de tamaño arbitrario de dimensiones arbitrarias, pero sin SFINAE: Primero necesitaremos una función de plantilla que itera std::vectorsy llama a la función deseada:

template <typename F, typename T, template<typename, typename> class V>
void iterate_all(V<T, std::allocator<T>> &xyz, F func)
{
    for (auto &v : xyz)
    {
        func(v);
    }
}

Y otra función de plantilla que itera cualquier tipo de vector de vectores y se llama a sí mismo:

template <typename F, typename T, template<typename, typename> class V> 
void iterate_all(V<V<T, std::allocator<T>>, std::allocator<V<T, std::allocator<T>>>> &xyz, F func)
{
    for (auto &v : xyz)
    {
        iterate_all(v, func);
    }
}

Independientemente del nivel de anidamiento, iterate_allllamará a la versión de vector de vectores a menos que la versión de vector de valores sea una mejor coincidencia, poniendo así fin a la recursividad.

int main()
{
    using V0 = std::vector< std::vector< std::vector<int> > >;
    using V1 = std::vector< std::vector< std::vector< std::vector< std::vector<int> > > > >;

    V0 A0 =   {{{0, 1}, {2, 3}}, {{4, 5}, {6, 7}}};
    V1 A1 = {{{{{9, 8}, {7, 6}}, {{5, 4}, {3, 2}}}}};

    iterate_all(A0, do_something_on_A);
    iterate_all(A1, do_something_on_A);

    return 0;
}

Creo que el cuerpo de la función es bastante simple y directo ... Me pregunto si el compilador podría desenrollar estos bucles (estoy casi seguro de que la mayoría de los compiladores podrían desenrollar el primer ejemplo).

Vea la demostración en vivo aquí .

Espero eso ayude.

PaperBirdMaster
fuente
1

Use algo en esta línea (su pseudocódigo, pero la idea sigue siendo la misma). Extrae el patrón para que se repita una vez y aplica una función diferente cada vez.

doOn( structure A, operator o)
{
    for (int k=0; k<A.size(); k++)
    {
            for (int i=0; i<A[k].size(); i++)
            {
                for (int j=0; j<A[k][i].size(); j++)
                {
                        o.actOn(A[k][i][j]);
                }
            }
    }
}

doOn(a, function12)
doOn(a, function13)
RobAu
fuente
1

¡Quédate con los bucles for anidados!

Todos los métodos sugeridos aquí tienen desventajas en términos de legibilidad o flexibilidad.

¿Qué sucede si necesita utilizar los resultados de un ciclo interno para el procesamiento en el ciclo externo? ¿Qué sucede si necesita un valor del ciclo externo dentro de su ciclo interno? La mayoría de los métodos de "encapsulación" fallan aquí.

Créame, he visto varios intentos de "limpiar" los bucles for anidados y, al final, resulta que el bucle anidado es en realidad la solución más limpia y flexible.

James Anderson
fuente
0

Una técnica que he usado son las plantillas. P.ej:

template<typename T> void do_something_on_A(std::vector<T> &vec) {
    for (auto& i : vec) { // can use a simple for loop in C++03
        do_something_on_A(i);
    }
}

void do_something_on_A(int &val) {
    // this is where your `do_something_on_A` method goes
}

Luego, simplemente llame do_something_on_A(A)a su código principal. La función de plantilla se crea una vez para cada dimensión, la primera vez con T = std::vector<std::vector<int>>, la segunda vez con conT = std::vector<int> .

Puede hacer esto más genérico usando std::function(u objetos similares a funciones en C ++ 03) como un segundo argumento si lo desea:

template<typename T> void do_something_on_vec(std::vector<T> &vec, std::function &func) {
    for (auto& i : vec) { // can use a simple for loop in C++03
        do_something_on_vec(i, func);
    }
}

template<typename T> void do_something_on_vec(T &val, std::function &func) {
    func(val);
}

Entonces llámalo como:

do_something_on_vec(A, std::function(do_something_on_A));

Esto funciona a pesar de que las funciones tienen la misma firma porque la primera función coincide mejor con cualquier elemento std::vectordel tipo.

JoshG79
fuente
0

Podría generar índices en un ciclo como este (A, B, C son dimensiones):

int A = 4, B = 3, C = 3;
for(int i=0; i<A*B*C; ++i)
{
    int a = i/(B*C);
    int b = (i-((B*C)*(i/(B*C))))/C;
    int c = i%C;
}
janek
fuente
Estoy de acuerdo contigo, está diseñado específicamente para 3 dimensiones;)
janek
1
¡Sin mencionar que es increíblemente lento!
noggin182
@ noggin182: la pregunta no era sobre velocidad, sino sobre evitar bucles for anidados; además, hay divisiones innecesarias allí, i / (B * C) se puede reemplazar por a
janek
Ok, esta es una forma alternativa, probablemente más eficiente (javascript): for (var i = 0, j = 0, k = 0; i <A; i + = (j == B-1 && k == C - 1)? 1: 0, j = (k == C - 1)? ((J == B-1)? 0: j + 1): j, k = (k == C - 1)? 0: k + 1) {consola.log (i + "" + j + "" + k); }
janek
0

Una cosa que puede querer probar si solo tiene declaraciones en el bucle más interno, y su preocupación es más sobre la naturaleza demasiado detallada del código, es usar un esquema de espacios en blanco diferente. Esto solo funcionará si puede indicar sus bucles for de manera lo suficientemente compacta como para que quepan en una línea.

Para su primer ejemplo, lo reescribiría como:

vector< vector< vector<int> > > A;
int i,j,k;
for(k=0;k<A.size();k++) for(i=0;i<A[k].size();i++) for(j=0;j<A[k][i].size();j++) {
    do_something_on_A(A[k][i][j]);
}

Esto es un poco empujarlo porque está llamando a funciones en los bucles externos, lo que equivale a poner declaraciones en ellos. He eliminado todos los espacios en blanco innecesarios y es posible que sea aceptable.

El segundo ejemplo es mucho mejor:

double B[10][8][5];
int i,j,k;

for(k=0;k<10;k++) for(i=0;i<8;i++) for(j=0;j<5;j++) {
    do_something_on_B(B[k][i][j]);
}

Esta puede ser una convención de espacios en blanco diferente a la que le gusta usar, pero logra un resultado compacto que, sin embargo, no requiere ningún conocimiento más allá de C / C ++ (como las convenciones de macros) y no requiere ningún truco como las macros.

Si realmente desea una macro, puede dar un paso más con algo como:

#define FOR3(a,b,c,d,e,f,g,h,i) for(a;b;c) for(d;e;f) for(g;h;i)

lo que cambiaría el segundo ejemplo a:

double B[10][8][5];
int i,j,k;

FOR3(k=0,k<10,k++,i=0,i<8,i++,j=0,j<5,j++) {
    do_something_on_B(B[k][i][j]);
}

y al primer ejemplo también le va mejor:

vector< vector< vector<int> > > A;
int i,j,k;
FOR3(k=0,k<A.size(),k++,i=0,i<A[k].size(),i++,j=0,j<A[k][i].size(),j++) {
    do_something_on_A(A[k][i][j]);
}

Es de esperar que pueda decir con bastante facilidad qué declaraciones van con cada declaración. Además, tenga cuidado con las comas, ahora no puede usarlas en una sola cláusula de ninguna de las fors.

Miguel
fuente
1
La legibilidad de estos es horrible. Atascar más de un forbucle en una línea no lo hace más legible, lo hace menos .
0

Aquí hay una implementación de C ++ 11 que maneja todo lo iterable. Otras soluciones se limitan a contenedores con ::iteratortypedefs o matrices: pero a for_eachse trata de iteración, no de contenedor.

También aíslo el SFINAE en un solo punto del is_iterablerasgo. El envío (entre elementos e iterables) se realiza mediante el envío de etiquetas, que encuentro es una solución más clara.

Los contenedores y las funciones aplicadas a los elementos están perfectamente reenviados, permitiendo tanto el acceso constcomo no consta las gamas y functores.

#include <utility>
#include <iterator>

La función de plantilla que estoy implementando. Todo lo demás podría entrar en un espacio de nombres de detalles:

template<typename C, typename F>
void for_each_flat( C&& c, F&& f );

El envío de etiquetas es mucho más limpio que SFINAE. Estos dos se utilizan para objetos iterables y objetos no iterables respectivamente. La última iteración de la primera podría usar un reenvío perfecto, pero soy vago:

template<typename C, typename F>
void for_each_flat_helper( C&& c, F&& f, std::true_type /*is_iterable*/ ) {
  for( auto&& x : std::forward<C>(c) )
    for_each_flat(std::forward<decltype(x)>(x), f);
}
template<typename D, typename F>
void for_each_flat_helper( D&& data, F&& f, std::false_type /*is_iterable*/ ) {
  std::forward<F>(f)(std::forward<D>(data));
}

Esta es una repetición necesaria para escribir is_iterable. Hago una búsqueda dependiente de argumentos en beginy enden un espacio de nombres detallado. Esto emula lo que un for( auto x : y )bucle hace razonablemente bien:

namespace adl_aux {
  using std::begin; using std::end;
  template<typename C> decltype( begin( std::declval<C>() ) ) adl_begin(C&&);
  template<typename C> decltype( end( std::declval<C>() ) ) adl_end(C&&);
}
using adl_aux::adl_begin;
using adl_aux::adl_end;

El TypeSinkes útil para probar si el código es válido. Hace el TypeSink< decltype(código ) >y si codees válido, la expresión es void. Si el código no es válido, SFINAE entra en acción y la especialización se bloquea:

template<typename> struct type_sink {typedef void type;};
template<typename T> using TypeSink = typename type_sink<T>::type;

template<typename T, typename=void>
struct is_iterable:std::false_type{};
template<typename T>
struct is_iterable<T, TypeSink< decltype( adl_begin( std::declval<T>() ) ) >>:std::true_type{};

Solo pruebo begin. También se adl_endpodría hacer una prueba.

La implementación final de for_each_flattermina siendo extremadamente simple:

template<typename C, typename F>
void for_each_flat( C&& c, F&& f ) {
  for_each_flat_helper( std::forward<C>(c), std::forward<F>(f), is_iterable<C>() );
}        

Ejemplo vivo

Esto está muy abajo en la parte inferior: siéntase libre de buscar las respuestas principales, que son sólidas. ¡Solo quería que se usaran algunas técnicas mejores!

Yakk - Adam Nevraumont
fuente
-2

En primer lugar, no debería utilizar un vector de vectores de vectores. Se garantiza que cada vector tiene memoria contigua, pero la memoria "global" de un vector de vectores no lo es (y probablemente no lo será). También debe usar la matriz de tipo de biblioteca estándar en lugar de las matrices de estilo C.

using std::array;

array<array<array<double, 5>, 8>, 10> B;
for (int k=0; k<10; k++)
    for (int i=0; i<8; i++)
        for (int j=0; j<5; j++)
            do_something_on_B(B[k][i][j]);

// or, if you really don't like that, at least do this:

for (int k=0; k<10; k++) {
    for (int i=0; i<8; i++) {
        for (int j=0; j<5; j++) {
            do_something_on_B(B[k][i][j]);
        }
    }
}

Sin embargo, mejor aún, podría definir una clase de matriz 3D simple:

#include <stdexcept>
#include <array>

using std::size_t;

template <size_t M, size_t N, size_t P>
class matrix3d {
    static_assert(M > 0 && N > 0 && P > 0,
                  "Dimensions must be greater than 0.");
    std::array<std::array<std::array<double, P>, N>, M> contents;
public:
    double& at(size_t i, size_t j, size_t k)
    { 
        if (i >= M || j >= N || k >= P)
            throw out_of_range("Index out of range.");
        return contents[i][j][k];
    }
    double& operator(size_t i, size_t j, size_t k)
    {
        return contents[i][j][k];
    }
};

int main()
{
    matrix3d<10, 8, 5> B;
        for (int k=0; k<10; k++)
            for (int i=0; i<8; i++)
                for (int j=0; j<5; j++)
                    do_something_on_B(B(i,j,k));
    return 0;
}

Podrías ir más allá y hacerlo completamente const-correcto, agregar multiplicación de matrices (propia y de elementos), multiplicación por vectores, etc. Incluso podrías generalizarlo a diferentes tipos (lo haría una plantilla si usa principalmente dobles) .

También puede agregar objetos proxy para poder hacer B [i] o B [i] [j]. ¿Podrían devolver vectores (en el sentido matemático) y matrices llenas de doble &, potencialmente?

Miles Rout
fuente