是否可以在O(1)时间内为C++向量赋值？

Question

请考虑以下Python程序,并执行以下步骤:

1)初始化两个列表A和B.

2)我们指定A = B.该操作的时间复杂度为O(1).

3)我们为B分配一个新的列表,它不会改变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]

现在,我想在C++中做类似的事情,其中​​A和B是向量:

1)初始化两个向量A和B.

2)我们指定A = B.根据en.cppreference.com,该操作的时间复杂度为O(n).

3)我们为B分配一个新的列表,它不会改变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]

我的问题

Python和C++程序之间的区别在于步骤2)的时间复杂度,其中我们指定A = B.

• 在Python中,它需要O(1)时间,因为我们只更改引用.然后'指向'B,即A和B都是对同一对象的引用.
• 在C++中,它需要O(n)时间,因为B的内容被复制到A. A不会'指向'与B相同的对象.

有没有办法让C++中的向量A指向O(1)时间内的向量B？

注意:我对C++不太熟悉,所以我甚至不知道将A和B视为C++中向量对象的引用是否有效.

Answer 1

由于您B在分配之后不使用值(之后A直接分配给它),您可以利用C++ 11移动语义:

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]

移动赋值运算符的时间复杂度为:

常量,除非std::allocator_traits<allocator_type>::propagate_on_container_move_assignment() 是false和分配器不比较相等(在这种情况下是线性的).

来源.