Insert into vector with conditional iterator

Question

Say I have a vector with various entries, which I want to insert into another vector, while leaving out entries that satisfy a condition.

For example, I want to insert a vector while leaving out all three's.

{1, 3, 2, 3, 4, 5, 3} -> { /* previous content, */ 1, 2, 4, 5}

What I came up with so far uses std::partition, which does not preserve the relative order and rearranges the source vector.

std::vector<int> source({1, 3, 2, 3, 4, 5, 3});
std::vector<int> target;

auto partition = std::partition(std::begin(source),
                   std::end(source), [](const auto& a) { return a == 3; });
target.insert(std::begin(target), partition, std::end(source));

What I am looking for is more of an iterator that checks a condition and moves on if the condition is not satisfied. Something like this:

target.insert(std::begin(target),
              conditional_begin(source, [](const auto& a) { return a != 3; },
              conditional_end(source));

I suppose a conditional_end function would be necessary, since std::end would return a different iterator type than conditional_begin.

Maybe I have overlooked something, so my questions are:

• Does the standard library provide something similar?
• Is there a different easy way to achieve my goal?
• Is there an easy way to implement the conditional iterator functionality?

Answer 1

As ranges will be standardized soon, this is an alternative using range-v3, the reference library for the proprosal:

#include <range/v3/view/concat.hpp>
#include <range/v3/view/filter.hpp>

using namespace ranges;

const std::vector<int> source{1, 3, 2, 3, 4, 5, 3};
const std::vector<int> target = view::concat(source,
    source | view::filter([](auto i){ return i != 3; }));

Answer 2

Yes, you can create a custom iterator that does what you want but it is currently a little tedious to create custom iterators using standard C++. It would look something like this:

template <typename Itr, typename F> 
struct ConditionalIterator {
  Itr itr;
  Itr end;
  F condition;

  using value_type = typename Itr::value_type;
  using difference_type = typename Itr::difference_type;
  using pointer = typename Itr::pointer;
  using reference = typename Itr::reference;
  using iterator_category = std::forward_iterator_tag;

  ConditionalIterator() = default;
  ConditionalIterator(Itr itr, Itr end, F condition): itr(itr), end(end), condition(condition) {}

  bool      operator!=(const ConditionalIterator &other) const { return other.itr != itr; }
  reference operator*() const { return *itr; }
  pointer   operator->() const { return &(*itr); }

  ConditionalIterator& operator++() {
    for (; ++itr != end;) {
      if (condition(*itr))
        break;
    }
    return *this;
  }
  ConditionalIterator operator++(int) {
    ConditionalIterator ret(*this);
    operator++();
    return ret;
  }
};

You can then create something like the conditional_begin and conditional_end helper functions you asked for. The only issue is that std::vector::insert expects the two iterators to have the same type. If we use a lambda for our condition then this will be part of the type of our conditional iterator. So we need to pass the lambda to both helper functions so that they return iterators with matching types:

template <typename C, typename F> 
auto conditional_begin(const C &source, F f) {
  return ConditionalIterator<typename C::const_iterator, F>(source.begin(),
                                                            source.end(), f);
}

template <typename C, typename F> 
auto conditional_end(const C &source, F f) {
  return ConditionalIterator<typename C::const_iterator, F>(source.end(),
                                                            source.end(), f);
}

Which you could call with a lambda like this:

auto condition = [](const auto &a) { return a != 3; };
target.insert(std::begin(target),
              conditional_begin(source, std::ref(condition)),
              conditional_end(source, std::ref(condition)));

Live demo.

My crude tests show, in this case, this ends up being significantly faster than simply using copy_if and back_inserter because std::vector::insert first works out how much memory to allocate before inserting. Just using back_inserter will cause multiple memory allocations. The difference in performance will depend on how expensive the condition is to evaluate. You can get the same speedup by using count_if to reserve enough space before using copy_if:

auto count = static_cast<size_t>(std::count_if(source.begin(),
                                 source.end(), condition));
target.reserve(target.size() + count);

std::copy_if(source.begin(),
             source.end(),
             std::back_inserter(target), condition);

Live demo.

Answer 3

Is there a different easy way to achieve my goal?

Yes, the standard already has this functionality built in. The function you are looking for is std::copy_if.

std::vector<int> source({1, 3, 2, 3, 4, 5, 3});
std::vector<int> target;

std::copy_if(source.begin(), 
             source.end(), 
             std::back_inserter(target), [](auto val){ return val != 3; });

Here, std::back_inserter(target), will call push_back on target for each element that the predicate returns true.