Is It More Efficient to Copy a Vector by Reserving and Copying, or by Creating and Swapping

Is it more efficient to copy a vector by reserving and copying, or by creating and swapping?

Your second example does not work if you send the argument by reference. Did you mean

void copyVecFast(vec<int> original) // no reference
{

  vector<int> new_;
  new_.swap(original); 
}

That would work, but an easier way is

vector<int> new_(original);

Copying std::vector: prefer assignment or std::copy?

Generally I would strongly prefer v2 = v1:

1. It is shorter and makes the intent more clear
2. std::copy won't work if v2 doesn't have the same length as v1 (it won't resize it, so it will retain some of the old elements best case (v2.size() > v1.size() and overwrite some random data used elsewhere in the program worst case
3. If v1 is about to expire (and you use C++11) you can easily modify it to move the contents
4. Performancewise assignment is unlikely to be slower then std::copy, since the implementers would probably use std::copy internally, if it gave a performance benefit.

In conclusion, std::copy is less expressive, might do the wrong thing and isn't even faster. So there isn't really any reason to use it here.

Fastest way to copy one vector into another conditionally

Well, you could use back_inserter:

std::vector<int> foo = {...whatever...};
std::vector<int> bar;
std::back_insert_iterator< std::vector<int> > back_it (bar);

std::copy_if (foo.begin(), foo.end(), back_it, MyPredicate);

or count element:

std::vector<int> foo = {...whatever...};
int mycount = count_if (foo.begin(), foo.end(), MyPredicate);
std::vector<int> bar (mycount);

std::copy_if (foo.begin(), foo.end(), bar.begin(), MyPredicate );

A third solution:

std::vector<int> foo = {...whatever...};
std::vector<int> bar (foo.size());

auto it = std::copy_if (foo.begin(), foo.end(), bar.begin(), MyPredicate );
bar.resize(std::distance(bar.begin(),it));

Inefficiency of copy-and-swap idiom?

Copy-and-swap with a std::vector can indeed lead to performance loss. The main issue here is that copying a std::vector involves two distinct stages:

1. Allocate new section of memory
2. Copy stuff in.

Copy-and-swap can eliminate #2 but not #1. Consider what you would observe prior to the swap() call but after the assignment op is entered. You have three vectors- the one which is about to be overwritten, the one which is a copy, and the original argument.

This clearly implies that if the vector which is about to be overwritten had sufficient or excess capacity, there's a waste in the creation of the intermediate vector, and a loss in the extra capacity of the source. Other containers can behave this way as well.

Copy-and-swap is a great baseline, especially when it comes to exception safety, but it's not globally the highest-performant solution. If you're in a tight area, then other more specialized implementations can be more efficient- but be warned, exception-safety in this area is non-trivial, and sometimes impossible if not copy-and-swapped.

STL vector reserve() and copy()

As noted in other answers and comments, you should just use vector's built-in functionality for this. But:

When you reserve() elements, the vector will allocate enough space for (at least?) that many elements. The elements do not exist in the vector, but the memory is ready to be used. This will then possibly speed up push_back() because the memory is already allocated.

When you resize() the vector, it will allocate enough space for those elements, but also add them to the vector.

So if you resize a vector to 100, you can access elements 0 - 99, but if you reserve 100 elements, they are not inserted yet, just ready to be used.

What you want is something like this:

vec2.reserve( vec1.size() );
copy(vec1.begin(), vec1.end(), std::back_inserter(vec2));

std::back_inserter is defined in <iterator>

Why does reallocating a vector copy instead of moving the elements?

Tip-of-trunk clang + libc++ gets:

foo(1)
foo(2)
foo(move(foo(1))
~foo(2)
~foo(1)

If you remove the noexcept from the move constructor, then you get the copy solution:

foo(1)
foo(2)
foo(foo(1))
~foo(1)
~foo(2)
~foo(1)

Why is resizing a vector faster than reserve and push_back?

push_back is costlier operation than index based access even if allocation has been taken care of before hand by reserve.

1. push_back will need to take care of end pointer so that vector size can be computed correctly
2. push_back will check for realloaction need. Essentially a branch prediction.
3. push_back will cause copy (or move) of value to be pushed back. In case of int, it shouldn't cause performance difference.

If you see assembly conversion (Taken from godbolt link given in question), index operation is non branching sequence of few moves and shift operation while push_back is much more involved. In long running loop (1000000 in given example), this difference will matter. Compiler optimization level can definitely impact the difference.

For index operator []

    push    rbp
    mov     rbp, rsp
    mov     QWORD PTR [rbp-8], rdi
    mov     QWORD PTR [rbp-16], rsi
    mov     rax, QWORD PTR [rbp-8]
    mov     rax, QWORD PTR [rax]
    mov     rdx, QWORD PTR [rbp-16]
    sal     rdx, 2
    add     rax, rdx
    pop     rbp
    ret

For push_back

    push    rbp
    mov     rbp, rsp
    sub     rsp, 16
    mov     QWORD PTR [rbp-8], rdi
    mov     QWORD PTR [rbp-16], rsi
    mov     rax, QWORD PTR [rbp-8]
    mov     rdx, QWORD PTR [rax+8]
    mov     rax, QWORD PTR [rbp-8]
    mov     rax, QWORD PTR [rax+16]
    cmp     rdx, rax
    je      .L73
    mov     rax, QWORD PTR [rbp-8] // When allocation is not needed
    mov     rcx, QWORD PTR [rax+8]
    mov     rax, QWORD PTR [rbp-8]
    mov     rdx, QWORD PTR [rbp-16]
    mov     rsi, rcx
    mov     rdi, rax
    call    void std::allocator_traits<std::allocator<int> >::construct<int, int const&>(std::allocator<int>&, int*, int const&)
    mov     rax, QWORD PTR [rbp-8]
    mov     rax, QWORD PTR [rax+8]
    lea     rdx, [rax+4]
    mov     rax, QWORD PTR [rbp-8]
    mov     QWORD PTR [rax+8], rdx
    jmp     .L75
.L73:   // When allocation is needed
    mov     rax, QWORD PTR [rbp-8]
    mov     rdi, rax
    call    std::vector<int, std::allocator<int> >::end()
    mov     rcx, rax
    mov     rdx, QWORD PTR [rbp-16]
    mov     rax, QWORD PTR [rbp-8]
    mov     rsi, rcx
    mov     rdi, rax
.L75:
    nop
    leave
    ret

---

Related Topics