Select 向量中的特定元素

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 与 lambda 一起使用，即 "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())

这里有一个 link 它按预期运行：cpp.sh/57jpc

正如评论所指出的那样，有一些关于这样做的安全性的讨论；这里的基本假设是 std::remove_if 将按顺序将谓词应用于 v1 的元素。 但是，文档中的语言并未明确保证这一点.它只是 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.

现在，仅使用指向 std::vector 的前向迭代器很难既保证结果的稳定性又不按顺序应用谓词。但确实可能这样做。

Answer 3

基于 remove_if 的替代方案是：

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.[=16 的内容=]

Answer 4

我其实很喜欢你做的方式，但我会做一些改变来限制临时向量的使用范围，我会使用 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 5

不同的版本擦除元素，但不需要像 Igor 的算法那样多的移动，并且在擦除少量元素的情况下可能更有效：

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

但是这个算法不稳定。

Answer 6

我听说你喜欢 lambda。

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() 支持容器，然后 returns 一个 ((Index,E&)->X)->(E&->X) 类型的 lambda —— returned 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];
  }
));

remove/erase中的移动限制应该意味着它在元素的原始位置调用 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 return 是一个函数对象，它接受它的参数，将它传递给 lambda1，然后将 return 值传递给 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];
  }
);

solving your problem (live example).

Answer 7

如果您使用 list（或 C++11 的 forward_list）而不是 vector，您可以在没有 moving/allocating/copying 的情况下就地执行此操作vector 操作所需的开销。完全可以使用任何 STL 容器来完成大多数与存储相关的事情，但是选择适当的容器通常会显着提高性能。

Select 向量中的特定元素

Select specific elements from a vector

c++

stdvector

c++11