Добавляем к вектору, итерации по нему?

У меня есть вектор, который я повторяю. Во время итерации я могу добавлять новые значения к вектору. Это выглядит примерно так:

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

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

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

или

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

Есть ли какие-либо рекомендации по работе с такими случаями? Комментирует цикл с помощью "Предупреждение: этот цикл намеренно присоединяется к вектору во время итерации. Измените осторожно" лучший подход? Я открыт для переключения контейнеров, если это делает вещи более надежными.

Ответ 1

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

Хорошим моментом для этого подхода является то, что происходящее очевидно, и оно работает в сценариях, где несколько потоков могут захватывать новые элементы.

Ответ 2

Если кто-то еще подходит и настраивает петлю, ее можно легко сломать.

Затем не использовать цикл for, вместо этого используйте цикл while. Для меня цикл a for всегда подразумевает простой итеративный цикл с использованием счетчика. Однако, если я столкнулся с циклом while, я чувствую, что все должно быть слишком сложно, чтобы выразить их в простом цикле for. Я посмотрю поближе, и я буду более осторожен с циклами "оптимизация" while, чем с циклами for.

Ответ 3

Разрешить AppendToVec обновлять i, если vec было перераспределено с использованием относительной позиции в старом векторе (i-vec.begin()).

Код:

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

Вывод:

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

Ответ 4

Как уже отмечалось, и как вы поняли, здесь есть проблема. У вас есть несколько возможных решений, поэтому не платите вслепую.

Большой толстый комментарий в верхней части цикла с тегом WARNING или любым другим вашим стандартом кодирования, чтобы предупредить будущего сопровождающего о том, что есть обман. Лучше всего не использовать, но может работать.
Если вы в состоянии заранее знать, сколько элементов будет добавлено (или у вас есть относительно жесткая верхняя граница), вы можете использовать reserve и вообще предотвратить перераспределение.
Использование std::deque. Большинство характеристик производительности схожи, однако вы можете добавлять и добавлять новые значения без аннулирования итераторов/ссылок и т.д.... выглядит естественным образом здесь.
Использование отдельной очереди и двойной петли

Я думаю, что deque - лучшее решение здесь. Он соответствует вашему алгоритму, и вам не нужно беспокоиться о проблемах. Вероятно, вы могли бы заменить большую часть vector вашего кода на deque. И если вы не хотите менять интерфейс:

Скопируйте vector в deque
Compute
Назначьте содержимое deque в vector

не будет содержать гораздо больше копий, чем просто перераспределение vector в два раза. Так что не стесняйтесь!

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

Ответ 5

Частый комментарий часто достаточно, чтобы сделать это ясно, например.

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

Ответ 6

Вам нужен случайный доступ к этому вектору? Если нет, более подходит std::list. Это мое личное мнение о том, что добавление к вектору в то время как итерация по нему не является хорошей идеей.

Ответ 7

Вы можете добавить в deque без аннулирования итераторов к своим элементам. Случайный доступ близок к эффективности вектора, поэтому его часто бывает хорошим выбором для его замены.

Ответ 8

Не слишком отличается от оригинала. Просто сделайте здесь несколько вещей:

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