Remove items from vector, and mutate those which are removed

Question

I have a std::vector<std::shared_ptr<Foo>> from which I want to erase-remove items matching some predicate. The removed objects should have a method called which sets some status for use elsewhere.

Is there a reason I should not do this in the predicate function when true is returned? It feels a little like mixing concerns, but the only alternatives I can think of seem much uglier.

Nicolanicolai

It would be better to summarize the alternatives, or else you're going to get them as answers. – Chlorate

That's how I would do it but, what can I say, I'm lazy. There's no alternative that still allows you to use the algorithm library, right? So, either way, you're violating some notion of "perfect" programming standards. (Edit: apparently there is but I would still be tempted to do it your way!) – Thole

That's the most efficient way I can think of. – Pannonia

Answer 1

There are two reasons why this is probably not a good idea.

First, most standard library algorithms should not use predicates what modify the elements they act on.

Second, std::remove and std::remove_if don't give you a good set of "removed" elements^*. You can only rely on the elements that are selected to keep. The "removed" elements might in fact be copies of the "good" ones. And since you are storing shared pointers, they could be pointing to the same objects as the "good" elements.

An alternative would be to use std::partition, then iterate over the relevant section of the partition, then use erase in a way similar to the erase-remove idiom.

auto p = std::partition(v.begin, v.end(), pred);
std::for_each(p, v.end(), call_method_functor);
v.erase(p, v.end());

---

^{* These algorithms should probably have been named keep and keep_if}

Bravissimo

That's a good solution but I don't really understand this part: "std::remove... doesn't give you a good set of 'removed' elements". Why does that matter if you're calling the only function you need on the object before the predicate function even returns? – Thole

@Thole - I have written code that attempted to use "removed" elements, and I got burned pretty bad. Bottom line is that you should not use the removed elements, except for erasure. The solution is exactly what juanchopanza has placed in his answer, std::partition (or std::stable_partition). – Nerval

I like your idea of using partition, but the part about remove(_if) not making any guarantees about the removed elements is probably irrelevant because the OP states he'll be operating on these objects from elsewhere. – Abrahamsen

@Abrahamsen - This is exactly what I was getting at. – Thole

@Thole If OP wants to act on what they consider to be the "removed" elements, then anything using remove is flawed. It doesn't matter if they call the method in the predicate (which in itself shouldn't happen anyway.) – Bravissimo

@Thole Whether it would work or not would depend on details we don't have. It is too fragile. – Bravissimo

Thanks for this answer -- it's really great. Using std::partition seems like a sane idea. Could you substantiate the first point you make though. Is the logic that predicates should be idempotent? – Nicolanicolai

@Abrahamsen I have the feeling OP expected the "removed" elements to be in the second section of the vector after the call to remove_if. That assumption doesn't hold, so it is too likely the code will break somewhere. – Bravissimo

Actually I wrote a small unit test to check what remove_if did as I didn't understand the relationship between that function and erase. My tests showed duplicates in the "removed" section as you say. However, in my case, setting the flag I want to in the predicate itself appears to work. Still, I feel that using partition is clearer and less likely to fail mysteriously at some point in the future. – Nicolanicolai

@DrewNoakes I'm not sure idempotent is the right term (my maths is rusty), but the functor applied to the same object many times should yield the same result. It has to behave as a function. In C++, you could consider that the parameter is const (although this need not be enforced by the compiler.) This is true of most algorithms, std::foreach being an exception that springs to mind. – Bravissimo

@DrewNoakes I mistakenly mentioned std::transform in my previous comment. I meant std::foreach. The difference is important! – Bravissimo

So now I come to implement this, it turns out I cannot use std::partition because it does not make a stable reording. Relative order of the elements is not preserved. I'll leave the question as is for now, as I didn't state that as an original requirement. However if you know of a way around this, I'd be glad to hear it! – Nicolanicolai

@DrewNoakes Perhaps std::stable_partition? – Bravissimo