Nathan_McKane's blog

Deleting elements from a set
By Nathan_McKane, 3 years ago, In English

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
  • Vote: I like it
  • +14
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Instead of making set2, you can make a vector v. Implementation would be similar but time complexity would be lower. Something like this:

Implementation
→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +26 Vote: I do not like it 
for (auto it = s.begin(); it != s.end(); ) {
    if (!condition(*it)) {
        it = s.erase(it);
    } else {
        ++it;
    }
}

Method erase(iterator) for all containers returns iterator to next item after last deleted item, so it works.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I tried the same thing using map. But it was giving segmentation fault (runtime error). So finally I tried this:

    auto it = s.begin();  
bool flag = 0;  
for (auto &x: s) {  
    if(flag)  
    {  
        s.erase(it);
        flag = 0;  
    }  
 
    if(condition)  
    {  
        it = s.find(x);  
        flag = 1;  
    } else {  
        ....  
    }       
}

    And it worked really well. Check out my accepted submission for the same question. Submission

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        See this submission I just made, it will make the things pretty clear!

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          114701551

          You do 

          pre.erase(x);

          Now $$$x$$$ is invalid iterator and in next iteration you do

          sum += x->ss[x->ss.size()-1-((x->ss.size())%i)];

          You access to invalid iterator. Of course it's UB.

          That's why you need to do

          x = pre.erase(x);

          Now $$$x$$$ is iterator to the next element after deleted and absoulute valid (if it's not end iterator of course).

          → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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]

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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]

    → Reply