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

Question

When I cut my teeth on C++03, I learned several approaches to writing a "give me the collection of things" function. But each has some setbacks.

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

• This must be implemented in a header file
• The interface doesn't communicate that an empty container is expected.

or:

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

• This is not container agnostic
• The interface doesn't communicate that an empty container is expected.

or:

std::vector<Thing> make_collection();

• This is not container agnostic
• There are several avenues for unnecessary copying. (Wrong container type, wrong contained type, no RVO, no move semantics)

Using modern C++ standards, is there a more idiomatic function interface to "produce a populated container"?

Answer 1

The first approach is type erasure based.

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

A sink is a callable that consumes instances of T. Data flows in, nothing flows out (visible to the caller).

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 takes a container, and generates a sink that consumes stuff to be inserted. In a perfect world, it would be make_emplacing_sink and the lambda returned would take auto&&..., but we write code for the standard libraries we have, not the standard libraries we wish to have.

Both of the above are generic library code.

In the header for your collection generation, you'd have two functions. A template glue function, and a non-template function that does the actual work:

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

You implement impl::populate_collection outside the header file, which simply hands over an element at a time to the sink<int>. The connection between the container requested, and the produced data, is type erased by sink.

The above assumes your collection is a collection of int. Simply change the type passed to sink and a different type is used. The collection produced need not be a collection of int, just anything that can take int as input to its insert iterator.

This is less than perfectly efficient, as the type erasure creates nearly unavoidable runtime overhead. If you replaced void populate_collection( sink<int> ) with template<class F> void populate_collection(F&&) and implemented it in the header file the type erasure overhead goes away.

std::function is new to C++11, but can be implemented in C++03 or before. The auto lambda with assignment capture is a C++14 construct, but can be implemented as a non-anonymous helper function object in C++03.

We could also optimize make_collection for something like std::vector<int> with a bit of tag dispatching (so make_collection<std::vector<int>> would avoid type erasure overhead).

---

Now there is a completely different approach. Instead of writing a collection generator, write generator iterators.

The first is an input iterator that call some functions to generate items and advance, the last is a sentinal iterator that compares equal to the first when the collection is exhasted.

The range can have an operator Container with SFINAE test for "is it really a container", or a .to_container<Container> that constructs the container with a pair of iterators, or the end user can do it manually.

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.

Answer 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.

Answer 3

You can do this in c++11 without container copying. Move constructor will be used instead of a copy constructor.

std::vector<Thing> make_collection()

Answer 4

I don't think there is one idiomatic interface to produce a populated container, but it sounds like in this case you simply need a function to construct and return a container. In that case you should prefer your last case:

std::vector<Thing> make_collection();

This approach will not produce any "unnecessary copying", as long as you are using a modern C++11-compatible compiler. The container is constructed in the function, then moved via move semantics to avoid making a copy.