为什么C++向量交换方法具有恒定的时间复杂度

Question

根据http://www.cplusplus.com/reference/vector/vector/swap/，交换两个向量内的元素仅具有恒定的复杂性。这是如何实施的？

Answer 1

无需逐一检查和交换每个元素。简单的向量实现具有两个成员的等价物：大小和指向数据的指针：

template<typename T>
class vector {
    std::size_t size;
    T* data;
};

要交换两个向量，只需交换其中每个成员即可。通过交换指针，这个向量将指向自由存储上另一个向量的数据，另一个向量将指向这个向量的数据。由于数据位于自由存储上，因此其生命周期并不与向量本身的生命周期固有地相关，因此像这样交换指针将导致每个向量接管另一个向量数据的生命周期，而不会出现问题。

void swap(vector& other) {
    using std::swap;
    swap(size, other.size);
    swap(data, other.data);
}

std::vector考虑到它需要处理的所有细节，其实现要复杂得多，但这个概念对于交换两个向量仍然适用。