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

Question

What triggered this question is some code along the line of:

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

std::swap(x,y);

And I was wondering if swapping the two requires twice the amount of memory that x needs.

On cppreference I found for std::vector::swap (which is the method that the last line effectively calls):

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.

And now I am more confused than before. What does std::vector::swap actually do when it does not move, copy or swap elements? How is it possible that iterators stay valid?

Does that mean that something like this is valid code?

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 internally stores (at least) a pointer to the actual storage for the elements, a size and a capacity.^† std::swap just swaps the pointers, size and capacity (and ancillary data if any) around; no doubling of memory or copies of the elements are made because the pointer in x becomes the pointer in y and vice-versa, without any new memory being allocated.

The iterators for vector are generally lightweight wrappers around pointers to the underlying allocated memory (that's why capacity changes generally invalidate iterators), so iterators produced for x before the swap seamlessly continue to refer to y after the swap; your example use of sort is legal, and sorts y.

If you wanted to swap the elements themselves without swapping storage (a much more expensive operation, but one that leaves preexisting iterators for x refering to x), you could use std::swap_range, but that's a relatively uncommon use case. The memory usage for that would depend on the implementation of swap for the underlying object; by default, it would often involve a temporary, but only for one of the objects being swapped at a time, not the whole of one vector.

---

^† Per the comments, it could equivalently use pointers to the end of the used space and the end of the capacity, but either approach is logically equivalent, and just microoptimizes in favor of slightly different expected use cases; storing all pointers optimizes for use of iterators (a reasonable choice), while storing size_type optimizes for .size()/.capacity() calls.

Answer 2

I will write a toy vector.

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

That is basically it. I'll implement a few methods so you see we have enough tools to work with:

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

actual vectors have exception safety issues, more concerns about object lifetime and allocators (I'm using ints, so don't care if I properly construct/destroy them), and might store 3 pointers instead of a pointer and 2 sizes. But swapping those 3 pointers is just as easy as swapping the pointer and 2 sizes.

Iterators in real vectors tend not to be raw pointers (but they can be). As you can see above, the raw pointer iterators to the vector a become raw pointer iterators into vector b when you do an a.swap(b); non-raw pointer vector iterators are basically fancy wrapped pointers, and have to follow the same semantics.

The C++ standard does not explicitly mandate an implementation that looks like this, but it was based off an implementation that looks like this, and it implicitly requires one that is almost identical to this (I'm sure someone could come up with a clever standard compliant vector that doesn't look like this; but every vector in every standard library I have seen has looked like this.)