Is it possible to assign new value to C++ vector in O(1) time?

Question

Consider the following Python program with the following steps:

1) Two lists A and B are initialized.

2) We assign A = B. The time complexity of this operation is O(1).

3) We assign a new list to B which does not change A.

A = [1, 2, 3]
B = [7, 8]
# A contains [1, 2, 3]
# B contains [7, 8]

#------------------------------------

A = B
# A contains [7, 8]
# B contains [7, 8]
# time complexity: O(1)

#------------------------------------

B = [55, 66, 77, 88]
# A still contains [7, 8]
# B now contains [55, 66, 77, 88]

Now, I want to do something similar in C++ where A and B are vectors:

1) Two vectors A and B are initialized.

2) We assign A = B. The time complexity of this operation is O(n) according to en.cppreference.com.

3) We assign a new list to B which does not change A.

vector<int> A = {1, 2, 3};
vector<int> B = {7, 8};
// A contains [1, 2, 3]
// B contains [7, 8]


A = B;   
// A contains [7, 8]
// B contains [7, 8]
// time complexity: O(n)


B = {55, 66, 77, 88};
// A still contains [7, 8]
// B now contains [55, 66, 77, 88]

My question

The difference between the Python and C++ program is the time complexity of step 2) where we assign A = B.

• In Python it takes O(1) time because we only change a reference. A then 'points to' B, i.e. A and B are both references to the same object.
• In C++ it takes O(n) time because the content of B is copied to A. A does not 'point to' the same object as B.

Is there any way to make the vector A in C++ point to the vector B in O(1) time?

Note: I'm not very familiar with C++ and so I don't even know if it's valid to consider A and B as references to vector objects in C++.

Answer 1

Since you don't use value of B after assigning it to A (you assign to it directly afterwards) you can take advantage of C++11 move semantics:

vector<int> A = {1, 2, 3};
vector<int> B = {7, 8};
A = std::move(B);
// O(1), see below
// B is in indeterminate but usable state now (probably empty).

B = {55, 66, 77, 88};
// A still contains [7, 8]
// B now contains [55, 66, 77, 88]

Time complexity of move assignment operator is:

Constant unless std::allocator_traits<allocator_type>::propagate_on_container_move_assignment() is false and the allocators do not compare equal (in which case linear).

source.