Nice way to append a vector to itself

Question

I want to duplicate the contents of the vector and want them to be appended at the end of the original vector i.e. v[i]=v[i+n] for i=0,2,...,n-1

I am looking for a nice way to do it, not with a loop. I saw std::vector::insert but the iterative version forbids a iterator to *this(i.e behaviour is undefined).

I also tried std::copy as follows(but it resulted in segmentation fault):

copy( xx.begin(), xx.end(), xx.end());

possible duplicate of [Wrong results when appending vector to itself using copy and back\_inserter](http://stackoverflow.com/questions/11511510/wrong-results-when-appending-vector-to-itself-using-copy-and-back-inserter) — Ben Voigt, Jul 14 '13 at 05:20
@BenVoigt, To be fair, when asking that question, I tried it and wanted to know why it didn't work. I didn't actually need an elegant working solution, so there are only mentions of any in the comments. — chris, Jul 14 '13 at 07:56
I have to wonder if most people would have got the implementation right the first time if they coded it with a loop. — MarkB, Jul 16 '13 at 01:52

Ben Voigt · Accepted Answer · 2014-03-13T18:34:47.570

Wow. So many answers that are close, none with all the right pieces. You need both resize (or reserve) and copy_n, along with remembering the original size.

auto old_count = xx.size();
xx.resize(2 * old_count);
std::copy_n(xx.begin(), old_count, xx.begin() + old_count);

or

auto old_count = xx.size();
xx.reserve(2 * old_count);
std::copy_n(xx.begin(), old_count, std::back_inserter(xx));

When using reserve, copy_n is required because the end() iterator points one element past the end... which means it also is not "before the insertion point" of the first insertion, and becomes invalid.

23.3.6.5 [vector.modifiers] promises that for insert and push_back:

Remarks: Causes reallocation if the new size is greater than the old capacity. If no reallocation happens, all the iterators and references before the insertion point remain valid. If an exception is thrown other than by the copy constructor, move constructor, assignment operator, or move assignment operator of T or by any InputIterator operation there are no effects. If an exception is thrown by the move constructor of a non-CopyInsertable T, the eﬀects are unspecified.

The first version generates a memset on both g++ and clang (plus a memmove). The second version can be optimized to a memmove. https://godbolt.org/z/U2dafw — user202729, Mar 15 '20 at 06:16
Looks to me as if the first version requires an accessible default constructor for the resize, while the second requires only a copy constructor. — Andrew Lazarus, Apr 24 '20 at 02:12
For the next one wondering, as I did: In addition to the different iterators, in the first example `vector::resize` is used, while in in the example `vector::reserve` is used. — Reizo, Aug 30 '20 at 22:45

Borgleader · Answer 2 · 2013-07-14T16:02:51.687

3

I would do it like this:

#include <algorithm>
#include <vector>
#include <utility>

int main(int argc, char* argv[])
{
    std::vector<int> v1 = { 1, 2, 3, 4, 5 };

    {
        std::vector<int> v2(v1.begin(), v1.end());
        std::copy(v1.begin(), v1.end(), std::back_inserter(v2));
        std::swap(v1, v2);
    }

    return 0;
}

EDIT: I added a slightly more efficient version.

#include <algorithm>
#include <vector>
#include <utility>

int main(int argc, char* argv[])
{
    std::vector<int> v1 = { 1, 2, 3, 4, 5 };

    {
        typedef std::move_iterator<decltype(v1)::iterator> VecMoveIter;
        std::vector<int> v2(v1);
        std::copy(VecMoveIter(v1.begin()), VecMoveIter(v1.end()), std::back_inserter(v2));
        v1 = std::move(v2);
    }

    return 0;
}

edited Jul 14 '13 at 16:02

answered Jul 14 '13 at 05:29

Borgleader

15,826
5
46
62

You forgot about the existence of a copy-constructor and `std::vector::insert` :) – chris Jul 14 '13 at 05:30
Not a bad thought, because the vector contents probably will get copied to a new location anyway. But you're adding an extra copy. Try constructing the new vector with the right capacity up front. – Ben Voigt Jul 14 '13 at 05:30
Also, it would be good to copy once and move the existing items instead of making two new copies of each. – Ben Voigt Jul 14 '13 at 05:33
Well if I do the allocation upfront I might as well delete my answer because then it becomes yours. But I agree on the move part of things. Besides the question is about a "nice way" not "the most efficient way" and I find my answer to be quite a clean and simple way of doing it. – Borgleader Jul 14 '13 at 06:01
@Borgleader: That wasn't where I meant to use move... I think there's a `std::move_iterator` adaptor you can use with the `std::copy`. – Ben Voigt Jul 14 '13 at 14:01
@BenVoigt Oh wow, TIL the existed. Thanks! (edited my answer in case anyone stumbles on to this question). – Borgleader Jul 14 '13 at 16:03

score 0 · Answer 3 · answered Jul 21 '14 at 15:53

For appending more than one slot of duplicates.

    int main() {
        std::vector<int> V;
        V.push_back(1);
        V.push_back(2);

        int oldSize = V.size();
        int newSize = oldSize;
        int nDupSlot = 4;

        V.resize(nDupSlot * oldSize);
        for(int i=0; i<(nDupSlot-1); ++i) {
            std::copy_n(V.begin(), oldSize, V.begin() + newSize);       
            newSize = newSize + oldSize;
         }

        for(int i =0; i<V.size(); ++i) {
            std::cout<<V[i];
            }

        return 0;
    }

Output:

12121212

score 0 · Answer 4 · answered Nov 22 '15 at 14:01

0

It might not be the most effective way, but it sure is simple:

std::vector<int> toAppend(xx);
xx.insert(xx.end(), toAppend.begin(), toAppend.end();

answered Nov 22 '15 at 14:01

Etienne

66
4

Nice way to append a vector to itself

4 Answers4

Linked

Related