C++ collect算法？

Question

有时我需要迭代容器的一部分元素，或者只想提取它们并忽略其余部分。我最终使用boost::range::adaptors::filtered创建这个延迟集合。

for(auto&& i : container | filtered(predicate)) {
  // .. do stuff
}

STL中缺少类似Ruby的collect算法的原因是什么（我们只有copy_if，并不相同）？或者有没有使用它的任何理由？

一种可能的实现方式如下：

template<class Container, class Predicate>
Container collect(Container&& c, Predicate&& p) {
  Container n;
  for(auto&& i : c) {
    if(p(i)) {
      n.push_back(i);
    }
  }
  return n;
}

但是一个lazy_collect也可能很有用，以避免拷贝。

下面的所有答案都很棒。我希望我可以标记它们中的所有内容。我之前不知道std::back_inserter。现在收集东西就像这样简单：

boost::copy( orig | filtered(predicate), std::back_inserter(collection));

- gnzlbg

---

@Angew 看起来你刚好在我添加 copy_if 不同的时候发了帖子。当使用 copy_if 时，你需要事先知道需要多少空间，这会导致 n container(count_if(old,predicate)); std::copy_if(old,n,predicate);。 - gnzlbg

正如我的回答所示，您可以使用back_inserter来绕过先验大小知识要求。 - Angew is no longer proud of SO

@PlasmaHH：这里问题的实质肯定是，“为什么boost范围适配器不好到没有进入标准？” :-) - Steve Jessop

@SteveJessop：如果有提案，那么它就被记录下来了。如果没有，那就是原因 ;) - PlasmaHH

@SteveJessop：确实如此。然而，有时候只是因为时间不够。有人应该全职支付一个ISO团队... - PlasmaHH

Answer 1

标准算法并不直接操作容器（创建或销毁容器，或更改其大小）。它们操作迭代器范围，而算法所做出的唯一更改是通过迭代器赋值。因此，您提出的操作完全超出了标准算法的范围。也许标准库中应该有一个大型的通用容器操作集，包括这个操作，但“STL哲学”是操作迭代器。您提出的非惰性操作可以使用std::back_inserter和std::copy_if（可选使用移动迭代器），或者move_if（如果您自己实现）。std::copy_if在C++03中缺失，但那只是一种意外疏忽。无法仅通过连接标准组件来完成惰性版本--没有干净的方法将一个算法的“输出”直接链接到另一个算法的“输入”而不使用中间存储。这就是为什么Boost提供了如此有趣的迭代器以及范围的原因。我不知道它们为什么没有被纳入C++11，但要注意C++11相当晚。由于时间不够，一些提案被放弃，因此原因可能很简单，“在已知的现有工作量的情况下，认为它从未被认为足够重要来提出提案”。关于您的特定实现，不是所有容器都有push_back，因此您可能不应该使用Container作为模板参数名称。PushBackSequence更能描述需求。

- Steve Jessop

---

还要注意，如果容器使用的是insert而不是push_back，你可以使用inserter代替back_inserter。 - Peter Wood

使用移动迭代器时要小心使用std::copy_if，因为您可能会在容器中散布有效但未指定状态的对象。最好自己编写move_if函数，并将所有有效但未指定的对象移动到末尾并返回指向该点开始的迭代器，以便像使用std::remove_if一样对这些项目进行分配或删除。 - Adrian

Answer 2

这个怎么样：

#include <algorithm>
#include <iterator>

std::copy_if(container.begin(), container.end(), std::back_inserter(result), []{...})

其中container是您想要收集的容器，result是将存储集合的容器。

- Angew is no longer proud of SO

---

OP写道“我们只有copy_if这个函数，但它不一样”，看起来他们意识到了这一点。虽然我同意，但是他们想要什么并不清楚。 - Andy Prowl

很好，我不知道back inserter。 - gnzlbg

Answer 3

评论中说：

使用copy_if时，需要提前知道需要多少空间

这不是真的。您可以使用back插入器来使用std :: copy_if：

#include <algorithm> // For std::copy_if
#include <iterator> // For std::back_inserter
#include <vector>
#include <iostream>

int main()
{
    std::vector<int> v(10);
    std::iota(begin(v), end(v), 0); // Fills the vector with 0..9

    std::vector<int> out;
    std::copy_if(begin(v), end(v), back_inserter(out), [] (int x) 
    //                             ^^^^^^^^^^^^^^^^^^
    {
        return x > 4; 
    });

    for (auto x : out) { std::cout << x << " "; }
}

这里有一个实时示例。

如果你想要一个直接在容器上工作而不是在由一对迭代器定义的范围上工作的函数，你可以编写以下辅助程序：

template<typename C1, typename C2, typename P>
void cont_copy_if(C1&& src, C2&& dst, P&& p)
{
    std::copy_if(
        begin(std::forward<C1>(src)),
        end(std::forward<C1>(src)),
        back_inserter(std::forward<C2>(dst)),
        std::forward<P>(p)
        );
}

您只需按照以下方式使用它：

int main()
{
    std::vector<int> v(10);
    std::iota(begin(v), end(v), 0);

    std::list<int> out;
//  ^^^^^^^^^
//  You could use a different destination container

    cont_copy_if(v, out, [] (int x) { return x > 4; });
//  ^^^^^^^^^^^^

    for (auto x : out) { std::cout << x << " "; }
}

当然还有实时示例。

- Andy Prowl

---

确实，谢谢！我之前不知道back_inserter。现在我可以这样做：boost::copy( old | filtered(pred), std::back_inserter(new))。 - gnzlbg

小心在同一变量（src）上两次调用std::forward。如果src绑定到r-value，则您实际上将src移动到begin()，因此将其传递到end()是危险的。 - bstamour

请改为 err. make foo(myobject x);。 - bstamour

假设foo的签名为void foo(myobject x);在这种情况下，如果不先重新分配变量，从同一变量两次转发到foo中是不明智的。也就是说，如果begin()和end()通过值传递它们的参数，则您的代码会导致奇怪的行为。它们接受引用，因此没关系，但因此转发无意义，所以这是无意义的。我的观点是，通常在不重新分配的情况下两次转发某些内容是不明智的，因为您不知道它是否会在未来被移动。 - bstamour

好的，我们终于达成了共识。这就是我想要指出的：通常情况下，在连续转发两次之前是不明智的，除非你确定在你转发到的函数中不会有移动构造。 - bstamour