-5

Why don't STL containers simply implement move using swap? E.g.

template <...>
class mycontainer {
public:
  mycontainer& operator= (mycontainer&& src) {
    swap(*this, src);
    return *this;
  }
};

Isn't the whole point of move to be fast? Doesn't swap already give us that?

I assumed that swap is fast for STL containers because they use PImpl or something, but it seems they do not. How then is swapping so fast?

François Andrieux
  • 28,148
  • 6
  • 56
  • 87
allyourcode
  • 21,871
  • 18
  • 78
  • 106
  • 6
    Who says that moving them is slow? Where are you getting that from? – Nicol Bolas Jun 01 '21 at 19:07
  • [Related](https://stackoverflow.com/questions/6687388/why-do-some-people-use-swap-for-move-assignments) – Cory Kramer Jun 01 '21 at 19:07
  • 4
    What is slow? How did you measure? How can see see the same results? I think you're omitting way too much code to make this question something that can actually be answered. Containers are implemented differently depending on specified requirements. Please refine your question with specifics. – Chris Uzdavinis Jun 01 '21 at 19:08
  • The `swap` operation has been part of C++ collections from when they were the Standard Template Library, before they became part of the C++ Standard Library. When they were added to the C++ standard, complexity constraints were put on `swap` for all the different container types and implementers have had plenty of time to write `swap` to be fast. Move assignment is much newer, and although the latest implementations of the C++ Standard Library do a good job, there are plenty of library versions floating around that were barely getting the new features to work let alone be fast. – Ben Voigt Jun 01 '21 at 19:11
  • 2
    If moving a container is slow, the container probably has messed up the move operation and is instead inadvertently doing a copy operation. – Eljay Jun 01 '21 at 19:12
  • 2
    (Side note: real "STL containers" have no support for move at all, because STL is very very very old) – Ben Voigt Jun 01 '21 at 19:12
  • @BenVoigt MSVC's implementation of the C++ Standard Library is also called "STL" https://github.com/microsoft/stl – Aykhan Hagverdili Jun 01 '21 at 20:03
  • @AyxanHaqverdili: The primary maintainer of the C++ Standard Library at Microsoft is Stephan T. Lavavej so his repo is named "stl". Those are his initials. – Ben Voigt Jun 01 '21 at 22:08
  • According to cplusplus.com, the complexity of moving is O(n): https://www.cplusplus.com/reference/vector/vector/operator=/ – allyourcode Jun 02 '21 at 05:00

1 Answers1

1

Why don't STL containers simply implement move using swap?

Swapping is (usually) slower than optimally implemented move construction or at best (rarely) equally fast.

Swapping + eventual destruction is (usually) slower than optimally implemented move assignment + eventual destruction or at best (rarely) equally fast.

Swapping alone is indeed faster than move assignment because the destruction of elements is postponed. But such postponement of destruction of elements by the move assignment operator of a container is not allowed by the C++ standard, so the move assignment that you suggest is non-conforming. Besides, those elements typically will eventually be destroyed and when that happens, you would've only lost efficiency.

Standard implementers would be allowed to use swap as long as they destroyed the elements some other way. But there is no efficiency advantage in doing that, and that may be their reason if they don't use it.

P.S. The generic std::swap - which is used when there is no member swap - is implemented by performing three moves. Standard containers implement a member swap that is faster than the generic swap, but still not as fast as a single move when including the eventual destruction.

eerorika
  • 232,697
  • 12
  • 197
  • 326