I was trying a problem in which I wanted to delete some elements from the set while iterating over the elements of the set.
Link to the problem: Problem C, Educational Round #108
Pseudo Code
for(condition in list_of_conditions):
for(element X in set):
if(condition(X) is false):
remove X from the set
else:
answer += result(X)
However, I failed to implement this in an optimized way. I wonder what are some of the shortest and most optimized codes to implement this idea...
Please share your ideas. Thank you!
Failed implementation (Runtime error)
My failed implementation
Accepted implementation
My accepted implementation
Instead of making set2, you can make a vector v. Implementation would be similar but time complexity would be lower. Something like this:
Method erase(iterator) for all containers returns iterator to next item after last deleted item, so it works.
I tried the same thing using map. But it was giving segmentation fault (runtime error). So finally I tried this:
And it worked really well. Check out my accepted submission for the same question. Submission
For map it works as well as for set as for vector as for any container with erase-method. If you get RE then either you don't do it right or you get it for other reason.
Without concrete submission I cannot tell anything more.
See this submission I just made, it will make the things pretty clear!
114701551
You do
Now $$$x$$$ is invalid iterator and in next iteration you do
You access to invalid iterator. Of course it's UB.
That's why you need to do
Now $$$x$$$ is iterator to the next element after deleted and absoulute valid (if it's not end iterator of course).
Use linked list.
Do two vector: a,b
a[i] — Index of first not deleted element after i
b[i] — Index of last not deleted element before i
So, when you delete element at index i do b[a[i]] = b[i]. a[b[i]] = a[i]
And also you will need to store index of first not deleted element to know from where you should iterate, and instead of doing i++ you should do i = a[i]