On Oct 17, 2009, at 4:39 AM, Christopher Jefferson wrote:
On 16 Oct 2009, at 02:10, Thomas Klimpel wrote:
So I'm left with the impression that there might be quite some good reasons not to implement move-assignment as swap, but no really conclusive counter examples against it. On the other hand, as long as the absence of conclusive counter examples can't be "proved", ruling that move-assignment may generally be implemented as swap will be risky or worse.
Just as one point of information, which I've previously seen used in favour of using swap as move.
While it is true that a move which doesn't swap on (for example) vector<T> is O(n) rather than O(1), due to the need to destruct all the elements, I found in experiments that sorting a range of vector<T> is actually very slightly faster when move-assignment is NOT implemented as swap, so performance isn't even really an argument in it's favour.
There's a theoretical foundation behind this empirical observation. sort is a "resource preserving" permutation (as are many, but not all, algorithms in <algorithm>). I.e. things just get rearranged. Nothing need be constructed or destructed, though such constructions/ destructions may happen as implementation details. swap is the simplest "resource preserving" permutation algorithm, and for the purposes of this argument, is no different from sort: template <class T> void swap(T& x, T& y) { T t(std::move(x)); x = std::move(y); y = std::move(t); } The construction of t will put x into a resource-less state. The move assignment of x is <em>into an object with a resource-less state</ em>. I.e. here it makes no difference if T's move assignment operator is implemented with or without clear(). There is nothing to clear(). This move assignment will put y into a resource-less state. In the last move assignment, it is again into an object with a resource-less state. There is nothing to clear() out of y by the time it is move- assigned into. This pattern: if you move assign into something, it is already resource-less; is just as true for sort as it is for swap. And for unique. And for stable_partition. And for stable_sort. And for inplace_merge. Etc. Thus the cost for clearing the lhs within a move-assignment prior to the transfer of resources is minimal. It is usually a no-op. So why do it? What's the benefit even if the cost is small? Consider std::remove: This is one of the few algorithms in <algorithm> which is not a "resource preserving" permutation. Consider remove({a, b, c, d, e}, c). This will result in the sequence {a, b, d, e, e'}. To achieve this result, the following move assignments will take place: c = move(d); d = move(e); The first move assignment is not into a resource-less c. If move assignment into c doesn't "clear", when do those resources go away? For most resources (such as memory), it doesn't really matter when. The resources will still be owned if move-assignment doesn't aggressively destroy them (probably by e'). But for some resources (threads, file handles, mutexes), it will matter if they live too long. The client calling std::remove may or may not destruct e' "soon". But the client asked std::remove to remove c (and presumably all of c's resources). I do not think it would be a good idea for std::remove to also say: Oh, and you better destruct e' too just to make sure c is really gone. This is the benefit of move assignment "clearing" potentially significant resources aggressively. I believe this benefit outweighs the cost. -Howard