Что на самом деле делает std::vector::swap?

vector внутренне хранит (по крайней мере) указатель на фактическое хранилище для элементов, размер и емкость. ^†std::swap просто меняет местами указатели, размер и емкость (и вспомогательные данные, если они есть) вокруг; никакого удвоения памяти или копий элементов не делается, потому что указатель в x становится указателем в y и наоборот, без выделения новой памяти.

Итераторы для vector обычно представляют собой легкие оболочки вокруг указателей на базовую выделенную память (поэтому изменения емкости обычно делают итераторы недействительными), поэтому итераторы, созданные для x до свопа, продолжают ссылаться на y после свопа; ваш пример использования sort является законным и сортирует y.

Если вы хотите поменять местами сами элементы без замены хранилища (гораздо более дорогая операция, но которая оставляет существующие итераторы для x, ссылающихся на x), вы можете использовать std::swap_range, но это относительно редкий вариант использования. Использование памяти для этого будет зависеть от реализации swap для базового объекта; по умолчанию это часто связано с временным, но только для одного из объектов, которые заменяются за раз, а не для всего одного vector.

^† Судя по комментариям, он может эквивалентно использовать указатели на конец используемого пространства и конец емкости, но любой подход логически эквивалентен и просто микрооптимизируется в пользу немного разных ожидаемых вариантов использования; хранение всех указателей оптимизирует использование итераторов (разумный выбор), а сохранение size_type оптимизирует вызовы .size()/.capacity().

Я напишу игрушечный вектор.

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; }
};

фактические векторы имеют проблемы с безопасностью исключений, больше беспокоятся о времени жизни объекта и распределителях (я использую целые числа, поэтому мне все равно, правильно ли я их создаю/уничтожаю), и могут хранить 3 указателя вместо указателя и 2 размера. Но поменять местами эти 3 указателя так же просто, как поменять местами указатель и 2 размера.

Итераторы в реальных векторах, как правило, не являются необработанными указателями (но могут быть). Как вы можете видеть выше, итераторы необработанных указателей на вектор a становятся итераторами необработанных указателей на вектор b, когда вы выполняете a.swap(b); несырые итераторы векторов указателей в основном представляют собой причудливые обернутые указатели и должны следовать той же семантике.

Стандарт C++ явно не предписывает реализацию, которая выглядит так, но он был основан на реализации, которая выглядит так, и неявно требует реализации, которая почти идентична этой (я уверен, что кто-то мог бы придумать умный стандарт совместимый вектор, который не выглядит так, но каждый вектор в каждой стандартной библиотеке, которую я видел, выглядел так.)