title: std::set erase complexity anomality?
body: <p>I am trying to figure out the complexity of erasing multiple elements from std::set. I am using <a href="http://en.cppreference.com/w/cpp/container/set/erase" rel="nofollow noreferrer">this page</a> as source.</p>
  
  <p>It claims that the complexity for erasing a single item using an iterator is amortized O(1), but erasing multiple items using the range form is log(c.size()) + std::distance(first, last) (i.e. - log of the set's size + the number of elements deleted).</p>
  
  <p>Taken at face value, if the number of elements to be erased (n) is much smaller than the number of elements in the set (m), this means that looping over the elements to be erased and erasing them one at a time is quicker (O(n)) than erasing them with one call (O(log m) assuming n&lt;&lt;m).</p>
  
  <p>Obviously, had that really been the case, the internal implementation of the second form would just do the above loop.</p>
  
  <p>Is this an error at the site? A bug in the specs? Am I just missing something?</p>
  
  <p>Thanks,
  Shachar</p>