5

Below is the most common implementation of std::swap:

template<typename T>
void std::swap(T& a, T& b) {
    auto tmp = std::move(a);
    a        = std::move(b);
    b        = std::move(tmp);
}

The C++ standard requires the time complexity of std::swap must be constant. So, if a container type, such as std::vector, std::list, and the like, has correctly implemented its move-ctor & move-assignment-operator; then, it doesn't seem necessary to define a swap member function for the type.

However, every container type in std namespace has defined its own swap member function, or a specialization of std::swap. I think there must be a concrete rationale behind the design, what's that?

Improve this question
1
  • 1
    The standard containers move/copy/swap constructors/operators (which may be called by std::swap()) would do move/copy/swap of individual elements in some [not all] cases. The member functions are specified to not do any move/copy/swap of individual elements. Commented Jul 8 at 2:19

2 Answers 2

Reset to default
14

The rationale for the std::containers specialized swap is history:

In C++98/03, there was no move semantics. Copy only. But there was std::swap(x, y), which worked by copying. The std::containers could have used std::swap(x, y) but it would have been very expensive: 1 copy construction and 2 copy assignments.

By implementing specialization, std::containers could just swap pointers and get an order of magnitude optimization, even without move semantics.

When C++11 came along (with move semantics), it didn't make sense to remove the specializations. Something would have broken somewhere. It was easier and safer just to upgrade the general swap and and leave the specializations alone.

Bonus points: It turns out that the specializations are slightly faster than the general swap, but not greatly so. Maybe by a load/store or two. But the main reason is history.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Why is void std::swap( std::filesystem::path& lhs, std::filesystem::path& rhs ) noexcept; still there, which is added in C++17? Is there another reason?
I didn't add that one, but my best guess is "muscle memory". Changing the standard is hard. Very hard. Even for someone who has lots of experience doing it. So one tends to copy existing idioms when doing so. That is the path of least risk, and least resistance when defending your design to your fellow committee members. Only when confronted with significant motivation (benefit to the C++ programmer) is it worth it to defend your design to the scrutiny of committee review.
I am reminded of this: snopes.com/fact-check/railroad-gauge-chariots. Not too far off the mark. :-)
3

For allocator-aware containers, the allocator may have different behaviours for swaps and move assignment/construction of the container.

If you attempt to swap containers with different allocators and propagate_on_container_swap is true_type, the allocators are swapped.

If you try to do the move-construct move-assign move-assign method, and propagate_on_container_move_assignment is false_type, this will have to reallocate with the existing allocators and move assign/move construct each individual element. This will not be a constant time operation.

For non-allocator-aware-containers, like std::array or std::inplace_vector, if the elements have specific swap behaviour, you want to be use it.

Also the C++ standard does not require swap to take constant time. https://eel.is/c++draft/utility.swap

In fact, std::array and std::inplace_vector swap are specified to take linear time: https://eel.is/c++draft/container.reqmts#50

Improve this answer

3 Comments

en.cppreference.com/w/cpp/utility/swap.html says std::swap's time complexity is constant.
The specialization for std::array says it is linear with respect to the size of the container. For the general case, constant time complexity means a constant number of moves of T, which can in turn have its own complexity that is not constant. en.cppreference.com/w/cpp/container/array/swap2.html
@Francois Andrieux Which makes sense since its sizeof is linear to number of elements as well.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.