Присоединиться к вектору, перебирая его?

Question

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

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

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

Answer 1

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

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

Answer 2

Если кто-то другой придет и настроит петлю, он может легко сломаться.

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

Answer 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

Answer 4

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

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

Answer 5

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

• Большой жирный комментарий в верхней части цикла, с тегом 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());
}

Answer 6

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

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

Answer 7

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

Answer 8

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