是否可以在O(1)时间内将新值分配给C ++向量? [英] Is it possible to assign new value to C++ vector in O(1) time?

问题描述

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

1) Two lists A and B are initialized.

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

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

3)我们为B分配了一个新列表，但不会更改A.

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]

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

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

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

1) Two vectors A and B are initialized.

2)我们分配A =B.根据

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

3)我们为B分配了一个新列表，但不会更改A.

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]

我的问题

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

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

• 在Python中，这需要O(1)时间，因为我们仅更改引用.然后A指向" B，即A和B都是对同一个对象的引用.
• 在C ++中，由于B的内容被复制到A，所以需要O(n)时间.A不会指向"与B相同的对象.

有什么方法可以使C ++中的向量A在O(1)时间内指向向量B?

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

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

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++.

推荐答案

由于您在将 B 的值分配给 A 后不再使用它(您将其分配给它)然后直接使用)，您可以利用C ++ 11 move语义:

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:

常数，除非 std :: allocator_traits< allocator_type> :: propagate_on_container_move_assignment()是 false 并且分配器的比较结果不相等(在这种情况下线性).

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).

源.

这篇关于是否可以在O(1)时间内将新值分配给C ++向量?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！