Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

std::remove() works as expected with literal but not with dereferenced iterator

Tags:

c++

c++17

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,

  1. Why I am able to remove all the instances of minimum by providing a literal but not a de-referenced iterator? i.e. Why does the following work?
auto iter = std::remove(std::begin(v), std::end(v), 1);

However,

  1. If I choose to stick with a de-reference iterator,
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.

like image 750
Sowmya Avatar asked Dec 31 '22 10:12

Sowmya


1 Answers

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

like image 122
PeterT Avatar answered Jan 25 '23 22:01

PeterT