用于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以外，没有标准容器被允许进行元素智能交换。