用於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以外，沒有標準容器被允許進行元素智能交換。