On Dec 28, 2008, at 2:41 PM, David Abrahams wrote:
on Sun Dec 28 2008, Howard Hinnant <hinnant-AT-twcny.rr.com> wrote:
On Dec 28, 2008, at 1:25 AM, David Abrahams wrote:
The conundrum here is that if we use that technique for tuple, then a tuple of empty types can never be empty itself. I'm starting to get ill just thinking about a generic framework for composing "logically empty" types that undoes this "EBO erasure" effect when necessary.
Perhaps I'm misunderstanding. Reverting from English to C++ in the hopes of clarification. :-) The C++0X program and its output below look quite reasonable to me:
<snip>
Reasonable, but unless I'm missing something, impossible, unless the tuple itself is derived from all those empty bases. A class containing an empty member is not itself empty, IIUC.
Ah, I see what you are saying. Yes, I agree.
I currently favor the "shallow hierarchy" design Doug outlined in c+ +std-lib-18989. Though EMO isn't shown in that description, it is pretty simple to add to that design.
/me rummages through his committee message archive...
As far as I can tell from that thread, your solution and Doug's shallow refinement show exactly the problem you were trying to warn about: any empty element types become (private) bases of the tuple type itself, leading to unintended namespace associations. As far as I can tell this is no different in spirit from
namespace std {
template <class T, class A> class vector : private A { ... };
} // std
Such an implementation of "EMO" is error prone as it associates the namespace of the client-supplied A with that of the vector
Quite so. I forgot one other language rule when I posted the vector example. [basic.lookup.argdep]/p2/b2:
... Furthermore, if T is a class template specialization, its associated namespaces and classes also include: the namespaces and classes associated with the types of the template arguments provided for template type parameters (excluding template template parameters);
Demonstration: typedef char one; struct two {one _[2];}; namespace std { template <class T, class A> struct vector { }; template <class T, class A> one test(vector<T, A>); } // std namespace mine { struct A {}; two test(std::vector<int, A>); } // mine #include <cstdio> int main() { std::printf("%zu\n", sizeof(test(std::vector<int, mine::A>()))); } Output: 2 I.e. The namespace of A is associated with std::vector<T, A>, whether or not vector derives from A. Silly me for forgetting that. /Some/ day I may master C++...
And, BTW, this is all way too hard; at its limit it leads to building every generic class template out of tuples instead of ordinary members.
This conclusion would be an option for class template designers, not a requirement. And it would be easier than constantly reinventing EMO. Back when c++std-lib-18989 was written (about 18 months ago) I implemented such a tuple, and used that implementation in preparing my previous message demonstrating a space-optimizing tuple. You are quite correct that the tuple does indeed end up deriving (indirectly in my example implementation) from client-supplied empty members. I think perhaps one important caveat is that the tuple *does not* derive from client-supplied types which have virtual functions (at least no known implementation of polymorphic types qualify as "empty"). Said differently, this implementation of tuple only derives from empty class types, and not from non-empty class types. Because of this caveat, and because of the associated namespace rule involving template parameters of template class types, I have not yet come up with a way for clients to detect the size optimization with the following exceptions (which I hope are acceptable to clients): 1. The tuple size optimization can be detected with sizeof. 2. The tuple size optimization can be detected by comparing the addresses of empty members and seeing that they may not be unique with respect to other tuple members: #include <tuple> #include <cstdio> struct empty1 {}; struct empty2 {}; int main() { typedef std::tuple<empty1, empty2> T2; T2 t; std::printf("address of std::get<0>(t) is %p\n", &std::get<0>(t)); std::printf("address of std::get<1>(t) is %p\n", &std::get<1>(t)); } address of std::get<0>(t) is 0xbffff65f address of std::get<1>(t) is 0xbffff65f "Unacceptable" means of detecting this optimization would include a change in overload resolution due to associated namespaces depending on whether or not the space optimization was performed (which would likely be error prone).
We probably should have an EMO in the core language after all.
I would probably be in favor of such a core change. Indeed, in the "next language" I imagine that a tuple-like construct might be a built- in type which lays the foundation for the layout of every client- defined aggregate type (complete with built-in type and value introspection). Imagine if you could inspect the member types of a struct as easily as you can a std::tuple. :-) -Howard