3

当我开始学习 C++03 时，我学会了几种编写“给我东西集合”函数的方法。但每个都有一些挫折。

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

或者：

void make_collection( std::vector<Thing> & );
  • 这与容器无关
  • 该接口不会传达预期的空容器。

或者：

std::vector<Thing> make_collection();
  • 这与容器无关
  • 有几种不必要的复制途径。（错误的容器类型，错误的包含类型，没有 RVO，没有移动语义）

使用现代 C++ 标准，是否有更惯用的函数接口来“生成填充容器”？

4

4 回答 4

7

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

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

Asink是一个可调用的，它使用 的实例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&&...，但是我们为我们拥有的标准库编写代码，而不是我们希望拥有的标准库。

以上都是通用库代码。

在您的集合生成的标题中，您将有两个函数。一个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;
}

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

以上假设您的收藏是int. 只需更改传递给sink的类型并使用不同的类型。生成的集合不必是 的集合int，只要是可以int作为其插入迭代器输入的任何内容即可。

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

std::function是 C++11 的新手，但可以在 C++03 或更早版本中实现。带有赋值捕获的autolambda 是 C++14 构造，但可以在 C++03 中实现为非匿名辅助函数对象。

我们还可以通过一些标签调度来优化make_collection一些东西（这样可以避免类型擦除开销）。std::vector<int>make_collection<std::vector<int>>

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

第一个是一个输入迭代器，它调用一些函数来生成项目并推进，最后一个是一个标记迭代器，当集合耗尽时与第一个迭代器比较。

该范围可以operator Container使用 SFINAE 测试“它是否真的是一个容器”，或者.to_container<Container>使用一对迭代器构建容器，或者最终用户可以手动进行。

These things are annoying to write, but Microsoft is proposing Resumable functions for C++ -- await and yield that make this kind of thing really easy to write. The generator<int> returned probably still uses type erasure, but odds are there will be ways of avoiding it.

To understand what this approach would look like, examine how python generators work (or C# generators).

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

note how fill_container sort of looks like make_inserting_sink turned upside down.

As noted above, the pattern of a generating iterator or range can be written manually without resumable functions, and without type erasure -- I've done it before. It is reasonably annoying to get right (write them as input iterators, even if you think you should get fancy), but doable.

boost also has some helpers to write generating iterators that do not type erase and ranges.

于 2015-03-05T18:23:47.380 回答
2

If we take our inspiration from the standard, pretty much anything of the form make_<thing> is going to return <thing> by value (unless profiling indicates otherwise I don't believe returning by value should preclude a logical approach). That suggests option three. You can make it a template-template if you wish to provide a bit of container flexibility (you just have to have an understanding as to whether the allowed container is associative or not).

However depending on your needs, have you considered taking inspiration from std::generate_n and instead of making a container, provide a fill_container functionality instead? Then it would look very similar to std::generate_n, something like 

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

Then you can either replace elements in an existing container, or use an insert_iterator to populate from scratch, etc. The only thing you have to do is provide the appropriate generator. The name even indicates that it expects the container to be empty if you're using insertion-style iterators.

于 2015-03-05T18:41:36.947 回答
0

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

std::vector<Thing> make_collection()
于 2015-03-05T18:17:44.807 回答
0

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

std::vector<Thing> make_collection();

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

于 2015-03-05T18:21:51.447 回答