Aggregating contributions from multiple donors

Question

As I try to modernize my C++ skills, I keep encountering this situation where "the STL way" isn't obvious to me.

I have an object that wants to gather contributions from multiple sources into a container (typically a std::vector). Each source is an object, and each of those objects provides a method get_contributions() that returns any number of contributions (from 0 to many). The gatherer will call get_contributions() on each contributor and aggregate the results into a single collection.

The question is, what's the best signature for get_contributions()?

Option 1: std::vector<contribution> get_contributions() const

This is the most straightforward, but it leads to lots of copying as the gatherer copies each set of results into the master collection. And yes, performance matters here. For example, if the contributors were geometric models and getting contributions amounted to tesselating them into triangles for rendering, then speed would count and the number of contributions could be enormous.

Option 2: template <typename container> void get_contributions(container &target) const

This allows each contributor to add its contributions directly to the master container by calling target.push_back(foo). The drawback here is that we're exposing the container to other types of inspection and manipulation. I'd prefer to keep the interface as narrow as possible.

Option 3: template <typename out_it> void get_contributions(out_it &it) const

In this solution, the aggregator would pass a std::back_insert_iterator for the master collection, and the individual contributors would do *it++ = foo; for each contribution. This is the best I've come up with so far, but I'm left with the feeling that there must be a more elegant way. The back_insert_iterator feels like a kludge.

Is Option 3 the best, or is there a better approach? Does this gathering pattern have a name?

Answer 1

There's a fourth, that would require you to define you iterator ranges. Check out Alexandrescu's presentation on "Iterators must go".

Answer 2

I would say there are two idiomatic STL ways: your Option 3 (taking an output iterator, which you'd pass by value, by the way) and taking a functor which you would call with each of the contributions.

Each of these is only appropriate if it is suitable to implement get_contributions as a template, of course.

Answer 3

Option 3 is the most idiomatic way. Note that you don't have to use back_insert_iterator. If you know how many elements are going to be added, you can resize the vector, and then provide a regular vector iterator instead. It won't call push_back then (and potentially save you some copying)

back_insert_iterator's main advantage is that it expands the vector as needed.

It's not a kludge though. It's designed for this exact purpose.

One minor adjustment would be to take pass the iterator by value, and then return it when the function returns.