CODEWITHSUNDEEP
c++vectorstl
Ben J
Ben J

Reputation: 1387

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

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.

Upvotes: 1

Views: 301

Answers (3)

Jarod42
Jarod42

Reputation: 217275

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

Upvotes: 4

Bgie
Bgie

Reputation: 513

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

Upvotes: 1

Lightness Races in Orbit
Lightness Races in Orbit

Reputation: 385144

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.

Upvotes: 1

Related Questions