CODEWITHSUNDEEP
c++c++11vector
Daniel
Daniel

Reputation: 8441

Why does std::vector::insert need to copy assign?

I was trying to understand the following behaviour:

#include <vector>
#include <iterator>    

struct Foo {
    Foo(int a) : a_ {a} {}
    const int a_; // Note the const
};

int main(int argc, char **argv) {
    std::vector<Foo> v1 {Foo {0}};
    std::vector<Foo> v2 {Foo {1}};

    auto first = std::begin(v2);
    auto last  = std::end(v2);

    for (; first != last; ++first) {
        v1.push_back(*first); // Fine
    }

    //v1.insert(v1.begin(), first, last); // Does not compile

    return 0;
}

It turns out the const member of Foo was implicitly deleting Foos copy-assignment operator, which std::vector::insert used.

Why does std::vector::insert need to copy assign while std::vector::push_back copy constructs? Does this mean it can be more efficient to manually concatenate two vectors? This is using LLVM.

Upvotes: 6

Views: 2166

Answers (2)

user743382
user743382

Reputation:

There is no reason why an assignment operator would be required, logically speaking. The insert operation can be implemented entirely by moving any existing element vec[x] to vec[x+1] by using (roughly) vec[x+1].~T(); new(&vec[x+1]) T(std::move(vec[x])); in a loop to destroy an existing element, and use in-place construction to move the previous element forward.

However, a more natural approach to write this, which in well-designed classes is typically at least as efficient if not more so too, is to use assignment for that: vec[x+1] = std::move(vec[x]);. An easy example of when it can be more efficient is if the construction and destruction of the vector's elements involves allocating and deallocating memory: using assignment easily bypasses that.

A decision was made that allowing vectors to use assignment operators has more benefits than drawbacks. Your class is unusual, and your class happens not to benefit from this decision. It's unfortunate, but there's no way of designing a vector that's perfect for every use case.

Upvotes: 8

Maxim Razin
Maxim Razin

Reputation: 9466

To insert an element into the vector, if it's not the end, you should move all the tail elements

[1][2][3][4][5]
 |  |  |    \  \ 
[1][2][3][6][4][5]

so, a move or copy constructor is required.

http://en.cppreference.com/w/cpp/container/vector/insert

You still can convert the loop into

copy(first, last, back_insterter(v1))

Upvotes: 2

Related Questions