How to Transfer Elements that Match a Predicate from One Vector to Another in C++?

user_1322765 0
Viewed 241

Given two vectors of copyable elements and a predicate over those items, what is an efficient and idiomatic method for:

  1. Removing matching items from the first vector
  2. Appending matching items to the second vector

The following snippet reflects my current thinking, but it does require two passes over the source vector.

vector<int> source{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
vector<int> target;

auto predicate = [](int n) { return n % 2 == 0; };

std::for_each(source.begin(), source.end(), [&predicate, &target](int n) {
    if (predicate(n)) {
        target.push_back(n);
    }
});

auto it = std::remove_if(source.begin(), source.end(), predicate);
source.erase(it, source.end());
std vector stl algorithm c++
2 Answers

I'd use std::partition to partition sourceinto two parts.

auto itr = std::partition(source.begin(), source.end(), predicate);

target.insert(target.end(), itr, source.end());

source.resize(itr - source.begin());

If the ordering needs to remain the same then use stable_partition.

user_13320410

I agree with @acraig5075, that stable_partition, followed by copy and erase will do what you want.

However, if you don't want to shuffle elements around in the source container (probably a futile wish, IMHO), you can do it in a loop: (untested code)

auto itr = source.begin();
while (itr != source.end()) {
   if (predicate(*itr)) {
      target.push_back(*itr);
      itr = source.erase(itr);
   } else
      ++itr;
}

Note that this will "slide down" the elements of elements one at a time as they are moved into target, which is why I opined that avoiding this was probably foolish. (Note: If you're working with list, then it is less foolish)

user_9924900
Related