交换两个整个向量/队列/堆栈时间成本？

Question

例如:

v1 = {1,2,3},    v2 = {4,5};
swap(v1, v2);

现在v1 = {4,5}, v2 = {1,2,3}

我认为它应该非常快,不考虑这两个向量的长度吗？它只是交换指针？

Answer 1

1. 我认为它应该非常快,不考虑这两个向量的长度吗？

是.std::swap因为标准std::vector的复杂性保证是恒定的时间:

23.3.6.3 $ 10,11 [vector.capacity](由我粗体显示):

void swap(vector& x);
效果:将*的内容和容量()与x的内容和容量()进行交换.
复杂性:恒定时间.

按$ 23.3.6.6/1 [vector.special],std::swapfor std::vectorSpecialized as:

template <class T, class Allocator>
void swap(vector<T,Allocator>& x, vector<T,Allocator>& y);
功效:
x.swap(y);

这里有一些解释:std :: vector :: swap和std :: swap(std :: vector)

将容器的内容与其他容器的内容进行交换.不会对单个元素调用任何移动,复制或交换操作.所有迭代器和引用仍然有效.过去的迭代器无效.

复杂性:不变.

2. 它只是交换指针？

基本上,它取决于您正在使用的STL的实现,但它是实现它的最常用方法.