title: Efficient removal of a set of integers from another set
body: <p>I have a (large) set of integers <code>S</code>, and I want to run the following pseudocode:</p>
  
  <pre><code>set result = {};
  while(S isn't empty)
  {
    int i = S.getArbitraryElement();
    result.insert(i);
    set T = elementsToDelete(i);
    S = S \ T; // set difference
  }
  </code></pre>
  
  <p>The function <code>elementsToDelete</code> is efficient (sublinear in the initial size of <code>S</code>) and the size of <code>T</code> is small (assume it's constant). <code>T</code> may contain integers no longer in <code>S</code>.</p>
  
  <p>Is there a way of implementing the above that is faster than O(|S|^2)? I suspect I should be able to get O(|S| k), where k is the time complexity of <code>elementsToDelete</code>. I can of course implement the above in a straightforward way using <code>std::set_difference</code> but my understanding is that <code>set_difference</code> is O(|S|). </p>