c++ - Remove elements from range and copy removed elements to new range

Question

I need a method to remove all elements fulfilling a certain criteria from a range (an std::vector in this particular case) and copy those removed elements to a new range (so something like std::remove_if with an output parameter.) Neither the order of the input range nor the order of the output range after this operation is relevant.

One naive approach would be using std::partition to find all "evil" elements, then copy those and last remove them, but this would touch all the "evil" elements twice without need.

Alternatively I could write the desired remove_if variant myself, but why reinvent the wheel (plus I do not know if I can match the efficiency of a high quality library implementation).

So the question is:

Does a such a function already exist? Boost is allowed, but standard C++ is preferred (the project does not depend on boost yet).

If not, is there a smart algorithm that is faster than a naive handcrafted remove_if variant would be?

Answer 1

No it doesn't. There's functions that do one (remove elements which match a predicate) or the other (copy elements which match a predicate) but not both. But it's easy enough to write our own in two steps:

template <typename InputIter, typename OutputIter, typename UnaryPredicate>
InputIter remove_and_copy(InputIter first, InputIter last,
                     OutputIter d_first, UnaryPredicate pred)
{
    std::copy_if(first, last, d_first, pred);
    return std::remove_if(first, last, pred);
}

To be used like:

std::vector<int> v = {1, 2, 3, 4, 5, 6, 7};
std::vector<int> u;

v.erase(
    remove_and_copy(v.begin(), v.end(), std::back_inserter(u),
                    [](int i) { return i%2 == 0; }),
    v.end()
);

// now v is {1, 3, 5, 7} and u is {2, 4, 6}

If you only need vector you can write it a bit differently, but still just 2 lines:

template <typename T, typename UnaryPredicate>
void remove_and_copy(std::vector<T>& from, std::vector<T>& to, UnaryPredicate pred)
{
    std::copy_if(from.begin(), from.end(), std::back_inserter(to), pred);
    from.erase(std::remove_if(from.begin(), from.end(), pred), from.end());
}

Or write your own loop:

template <typename T, typename UnaryPredicate>
void remove_and_copy(std::vector<T>& from, std::vector<T>& to, UnaryPredicate pred)
{
    for (auto it = from.begin(); it != from.end(); ) {
        if (pred(*it)) {
            to.push_back(*it);
            it = from.erase(it);
        }
        else {
            ++it;
        }
    }
}

Usage of either:

remove_and_copy(v, u, [](int i) { return i%2 == 0; });