---

为什么 std::vector::swap 高效？

本文记录一些零碎的源码阅读笔记，逐步拼凑成一个整体，帮助理解：当我们在操作 vector 时，背后究竟发生了什么，为什么它能在保持高效的同时提供稳定的接口。

---

一、swap 的接口定义

在 libstdc++ 中，vector::swap 的实现如下：

/**
 *  @brief  Swaps data with another %vector.
 *  @param  __x  A %vector of the same element and allocator types.
 *
 *  This exchanges the elements between two vectors in constant time.
 *  (Three pointers, so it should be quite fast.)
 *  Note that the global std::swap() function is specialized such that
 *  std::swap(v1,v2) will feed to this function.
 *
 *  Whether the allocators are swapped depends on the allocator traits.
 */
void swap(vector& __x) noexcept {
#if __cplusplus >= 201103L
    __glibcxx_assert(_Alloc_traits::propagate_on_container_swap::value
             || _M_get_Tp_allocator() == __x._M_get_Tp_allocator());
#endif
    this->_M_impl._M_swap_data(__x._M_impl);
    _Alloc_traits::_S_on_swap(_M_get_Tp_allocator(),
                              __x._M_get_Tp_allocator());
}

调用 v1.swap(v2) 或 std::swap(v1, v2) 最终都会触发这段逻辑。

---

二、发生了什么？

vector 内部使用 _M_impl 作为存储管理层，里面维护了三个关键指针：

• _M_start → 起始位置
• _M_finish → 当前元素的结束位置
• _M_end_of_storage → 容量的结束位置

交换时，实际上只需要 交换这三个指针，而不必拷贝或移动元素。

_M_swap_data 的实现

void _M_swap_data(_Vector_impl_data& __x) noexcept {
    _Vector_impl_data __tmp;
    __tmp._M_copy_data(*this);
    _M_copy_data(__x);
    __x._M_copy_data(__tmp);
}

void _M_copy_data(const _Vector_impl_data& __x) noexcept {
    _M_start = __x._M_start;
    _M_finish = __x._M_finish;
    _M_end_of_storage = __x._M_end_of_storage;
}

这段代码做的事情非常简单：把三个指针在两个 vector 之间互换。

---

三、为什么这样高效？

1. 仅交换指针

   • swap 并没有对元素做逐个拷贝或移动操作，只是简单地互换内部指针。
   • 时间复杂度：O(1)。

2. 避免内存分配

   • 两个 vector 的底层内存并没有被释放或重新申请。
   • vector1 直接“接管”了 vector2 的内存，反之亦然。

3. 安全性保障

   • 前提是 两个 vector 使用相同的分配器（allocator）。
   • 如果 allocator 不一致，简单的指针交换可能带来严重问题，所以源码里有断言检查。

4. 实现层与接口层分离

   • vector 把底层实现细节封装在 _M_impl 中。
   • swap 只需要操作 _M_impl，不会破坏其他接口。
   • 这种分层设计使得指针交换成为可行且高效的方案。

---

四、类比与启示

这种实现让 swap 成为一种“廉价”的操作：

• 普通的元素拷贝或赋值，可能是 O(n)。
• swap 只需交换 3 个指针，复杂度 O(1)，开销几乎可以忽略不计。

在实际开发中，这种 接口层与实现层分离 的思想非常重要：

• 接口层只负责语义正确性。
• 实现层封装底层细节，保证可扩展性和高效性。
• 例如：多加一层 _M_impl，就使得 swap 变得极其高效。

正如一句话所说：

没有什么问题是多分一层解决不了的，如果有，那说明你的代码设计有问题。

---

五、总结

• vector::swap 的本质是 三个指针的交换。
• 不会涉及元素拷贝、析构或内存分配。
• 因此它是一个 常数时间 操作，非常高效。
• 高效的背后，是 vector 的 实现层设计合理（指针 + allocator 封装）。

---