ansaurus

Question

What is the most efficient way to append one std::vector to the end of another?

Answer 1

+11 A:

After a lot of arguing (and a reasonable comment from Matthieu M. and villintehaspam), I'll change my suggestion to

v1.insert( v1.end(), v2.begin(), v2.end() );

I'll keep the former suggestion here:

v1.reserve( v1.size() + v2.size() ); 
v1.insert( v1.end(), v2.begin(), v2.end() );

There are some reasons to it the latter way, although none of them enough strong:

there is no guarantee on to what size will the vector be reallocated -- e.g. if the sum size is 1025, it may get reallocated to 2048 -- dependant on implementation. There is no such guarantee for reserve either, but for a specific implementation it might be true. If hunting for a bottleneck it might be rasonable to check that.
reserve states our intentions clear -- optimization may be more efficient in this case (reserve could prepare the cache in some top-notch implementation).
also, with reserve we have a C++ Standard guarantee that there will be only a single reallocation, while insert might be implemented inefficiently and do several reallocations (also something to test with a particular implementation).

Kornel Kisielewicz 2010-02-05 15:39:45

The reserve is most likely unnecessary, since that will probably be done automatically by the insert function.

villintehaspam 2010-02-05 15:41:26

There is no guarantee that reserve will allocate exactly the amount of storage you request. The only guarantee is that capacity() will be >= to what you request.

villintehaspam 2010-02-05 15:58:47

@villintehaspam - theres also **no** guarantee in the standard that insert will not do several reallocations instead of one. There **is** a guarantee on reserve however: `It is guaranteed that no reallocation takes place during insertions that happen after a call toreserve() until the time when an insertion would make the size of the vector greater than the sizespecified in the most recent call to reserve().` Hence, reserve is more safer.

Kornel Kisielewicz 2010-02-05 16:09:42

@Kornel Kisielewicz: Actually I believe there more or less is such a guarantee (for normal iterators) in item 23.2.4.4, where the complexity is specified to be linear in the number of elements in the range [first,last) plus the distance to the end of the vector. Multiple reallocations wouldn't fit the bill, unless I am mistaken?

villintehaspam 2010-02-05 16:18:43

@villintehaspam: strong point -- and I can put my weapons down in this argument, but not an ultimate one -- you assume that a reallocation takes O(n) time what might not be true in case if a vector would be implemented similarily to a "rope" -- hence fragmented. Not that I know of any such implementation, but it would still adhere to the 03 standard (not the 1x though, where data is guaranteed to be continuous). Also, I can fully imagine a implementation where reserve is "exact" while "insert" reallocation is not. It's always good to state your demands explicitly.

Kornel Kisielewicz 2010-02-05 16:27:12

A vector is already guaranteed to be contiguous. You must be confusing it with std::string.

UncleBens 2010-02-05 16:32:08

@UncleBens, true, my error.

Kornel Kisielewicz 2010-02-05 16:36:56

That reserve doesn't appear to make any difference neither with GCC 4.4 nor VC++ 2005. I think you are also confusing the whole matter with the resizing strategy used by push_back. (VC++ allocates more than requested for *strings* - at least with small values - so as to request blocks whose size is a multiple of two or so, but again reserving before appending makes no difference in the resulting capacity. Appending a string of 100 characters to a string of 100 characters results in a string with the capacity of 207 either way.)

UncleBens 2010-02-05 17:07:15

also, you should determine which of the vectors is larger than the other and insert the smaller one into the larger one ;)

ceretullis 2010-02-05 17:12:25

secondly, since you are using insert and not copy, the reserve is gratuitous... you don't need it. Under the hood insert is probably going to do the reserve in one chunk and not push_back() like copy() would.

ceretullis 2010-02-05 17:14:13

@ceretullis, now the size comparison point is a strong one, mind if I include that in the answer?

Kornel Kisielewicz 2010-02-05 17:18:42

