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, Dec 07 '11 at 12:12
Why not? `std::unique` is not copyable but movable. It can be moved to the end of container. — ali_bahoo, Dec 07 '11 at 12:12
@interjay: Move-assignable is enough to use `std::remove_if`. — kennytm, Dec 07 '11 at 12:14
@KennyTM: But the predicate given in the question takes a parameter by value, so needs a copy constructor. — interjay, Dec 07 '11 at 12:16
@KennyTM: Passing a `std::unique_ptr` as value would remove the raw pointer, leaving it `nullptr`. — ali_bahoo, Dec 07 '11 at 12:20
@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, Dec 07 '11 at 12:24
@interjay Ok, that is right. Copying `unique_ptr` is causing compilation errors. — BЈовић, Dec 07 '11 at 12:41

score 8 · Answer 1 · answered Dec 07 '11 at 12:06

8

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 07 '11 at 12:06

Kerrek SB

464,522
92
875
1,084

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. – James Kanze Dec 07 '11 at 12:12
@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). – Kerrek SB Dec 07 '11 at 12:54
@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. – James Kanze Dec 07 '11 at 13:49
1

@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.) – Kerrek SB Dec 07 '11 at 14:20

score 3 · Accepted Answer · answered Dec 07 '11 at 12:18

3

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.

answered Dec 07 '11 at 12:18

BЈовић

62,405
41
173
273

§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. – James Kanze Dec 07 '11 at 12:28
I've got n3242. Is §25.3.8/6 added after that? My /6 discusses about `remove_copy[_if]`. – kennytm Dec 07 '11 at 14:04
2

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. – Howard Hinnant Dec 07 '11 at 15:11

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

2 Answers2

Linked