C++ STL中向量的恒定时间交换逻辑

Question

为什么交换两个C++ STL向量的内容所需的时间复杂度与相应向量的大小无关？

参考:http://www.cplusplus.com/reference/vector/vector/swap/

Answer 1

典型的矢量实现存储:

• 分配器
• 指向第一个元素的指针
• 指向过去位置的指针,或等效的大小
• 指向向量所拥有的内存块末尾的指针,或等效的容量

swap()简单地交换指针,如果allocator_traits<allocator_type>::propagate_on_container_swap::value是,则为分配器.它没有按元素交换.实际上,除了std::array允许进行元素交换之外,没有标准容器.