What if it matters conceptually what is appended to what? - And another thought about the reserve issue: doesn't this increase the maintenance burden? It basically doesn't add any value, at least with some common implementations. However, I could imagine that eventually you might want to append the contents of a different vector altogether - now you might end up reserving *too little* and *two* memory allocations instead. (Anyway, I'm not religious about this.)

UncleBens 2010-02-05 17:50:22

@ceretullis: comparison is irrelevant here, since the OP requires that `v1` be the target and `v2` be appended to it. Sometimes order matters. Also, if I were to compare, I would rather check the capacity than the size, to see if one is big enough to contain all the data. If you have to extend the capacity of one, you will end up copying the content of both anyway, and the order of the copies does not really matter...

Matthieu M. 2010-02-05 17:58:57

@Kornel: I would probably not use `reserve` and trust `insert`. Also there is a confusion with complexity. `push_back` has amortized constant complexity because of the growing strategy used (usually `2*x+1`) and thus even with multiple reallocation `insert` would have an amortized linear complexity. Note that if you are inserting with anything else than `RandomAccessIterator`, you may be better off not computing the length of the range and just `push_back`... I don't know if they made a special case for `random_access_iterator_tag`.

Matthieu M. 2010-02-05 18:02:34

@Matthieu, *sigh*, you've convinced me, I edited the answer :>

Kornel Kisielewicz 2010-02-05 18:19:16

@Matthieu: good point about comparing capacity rather than size.

ceretullis 2010-02-05 23:14:24

Answer 2

+11 A:

Probably better and simpler to use a dedicated method: vector.insert

v1.insert(v1.end(), v2.begin(), v2.end());

As Michael mentions, unless the iterators are input iterators, the vector will figure out the required size and copy appended data at one go with linear complexity.

UncleBens 2010-02-05 15:40:12

AS long as the the iterators are forward, bidirectional, or random access,the final size of the vector will be determined up front and reserved. So there's no need to perform a `reserve()` up front. If the iterators happen to be input iterators, this can't be done, and the vector might have to be reallocated several times dependending on how many items end up getting added.

Michael Burr 2010-02-05 15:46:23

@Michael, see my answer for the reason for reserve.

Kornel Kisielewicz 2010-02-05 15:53:06

@Kornel Kisielewicz: That is incorrect, reserve might also allocate more memory than needed.

villintehaspam 2010-02-05 15:55:44

@villintehaspam - **might**, that's why I wrote "strong hint"

Kornel Kisielewicz 2010-02-05 15:58:21

I suppose it all comes down to quality of implementation. I prefer to trust the implementation, because I don't see a technical reason why that **reserve** should make any difference. If your implementation decides to overallocate with plain insert, it is just as likely to overallocate with reserve.

UncleBens 2010-02-05 16:27:00

@Michael: I don't know if I should be relieved that using forward iterators it will first compute the size... I mean it may require lots and lots of read all over the memory, how are we sure that this is better than just pushing back and (perhaps) reallocating ?

Matthieu M. 2010-02-05 18:04:46

@Matthieu: Appending is just a special case of inserting. And it is really hard to determine what would be more expensive - iterating a linked list to know its size, or risking with multiple reallocations. And the OP mentioned he's appending a **vector** to another vector.

UncleBens 2010-02-05 18:23:47

@Matthieu: All I can say is that the standard requires that when using forward iterators "complexity is linear in the number of elements in the range [first, last) plus the distance to the end of the vector". which I take to mean that it can't reallocate (and therefore copy the initial portion) of the array several times depending on the number of items in the iterator range. Therefore, as far as I can tell, it needs to figure out how many items are in the range up front.

Michael Burr 2010-02-05 18:31:00

@Michael: actually the complexity could well be "amortized linear". After all `push_back` has "amortized constant" complexity because of the growing strategy `2*x+1`. Therefore I am not sure that it actually compute the distance upfront, though it would definitely be a premium with `RandomAccessIterator` as it's a constant time operation.

Matthieu M. 2010-02-06 14:48:06

Answer 3

+1 A:

If you have a vector of pod-types, and you really need the performance, you could use memcpy, which ought to be faster than vector<>.insert(...):

v2.resize(v1.size() + v2.size());
memcpy((void*)&v1.front(), (void*)&v2[v1.size()], sizeof(v1.front())*v1.size());

Update: Although I would only use this if performance is really, really, needed, the code is safe for pod types.

Viktor Sehr 2010-02-05 15:44:16

Altough I'm not 100% sure because resize does a lot of unnessesary contructor calls.

Viktor Sehr 2010-02-05 15:45:52

@dirkgently: thats why I used resize and not reserve.

Viktor Sehr 2010-02-05 15:46:43

Yes, this is very fast, but it uses implementation details.

Notinlist 2010-02-05 15:53:26

Probably slower. It first sets the memory to zero, and then overwrites it with the correct values. A modern STL implementation detects PODs automatically, and when copying them will generate an __aligned__ memory copy. Thus, it saves both the zeroing and the alignment check in `memcpy()`

MSalters 2010-02-05 15:56:39

Can I do this for vector<shared_ptr<ptime>>? (ptime is immutable)

Alex Jenter 2010-02-05 15:57:10

@MSalters: a modern compiler might also detect that the zeros are never read, and skip the initialization.

Viktor Sehr 2010-02-05 16:01:52

@Alex Jenter: No you cant, only POD types(look up pod on wikipedia)

Viktor Sehr 2010-02-05 16:02:26

@Alex: I suspect that this would guarantee messing up the reference count. You'll have shared pointers in both v1 and v2, but those will not know they have been copied.

UncleBens 2010-02-05 16:03:19

@Viktor, @UncleBens: Thanks, you are absolutely right, come to think of it, I could have figured this out myself. Sorry. I feel stupid now :)

Alex Jenter 2010-02-05 16:06:00

If `memcpy` is really safe, the implementation probably calls it directly anyway.

Potatoswatter 2010-02-05 18:26:04

Answer 4

+3 A:

If you happen to use Boost you can download the development version of the RangeEx library from the Boost Vault. This lib. was accepted into Boost a while ago but so far it hasn't been integrated with the main distribution. In it you'll find a new range-based algorithm which does exactly what you want:

boost::push_back(v1, v2);

Internally it works like the answer given by UncleBens, but the code is more concise and readable.

Manuel 2010-02-05 16:50:35

ansaurus

tags:

views:

answers:

What is the most efficient way to append one std::vector to the end of another?

related questions