编写一个现代功能界面来"生成一个填充的容器"

Question

当我在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++标准,是否有一个更加惯用的函数接口来"生成一个填充的容器"？

Answer 1

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

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&&...,但是我们为我们拥有的标准库编写代码,而不是我们希望拥有的标准库.

以上都是通用库代码.

在您的集合生成的标题中,您有两个功能.一个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或之前实现.auto具有赋值捕获的lambda是C++ 14构造,但可以在C++ 03中实现为非匿名辅助函数对象.

我们还可以make_collection通过一些std::vector<int>标签调度来优化(因此make_collection<std::vector<int>>可以避免类型擦除开销).

现在有一种完全不同的方法.编写生成器迭代器而不是编写集合生成器.

第一个是输入迭代器,它调用一些函数来生成项目并前进,最后一个是一个sentinal迭代器,它在收集时被比较时等于第一个迭代器.

该范围可以operator Container使用SFINAE测试"它真的是一个容器",或者.to_container<Container>用一对迭代器构造容器,或者最终用户可以手动完成.

这些东西很难编写,但是微软正在为C++提出Resumable函数 - 等待和屈服,这使得这类东西真的很容易编写.在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 还有一些助手可以编写生成迭代器而不键入erase和range.