为 "produce a populated container" 编写现代函数接口

Question

当我学习 C++03 时，我学会了几种编写 "give me the collection of things" 函数的方法。但各有各的挫折。

template< typename Container >
void make_collection( std::insert_iterator<Container> );

这个must be implemented in a header file
界面未告知需要空容器。

或：

void make_collection( std::vector<Thing> & );

这是不是容器不可知论者
界面未告知需要空容器。

或：

std::vector<Thing> make_collection();

这是不是容器不可知论者
有几种途径可以进行不必要的复制。（错误的容器类型，错误的 contained 类型，没有 RVO，没有移动语义）

使用现代 C++ 标准，是否有比 "produce a populated container" 更惯用的函数接口？

Answer 1

您可以在 c++11 中执行此操作而无需容器复制。将使用移动构造函数而不是复制构造函数。

std::vector<Thing> make_collection()

Answer 2

我不认为有一个 惯用的 接口来生成填充的容器，但听起来在这种情况下你只需要一个函数来构造和 return 一个容器。在那种情况下，您应该更喜欢最后一种情况：

std::vector<Thing> make_collection();

只要您使用现代 C++11 兼容编译器，这种方法就不会产生任何结果 "unnecessary copying"。容器在函数中构造，然后通过移动语义移动以避免复制。

Answer 3

第一种方法是基于类型擦除。

template<class T>
using sink =  std::function<void(T&&)>;

A sink 是一个消耗 T 实例的可调用对象。数据流入，没有流出（调用者可见）。

template<class Container>
auto make_inserting_sink( Container& c ) {
  using std::end; using std::inserter;
  return [c = std::ref(c)](auto&& e) {
    *inserter(c.get(), end(c.get()))++ = decltype(e)(e);
  };
}

make_inserting_sink 获取一个容器，并生成一个 sink 来消耗要插入的内容。在一个完美的世界中，它将是 make_emplacing_sink，返回的 lambda 将采用 auto&&...，但我们为我们拥有的标准库编写代码，而不是我们希望拥有的标准库。

以上均为泛型库代码

在 collection 一代的 header 中，您将有两个功能。一个 template 胶水函数，以及一个 non-template 完成实际工作的函数：

namespace impl {
  void populate_collection( sink<int> );
}
template<class Container>
Container make_collection() {
  Container c;
  impl::populate_collection( make_inserting_sink(c) );
  return c;
}

您在 header 文件之外实现 impl::populate_collection，它只是一次将一个元素移交给 sink<int>。请求的容器和生成的数据之间的连接被类型擦除 sink。

以上假定您的 collection 是 int 的 collection。只需更改传递给 sink 的类型，就会使用不同的类型。生成的 collection 不必是 int 的 collection，只要可以将 int 作为其插入迭代器的输入即可。

这不是非常有效，因为类型擦除会产生几乎不可避免的运行时开销。如果您将 void populate_collection( sink<int> ) 替换为 template<class F> void populate_collection(F&&) 并在 header 文件中实现它，类型擦除开销就会消失。

std::function 是 C++11 的新增功能，但可以在 C++03 或更早版本中实现。带赋值捕获的 auto lambda 是一个 C++14 构造，但可以在 C++03 中作为 non-anonymous 辅助函数 object 实现。

我们还可以针对 std::vector<int> 之类的内容优化 make_collection，并进行一些标记分派（因此 make_collection<std::vector<int>> 会避免类型擦除开销）。

现在有一种完全不同的方法。与其编写 collection 生成器，不如编写生成器迭代器。

第一个是一个输入迭代器，它调用一些函数来生成项目并前进，最后一个是一个前哨迭代器，当 collection 耗尽时，它与第一个比较相等。

范围可以有一个 operator Container SFINAE 测试 "is it really a container"，或者一个 .to_container<Container> 用一对迭代器构造容器，或者最终用户可以手动完成.

这些东西写起来很烦人，但是Microsoft is proposing Resumable functions for C++ -- await and yield使得这种东西真的好写。返回的 generator<int> 可能仍然使用类型擦除，但很可能会有避免它的方法。

要了解此方法的外观，请检查 python 生成器（或 C# 生成器）的工作原理。

// exposed in header, implemented in cpp
generator<int> get_collection() resumable {
  yield 7; // well, actually do work in here
  yield 3; // not just return a set of stuff
  yield 2; // by return I mean yield
}
// I have not looked deeply into it, but maybe the above
// can be done *without* type erasure somehow.  Maybe not,
// as yield is magic akin to lambda.

// This takes an iterable `G&& g` and uses it to fill
// a container.  In an optimal library-class version
// I'd have a SFINAE `try_reserve(c, size_at_least(g))`
// call in there, where `size_at_least` means "if there is
// a cheap way to get the size of g, do it, otherwise return
// 0" and `try_reserve` means "here is a guess asto how big
// you should be, if useful please use it".
template<class Container, class G>
Container fill_container( G&& g ) {
  Container c;
  using std::end;
  for(auto&& x:std::forward<G>(g) ) {
    *std::inserter( c, end(c) ) = decltype(x)(x);
  }
  return c;
}
auto v = fill_container<std::vector<int>>(get_collection());
auto s = fill_container<std::set<int>>(get_collection());

注意 fill_container 有点像 make_inserting_sink 颠倒了。

如上所述，生成迭代器或范围的模式可以在没有可恢复函数和类型擦除的情况下手动编写——我以前做过。做对是相当烦人的（将它们写成输入迭代器，即使你认为你应该花哨），但可行。

boost 也有一些帮助程序来编写不键入擦除和范围的生成迭代器。

Answer 4

如果我们从标准中汲取灵感，几乎所有 make_<thing> 形式的内容都将 return <thing> 按值计算（除非分析表明不是这样，我不相信return按值计算应该排除合乎逻辑的方法）。这表明选项三。如果您希望提供一些容器灵活性，您可以将其设为模板模板（您只需要了解允许的容器是否具有关联性即可）。

但是，根据您的需要，您是否考虑过从 std::generate_n 中汲取灵感，而不是制作容器，而是提供 fill_container 功能？然后它看起来非常类似于 std::generate_n，类似于

template <class OutputIterator, class Generator>
void fill_container (OutputIterator first, Generator gen);

然后您可以替换现有容器中的元素，或使用 insert_iterator 从头开始填充等。您唯一需要做的就是提供适当的生成器。该名称甚至表明，如果您使用插入式迭代器，它希望容器为空。

为 "produce a populated container" 编写现代函数接口

Writing a modern function interface to "produce a populated container"

c++

c++11

c++14

c++17