std::vector::swap 实际上是做什么的？

Question

触发这个问题的是一些代码：

std::vector<int> x(500);
std::vector<int> y;

std::swap(x,y);

而且我想知道交换两者是否需要 x 所需内存量的两倍。

在 cppreference 上，我找到了 std::vector::swap（这是最后一行有效调用的方法）：

Exchanges the contents of the container with those of other. Does not invoke any move, copy, or swap operations on individual elements.

All iterators and references remain valid. The past-the-end iterator is invalidated.

现在我比以前更糊涂了。当 std::vector::swap 不移动、复制或交换元素时，它实际上做了什么？迭代器怎么可能保持有效？

这是否意味着像这样的代码是有效的代码？

std::vector<int> x(500);
std::vector<int> y;
auto it = x.begin();
std::swap(x,y);
std::sort(it , y.end()); // iterators from different containers !!

Answer 1

vector 在内部存储（至少）指向元素实际存储的指针、大小和容量。^† std::swap 只是交换周围的指针、大小和容量（以及辅助数据，如果有的话）；因为 x 中的指针变成了 y 中的指针，反之亦然，没有分配任何新内存。

vector 的迭代器通常是指向底层分配内存的指针的轻量级包装器（这就是容量变化通常会使迭代器无效的原因），so iterators produced for x before the swap seamlessly continue to refer to y after the swap；您对 sort 的示例使用是合法的，并且对 y.

进行排序

如果您想要在不交换存储的情况下交换元素本身（这是一种更昂贵的操作，但是会留下 x 的先前存在的迭代器引用 x)，你可以 use std::swap_range，但这是一个相对不常见的用例。内存使用量取决于底层对象的 swap 的实现；默认情况下，它通常会涉及一个临时对象，但一次只交换一个对象，而不是整个对象 vector.

^† 根据评论，它可以等效地使用指针指向所用 space 的末尾和容量的末尾，但是这两种方法在逻辑上都是等效的，并且只是微优化以支持略有不同的预期用例；存储所有指针优化迭代器的使用（一个合理的选择），而存储 size_type 优化 .size()/.capacity() 调用。

Answer 2

我会写一个玩具矢量图

struct toy_vector {
  int * buffer = 0;
  std::size_t valid_count = 0;
  std::size_t buffer_size = 0;

  int* begin() { return buffer; }
  int* end() { return buffer+valid_count; }
  std::size_t capacity() const { return buffer_size; }
  std::size_t size() const { return valid_count; }

  void swap( toy_vector& other ) {
    std::swap( buffer, other.buffer );
    std::swap( valid_count, other.valid_count );
    std::swap( buffer_size, other.buffer_size );
  }

基本上就是这样。我将实施一些方法，以便您看到我们有足够的工具可以使用：

  int& operator[](std::size_t i) { return buffer[i]; }

  void reserve(int capacity) {
    if (capacity <= buffer_size)
      return;
    toy_vector tmp;
    tmp.buffer = new int[capacity];
    for (std::size_t i = 0; i < valid_count; ++i)
      tmp.buffer[i] = std::move(buffer[i]);
    tmp.valid_count = valid_count;
    tmp.buffer_size = capacity;
    swap( tmp );
  }
  void push_back(int x) {
    if (valid_count+1 > buffer_size) {
      reserve( (std::max)((buffer_size*3/2), buffer_size+1) );
    buffer[valid_count] = std::move(x);
    ++valid_count;
  }
  // real dtor is more complex.
  ~toy_vector() { delete[] buffer; }
};

实际向量有异常安全问题，更多关注对象生命周期和分配器（我使用的是整数，所以不关心我是否正确 construct/destroy 它们），并且可能存储 3 个指针而不是一个指针和 2 种尺寸。但是交换这 3 个指针就像交换指针和 2 个大小一样简单。

实向量中的迭代器往往不是原始指针（但它们可以是）。正如您在上面看到的，当您执行 a.swap(b) 时，指向向量 a 的原始指针迭代器变成指向向量 b 的原始指针迭代器；非原始指针向量迭代器基本上是奇特的包装指针，并且必须遵循相同的语义。

C++ 标准没有明确地强制看起来像这样的实现，但它基于看起来像这样的实现，并且隐含地要求一个几乎相同的实现对此（我敢肯定有人会想出一个看起来不像这样的聪明的标准兼容向量；但我见过的每个标准库中的每个向量都看起来像这样。）

std::vector::swap 实际上是做什么的？

What does std::vector::swap actually do?

c++

swap

vector