According to http://www.cplusplus.com/reference/vector/vector/swap/, swapping the elements inside two vectors only has constant complexity. How is this implemented?
1 Answers
There's no need to go through and swap each element one by one. The naive vector implementation has the equivalent of two members: a size and a pointer to the data:
template<typename T>
class vector {
std::size_t size;
T* data;
};
To swap two vectors, you need only swap each of these members. By swapping the pointers, this vector will point to the other vector's data on the free store and the other will point to this one's data. Because the data is on the free store, its lifetime is not inherently tied to the lifetime of the vector itself, so swapping pointers like this will cause each vector to take over the lifetime of the other vector's data without issue.
void swap(vector& other) {
using std::swap;
swap(size, other.size);
swap(data, other.data);
}
std::vector is much more complex in its implementation given all the fine details it needs to handle, but this concept still holds true for swapping two vectors.
Related