从矢量中选择特定元素

Question

我有一个向量v1,和一个v2相同大小的布尔向量.我想从v1所有值中删除,以便并行元素v2是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;

有没有更好的方法呢？

• 在C++ 03中
• 在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());

与您的相同,除了它就地工作,不需要额外的存储空间.这基本上是一个重新实现std::remove_if(很难直接使用,因为它使用的函数对象被赋予一个值,而不是容器中的索引或迭代器).

Answer 2

在C++ 11可以使用std::remove_if并std::erase用拉姆达,这是"擦除-删除-成语":

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

这里有一个指向它的链接:cpp.sh/57jpc

正如评论所指出的那样,对于这样做的安全性有一些讨论; 这里的基本假设是std::remove_if将谓词应用于v1 有序元素.但是,doc中的语言并未明确保证这一点.它只是声明:

通过移动(通过移动分配)范围中的元素来完成移除,使得不被移除的元素出现在范围的开头.保留的元素的相对顺序被保留,容器的物理大小不变.指向新逻辑端和范围的物理端之间的元素的迭代器仍然是可解除引用的,但元素本身具有未指定的值(根据MoveAssignable后置条件).调用remove之后通常会调用容器的erase方法,该方法会擦除未指定的值并减小容器的物理大小以匹配其新的逻辑大小.

现在,仅使用前向迭代器来std::vector保证结果的稳定性并且不按顺序应用谓词将是困难的.但这肯定是可能的.

Answer 3

remove_if基于A 的替代方案是:

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

还要考虑如果你只需要一个v1跳过某些元素的视图,你可以避免修改v1和使用类似的东西boost::filter_iterator.

Answer 4

我听说你喜欢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 );
    };
  };
};

这可能很有用.它需要一个.data()支持容器,然后返回一个类型的lambda ((Index,E&)->X)->(E&->X)- 返回的lambda将一个索引元素访问者转换为一个元素访问者.lambda柔道的种类.

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;
}

因为我讨厌在客户端代码中删除擦除习惯用法.

现在代码很漂亮:

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

删除/擦除中对移动的限制应该意味着它在元素的原始位置调用lambda.

我们可以通过更多元素步骤来实现这一目标.它在中间变得复杂......

首先,微小的命名运算符库:

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) );
  }
}

现在我们定义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;

它定义了一个令牌then,它lambda1 ->*then* lambda2返回一个接受其参数的函数对象,将其传递给lambda1,然后将返回值传递给lambda2.

接下来我们定义to_index(container):

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

我们也保留了以上内容erase_if.

这导致:

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

解决你的问题(现场例子).