Select specific elements from a vector

Question

I have a vector v1, and a boolean vector v2 of the same size. I want to delete from v1 all values such that the parallel element of v2 is false:

vector<int> v3; // assume v1 is vector<int>
for (size_t i=0; i<v1.size(); i++)
    if (v2[i])
        v3.push_back(v1[i]);
v1=v3;

Is there a better way to do it?

• in C++03
• in C++11

Answer 1

size_t last = 0;
for (size_t i = 0; i < v1.size(); i++) {
  if (v2[i]) {
    v1[last++] = v1[i];
  }
}
v1.erase(v1.begin() + last, v1.end());

Same as yours essentially, except it works in-place, not requiring additional storage. This is basically a reimplementation of std::remove_if (which would be difficult to use directly, because the function object it uses is given a value, not an index or iterator into the container).

Answer 2

In C++11 you can use std::remove_if and std::erase with a lambda, which is the "erase-remove-idiom":

size_t idx = 0;
v1.erase(std::remove_if(v1.begin(),
                          v1.end(),
                          [&idx, &v2](int val){return !v2[idx++];}),
           v1.end())

And here's a link to it functioning as intended: cpp.sh/57jpc

As the comments point out however, there's a bit of discussion about the safety of doing it this way; the underlying assumption here is that std::remove_if will apply the predicate to the elements of v1 in order. However, the language in the doc doesn't explicitly guarantee this. It simply states:

Removing is done by shifting (by means of move assignment) the elements in the range in such a way that the elements that are not to be removed appear in the beginning of the range. Relative order of the elements that remain is preserved and the physical size of the container is unchanged. Iterators pointing to an element between the new logical end and the physical end of the range are still dereferenceable, but the elements themselves have unspecified values (as per MoveAssignable post-condition). A call to remove is typically followed by a call to a container's erase method, which erases the unspecified values and reduces the physical size of the container to match its new logical size.

Now, it would be difficult with only a forward iterator to a std::vector to both guarantee stability for results and not apply the predicate in-order. But it's certainly possible to do so.

Answer 3

A remove_if-based alternative is:

v1.erase(std::remove_if(v1.begin(), v1.end(),
                        [&v1, &v2](const int &x){ return !v2[&x - &v1[0]]; }),
         v1.end());

---

Also consider that if you only need a view on v1 in which some elements are skipped, you can avoid to modify v1 and use something like boost::filter_iterator.

Answer 4

I hear you like lambdas.

auto with_index_into = [](auto&v){
  return [&](auto&& f){
    return [&,f=decltype(f)(f)](auto& e){
      return f( std::addressof(e)-v.data(), e );
    };
  };
};

This may be useful. It takes a .data() suporting container, then returns a lambda of type ((Index,E&)->X)->(E&->X) -- the returned lambda converts an indexed element visitor to an element visitor. Sort of lambda judo.

template<class C, class Test>
auto erase_if( C& c, Test&& test) {
  using std::begin; using std::end;
  auto it=std::remove_if(begin(c),end(c),test);
  if (it==end(c)) return false;
  c.erase(it, end(c));
  return true;
}

because I hate the remove erase idiom in client code.

Now the code is pretty:

erase_if( v1, with_index_into(v1)(
  [](std::size_t i, auto&e){
    return !v2[i];
  }
));

The restriction on moves in remove/erase should mean it invokes the lambda on the element in its original position.

---

We can do this with more elemental steps. It gets complicated in the middle...

First, tiny named operator library:

namespace named_operator {
  template<class D>struct make_operator{};

  enum class lhs_token {
    star = '*',
    non_char_tokens_start = (unsigned char)-1,
    arrow_star,
  };

  template<class T, lhs_token, class O> struct half_apply { T&& lhs; };

  template<class Lhs, class Op>
  half_apply<Lhs, lhs_token::star, Op>
  operator*( Lhs&& lhs, make_operator<Op> ) {
    return {std::forward<Lhs>(lhs)};
  }
  template<class Lhs, class Op>
  half_apply<Lhs, lhs_token::arrow_star, Op>
  operator->*( Lhs&& lhs, make_operator<Op> ) {
    return {std::forward<Lhs>(lhs)};
  }

  template<class Lhs, class Op, class Rhs>
  auto operator*( half_apply<Lhs, lhs_token::star, Op>&& lhs, Rhs&& rhs )
  {
    return named_invoke( std::forward<Lhs>(lhs.lhs), Op{}, std::forward<Rhs>(rhs) );
  }

  template<class Lhs, class Op, class Rhs>
  auto operator*( half_apply<Lhs, lhs_token::arrow_star, Op>&& lhs, Rhs&& rhs )
  {
    return named_next( std::forward<Lhs>(lhs.lhs), Op{}, std::forward<Rhs>(rhs) );
  }
}

Now we define then:

namespace lambda_then {
  struct then_t:named_operator::make_operator<then_t> {} then;

  template<class Lhs, class Rhs>
  auto named_next( Lhs&& lhs, then_t, Rhs&& rhs ) {
    return
      [lhs=std::forward<Lhs>(lhs), rhs=std::forward<Rhs>(rhs)]
      (auto&&...args)->decltype(auto)
    {
      return rhs( lhs( decltype(args)(args)... ) );
    };
  }
}
using lambda_then::then;

which defines a token then such that lambda1 ->*then* lambda2 returns a function object that takes its arguments, passes it to lambda1, then passes the return value to lambda2.

Next we define to_index(container):

template<class C>
auto index_in( C& c ) {
  return [&](auto& e){
    return std::addressof(e)-c.data();
  };
}

we also keep the above erase_if.

This results in:

erase_if( v1,
  index_in(v1)
  ->*then*
  [&](auto i){
    return !v2[i];
  }
);

solving your problem (live example).

Answer 5

I actually quite like the way you did it but I would make a couple of changes in limiting the scope the temporary vector is used and I would use std::vector::swap to avoid a copy at he end. If you have C++11 you could use std::move instead of std::vector::swap:

#include <vector>
#include <iostream>

int main()
{
    std::vector<int> iv = {0, 1, 2, 3, 4, 5, 6};
    std::vector<bool> bv = {true, true, false, true, false, false, true};

    // start a new scope to limit
    // the lifespan of the temporary vector
    {
        std::vector<int> v;

        // reserve space for performance gains
        // if you don't mind an over-allocated return
        // v.reserve(iv); 

        for(std::size_t i = 0; i < iv.size(); ++i)
            if(bv[i])
                v.push_back(iv[i]);

        iv.swap(v); // faster than a copy
    }

    for(auto i: iv)
        std::cout << i << ' ';
    std::cout << '\n';
}

Answer 6

Different version that erases elements in place but does not require as many moves as Igor's algo requires and in case of small amount of elements to be erased could be more efficient:

using std::swap;
size_t last = v1.size();
for (size_t i = 0; i < last;) {
   if( !v2[i] ) {
       --last;
       swap( v2[i], v2[last] );
       swap( v1[i], v1[last] );
   } else 
       ++i;
}
v1.erase(v1.begin() + last, v1.end());

but this algo is unstable.

Answer 7

If you use a list (or forward_list for C++11) instead of a vector, you can do this in-place without the moving/allocating/copying overhead required for vector operations. It's perfectly possible to do most storage-related things with any STL container, but appropriate choice of containers will often give significant improvements in performance.