I recently had a C++ problem and found an answer that tickled my brain. In the spirit of Car Talk on NPR, I thought I'd share it in the form of a puzzler. Say that you are given a set of types, and you must find the "common" type, where common is defined as follows: - If all the types are the same, say X, then the common type is X - If some types are X and some are Default (where Default is a known special type), the common type is X - If some types are X and some are Y (and neither X nor Y is Default), then there is no common type. It's an error and you should issue a diagnostic. So for example: [Default, Default, Default] --> Default [Default, A, Default] --> A [B, B, B] --> B [Default, C, D] --> Error, issue diagnostic. And here's the kicker ... do it in O(1). No O(N) recursive template instantiations allowed. Assume that the maximum size of the set is known ahead of time. Answer next week, unless someone beats me to it. -- Eric Niebler Boost Consulting www.boost-consulting.com
________________________________________ De: boost-bounces@lists.boost.org [boost-bounces@lists.boost.org] En nombre de Eric Niebler [eric@boost-consulting.com] Enviado el: sábado, 12 de abril de 2008 9:28 Para: Boost mailing list Asunto: [boost] A C++ puzzler
I recently had a C++ problem and found an answer that tickled my brain. In the spirit of Car Talk on NPR, I thought I'd share it in the form of a puzzler. [...]
Hello Eric, I am not sure if this is what you have in mind, since from your description is not clear how the input types are represented: I've assumed they're just the args of a class template with a fixed number of template parameters: struct default_t{}; template<typename T> struct holder_base{typedef T type;}; template<> struct holder_base<default_t>{}; template<typename T,int> struct holder:virtual holder_base<T>{}; template<typename T1,typename T2,typename T3,typename T4,typename T5> struct common_type_base: holder<T1,1>,holder<T2,2>,holder<T3,3>,holder<T4,4>,holder<T5,5>{}; template<typename T1,typename T2,typename T3,typename T4,typename T5> struct common_type:common_type_base<T1,T2,T3,T4,T5> { typedef typename common_type_base<T1,T2,T3,T4,T5>::type type; }; template<> struct common_type<default_t,default_t,default_t,default_t,default_t> { typedef default_t type; }; Best, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
Hey, my implementation is in the attachment. It's rather ugly ;) so it's probably not what You had in mind, but AFAIK it works. the common_type<...> template is declared only for three args, but with a little help from boost/preprocessor it could be generalized to N params. Unfortunatelly i don't have the time to play with that right now :-P. Nice puzzler though ;) Best, On Sat, Apr 12, 2008 at 12:15 PM, JOAQUIN M. LOPEZ MUÑOZ <joaquin@tid.es> wrote:
________________________________________ De: boost-bounces@lists.boost.org [boost-bounces@lists.boost.org] En nombre de Eric Niebler [eric@boost-consulting.com] Enviado el: sábado, 12 de abril de 2008 9:28 Para: Boost mailing list Asunto: [boost] A C++ puzzler
I recently had a C++ problem and found an answer that tickled my brain. In the spirit of Car Talk on NPR, I thought I'd share it in the form of a puzzler. [...]
Hello Eric, I am not sure if this is what you have in mind, since from your description is not clear how the input types are represented: I've assumed they're just the args of a class template with a fixed number of template parameters:
struct default_t{};
template<typename T> struct holder_base{typedef T type;};
template<> struct holder_base<default_t>{};
template<typename T,int> struct holder:virtual holder_base<T>{};
template<typename T1,typename T2,typename T3,typename T4,typename T5> struct common_type_base: holder<T1,1>,holder<T2,2>,holder<T3,3>,holder<T4,4>,holder<T5,5>{};
template<typename T1,typename T2,typename T3,typename T4,typename T5> struct common_type:common_type_base<T1,T2,T3,T4,T5> { typedef typename common_type_base<T1,T2,T3,T4,T5>::type type; };
template<> struct common_type<default_t,default_t,default_t,default_t,default_t> { typedef default_t type; };
Best,
Joaquín M López Muñoz Telefónica, Investigación y Desarrollo _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
-- ________________ ::matus_chochlik
Hmm, just realized that the design of mine has one dumb flaw. It's not working when the common base is not in the set: ... struct A { }; struct B { }; struct C : A { }; struct D : B { }; struct E : B { }; struct F : B { }; struct G : F { }; ... // ok print_result(cout, "[C,C,A] -> A", is_same<common_type<C, C, A>::result, A>::value); print_result(cout, "[B,D,E] -> B", is_same<common_type<B, D, E>::result, B>::value); print_result(cout, "[B,D,G] -> B", is_same<common_type<B, D, G>::result, B>::value); // nogood :/ print_result(cout, "[D,E,F] -> B", is_same<common_type<D, E, F>::result, B>::value); On Sat, Apr 12, 2008 at 12:41 PM, Matus Chochlik <chochlik@gmail.com> wrote:
Hey,
my implementation is in the attachment. It's rather ugly ;) so it's probably not what You had in mind, but AFAIK it works.
the common_type<...> template is declared only for three args, but with a little help from boost/preprocessor it could be generalized to N params. Unfortunatelly i don't have the time to play with that right now :-P.
Nice puzzler though ;)
Best,
On Sat, Apr 12, 2008 at 12:15 PM, JOAQUIN M. LOPEZ MUÑOZ <joaquin@tid.es> wrote:
________________________________________ De: boost-bounces@lists.boost.org [boost-bounces@lists.boost.org] En nombre de Eric Niebler [eric@boost-consulting.com] Enviado el: sábado, 12 de abril de 2008 9:28 Para: Boost mailing list Asunto: [boost] A C++ puzzler
I recently had a C++ problem and found an answer that tickled my brain. In the spirit of Car Talk on NPR, I thought I'd share it in the form of a puzzler. [...]
Hello Eric, I am not sure if this is what you have in mind, since from your description is not clear how the input types are represented: I've assumed they're just the args of a class template with a fixed number of template parameters:
struct default_t{};
template<typename T> struct holder_base{typedef T type;};
template<> struct holder_base<default_t>{};
template<typename T,int> struct holder:virtual holder_base<T>{};
template<typename T1,typename T2,typename T3,typename T4,typename T5> struct common_type_base: holder<T1,1>,holder<T2,2>,holder<T3,3>,holder<T4,4>,holder<T5,5>{};
template<typename T1,typename T2,typename T3,typename T4,typename T5> struct common_type:common_type_base<T1,T2,T3,T4,T5> { typedef typename common_type_base<T1,T2,T3,T4,T5>::type type; };
template<> struct common_type<default_t,default_t,default_t,default_t,default_t> { typedef default_t type; };
Best,
Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
-- ________________ ::matus_chochlik
-- ________________ ::matus_chochlik
On Sat, Apr 12, 2008 at 12:15 PM, JOAQUIN M. LOPEZ MUÑOZ <joaquin@tid.es> wrote:
Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
Mine is very similar to Joaquin one with one less indirection level. Default type here is assumed to be int, just to easy the test. template<typename T> struct each_type { typedef T type; }; template<> struct each_type<int> {}; // int is the default_type template<typename T, int n> struct unique_type : virtual each_type<T> {}; template<typename T1, typename T2, typename T3> struct test : unique_type<T1, 0>, unique_type<T2, 1>, unique_type<T3, 2> {}; template<> struct test<int, int, int> { typedef int type; }; testing is: int main(int, char**) { test<int, int, int>::type default_value = 0; test<int, char, int>::type char_value = 'x'; test<int, char, char>::type char_value_2 = 'y'; // test<int, char, double>::type error_value; compile error here! return 0; }
On Sat, Apr 12, 2008 at 9:28 AM, Eric Niebler <eric@boost-consulting.com> wrote:
I recently had a C++ problem and found an answer that tickled my brain. In the spirit of Car Talk on NPR, I thought I'd share it in the form of a puzzler.
Say that you are given a set of types, and you must find the "common" type, where common is defined as follows:
- If all the types are the same, say X, then the common type is X - If some types are X and some are Default (where Default is a known special type), the common type is X - If some types are X and some are Y (and neither X nor Y is Default), then there is no common type. It's an error and you should issue a diagnostic.
So for example:
[Default, Default, Default] --> Default [Default, A, Default] --> A [B, B, B] --> B [Default, C, D] --> Error, issue diagnostic.
And here's the kicker ... do it in O(1). No O(N) recursive template instantiations allowed. Assume that the maximum size of the set is known ahead of time.
In your honor, the master of conditional operator tricks, here is my solution. The easy part only allows one to retrieve the common type inside a template function. With some sizeof trickery you can of course retrieve it anywhere. It is not generalized (it needs some per-type boilerplate, which should be easily wrappable in a macro). -- gpd
On Sat, 12 Apr 2008 09:28:51 +0200, Eric Niebler <eric@boost-consulting.com> wrote:
I recently had a C++ problem and found an answer that tickled my brain. In the spirit of Car Talk on NPR, I thought I'd share it in the form of a puzzler.
Here, there is my solution (attached), it's not the smartest but it's not too bad! Regards, Marco Cecchetti -- Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
AMDG Eric Niebler wrote:
I recently had a C++ problem and found an answer that tickled my brain. In the spirit of Car Talk on NPR, I thought I'd share it in the form of a puzzler
Another solution in the mix. All PP magic. I pushed it up to 13 parameters before msvc 9.0 failed. In Christ, Steven Watanabe #include <boost/preprocessor/seq/for_each_product.hpp> #include <boost/preprocessor/seq/enum.hpp> #include <boost/preprocessor/seq/fold_left.hpp> #include <boost/preprocessor/repetition/enum_params.hpp> #include <boost/preprocessor/repetition/enum_params_with_a_default.hpp> #include <boost/preprocessor/control/if.hpp> #include <boost/preprocessor/cat.hpp> #include <boost/preprocessor/logical/and.hpp> #define COMMON_TYPE_LIMIT_PARAMS 4 struct default_t {}; #define IS_DEFAULT_default_t 1 #define IS_DEFAULT_T 0 #define IS_DEFAULT(x) BOOST_PP_CAT(IS_DEFAULT_, x) #define TEST(s, state, elem) BOOST_PP_AND(state, IS_DEFAULT(elem)) #define IS_ALL_DEFAULT(seq) BOOST_PP_SEQ_FOLD_LEFT(TEST, 1, seq) #define WITH_T(args) template<class T> struct common_type<BOOST_PP_SEQ_ENUM(args)> { typedef T type; }; #define DEFAULT(args) template<> struct common_type<BOOST_PP_SEQ_ENUM(args)> { typedef default_t type; }; #define SPECIALIZATION(r, args) BOOST_PP_IF(IS_ALL_DEFAULT(args), DEFAULT, WITH_T)(args) template<BOOST_PP_ENUM_PARAMS_WITH_A_DEFAULT(COMMON_TYPE_LIMIT_PARAMS, class T, default_t)> struct common_type {}; #define PARAMETERS(z, n, data) ((T)(default_t)) BOOST_PP_SEQ_FOR_EACH_PRODUCT(SPECIALIZATION, BOOST_PP_REPEAT(COMMON_TYPE_LIMIT_PARAMS, PARAMETERS, ~)) int main() { typedef common_type<int, int, int>::type int1; typedef common_type<int, default_t, int>::type int2; typedef common_type<default_t, int, int, default_t>::type int3; //typedef common_type<default_t, int, char, default_t>::type error1; typedef common_type<>::type default1; }
Eric Niebler wrote:
I recently had a C++ problem and found an answer that tickled my brain. In the spirit of Car Talk on NPR, I thought I'd share it in the form of a puzzler. <snip> Answer next week, unless someone beats me to it.
Wow, everybody loves a puzzle! This is good fun. Joaquin and Marco Co.: virtual inheritance. Clever! I think it instantiates O(N) templates though. Matus: This works but has scalability problems. To handle a set with N types, you need 2^N specializations of common_type_helper_picker. Giovalli: conditional operator. Wish I thought of that. But it requires types to be associated with integers via a global registry, so I can't use it. Is there a way to avoid select() and result<>? It's easy with typeof, but can you do it without? Marco Ce: This is pretty good! I think this instantiates O(1) templates in the case that a common type exists. Awesome. It's simpler that what I came up with, too. Steven W: Wow, makes my head hurt. I think I see what's going on -- 2^N specializations? Might not scale so well. Daniel Fey: Similar to what I came up with, but there's a trick that can (a) knock the 2^N overloads down to N, and (b) eliminate the need for typeof. -- Eric Niebler Boost Consulting www.boost-consulting.com
Hi, Here's a solution similar to Marco's - finds the first non default type using template specialization. It uses sizeof to check whether the types following first non-default type are conforming. Anand. On Sat, Apr 12, 2008 at 2:38 PM, Eric Niebler <eric@boost-consulting.com> wrote:
Eric Niebler wrote:
I recently had a C++ problem and found an answer that tickled my brain. In the spirit of Car Talk on NPR, I thought I'd share it in the form of a puzzler. <snip> Answer next week, unless someone beats me to it.
Wow, everybody loves a puzzle! This is good fun.
Joaquin and Marco Co.: virtual inheritance. Clever! I think it instantiates O(N) templates though.
Matus: This works but has scalability problems. To handle a set with N types, you need 2^N specializations of common_type_helper_picker.
Giovalli: conditional operator. Wish I thought of that. But it requires types to be associated with integers via a global registry, so I can't use it. Is there a way to avoid select() and result<>? It's easy with typeof, but can you do it without?
Marco Ce: This is pretty good! I think this instantiates O(1) templates in the case that a common type exists. Awesome. It's simpler that what I came up with, too.
Steven W: Wow, makes my head hurt. I think I see what's going on -- 2^N specializations? Might not scale so well.
Daniel Fey: Similar to what I came up with, but there's a trick that can (a) knock the 2^N overloads down to N, and (b) eliminate the need for typeof.
-- Eric Niebler Boost Consulting www.boost-consulting.com _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Sat, 12 Apr 2008 21:13:40 +0200, Anand Shankar <anand.shankar.k@gmail.com> wrote:
Hi,
Here's a solution similar to Marco's - finds the first non default type using template specialization. It uses sizeof to check whether the types following first non-default type are conforming.
Anand.
Really a nice solution! Marco -- Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
Marco wrote:
On Sat, 12 Apr 2008 21:13:40 +0200, Anand Shankar <anand.shankar.k@gmail.com> wrote:
Hi,
Here's a solution similar to Marco's - finds the first non default type using template specialization. It uses sizeof to check whether the types following first non-default type are conforming.
Anand.
Really a nice solution!
Correct me if my thinking is incorrect but I think a solution using a variable number of template specialization has an implicit O(f(N)) complexity where f(N) is some non-constant function of N. The compiler needs to iterate through all the specializations in order to find the match, which is the same as you explicitly iterating through some sort of fusion data structure. It may optimize this somehow but it still isn't O(1). Interesting puzzle. Can't wait to see all the answers. -- Sohail Somani http://uint32t.blogspot.com
On Sat, 12 Apr 2008 22:24:53 +0200, Sohail Somani <sohail@taggedtype.net> wrote:
Marco wrote:
On Sat, 12 Apr 2008 21:13:40 +0200, Anand Shankar <anand.shankar.k@gmail.com> wrote:
Hi,
Here's a solution similar to Marco's - finds the first non default type using template specialization. It uses sizeof to check whether the types following first non-default type are conforming.
Anand.
Really a nice solution!
Correct me if my thinking is incorrect but I think a solution using a variable number of template specialization has an implicit O(f(N)) complexity where f(N) is some non-constant function of N. The compiler needs to iterate through all the specializations in order to find the match, which is the same as you explicitly iterating through some sort of fusion data structure. It may optimize this somehow but it still isn't O(1).
Interesting puzzle. Can't wait to see all the answers.
Your concern is sensible, and someone with a more insight than me on how a compiler works should give an answer, here. Anyway this is my point of view: the compiler has to do O(N) comparisons to find the right match but only the matching template specialization will be instantiated, so actually we need O(1) template instantiation only. Marco -- Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
Marco wrote:
On Sat, 12 Apr 2008 22:24:53 +0200, Sohail Somani <sohail@taggedtype.net> wrote:
Correct me if my thinking is incorrect but I think a solution using a variable number of template specialization has an implicit O(f(N)) complexity where f(N) is some non-constant function of N. The compiler needs to iterate through all the specializations in order to find the match, which is the same as you explicitly iterating through some sort of fusion data structure. It may optimize this somehow but it still isn't O(1).
Interesting puzzle. Can't wait to see all the answers.
Your concern is sensible, and someone with a more insight than me on how a compiler works should give an answer, here. Anyway this is my point of view: the compiler has to do O(N) comparisons to find the right match but only the matching template specialization will be instantiated, so actually we need O(1) template instantiation only.
It's certainly the case that finding the correct specialization of N possibilities is not free. But finding the correct specialization and instantiating one template is *much* cheaper than instantiating N templates. At least, that's been my experience. -- Eric Niebler Boost Consulting www.boost-consulting.com
Marco wrote:
On Sat, 12 Apr 2008 22:24:53 +0200, Sohail Somani <sohail@taggedtype.net> wrote:
Correct me if my thinking is incorrect but I think a solution using a variable number of template specialization has an implicit O(f(N)) complexity where f(N) is some non-constant function of N. The compiler needs to iterate through all the specializations in order to find the match, which is the same as you explicitly iterating through some sort of fusion data structure. It may optimize this somehow but it still isn't O(1).
Interesting puzzle. Can't wait to see all the answers.
Your concern is sensible, and someone with a more insight than me on how a compiler works should give an answer, here. Anyway this is my point of view: the compiler has to do O(N) comparisons to find the right match but only the matching template specialization will be instantiated, so actually we need O(1) template instantiation only.
Clearly, I misread the O(1) template instantiations requirement. Thanks for clarifying for me. And to reply to Eric, it is also my experience that O(N) comparisons (would probably actually be O(N*MAX_TYPES) comparisons) are better than O(N) instantiations, but I'm sure the "Proto"-typical C++ guru (Eric) knows about that ;-) -- Sohail Somani http://uint32t.blogspot.com
On Sat, Apr 12, 2008 at 8:38 PM, Eric Niebler <eric@boost-consulting.com> wrote:
Eric Niebler wrote:
I recently had a C++ problem and found an answer that tickled my brain. In the spirit of Car Talk on NPR, I thought I'd share it in the form of a puzzler. <snip>
Answer next week, unless someone beats me to it.
Wow, everybody loves a puzzle! This is good fun.
Yup! Great fun.
Giovalli:
Giova*ll*i ?!?!?!
conditional operator. Wish I thought of that. But it requires types to be associated with integers via a global registry, so I can't use it. Is there a way to avoid select() and result<>? It's easy with typeof, but can you do it without?
Here is a try. it probably will look more at home at an obfuscated C++ context. It works up to 5 types. Extending it beyond is a matter of a little of pp metaprogramming. The only O(N) template (that I can see) instantiation is template<class T> default_type::operator T(); And you do not pay for it if you do not use default_type (partially specializing common_type may work as an optimization). I'll try to get rid even of this. Even if there are very few template instantiations, compile time isn't that good. I thought that compile time integral expression computations were basically free. Maybe I'm missing something. -- gpd
Giovanni Piero Deretta wrote:
On Sat, Apr 12, 2008 at 8:38 PM, Eric Niebler <eric@boost-consulting.com> wrote:
Giovalli:
Giova*ll*i ?!?!?!
Whoops, sorry. :-P
conditional operator. Wish I thought of that. But it requires types to be associated with integers via a global registry, so I can't use it. Is there a way to avoid select() and result<>? It's easy with typeof, but can you do it without?
Here is a try. it probably will look more at home at an obfuscated C++ context.
It works up to 5 types. Extending it beyond is a matter of a little of pp metaprogramming.
The only O(N) template (that I can see) instantiation is template<class T> default_type::operator T();
Not a problem. It's a function template, so instantiating it would be cheaper than instantiating a class template (I think), but you're not even instantiating it. It doesn't even have a definition.
And you do not pay for it if you do not use default_type (partially specializing common_type may work as an optimization).
I'll try to get rid even of this.
Even if there are very few template instantiations, compile time isn't that good. I thought that compile time integral expression computations were basically free. Maybe I'm missing something.
This solution is very clever! Why do you say that compile time is poor? What are you benchmarking against? -- Eric Niebler Boost Consulting www.boost-consulting.com
On Sun, Apr 13, 2008 at 9:42 PM, Eric Niebler <eric@boost-consulting.com> wrote:
Giovanni Piero Deretta wrote:
conditional operator. Wish I thought of that. But it requires types to be associated with integers via a global registry, so I can't use it. Is there a way to avoid select() and result<>? It's easy with typeof, but can you do it without?
Here is a try. it probably will look more at home at an obfuscated C++ context.
It works up to 5 types. Extending it beyond is a matter of a little of pp metaprogramming.
The only O(N) template (that I can see) instantiation is template<class T> default_type::operator T();
Not a problem. It's a function template, so instantiating it would be cheaper than instantiating a class template (I think), but you're not even instantiating it. It doesn't even have a definition.
D'oh right! I assumed that generating the function signature counted as instantiation. Obviously it doesn't. I have even introduced a bug in a mindless try to eliminate all template usage: while the following: struct C{};
And you do not pay for it if you do not use default_type (partially specializing common_type may work as an optimization).
I'll try to get rid even of this.
Even if there are very few template instantiations, compile time isn't that good. I thought that compile time integral expression computations were basically free. Maybe I'm missing something.
This solution is very clever! Why do you say that compile time is poor? What are you benchmarking against?
-- Eric Niebler Boost Consulting www.boost-consulting.com _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
[I have sent an incomplete message by mistake... here is the conclusion] On Sun, Apr 13, 2008 at 11:31 PM, Giovanni Piero Deretta <gpderetta@gmail.com> wrote:
On Sun, Apr 13, 2008 at 9:42 PM, Eric Niebler <eric@boost-consulting.com> wrote:
Giovanni Piero Deretta wrote:
conditional operator. Wish I thought of that. But it requires types to be associated with integers via a global registry, so I can't use it. Is there a way to avoid select() and result<>? It's easy with typeof, but can you do it without?
Here is a try. it probably will look more at home at an obfuscated C++ context.
It works up to 5 types. Extending it beyond is a matter of a little of pp metaprogramming.
The only O(N) template (that I can see) instantiation is template<class T> default_type::operator T();
Not a problem. It's a function template, so instantiating it would be cheaper than instantiating a class template (I think), but you're not even instantiating it. It doesn't even have a definition.
D'oh right! I assumed that generating the function signature counted as instantiation. Obviously it doesn't. I have even introduced a bug in a mindless try to eliminate all template usage: while the following:
struct C{}; struct D : C{}; assert(is_same<C,common<C, D>::type>); works as expected, this doesn't: assert(is_same<C, common<D, C>::type) The fix is simple: add the overload template<class T> true_& match(T&, T&); and change the result type of the match(...) overload to false.
And you do not pay for it if you do not use default_type (partially specializing common_type may work as an optimization).
I'll try to get rid even of this.
Even if there are very few template instantiations, compile time isn't that good. I thought that compile time integral expression computations were basically free. Maybe I'm missing something.
This solution is very clever! Why do you say that compile time is poor? What are you benchmarking against?
I have used a very scientific benchmark: I run the test and was mildly annoyed by the time it took to compile :). Anyways, there are actually N^2 applications of operator:? . The "inner loop" is always the same, but I do not know if compilers do memoization of constant expressions, so it might be worthwhile to do this optimization by hand. -- gpd
On Sat, 2008-04-12 at 11:38 -0700, Eric Niebler wrote:
Eric Niebler wrote: Wow, everybody loves a puzzle! This is good fun.
For sure! :)
Daniel Fey: Similar to what I came up with, but there's a trick that can (a) knock the 2^N overloads down to N, and (b) eliminate the need for typeof.
s/Fey/Frey/ The new version (attached) has only 4 overloads instead of N, but it still uses typeof. Regards, Daniel
On Sun, 2008-04-13 at 12:51 +0200, Daniel Frey wrote:
The new version (attached) has only 4 overloads instead of N, but it still uses typeof.
OK, another version. No typeof and O(1), due to the fact that in the good case the common_type_helper must always be instantiated with the same T, so the number of template instantiations doesn't grow, it has a constant limit. The bad case will fail anyway, but it might need some instantiations before finding out. I hope that this solution is acceptable for you. Regards, Daniel
________________________________________ De: boost-bounces@lists.boost.org [boost-bounces@lists.boost.org] En nombre de Daniel Frey [d.frey@gmx.de] Enviado el: domingo, 13 de abril de 2008 13:43 Para: boost@lists.boost.org Asunto: Re: [boost] A C++ puzzler On Sun, 2008-04-13 at 12:51 +0200, Daniel Frey wrote:
The new version (attached) has only 4 overloads instead of N, but it still uses typeof.
OK, another version. No typeof and O(1), due to the fact that in the good case the common_type_helper must always be instantiated with the same T, so the number of template instantiations doesn't grow, it has a constant limit. The bad case will fail anyway, but it might need some instantiations before finding out. I hope that this solution is acceptable for you.
Instead of having nested common_type_helper invokations in the common type calculation formula, you can do it linearly like this: template< typename T0, typename T1, typename T2, typename T3, typename T4, typename T5, typename T6, typename T7 > struct common_type { typedef typename common_type_helper<T0,T1>::type t0; typedef typename common_type_helper<t0,T2>::type t1; typedef typename common_type_helper<t1,T3>::type t2; typedef typename common_type_helper<t2,T4>::type t3; typedef typename common_type_helper<t3,T5>::type t4; typedef typename common_type_helper<t4,T6>::type t5; typedef typename common_type_helper<t5,T7>::type t6; typedef t6 type; }; which has the advantage of being much more easily automatable via Boost.Preprocessor. Boost.PP-generated modified version attached. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
Eric Niebler wrote:
I recently had a C++ problem and found an answer that tickled my brain. In the spirit of Car Talk on NPR, I thought I'd share it in the form of a puzzler.
Here is my solution. Not sure that it satisfies the conditions though. Regards, Juraj Ivančić #include "boost/static_assert.hpp" #include "boost/type_traits/is_same.hpp" #include "boost/mpl/if.hpp" class ErrorFoundTwoNonDefaultTypes {}; class Default {}; template<typename T1, typename T2> struct FindNonDefault { typedef typename boost::mpl::if_ < boost::is_same<T1, Default>, T2, typename boost::mpl::if_ < boost::is_same<T2, Default>, T1, ErrorFoundTwoNonDefaultTypes >::type >::type type; }; template<typename T1, typename T2> struct DetermineCommonBetweenTwo { typedef typename boost::mpl::if_ < boost::is_same<T1, T2>, T1, typename FindNonDefault<T1, T2>::type >::type type; }; template < typename T1 , typename T2 = Default, typename T3 = Default, typename T4 = Default, typename T5 = Default, typename T6 = Default, typename T7 = Default
struct DetermineCommon { typedef typename DetermineCommonBetweenTwo < T7, typename DetermineCommonBetweenTwo < T6, typename DetermineCommonBetweenTwo < T5, typename DetermineCommonBetweenTwo < T4, typename DetermineCommonBetweenTwo < T3, typename DetermineCommonBetweenTwo < T2, T1 >::type >::type >::type >::type >::type >::type type; }; //-------------------- class A {}; class B {}; BOOST_STATIC_ASSERT(( boost::is_same<typename DetermineCommon<Default, Default, Default, Default>::type, Default >::value )); BOOST_STATIC_ASSERT(( boost::is_same<typename DetermineCommon<A , A , Default, A >::type, A >::value )); BOOST_STATIC_ASSERT(( boost::is_same<typename DetermineCommon<A , Default, Default, A >::type, A >::value )); BOOST_STATIC_ASSERT(( boost::is_same<typename DetermineCommon<Default, A >::type, A >::value )); BOOST_STATIC_ASSERT(( boost::is_same<typename DetermineCommon<Default, A , Default, A >::type, A >::value )); BOOST_STATIC_ASSERT(( boost::is_same<typename DetermineCommon<A , B >::type, ErrorFoundTwoNonDefaultTypes>::value )); BOOST_STATIC_ASSERT(( boost::is_same<typename DetermineCommon<A , Default, B >::type, ErrorFoundTwoNonDefaultTypes>::value )); BOOST_STATIC_ASSERT(( boost::is_same<typename DetermineCommon<A , Default, Default, B >::type, ErrorFoundTwoNonDefaultTypes>::value )); BOOST_STATIC_ASSERT(( boost::is_same<typename DetermineCommon<A , B , Default >::type, ErrorFoundTwoNonDefaultTypes>::value )); //-------------------- int main() { return 0; }
Juraj Ivančić wrote:
Eric Niebler wrote:
I recently had a C++ problem and found an answer that tickled my brain. In the spirit of Car Talk on NPR, I thought I'd share it in the form of a puzzler.
Here is my solution. Not sure that it satisfies the conditions though.
Here I added a minor improvement which did not occur to me until reading latest solutions from Daniel Frey. Regards, Juraj Ivančić #include "boost/static_assert.hpp" #include "boost/type_traits/is_same.hpp" #include "boost/mpl/if.hpp" class ErrorFoundTwoNonDefaultTypes {}; class Default {}; template<typename T1, typename T2> struct FindNonDefault { typedef typename boost::mpl::if_ < boost::is_same<T1, Default>, T2, typename boost::mpl::if_ < boost::is_same<T2, Default>, T1, ErrorFoundTwoNonDefaultTypes >::type >::type type; }; template<typename T1, typename T2> struct DetermineCommonBetweenTwo { typedef typename boost::mpl::if_ < boost::is_same<T1, T2>, T1, typename FindNonDefault<T1, T2>::type >::type type; }; template < typename T1 , typename T2 = Default, typename T3 = Default, typename T4 = Default, typename T5 = Default, typename T6 = Default, typename T7 = Default, typename T8 = Default
struct DetermineCommon { typedef typename DetermineCommonBetweenTwo < typename DetermineCommonBetweenTwo < typename DetermineCommonBetweenTwo<T1,T2>::type, typename DetermineCommonBetweenTwo<T3,T4>::type >::type, typename DetermineCommonBetweenTwo < typename DetermineCommonBetweenTwo<T5,T6>::type, typename DetermineCommonBetweenTwo<T7,T8>::type >::type >::type type; }; //-------------------- class A {}; class B {}; BOOST_STATIC_ASSERT(( boost::is_same<typename DetermineCommon<Default, Default, Default, Default>::type, Default >::value )); BOOST_STATIC_ASSERT(( boost::is_same<typename DetermineCommon<A , A , Default, A >::type, A >::value )); BOOST_STATIC_ASSERT(( boost::is_same<typename DetermineCommon<A , Default, Default, A >::type, A >::value )); BOOST_STATIC_ASSERT(( boost::is_same<typename DetermineCommon<Default, A >::type, A >::value )); BOOST_STATIC_ASSERT(( boost::is_same<typename DetermineCommon<Default, A , Default, A >::type, A >::value )); BOOST_STATIC_ASSERT(( boost::is_same<typename DetermineCommon<A , B >::type, ErrorFoundTwoNonDefaultTypes>::value )); BOOST_STATIC_ASSERT(( boost::is_same<typename DetermineCommon<A , Default, B >::type, ErrorFoundTwoNonDefaultTypes>::value )); BOOST_STATIC_ASSERT(( boost::is_same<typename DetermineCommon<A , Default, Default, B >::type, ErrorFoundTwoNonDefaultTypes>::value )); BOOST_STATIC_ASSERT(( boost::is_same<typename DetermineCommon<A , B , Default >::type, ErrorFoundTwoNonDefaultTypes>::value )); //-------------------- int main() { return 0; }
Eric Niebler wrote:
I recently had a C++ problem and found an answer that tickled my brain. In the spirit of Car Talk on NPR, I thought I'd share it in the form of a puzzler.
OK, here's my solution. It's no better than some of the others I've seen posted here. Just a different way to skin the cat. #include <boost/mpl/assert.hpp> #include <boost/preprocessor.hpp> #include <boost/type_traits/is_same.hpp> #define M 10 struct Default {}; struct ignore { ignore(...); }; template<typename E> struct nondeducable { typedef nondeducable type; nondeducable(E*&); nondeducable(Default*&); }; template<> struct nondeducable<Default> { typedef nondeducable type; nondeducable(Default*&); }; template<int N, BOOST_PP_ENUM_PARAMS_WITH_A_DEFAULT(M, class A, void)> struct select_nth { BOOST_MPL_ASSERT_MSG((false), NO_COMMON_TYPE, (select_nth)); }; #define M0(Z, N, _) \ template<BOOST_PP_ENUM_PARAMS_Z(Z, M, class A)> \ struct select_nth<N BOOST_PP_ENUM_TRAILING_PARAMS_Z(Z, M, A)> \ { \ typedef BOOST_PP_CAT(A, N) type; \ }; BOOST_PP_REPEAT(M, M0, ~) #undef M0 template<BOOST_PP_ENUM_PARAMS_WITH_A_DEFAULT(M, class A, Default)> struct common_type { static char (&deducer(BOOST_PP_ENUM_PARAMS(M, ignore BOOST_PP_INTERCEPT)))[M+1]; #define M0(Z, N, _) \ static BOOST_PP_CAT(A, N) *BOOST_PP_CAT(a, N); \ template<typename T> \ static char (&deducer( \ BOOST_PP_ENUM_PARAMS_Z(Z, N, Default *& BOOST_PP_INTERCEPT) \ BOOST_PP_COMMA_IF(N) T *& \ BOOST_PP_ENUM_TRAILING_PARAMS_Z( \ Z \ , BOOST_PP_DEC(BOOST_PP_SUB(M, N)) \ , typename nondeducable<T>::type BOOST_PP_INTERCEPT \ ) \ ))[N+1]; BOOST_PP_REPEAT(M, M0, ~) #undef M0 static int const value = sizeof(deducer( BOOST_PP_ENUM_PARAMS(M, a))) - 1; typedef typename select_nth<value BOOST_PP_ENUM_TRAILING_PARAMS(M, A)>::type type; }; int main() { using boost::is_same; BOOST_MPL_ASSERT((is_same<common_type<Default, Default, int, Default>::type, int>)); BOOST_MPL_ASSERT((is_same<common_type<int, Default, int, Default>::type, int>)); BOOST_MPL_ASSERT((is_same<common_type<int, int, int, int>::type, int>)); BOOST_MPL_ASSERT((is_same<common_type<Default, Default, Default>::type, Default>)); // MPL assertion failure //common_type<int, short, Default>::type t; } The gist is to build an overload set like: deducer(T, Non<T>::type, Non<T>::type) deducer(Default, T, Non<T>::type, Non<T>::type) deducer(Default, Default, T, Non<T>::type) deducer(Default, Default, Default, T) Where both T and Default are convertible to Non<T>::type. The overload that gets selected has deduced T to be the common type. With decltype we could read it out directly. Instead I encode the index of T in the return type. There is one additional overload that gets selected only if there is no common type. If a common type exists, we instantiate nondeducable<T>, possibly nondeducable<Default>, and a select_nth template. That's it. -- Eric Niebler Boost Consulting www.boost-consulting.com
participants (11)
-
Anand Shankar -
Daniel Frey -
Eric Niebler -
Giovanni Piero Deretta -
JOAQUIN M. LOPEZ MUÑOZ -
Juraj Ivančić -
Marco -
Marco Costalba -
Matus Chochlik -
Sohail Somani -
Steven Watanabe