从向量中选择特定元素

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中

你知道有没有更好的做法吗？

• 在C++03中
• 在C++11中

- user31264

---

@IgorTandetnik 哦，明白了。现在看到这个任务，我就明白了 :) - eerorika

你确定你需要一个新的vector而不是一个范围（即具有begin()和end()函数的对象）吗？ - lorro

很惊讶还没有人提到zip迭代器。https://dev59.com/G2cs5IYBdhLWcg3w0HSz#12553437？ - Lightness Races in Orbit

@screwnut - vector::erase() 的时间复杂度是线性的。使用 erase() 删除每个有问题的元素会导致二次时间复杂度。vector::erase() 还会使后续元素的所有指针、引用和迭代器无效。这个函数速度慢，不安全，通常应该避免使用。（我希望你不会说“那就用列表”。）除此之外，我们可能需要有问题的元素来确定其他元素的有效性。 - user31264

PS：“但是所有的答案都使用了erase，包括你接受的答案。”- 不仅仅是我接受的答案，大多数其他答案都只使用了一次erase，并且它们也仅用于数组的最后部分。这种特殊情况下的vector::erase 操作既快速又安全。 - user31264

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 的重新实现（直接使用该函数对象会很困难，因为它给出的是值，而不是容器中的索引或迭代器）。

- Igor Tandetnik

---

如果v1中包含的内容比int更复杂，那么可以通过执行以下操作进一步进行优化：v1[last++] = std::move(v1[i]);。 - Angew is no longer proud of SO

这个肯定与每个版本兼容。 - Ceros

据我所记，实现允许假设rvalue参数是对象的唯一链接，并相应地编写实现（例如，对于vector/string，脑海中首先想到的实现不支持s = move(s)情况）。 - RiaD

@Angew 自我移动赋值是不可取的。 - T.C.

当然，@T.C. 您说得对。所以我的“优化”想法会彻底失败 :-( 不过我会留下这个评论作为讨论的参考。 - Angew is no longer proud of SO

Answer 2

在C++11中，您可以使用lambda表达式与std::remove_if和std::erase一起使用，这就是“erase-remove惯用语”：

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的元素。然而，文档中的语言并没有明确保证这一点。它只是陈述：

移除是通过以这样一种方式移动（通过移动赋值），使得不需要移除的元素出现在范围的开始位置来完成的。剩余元素的相对顺序被保留，容器的物理大小保持不变。指向新逻辑结尾和范围物理结尾之间的元素的迭代器仍然可解引用，但元素本身具有未指定的值（按MoveAssignable后置条件）。调用移除通常会随后调用容器的erase方法，该方法将擦除未指定的值，并将容器的物理大小减小到与其新逻辑大小相匹配。

现在，仅使用前向迭代器对std::vector进行排序，既要保证结果的稳定性，又要不按顺序应用谓词是困难的。但这当然是可能的。

- aruisdante

---

我想知道idx和val能保持同步的程度；函数对象是否会按正确的顺序为每个值调用。 - Igor Tandetnik

算法的稳定性要求（algorithm.stable）保留元素的相对顺序，但我没看到它指明谓词必须按顺序为每个元素调用。我只知道 for_each 算法明确保证了这一点；它必须明确说明这一点的事实，让我认为，在缺乏这种语言规定的情况下，实现有可能会无序地调用谓词。 - Igor Tandetnik

前向迭代器不是输入迭代器，它们是多遍迭代器。可以完全可能地无序应用谓词，甚至并行执行。 - Angew is no longer proud of SO

作为 std::remove_if 的操作，它会将从移动到容器末尾的元素向下移动吗？这将破坏两个向量之间的关联。 - Galik

@aruisdante，应该是“sequenced”，而不是“sequential”——两者意义完全不同。“Sequenced”基本上意味着“单线程”——与“unsequenced”相反，后者可能在不同的线程上并行运行。它并不涉及调用顺序，只是说明它们不会并行运行。 - Igor Tandetnik

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 的内容。

- manlio

Answer 4

我听说你喜欢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()的容器，然后返回一个类型为((Index,E&)->X)->(E&->X)的Lambda表达式 - 返回的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;

这段文字涉及到 IT 技术，其中定义了一个名为“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];
  }
);

solving your problem (live example).

- Yakk - Adam Nevraumont

---

@guygreer 使用auto&&x参数的完美转发最好使用decltype(x)(x)实现。由于lambda可能是rvalue，仅使用引用是不礼貌的。 - Yakk - Adam Nevraumont

好的，现在明白了。 - SirGuy

好的解决方案。当然完全看不懂，但是很好地运用了C++技巧 :) +1 - Richard Hodges

@rich 我认为如果再加一些代码会更好。比如 erase_if(v1,element_to_index(v1)->*then*[&](auto i){return !v2[i];})); - Yakk - Adam Nevraumont

@yakk，干吧！你知道我喜欢它！ - Richard Hodges

Answer 5

我实际上很喜欢你的做法，但我会对临时向量使用范围进行限制，并在最后使用std::vector::swap来避免复制。如果您有C++11，可以改用std::move而不是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';
}

- Galik

---

在 C++11 中，您可以使用 std::move 来代替 std::swap，以避免复制并更明确地表达意图。 - aruisdante

顺便说一下优化的问题：v.reserve(iv.size()) 可以防止多次调整 vector 大小，但会导致过度分配内存。 - Martin Ba

Answer 6

不同版本的算法可以就地删除元素，但不需要像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());

但是这个算法不稳定。

- Slava

Answer 7

如果您使用 list（或C++11中的forward_list）而不是vector，则可以在不需要vector操作所需的移动/分配/复制开销的情况下原地执行此操作。 使用任何STL容器都完全可以完成大多数与存储相关的事情，但适当选择容器通常会显着提高性能。

- Graham

---

使用list删除元素最少需要移动“next”指针以删除节点，并且对于_每个删除_，需要释放已删除的节点。我甚至不会提及在内存中跟随链接所产生的缓存性能影响... 在放弃向量之前测量转换为列表的移动。 - David Thomas

@DavidThomas 当然可以，但它可能比移动向量的整个内容影响要小。如果你只有几个元素，那么肯定要坚持使用向量。如果你有成千上万或数百万个元素，则最好使用就地列表或设置新向量，并且您可能需要使用双端队列以便添加新元素更便宜。如果您有数千万个元素，则通常希望进行原地操作，因为您不希望承受持有副本的RAM负担。 - Graham