Talk:cpp/algorithm/remove

Where in the standard is a requirement stating that the predicate for remove_if should not modify the objects passed to it? Benjamin Lindley 22:50, 27 April 2012 (PDT)

It looks like there are some footnotes in 25.1 that describe general constraints on algorithms -- perhaps these are the source of that claim?

"4. For purposes of determining the existence of data races, algorithms shall not modify objects referenced through an iterator argument unless the specification requires such modification."

"8. ... The function object pred shall not apply any non-constant function through the dereferenced iterator."

--Nate 05:11, 28 April 2012 (PDT)

Yes, §25.1[algorithms.general]/8 (/7 in C++03) is almost certainly what the predicate template refers to. --Cubbi 07:36, 28 April 2012 (PDT)

I see. That upsets me. I wonder why they considered such a requirement necessary. --Benjamin Lindley 09:19, 30 April 2012 (PDT)

Maybe the standards committee is secretly trying to make C++ a functional programming langauge. But seriously, it doesn't seem to unreasonable to require that something called a 'predicate' not have side effects. --Nate 15:40, 30 April 2012 (PDT)

[edit] Mentioning file deletion overload?

Should this page mention that std::remove also has a unrelated (const char *) overload that deletes disk files? -- Myria (talk) 16:08, 2 June 2016 (PDT)

good point! --Cubbi (talk) 20:10, 2 June 2016 (PDT)

[edit] No invalidation of iterators

We should mention that std::remove and std::remove_if do not invalidate iterators.

The erase-remove idiom relies on this:

#include <vector>
#include <algorithm>
#include <cassert>
 
int main()
{
  {
    std::vector<int> vec{1, 2, 1, 3, 1, 4, 1, 5, 1};
    auto e = vec.end();
    auto rem = std::remove(vec.begin(), vec.end(), 1);
    assert(e == vec.end());
 
    vec.erase(rem, vec.end());
    //assert(e != vec.end()); // this will usually be hold
  }
  {
    std::vector<int> vec{1, 2, 1, 3, 1, 4, 1, 5, 1};
    vec.erase(std::remove(vec.begin(), vec.end(), 1), vec.end()); // it is not specified which argument is evaluated first!!!!!!!
  }
}

The last line of code only works if vec.end() is not changed (invalidated) before and after executing std::remove. This is important, because we do not know which argument is evaluated first.

[edit] Linear complexity or quadratic?

remove() and remove_if() move the content of the container, which might be expensive in a vector. So in a vector containing {1,0,2,0,3,0,4,0,5,0,...} a remove(v.begin(), v.end(), 0) would move the whole remaining parts of the vector on every second element. --Roker (talk) 08:25, 27 April 2021 (PDT)

It is linear complexity as specified on the page, check out the possible implementation to see how it achieves this. --Ybab321 (talk) 08:49, 27 April 2021 (PDT)

[edit] Possible Implementation seems to be "not possible"

If you try to remove the last element in the container, std::move will never be called and no element will be removed.

that's correct behavior for std::remove --Cubbi (talk) 06:23, 30 September 2022 (PDT)

Do note that last doesn't refer to the last element in the container, but rather the position beyond the last element, i.e. last is a poor name for the end iterator. If you were to call std::remove(it, it, *it) (so that first == last), it would correctly do nothing --Ybab321 (talk) 06:26, 30 September 2022 (PDT)

I think OP is talking about e.g. removing 3 from vector{1,2,3}, in which case std::move is not called because there is nothing to shift. --Cubbi (talk) 06:28, 30 September 2022 (PDT)

Since i is initialised to first but then incremented in the test, when is the first element checked in the possible implementation? (BTW, has the above comment on removing the last element been fixed in the possible implementation? Doesn't seem to)

The first element is checked by std::find. Regarding the last element, there's no fix to be made --Ybab321 (talk) 06:12, 1 November 2022 (PDT)