Search code examples
c++c++11containersmove

Accumulating many vectors into a single container w/o copying


Is it possible in C++11 to accumulate many std::vectors, each returned by given a function (whose API I cannot change), into a std container without copying any element?

std::vector<int> make_vect();
container acc;                           // what is container?
do {
    acc.append(std::move(make_vect()));  // how to implement this?
} while(acc.size() < n);

Note 1 that elements must not be copied even if they have no move constructor of move assignment operator, such as int in the example. So you can move a chunk of elements (by copying a pointer), but not individual elements.

Note 2 that container must allow for iteration through all accumulated elements using a single iterator. So std::vector<std::vector<>> or similar is not allowed.

Clearly, it is straightforward to write some container allowing this or to use std::list<std::vector<>> and provide your own iterator, but does the std library provide the desired functionality without such user-written additions?

It seems that the requested functionality is nothing particularly outlandish and I'm surprised how hard (if not impossible) it is even with C++11.


Solution

  • TL;DR I don't think a stock Standard Container can do what you ask. Here's why.

    Remember that move semantics for containers are efficient because they are implemented as scope-bound handles to dynamically allocated memory. Moving a container is implemented as copying the handle, while not touching the contained elements.

    Your first (explicit) constraint is not to copy any element of any of the containers. That necessitates copying the handles into your putative acc_container. In other words, you want a acc_container<std::vector<T>>. Any of the Standard Containers will allow you to do that efficiently no matter how big individual T elements.

    Your second (implicit, inferred from the comments) constraint is that you want to have a uniform interface over all the elements of all individual vectors. In other words, you would like to use this as acc_container<T>. This requires an extra level of indirection in the iterators of your acc_container, where the iterator detects it has reached the end of one of the current vector<T>, and jump to the beginning of the next vector<T>.

    Such a container does not exist in the Standard Library.

    The easiest work-around is to use a std::vector<std::vector<T>> (to avoid copying T elements), and write your own iterator adaptors (e.g. using boost::indirect_iterator, to provide iteration over T elements).

    Unfortunately, even if you provide non-member begin() / end() functions that initialize these indirect iterators from the member .begin()/.end(), range-for will not use ADL to look up these functions because it will prefere the old member functions .begin() / .end(). Furthermore, you will not be able to e.g. insert() a T element directly into your compound container, unless you also provide non-member insert() (and similarly for other functionality).

    So if you want a bona fide compound container, with range-for support and a native interface of member functions, you need to write one yourself (with std::vector<std::vector<T> as back-end, and the entire std::vector<T> interface written on top of it). Maybe you can suggest it on the Boost mailinglist as a nice project.

    UPDATE: here's a link to an old paper by Matt Austern on Segmented Iterators and Hierarchial Algorithms that shows some performance benefits from this approach. The downside is that you also need to make standard algorithms aware of these iterators.