c++ - 具有恒定复杂度的双端队列交换函数的实现

Question

据说 std::deque 交换函数需要恒定的时间，而不是线性的。 http://www.cplusplus.com/reference/deque/deque/swap-free/。那么该功能是如何实现的呢？

Answer 1

所有可调整大小的标准库容器（即所有 except std::array）都必须将其内容存储在动态分配的内存中。那是因为它们可以任意变大，并且没有办法在容器对象本身占用的固定空间中存储任意多个对象。换句话说，它一定是可能的container.size() > sizeof(container)。

这意味着容器对象只存储指向其内容的指针，而不是内容本身。因此，交换两个容器意味着简单地交换这些指针。以极其简化的形式：

template <class T>
class Container
{
  T *_begin, *_end;

  friend void swap(Container &a, Container &b)
  {
    std::swap(a._begin, b._begin);
    std::swap(a._end, b._end);
  }
};

当然，在实践中，这会因为分配器等的存在而变得复杂，但原理是一样的。

Answer 2

deque 的实现通常通过使用 pimpl idiom 来隐藏（每个 deque 都有一个指向实现的指针）。然后交换指针。可能（也）是双端队列至少持有一个指向其缓冲区的指针，然后交换（与相关成员，如大小）。

这篇文章（复制和交换习语）与如何实现交换有关。