[boost] [interest] underlying type library

Subject: [boost] [interest] underlying type library
From: Julian Gonggrijp (j.gonggrijp_at_[hidden])
Date: 2011-08-20 12:09:09

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);
}

The benefits of an underlying type library go far beyond the swap 
algorithm. For a start, any algorithm which moves values around 
without an inherent need to copy them could use the same mechanism as 
the swap algorithm above. Apart from that, it can help to simulate 
rvalue references and move semantics in pre-C++11 compilers in an 
efficient way. Concluding, a library which provides these tools has an 
immense potential for improving efficiency and convenience anywhere 
C++ is used.

After reading the lecture notes, I came up with an idea on how to 
realise such a library in a fully generic way. Alexander Stepanov and 
Sean Parent have been so kind to review my idea. The idea seemed 
feasible and they encouraged me to submit something to Boost. In the 
meanwhile I have successfully managed to implement my idea, so here I 
am. :-)

Apart from its fundamental nature in general, my library might bear 
special relevance to Boost.Swap and Boost.Move. Is your interest 
piqued?

Kind regards,
-Julian

[1] http://www.stepanovpapers.com/notes.pdf