Removing multiple elements from stl list while iterating

Question

This is not similar to Can you remove elements from a std::list while iterating through it?. Mine is a different scenario.

Lets say I have a list like this.

1  2  3  1  2  2  1  3

I want to iterate this stl list in such a way that When I first encounter an element X I do some activity and then I need to remove all the elements X in that list and continue iterating. Whats an efficient way of doing this in c++.

I am worried that when i do a remove or an erase I will be invalidating the iterators. If it was only one element then I could potentially increment the iterator and then erase. But in my scenario I would need to delete/erase all the occurances.

Was thinking something like this

while (!list.empty()) {
   int num = list.front();
   // Do some activity and if successfull
   list.remove(num);
   }

Dont know if this is the best.

@PSIAlt sorry, I thought we were talking about vectors, not lists. — dwcanillas, Apr 22 '15 at 16:03
Is it mandatory to remove while iterating or can you modify the list prior to the iteration? In latter case, you could use `list::unique` to keep only the unique elements which is basically what you need. — lmNt, Apr 22 '15 at 16:04
Yes i need to do the activity from the front of the list. (Its kind of a queue). — AMM, Apr 22 '15 at 16:07
From list::unique documentation: "Notice that an element is only removed from the list container if it compares equal to the element immediately preceding it. Thus, this function is especially useful for sorted lists." OP's list isn't sorted. — Benjy Kessler, Apr 22 '15 at 16:07
Maybe: pos = std::find(...), ... activity ... obsolete = std::remove(pos, list.end(), x), std::erase(obsolete, list.end()) — , Apr 22 '15 at 16:09
To me, your approach seem quite good! For `list::remove()`, "Iterators, pointers and references referring to elements removed by the function are invalidated. All other iterators, pointers and reference keep their validity." Isn't is the best we can get in this situation? — Arun, Apr 22 '15 at 16:12
Doing that runs in O(n^2). Because at every element you have to iterate over the entire list to remove other elements.. — Benjy Kessler, Apr 22 '15 at 16:13
Can you clarify what "remove all the elements X in that list" means? Do you mean, all the *other* elements or really *all*? Like, given `{3, 1, 3, 2}`, do you want back `{3, 1, 2}` or `{}`? — Barry, Apr 22 '15 at 16:39

Benjy Kessler · Answer 1 · 2015-04-22T16:26:42.147

Save a set of seen numbers and if you encounter a number in the set ignore it. You can do as follows:

list<int> old_list = {1, 2, 3, 1, 2, 2, 1, 3};
list<int> new_list;
set<int> seen_elements;
for(int el : old_list) {
  if (seen_elements.find(el) == seen_elements.end()) {
    seen_elements.insert(el);
    new_list.push_back(el);
  }
}
return new_list;

This will process each value only once and the new_list will only contain the first copy of each element in the old_list. This runs in O(n*log(n)) because each iteration performs a set lookup (you can make this O(n) by using a hashset). This is significantly better than the O(n^2) that your approach runs in.

Removing multiple elements from stl list while iterating

1 Answers1