1

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.

Walter
  • 44,150
  • 20
  • 113
  • 196
  • 1
    The return value of a function is already an rvalue (if it's not an lvalue reference), so you don't need to `std::move` it. – dyp Sep 13 '13 at 07:06
  • "without copying any element" is moving the elements allowed? – dyp Sep 13 '13 at 07:08
  • @DyP right. I only wanted to emphasize that no copy is done at that stage and that `acc.append()` (whatever that is) should take a rvalue reference. – Walter Sep 13 '13 at 07:08
  • A direct answer to your question, but probably not what you're looking for: `std::anycontainer` in which you can move the vector. This is not ideal for accessing afterwards. – stefaanv Sep 13 '13 at 07:09
  • @stefaanv Yes, I know that solution. It is exactly the one I wanted to avoid. – Walter Sep 13 '13 at 07:11
  • do you want to have the `acc` container hide from the user that it got initialized from several individual containers? In that case, I think the answer is no. – TemplateRex Sep 13 '13 at 07:12
  • @TemplateRex You think. I though so too. Can you be more affirmative (and provide evidence)? – Walter Sep 13 '13 at 07:13
  • I.e. you want something like a `deque`, i.e. a list of chunks, where you can manually add those chunks? – dyp Sep 13 '13 at 07:14
  • What you're asking for is an STL container for iterator ranges for which it provides a meta-iterator? E.g. you say `std::vector v1 = { 1,2,3 }; std::vector v2 = { 4,5,6 }; acc.add(v1); acc.add(v2);` and 'acc' contains references/pointers/iterators for v1 and v2, not actually copying the data, but `acc[3]` or `acc.begin() + 3` would return '4'? I don't think such a thing exists. – kfsone Sep 13 '13 at 07:16
  • Yeah, clearly a container that internally has a list/array of chunks is what we need, i.e. a `std::deque` or a `container`. For the former, I don't know how to append `vector`s. For the latter there is no single iterator for iterating all elements ... – Walter Sep 13 '13 at 07:18
  • Maybe you rather need an iterator than a new container type. E.g. use `list>` or `vector>` (or `deque>`) and then provide an iterator type that iterates over all nested elements. – dyp Sep 13 '13 at 07:19
  • One workaround would be storing the returned vectors and keeping another vector of pointers to the elements. – JohannesD Sep 13 '13 at 07:20
  • @JohannesD but how to you iterate with a single iterator all elements? – Walter Sep 13 '13 at 07:22
  • @Walter - the vector of pointers would store a pointer to each element in each of the vectors, so, given two vectors `v` and `w`, it would look like `{ &v[0], &v[1], ..., &v[n], &w[0], &w[1], ..., &w[m] }` – JohannesD Sep 13 '13 at 07:27

1 Answers1

3

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.

Community
  • 1
  • 1
TemplateRex
  • 69,038
  • 19
  • 164
  • 304
  • *you want a `acc_container>`* why? What about `std::deque<>` (which internally has the former structure)? – Walter Sep 13 '13 at 07:43
  • @Walter - `std::deque` maintains carefully selected invariants on the length and number of the internal "chunks" to be performant - not just any old vectors will do. – JohannesD Sep 13 '13 at 07:55
  • @Walter First: a `std::deque` does not expose these internal "pages" in its interface. Furthermore, a `std::deque` has fixed-size pages in practice, not variable sized ones like you need if you want to append arbitrary vectors. Finally, with internal pages, how are you going to append without copying? Remember, moving containers is copying handles. – TemplateRex Sep 13 '13 at 08:08
  • @Walter I updated my answer with a link to an interesting paper on the subject. – TemplateRex Sep 16 '13 at 14:03
  • @TemplateRex thnx. Yes, it looks really old (though I couldn't find a date, but they cite nothing more recent than 1998). They even thank our own Dietmar Kuehl in the acknowledgements ... – Walter Sep 16 '13 at 15:01