how can I correctly apply the erase remove idiom on a sorted vector?

Question

Often, we'd like to apply the erase remove idiom to properly eradicate an element from a vector e.g.:

v.erase( std::remove( std::begin(v), std::end(v), 5 ), std::end(v) ); 

where v is a vector of integers.

But what if the vector were sorted first? Will the following do the same thing, and if so, is it the most optimal way?

std::sort(v.begin(), v.end());

IntegerVector::iterator it = std::lower_bound(v.begin(), v.end(), 5);

if(it != v.end()) {
    (void)v.erase(it, v.end());
}

Does this correctly apply the erase-remove idiom? Is the vector still sorted after the removal process (I assume that it is)? Don't we need to do something like this:

(void)v.erase(std::remove(it), v.end());

(incorrect syntax for std::remove, but hopefully you get the idea).

Thanks,

Ben.

Answer 1

It's not the erase-remove idiom any more but, yes, it'll do the job correctly, optimally and stably.

std::remove gathers all the unwanted elements into one contiguous block before erasure, but your sortedness has already done that so it's not needed.

You can drop the meaningless (void) prefixes.

Answer 2

You may use:

auto range = std::equal_range(std::begin(v), std::end(v), 5);
v.erase(range.first, range.second);

For C++03, you have to replace auto with (the verbose) std::pair<IntegerVector::iterator, IntegerVector::iterator>

std::equal_range returns a pair of iterator where range [first, second) has values equivalent to given value (5 here) (assuming v is sorted).

Answer 3

Quite sure your code is not correct, assuming you want to remove all elements equal to 5. Here is the corrected version:

std::sort(v.begin(), v.end());

auto lower = std::lower_bound(v.begin(), v.end(), 5);

if(lower != v.end()) {
  auto upper = std::upper_bound(lower,v.end(), 5);
  v.erase(lower,upper);
}