-1

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?

Baum mit Augen
  • 49,044
  • 25
  • 144
  • 182
  • possible duplicate of [Best way to extract a subvector from a vector?](http://stackoverflow.com/questions/421573/best-way-to-extract-a-subvector-from-a-vector) – IdeaHat Dec 05 '14 at 16:38
  • @IdeaHat My "evil" elements need not be adjacent. – Baum mit Augen Dec 05 '14 at 16:42
  • @0x499602D2 Maybe i'm reading the reference wrong, but doesn't that just copy all "good" elements (which I don't need copied btw) without modifying the input range? – Baum mit Augen Dec 05 '14 at 16:46
  • It says it copies elements not fulfilling a certain predicate, but no it doesn't actually remove the elements from the original container. By bad. :) – David G Dec 05 '14 at 16:48
  • 1
    @0x499602D2 `remove_copy` and `remove_copy_if` seem really poorly named. There's no `remove`-ing going on! It's really like `copy_if_not`... – Barry Dec 05 '14 at 16:55

2 Answers2

2

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; });
Barry
  • 286,269
  • 29
  • 621
  • 977
  • Well that iterates the whole range twice, sadly I do not see how this is preferable to the `std::partition` method I mentioned yet. – Baum mit Augen Dec 05 '14 at 16:52
  • @BaummitAugen Depends on relative expense, but this will be faster, assuming write is slower than read. The partition method requires at most `((last-first)/2 swaps)*(3 writes/swap)+evil_count` writes. Barry will require `2*evil_count` writes (the destination of the writes will never need to be kept, so you don't need swaps). This will also be stable, while partition will not. However, measuring would be the only real way to prove this argument. – IdeaHat Dec 05 '14 at 17:02
  • "Measure everything", as always. :) Yeah I will need to do this anyway, I was just hoping for someone having done that for me already. The ranges are pretty long compared to `num_evil` but swapping is not free either of course. I will see... – Baum mit Augen Dec 05 '14 at 17:12
  • @BaummitAugen I'd be surprised if using the algos was slower than `stable_partition`... but you could always write your own loop. Updated my answer. – Barry Dec 05 '14 at 17:32
  • @Barry Yeah I will measure it some time this weekend. I don't need stable by the way. – Baum mit Augen Dec 05 '14 at 17:35
2

The problem with removing while using iterators is that you don't have access to the actual container, so you can't actually get rid of the elements. Rather, for instance, what std::remove() does is move the target range to the end of the range, which the container will later use to actually remove the elements.

Instead, you can have your function take the stream as a parameter so you can call its removal method once the target value is found:

#include <algorithm>
#include <iterator>
#include <string>
#include <iostream>

template <typename Container, typename OutputIt, typename UnaryPredicate>
auto remove_and_copy_if(Container& c, OutputIt d_first, UnaryPredicate pred)
    -> decltype(c.begin())
{
    auto it = std::begin(c);
    for (; it != std::end(c);  )
    {
        while (it != std::end(c) && pred(*it))
        {
            d_first++ = *it;
            it = c.erase(it);
        }

        if (it != std::end(c)) ++it;
    }
    return it;
}

template <typename Container, typename OutputIt, typename T>
auto remove_and_copy(Container& c, OutputIt d_first, T const& value)
    -> decltype(c.begin())
{
    return remove_and_copy_if(c, d_first, 
    [&] (T const& t) { return t == value; });
}

int main()
{
    std::string str = "Text with some   spaces ";
    std::string output;
    std::cout << "Before: " << str << '\n';

    remove_and_copy(str, std::back_inserter(output), ' ');

    std::cout << "After: " << str << '\n';
    std::cout << "Characters removed: " << output << '\n';
}

Demo

David G
  • 94,763
  • 41
  • 167
  • 253