While learning remove-erase idiom, as well as understanding how std::min_element() work How to use std::min_element in C++17?. I thought to try removing minimum element from the following piece of code:
#include <algorithm>
#include <iostream>
#include <vector>
int main()
{
std::vector<int> v{3, 1, 4, 1, 5, 9};
std::vector<int>::iterator result = std::min_element(v.begin(), v.end());
std::cout << "min element at: " << std::distance(v.begin(), result);
}
There are two minimum elements in v. I tried to remove both of them with added diagnostics
int main()
{
std::vector<int> v{3, 1, 4, 1, 5, 9};
std::vector<int>::iterator result = std::min_element(v.begin(), v.end());
v.erase(result); // This removes just one minimum. What if need to remove all?
v.push_back(1); // Okay, let's add the minimum again
std::vector<int>::iterator another_result = std::min_element(v.begin(), v.end());
std::cout << "min element: " << *another_result << std::endl;
auto iter = std::remove(std::begin(v), std::end(v), *another_result);
// If I write 1 instead of *another_result, I manage to remove all 1's. No need to use iter-1 in erase idiom then.
std::cout << "\nWhere is my iterator pointing? It is at: " << std::distance(v.begin(), iter);
v.erase(iter, std::end(v)); // All the minimum are gone if I use iter-1 instead of iter and use *another_result
std::for_each(v.begin(), v.end(), [](const int& x){std::cout << x << " ";}); // Why is still "1" there?
}
link
My questions are, as highlighted in the code with the comments,
auto iter = std::remove(std::begin(v), std::end(v), 1);
However,
auto iter = std::remove(std::begin(v), std::end(v), *another_result);
Doesn't remove all the instances of minimum while sticking to remove-erase idiom.
It looks like you are comparing with a reference into the vector. The element you passed in then gets moved by remove
and when comparing against it a second time the reference observes some other value.
This works just fine:
int by_value = *another_result;
auto iter = std::remove(std::begin(v), std::end(v), by_value);
The third parameter of the std::remove
overload you're using takes a const T&
, but it's "invalidating" the reference in the process of doing its operation.
If you look at the "possible implementation" on en.cppreference
template< class ForwardIt, class T >
ForwardIt remove(ForwardIt first, ForwardIt last, const T& value)
{
first = std::find(first, last, value);
if (first != last)
for(ForwardIt i = first; ++i != last; )
if (!(*i == value))
*first++ = std::move(*i); //here it changes the value that "value" points to
//if you are using a reference of an element inside the vector
return first;
}
This problem is also mentioned in the "Notes" section as:
Because std::remove takes value by reference, it can have unexpected behavior if it is a reference to an element of the range [first, last).
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With