STL Containers Move Assignment Complexity

[Daniel Armengod]

I am new to this forums, somewhat new to participating in online forums in general and also a beginner programmer. Please point out any mistakes you see in this post, be they related to the question or the post itself (e.g. filed under incorrect subforum, question not explained well enough, answer readily available somewhere else). Thank you for your time.

While reading the reference on vectors I came across something I don't understand.
http://www.cplusplus.com/reference/vector/vector/operator=/
The complexity of the move assignment operation for vectors¹ is listed as having linear complexity in size. That confuses me to no end because I've also been reading up on rvalue references and move semantics, and I kinda expected the move assignment operation to have constant complexity (like the move construction does, because isn't that the whole point?).

What's worse is that I found a different source (http://en.cppreference.com/w/cpp/container/vector/operator%3D) that claims the operation has constant complexity! Which one is correct, and why? The only thing I can think of (and I might have it all wrong) is that the linear cost comes from possible destructor calls of the assignment target's contained objects, if those are of a class that has a custom destructor. In that case I believe it would be linear in the target's size, instead of the source's size.

Of course, it might just be that one of the sites is wrong, but it's generally a very bad idea to go with that assumption unless you know the subject you're reading on damn well.

¹ In fact, all containers that define a custom operator= are listed as having linear complexity for move assignment.

[MiiNiPaa]

It is values for copy assigment, just was not updated for C++11. Complexivity for move assigment is constant.
Cost of destruction usually not counted in complexivity calculations.

[Peter87]

The vector that is assigned to might already contain elements and those elements will all have to be destroyed first so that is why the complexity is linear.

[JLBorges]

Since C++11, you can use the move assignment semantics instead. All containers provide move assignment operators (array<> implicitly again), declared for rvalues, which internally just swap pointers to the memory of values rather than copying all values. The exact behavior is not specified, but the guarantee of constant complexity for this operation leads to an implementation like this. The C++ standard library simply specifies that after a move assignment, the container on the left hand side of the assignment has the elements that the container on the right hand side of the assignment had before. The contents of the container on the right hand side are undefined afterward:

    std::vector<int> v1 ;
    std::vector<int> v2 ;
    
    // ...
    
    // move contents of v1 into v2, state of v1 undefined afterward
    v2 = std::move(v1) ;

So, for performance reasons, you should use this way of assignmentif after the assignment, the contents of the container on the right hand side are no longer used.
- 'The C++ Standard Library: A Tutorial and Reference' by Nicolai M. Josuttis

Essentially, that means: v2 = std::move(v1) ; may be implemented as: std::swap(v1,v2) ;

[Cubbi]

it's constant unless POCMA is false and the allocators don't compare equal, in which case it's linear since it's forced to move-assign every element individually. cppreference explains it in the text, but not in the complexity summary. fixed.