Deleting elements from a set

Блог пользователя Nathan_McKane

Автор Nathan_McKane, 5 лет назад, По-английски

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

for (condition in list_of_conditions)
{
   for(int X: set)
   {
      if(condition(X) == false)
         set.erase(X);
      else
         answer += X;
   }
}

Accepted implementation

My accepted implementation

for (condition in list_of_conditions)
{
   Create an empty set (set2)
   for(int X: set)
   {
      if(condition(X) == true)
      {
         answer += X;
         set2.insert(X);
      }
   }
   set.clear();
   for(element X in set2)
      set.insert(X);
}

#set, #implementation

Nathan_McKane
5 лет назад
9

Комментарии (8)

Показать архивные | Написать комментарий?

moondancer

5 лет назад, скрыть # |

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

Implementation

for (condition in list_of_conditions)
{
   Create an empty vector (v)
   for(int X: set) {
      if(condition(X) == true) {
         answer += X;
      }
      else {
         v.push_back(X);
      }
   }
   for(element X in v)
      set.erase(X);
}

→ Ответить

balalaika

5 лет назад, скрыть # |

← Rev. 3 →

+26

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.

→ Ответить

mr_cruise

5 лет назад, скрыть # ^ |

← Rev. 2 →

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

→ Ответить

balalaika

5 лет назад, скрыть # ^ |

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.

→ Ответить

mr_cruise

5 лет назад, скрыть # ^ |

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

→ Ответить

balalaika

5 лет назад, скрыть # ^ |

← Rev. 2 →

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).

→ Ответить

brezhart

5 лет назад, скрыть # |

← Rev. 2 →

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]

→ Ответить

brezhart

5 лет назад, скрыть # ^ |

← Rev. 2 →

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]

→ Ответить