What is a "Regular Type" in the context of move semantics?

Question

Alex Stepanov defined Regular Types as types satisfying certain properties around copying and equality. Now that C++11 has added move semantics to the realm of generic programming, Stepanov's definition is no longer complete. I'm looking for a good reference on regular types that includes their interaction with move semantics.

Answer 1

Summary:

For C++11 I would include:

• move-ctor (noexcept)
• move-assign (noexcept)
• total ordering (operator<() for natural total order and std::less<> if a natural total order does not exist).
• hash<>

And would remove:

• swap() (non-throwing) - replaced by move operations.

Commentary

Alex revisits the concept of a regular type in Elements of Programming. In fact, much of the book is devoted to regular types.

There is a set of procedures whose inclusion in the computational basis of a type lets us place objects in data structures and use algorithms to copy objects from one data structure to another. We call types having such a basis regular, since their use guarantees regularity of behavior and, therefore, interoperability. -- Section 1.5 of EoP

In EoP, Alex introduces the notion of an underlying_type which gives us a non-throwing swap algorithm that can be used to move. An underlying_type template isn't implementable in C++ in any particularly useful manner, but you can use non-throwing (noexcept) move-ctor and move-assign as reasonable approximations (an underlying type allows moving to/from a temporary without an additional destruction for the temporary). In C++03, providing a non-throwing swap() was the recommended way to approximate a move operation, if you provide move-ctor and move-assign then the default std::swap() will suffice (though you could still implement a more efficient one).

[ I'm on record as recommending that you use a single assignment operator, passing by value, to cover both move-assign and copy-assign. Unfortunately the current language rules for when a type gets a default move-ctor causes this to break with composite types. Until that is fixed in the language you will need to write two assignment operators. However, you can still use pass by value for other sink arguments to avoid combinatorics in handling move/copy for all arguments. ]

Alex also adds the requirement of total ordering (though there may not be a natural total order and the ordering may be purely representational). operator<() should be reserved for the natural total ordering. My suggestion is to specialize std::less<>() if a natural total ordering is not available, there is some precedent for that in the standard).

In EoP, Alex relaxes the requirements on equality to allow for representational-equality as being sufficient. A useful refinement.

A regular type should also be equationally complete (that is, operator==() should be implementable as a non-friend, non-member, function). A type that is equationally complete is also serializable (though without a canonical serialization format, implementing the stream operators are of little use except for debugging). A type that is equationally complete can also be hashed. In C++11 (or with TR1) you should provide a specialization of std::hash.

Another property of regular types is area() for which there is not yet any standard syntax - and likely little reason to actually implement except for testing. It is a useful concept for specifying complexity - and I frequently implement it (or an approximation) for testing complexity. For example, we define the complexity of copy as bounded by the time to copy the area of the object.

The concept of a regular type is not language-specific. One of the first things I do when presented with a new language is work out how regular types manifest in that language.

Answer 2

Constraints of generic programming are best stated in terms of expressions. A more modern rendition of the same constraint on copiability would be that both statements should be valid:

T b = a; 

and

T b = ra; 

where a is an lvalue with type T or const T and ra is an rvalue with type T or const T. (With similar post-conditions.)

This formulation is in the spirit of the paper, I believe. Do note that C++03 already makes use of notions like lvalues and rvalues, such that the constraint we've expressed requires that something like T source(); T b = source(); be valid -- certainly something that seems sensible.

Under those constraints, then not much changes with C++11. Of particular note is that such a (pathological) type is irregular:

struct irregular {     irregular() = default;     irregular(irregular const&) = default;     irregular& operator=(irregular const&) = default;      irregular(irregular&&) = delete;     irregular& operator=(irregular&&) = delete; }; 

because something like irregular a; irregular b = a; is valid while irregular source(); irregular b = source(); isn't. It's a type that is somewhat copyable (resp. copy assignable), but not quite enough. [ This has been considered somewhat of a defect and is slated to be changed for C++1y, where such a type will in fact be copyable. ]

Going further, for the post-condition that a copy must be equivalent in some sense to the original (or, for rvalues, to the original before the copy) to hold, a move special member can only ever be an 'optimization' of the respective copy special member. Another way to put it is that copy semantics are a refinement of move semantics. This means that the assertion must hold in the following:

T a; T b = a; T c = std::move(a); assert( b == c ); 

I.e. whether we arrived there via a copy 'request' (that is, an expression involving an lvalue source) or via a move request (an expression involving an rvalue source), we must have the same result regardless of what 'actually' happened (whether a copy special member or move special member was involved, if at all).

Of interest is the fact that the traits such as std::is_copy_constructible used to be called std::has_copy_constructor, but were renamed to put the emphasis on expressions rather than intrinsic properties: something like std::is_copy_constructible<int>::value && std::is_move_assignable<int>::value is true regardless of the fact that int has no constructors or assignment operators.

I advise you to really do generic programming by expressing constraints on the expression level because e.g. the presence or absence of a move constructor is neither sufficient nor necessary for a type to be copy constructible.