CODEWITHSUNDEEP
c++loopsfor-loopdynamicvector
Caner
Caner

Reputation: 25

For loop iterating over growing vector

My problem is, the for loop below always iterates only once.

Before entering the loop, the search_list size is always 1. But the search_list vector may grow inside the loop, and should iterate respectively in case some element is added to the list.

   std::vector<int> search_list;
   search_list.clear();
   search_list.push_back(first_elem);

   for(auto &discover : search_list)
   {
       ......
       if(&std::find(face_ids.begin(), face_ids.end(), i))
       {
           search_list.push_back(i);
       }
       ......
   }

How can I make this for loop to iterate multiple times based on that growing vector? Even though something is pushed to the search list, it does not iterate more than once. If something is added, it should set the discover to that element and re-enter the loop.

Upvotes: 2

Views: 3679

Answers (3)

Math
Math

Reputation: 2446

Your problem is that the iterator is created when you begin the loop but is not updated then. You should do the for loop over an index :

std::vector<int> search_list;
search_list.clear();
search_list.push_back(first_elem);

for (int ii=0 ; ii < search_list.size() ; ii++) {
       ......
       if(&std::find(face_ids.begin(), face_ids.end(), i))
       {
           search_list.push_back(i);
       }
       ......
}

This way, if an element gets added, search_list.size() will grow and the loop will go on since it will call it every time.

Be aware that if the if statement is always verified, this would yield an infinite loop.

Edit: following the suggestion of Félix Cantournet, here is a version with a while loop and some control that it cannot go infinite

int max_it = 1000;
int ii=0;
...
// i = MAGIC
...
while (&std::find(face_ids.begin(), face_ids.end(), i) && ii < max_it) {
       search_list.push_back(i);
       ......
       // i = NEW MAGIC
       ......
       ii++;
}

Upvotes: 4

Walter
Walter

Reputation: 45454

The problem is that you not only change the end of the list within the loop (which invalidates the use of a range-based for loop), but possibly also invalidate all iterators of the list (which invalidates a iterator based for loop.

Therefore, you must resort to something that will not be invalidated. The only thing fits this bill is the index. as in Math's answer.

However, this means that your algorithm is specific to using a vector but not, say, a list (when you could still use an iterator-based for-loop).

Upvotes: 1

Rob
Rob

Reputation: 1974

Doing operations on a container that add or remove elements - or resize - can invalidate all iterators for that container.

A range based for loop assumes the iterators are not invalidated, so would give undefined behaviour if they are. Essentially, you'll need to resort to a traditional loop. Break out and restart the outer loop if the container is resized (e.g. place your outer loop in another loop that keeps going as needed).

It will typically involve restructuring your code but, usually, it is safer to avoid resizing a container within a loop that is iterating over the same container. There are few circumstances in practice where that is not possible.

Upvotes: 1

Related Questions