6

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.

Daniel
  • 8,179
  • 6
  • 31
  • 56
  • 1
    `insert` needs to handle insertion in the middle, which requires copying or moving all subsequent elements, mostly using assignment. `push_back` only needs to handle insertion at the end. – T.C. Feb 15 '15 at 17:12
  • 1
    You do realise that your `for`...`push_back` and `insert` don't do the same thing, don't you? The former appends, the latter inserts at a specific position. –  Feb 15 '15 at 17:12

2 Answers2

7

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.

  • So does mean that contrary to the accepted answer in [this post](http://stackoverflow.com/questions/3177241/best-way-to-concatenate-two-vectors), the most efficient way to concatenate two vectors is actually `std::copy(v2.begin(), v2.end(), std::back_inserter(v1))`? – Daniel Feb 15 '15 at 17:28
  • 2
    @Daniel More general does not necessarily mean more efficient. – T.C. Feb 15 '15 at 17:33
  • @hvd I understand your answer, but I specifically referred to concatenating two vectors in my comment, where I'm assuming there will be no assignment as no elements need to change position. – Daniel Feb 15 '15 at 17:43
  • 1
    Also note that if you are inserting at the end, the assignment operator probably won't even be used (though it still needs to exist). – Benjamin Lindley Feb 15 '15 at 17:43
  • @BenjaminLindley Indeed, so if we are being pedantic, `insert` will surely have more conditionals than `copy`, and will therefore be less efficient *for concatenation*. Anyway.. this is probably going off topic. – Daniel Feb 15 '15 at 17:48
  • 2
    @Daniel Ah, I see what you're trying to say now. The `insert` method needs to work regardless of what arguments you pass to it. It may use the assignment operator with some argument values, and may not use them with some other values, but it won't be known at compile-time which approach gets used. Yeah, Benjamin Lindley is right, the assignment operator will likely appear only in a loop that happens to execute zero times in your case, which still requires it to exist, but won't affect performance. –  Feb 15 '15 at 17:48
  • @Daniel: `std::copy` used with a `back_inserter` though will have to check capacity for every inserted element. `vector::insert` doesn't need to do that (when passed random access iterators), if it is implemented optimally. – Benjamin Lindley Feb 15 '15 at 17:52
  • @BenjaminLindley that's true, I'm assuming `push_back` would need to make a similar check so even a hand-written loop wouldn't be more efficient. – Daniel Feb 15 '15 at 17:55
2

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))
Maxim Razin
  • 9,114
  • 7
  • 34
  • 33
  • 1
    "so, a move or copy constructor is required." -- The class in the question has both a copy and a move constructor. All it lacks is an assignment operator. –  Feb 15 '15 at 17:16