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

1
votes

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.

3
c++vectorstl
Note: You do not have to write (void)v.erase(...);; v.erase(...); will do the same. – user2249683
Dieter, that is true, but erase returns an iterator and for fully lint-free code, its necessary to cast it to void. I like my code to be lint-free – Ben J
It looks like you are erasing all elements starting from the first occurrence of 5? – Bgie

3 Answers

1
votes

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.

4
votes

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

1
votes

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);
}