Can you use `std::remove_if` on a container of `std::unique_ptr`?

Question

Given an std::vector<std::unique_ptr<SomeType> >, is it legal to use remove_if on it? In other words, given this code:

std::vector<std::unique_ptr<SomeType> > v; // fill v, all entries point to a valid instance of SomeType... v.erase( std::remove_if( v.begin(), v.end(), someCondition ), v.end() );

, am I guaranteed after the erase that all pointers still in v are valid. I know that given the intuitive implementation of std::remove_if, and given all of the implementations I've looked at, they will be. I'd like to know if there is anything in the standard which guarantees it; i.e. that std::remove_if is not allowed to copy any of the valid entries without recopying the copy into its final location.

(I am, of course, supposing that the condition doesn't copy. If the condition has a signature like:

struct Condition { bool operator()( std::unique_ptr<SomeType> ptr ) const; };

, then of course, all of the pointers will be invalid after remove_if.)

unique_ptr is not copy constructible, so if you used that predicate your code wouldn't compile. — interjay
– interjay, Commented Dec 7, 2011 at 12:12
Why not? std::unique is not copyable but movable. It can be moved to the end of container. — ali_bahoo
– ali_bahoo, Commented Dec 7, 2011 at 12:12
@KennyTM: But the predicate given in the question takes a parameter by value, so needs a copy constructor. — interjay
– interjay, Commented Dec 7, 2011 at 12:16
@VJovic: No, he didn't. He gave that predicate as an example of one that does copy. Then he made an incorrect statement about pointers being invalidated, which would be true with auto_ptr but not unique_ptr (the code simply wouldn't compile). — interjay
– interjay, Commented Dec 7, 2011 at 12:24

Kerrek SB · Accepted Answer · 2011-12-07 12:06:54Z

9

Just like erase() and resize(), remove_if() will move elements (possibly via swapping), so the container elements do not need to be copyable. There's nothing special about unique_ptr, it's just another move-only type.

As you point out, the predicate should of course take elements by const-reference. Again, just like for any movable type.

answered Dec 7, 2011 at 12:06

Kerrek SB

481k96 gold badges904 silver badges1.1k bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

James Kanze Over a year ago

Where is this stated in the standard? And more importantly, where is it stated that remove_if doesn't move to some temporary, perhaps later to leave the value there because it determines that doesn't need to put it elsewhere? The containers and there member functions have been reworded to reflect move semantics, but I'm not aware of any changes in the language describing remove_if in this regard.

Kerrek SB Over a year ago

@JamesKanze: Note that the state of the "removed" elements is unspecified. Your pointers will be released at the latest when you erase the tail sequence or when you reassign the elements in it, but possibly sooner (i.e. the standard doesn't say).

James Kanze Over a year ago

@KerrekSB The state of the "removed" elements isn't what is worrying me. It's the state of the elements which weren't removed. Suppose remove_if takes a copy of the element preparatory to moving it, then decides that it doesn't have to be moved.

Kerrek SB Over a year ago

@JamesKanze: It wouldn't do that. It would only ever move the elements. If you don't have a copy constructor and the move constructor isn't noexcept, then it wouldn't even compile, I think, or at least then you have to live the the risk of having exceptions. (This follows from 17.6.3.5: Allocator Requirements.)

BЈовић · Accepted Answer · 2011-12-07 12:18:06Z

25.3.8 in the N3290 speaks about remove function :

Requires: The type of *first shall satisfy the MoveAssignable requirements (Table 22).

and

Note: each element in the range [ret,last), where ret is the returned value, has a valid but unspeciﬁed state, because the algorithms can eliminate elements by swapping with or moving from elements that were originally in that range.

This means that it depends on your predicate operator. Since your predicate doesn't create a copy, then the elements are not going to be copied.

§25.3.8/1 is a constraint on the targetted type, not on the implementation of remove. §25.3.8/6 is what I was looking for. Too bad it's a note, and not normative. But it does make the intent clear. I should have read the notes, and not just the normative text, before posting. +1 anyway, and I'll consider it the final response if no one finds anything more definite.
I've got n3242. Is §25.3.8/6 added after that? My /6 discusses about remove_copy[_if].
I believe that note is incorrect. Good thing it isn't normative. ;-) The algorithm is not allowed to swap elements because the elements aren't required to be Swappable. The algorithm can only use move assignment.

Collectives™ on Stack Overflow

Can you use `std::remove_if` on a container of `std::unique_ptr`?

2 Answers 2

4 Comments

3 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

3 Comments

Linked

Related