c++ - iterativo - iterar con matlab

¿Anexar a un vector mientras se itera sobre él?

Question

Tengo un vector sobre el que estoy iterando. Mientras itero, puedo agregar nuevos valores al vector. Parece algo así como:

struct Foo
{
   bool condition;
};

void AppendToVec(vector<Foo>& v)
{
   ...
   v.push_back(...);
}

vector<Foo> vec;
...
for (vector<Foo>::size_type i = 0; i < vec.size(); ++i)
{
   if (vec[i].condition) AppendToVec(vec);
}

Esto funciona bien, y de hecho maneja con elegancia el caso en el que los elementos recién agregados requieren recursivamente más elementos para agregar, pero se siente un poco frágil. Si alguien más viene y ajusta el bucle, puede romperse fácilmente. Por ejemplo:

//No longer iterates over newly appended elements
vector<Foo>::size_type size = vec.size();
for (vector<Foo>::size_type i = 0; i < size; ++i)
{
   if (vec[i].condition) AppendToVec(vec);
}

o

//Vector resize may invalidate iterators
for (vector<Foo>::iterator i = vec.begin(); i != vec.end(); ++i)
{
   if (vec->condition) AppendToVec(vec);
}

¿Existen mejores prácticas para manejar casos como este? Es comentar el bucle con una "Advertencia: este bucle se agrega intencionalmente al vector mientras se está iterando. ¿Cambiar con precaución" es el mejor enfoque? También estoy abierto a cambiar contenedores si eso hace que las cosas sean más robustas.

Answer 1

Si alguien más viene y ajusta el bucle, puede romperse fácilmente.

Entonces no uses un bucle for , usa un bucle while en su lugar. Para mí, un bucle for siempre implica un bucle iterativo simple utilizando un contador . Sin embargo, si encuentro un bucle de while , siento que las cosas deben haber sido demasiado complicadas para expresarlas en un bucle simple for . Miraré más de cerca y tengo más cuidado con la "optimización" de los bucles que con los bucles.

Answer 2

¿Necesita acceso aleatorio a este vector? Si no, una std::list es más apropiada. Es mi opinión personal que agregar un vector mientras se repite sobre él no es una buena idea.

Answer 3

Como se ha señalado, y como percibió, hay un problema aquí. Sin embargo, tienes varias soluciones posibles, así que no cargues a ciegas.

• Un gran comentario en la parte superior del bucle, con la etiqueta WARNING o lo que requiera su estándar de codificación, para advertir al futuro mantenedor de que hay un engaño involucrado. Mejor no usado, pero podría funcionar.
• Si puede saber de antemano cuántos elementos se agregarán (o si tiene un límite superior relativamente ajustado), puede usar la reserve y evitar la reasignación por completo.
• Utilizando un std::deque . La mayoría de las características de rendimiento son similares, sin embargo, puede añadir y añadir nuevos valores sin invalidar los iteradores / referencias, etc.
• Usando una cola separada y un bucle doble

Creo que deque es la mejor solución aquí. Se ajusta a su algoritmo y no tiene que preocuparse por los problemas. Probablemente podría reemplazar la mayor parte del vector en su código por deque . Y si no quieres cambiar la interfaz:

• Copia el vector en el deque
• Calcular
• Asignar el contenido de deque al vector

no implicará muchas más copias que simplemente reasignar el vector dos veces. Así que siéntete libre!

void treat(std::vector<int>& vec)
{
   // WARNING: we use a deque because of its iterator invalidation properties
   std::deque<int> deq(vec.begin(), vec.end());

   for (std::deque<int>::const_iterator it = deq.begin(); it != deq.end(); ++it)
   {
     if (it->condition()) deq.push_back(func(*it));
   }

   vec.assign(deq.begin(), deq.end());
}

Answer 4

Mi enfoque para este problema a menudo es crear una cola a la que agrego cualquier elemento nuevo, y luego, después de recorrer el contenedor original, procesar los elementos de la cola y / o agregarlos al original.

Los puntos positivos de este enfoque son que lo que está ocurriendo es obvio, y funciona en escenarios en los que múltiples subprocesos podrían estar agregando nuevos elementos.

Answer 5

No muy diferente del original. Solo haciendo algunas cosas explícitas aquí:

for (vector<Foo>::size_type i = 0, n = vec.size(); i < n; ++i)
  if (vec[i].condition){
    AppendToVec(vec);
    n = vec.size();
  }

Answer 6

Permita que AppendToVec actualice i si se ha reasignado vec utilizando la posición relativa en el vector anterior ( i-vec.begin() ).

Código:

void AppendToVec(vector<int> & vec, vector<int>::iterator & i)
{
    const int some_num = 1;
    const size_t diff = i-vec.begin();
    vec.push_back(some_num);
    i = vec.begin()+diff;
}

int main(int argc, char* argv[])
{    
     const size_t arbit_size = 10;
     const size_t prior_size = 3;
     vector<int> vec;

     // Fill it up with something
     for(size_t i = 0; i < prior_size; ++i) vec.push_back(static_cast<int>(i));

     // Iterate over appended elements
     vector<int>::iterator i = vec.begin();
     while(i != vec.end())
     {
      cout<<*i<<","<<vec.size()<<endl;
      if(vec.size()<arbit_size) AppendToVec(vec,i);
      ++i;
     }

     return 0;
}

Salida:

0,3
1,4
2,5
1,6
1,7
1,8
1,9
1,10
1,10
1,10

Answer 7

Puede adjuntar a un deque sin invalidar los iteradores a sus elementos. El acceso aleatorio está cerca de la eficiencia del vector, por lo que a menudo es una buena opción para reemplazarlo.

Answer 8

Un comentario en línea es a menudo suficiente para aclarar esto, por ejemplo

for (vector<Foo>::size_type i = 0; i < vec.size() /* size grows in loop! */; ++i)
{
   if (vec[i].condition) AppendToVec(vec);
}