Moving elements satisfying a predicate from one container to another I've implemented a C++ algorithm that moves elements satisfying a given unary predicate from one container into the other, deleting them from the input container.

This is my implementation:

/**
 * Moves all elements in the input container 
 * that satisfy the given predicate
 * into the output container,
 * and erases them from the input container.
 * @tparam Container The container type.
 * @tparam UnaryPredicate The predicate type.
 * @param in The input container.
 * @param out The output container.
 * @param predicate The predicate to satisfy.
 */
template &lt;class Container, class UnaryPredicate&gt;
void move_and_erase_if(Container &amp;in, Container &amp;out, UnaryPredicate predicate) {
    // sort the input container so that all elements that 
    // satisfy the predicate are moved to the end.
    std::sort(in.begin(), in.end(), [=](auto &amp;a, auto &amp;b){
        return !predicate(a) &amp;&amp; predicate(b);
    });

    // find the first element in the sorted container 
    // that satisfies the predicate.
    // all elements following that element 
    // also satisfy the predicate.
    auto it = std::find_if(in.begin(), in.end(), [=](auto &amp;val) {
        return predicate(val);
    });

    // move the elements satisfying the predicate 
    // into the output container.
    std::move(it, in.end(), std::back_inserter(out));

    // erase the elements satisfying the predicate
    // from the input container.
    in.erase(it, in.end());
}


Is there a more efficient way to achieve this? Specifically, the call to std::find_if bugs me, as it applies the predicate to all elements a second time, until it finds the first one that satisfies it.

I've written an example application using the algorithm on ideone.
Sorting the source is not specified as a requirement, so it seems that std::partition would do the necessary job more efficiently. As a perk benefit, std::partition returns the partition point, eliminating the need to std::find_if.

If you still want to follow the sorting path, consider std::lower_bound instead of find_if.