Le 20/08/11 18:09, Julian Gonggrijp a écrit :
Dear Boost developers,
std::swap is commonly implemented by copying the arguments. For non-POD types this can be very inefficient. Two solutions are available. The first option, which is commonly employed, is to manually override std::swap for every non-POD type, making use of the implementation details of the type. The other option is to provide a library which makes it possible to implement the swap algorithm once, in a way that is efficient for any type (POD or non-POD), and which works even if a type isn't copyable. The latter is what I'll be proposing here.
Back in March, Vicente Botet posted a link to the highly inspiring 'Notes on Programming' by Alexander Stepanov [1]. Lectures 4 and 5 cover the (hypothetical) move_raw algorithm and the (hypothetical) UNDERLYING_TYPE type function, as well as their relevance to the swap algorithm. I'll try to reproduce the essential points of this discussion below.
move_raw(s, t) moves the value of s to t. t is guaranteed to be left in a valid state but s isn't. In particular, the destruction of s might corrupt t because they point to the same additional resources. Another move operation into s, say, move_raw(r, s) will however restore s into a new valid state.
UNDERLYING_TYPE(T) represents a type which is (conceptually speaking) a POD-type with the same member data (and hence the same alignment) as T. The underlying type can be used to allocate space for a T object and to temporarily store the state of a T object.
Using move_raw and UNDERLYING_TYPE, a swap algorithm can be implemented which works and is efficient for any type:
template<class T> void swap (T& x, T& y) { UNDERLYING_TYPE(T) temp; move_raw (x, temp); move_raw (y, x); move_raw (temp, y); }
Apart from its fundamental nature in general, my library might bear special relevance to Boost.Swap and Boost.Move. Is your interest piqued?
Hi, I've used someting similar on TBoost.STM (a transaction in memory library) to backup the data to be restored when rollback is needed. The advantage to rollback on a POD where that no constructors/destructors where called due to the commit/rollback transaction mechanisms. The backup and the restore where implemented by specific functions, that at the end did a memcpy. Even if this is undefined behavior, it was esential to the library either in terms of preserving the contraints of the program or improving the performances. I understand that Boost can not rely on libraries promoting undefined behavior, but sometimes using undefined behavior can be accepted if at the end the function ensures everything is in a state that is consistent. The swap example is a good example. Even if the function could use instructions that have undefined behavior, a program calling this function could have a coherent state for all the variables. Best, Vicente