C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  Ideal min/max          C++Talk.NET Forum Index -> C++ Language (Moderated) View previous topic :: View next topic   Author Message Jason Hise Guest Posted: Wed Sep 06, 2006 10:57 pm    Post subject: Ideal min/max I remember reading about an elegant solution mentioned by Andrei Alexandrescu for generating ideal min and max templates, but I can't find where I read it. The solution involved some sort of double nesting of the question colon operator in order to determine the correct return type. I believe it was mentioned in passing in an article of his on some other subject. Does anyone know what this solution was or where I could find it? [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Michael Olea Guest Posted: Thu Sep 07, 2006 3:57 am    Post subject: Re: Ideal min/max Jason Hise wrote: Quote: I remember reading about an elegant solution mentioned by Andrei Alexandrescu for generating ideal min and max templates, but I can't find where I read it. The solution involved some sort of double nesting of the question colon operator in order to determine the correct return type. I believe it was mentioned in passing in an article of his on some other subject. Does anyone know what this solution was or where I could find it? I have not seen the article (and I too would like a reference to it) but I have been thinking about type promotion. An example is adding two points (vectors in a vector space), where the coordinate values might be floating point or integral: template<typename T, size_t dimension> class Point { ... protected T component[dimension]; }; The issue is how to determine the return type of operators like +: template<typename T, typename U, size_t N) Point<typename PromoteTo<T,U>::Type, N> operator+(const Point<T,N>& p, const Point<U,N>& q) { ... } There is a brief discussion of a type promotion template in Vanedevoorde and Josuttis' book "C++ Templates: The Complete Guide". The idea is that PromoteTo returns the more "inclusive" type; so if its arguments are an integral type and a floating point type it returns the floating point type. Things get interesting, however, when the arguments are two integral types, one signed, the other unsigned, e.g: PromoteTo<signed char, unsigned char>. My solution is to return the smallest signed integral type that can represent the union of the values representable by its two type arguments. So, PromoteTo<signed char, unsigned char> would return short, assuming shorts are bigger than chars. There are two problems with that approach: 1) there may be no such type (e.g. PromoteTo<long, unsigned long> in an environment that does not include long long, or PromoteTo<long long, unsigned long long> in an environment that does). My "solution" in such cases is to generate a compile-time error, but I'm not so sure that is best. The other problem is that this is not necessarily the desired behavior. For example, the result of max(x, y) when x is a signed char and y is an unsigned char can always be represeted by an unsigned char, whereas the result of min(x, y) under the same conditions can always be represented by a signed char. Maybe there should be 3 type promoters: PromoteTo, PromoteToMax, and PromoteToMin? -- Michael [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Christian Rössel Guest Posted: Thu Sep 07, 2006 7:19 pm    Post subject: Re: Ideal min/max Jason Hise schrieb: Quote: I remember reading about an elegant solution mentioned by Andrei Alexandrescu for generating ideal min and max templates, but I can't find where I read it. The solution involved some sort of double nesting of the question colon operator in order to determine the correct return type. I believe it was mentioned in passing in an article of his on some other subject. Does anyone know what this solution was or where I could find it? Hi Jason, it was published in C/C++ Users Journal and is available from here: http://www.ddj.com/dept/cpp/184403774 Regards, Christian [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top jk Guest Posted: Thu Sep 07, 2006 7:28 pm    Post subject: Re: Ideal min/max Jason Hise wrote: Quote: I remember reading about an elegant solution mentioned by Andrei Alexandrescu for generating ideal min and max templates, but I can't find where I read it. The solution involved some sort of double nesting of the question colon operator in order to determine the correct return type. I believe it was mentioned in passing in an article of his on some other subject. Does anyone know what this solution was or where I could find it? was it this? http://www.ddj.com/dept/cpp/184403774 a lot of andrei's articles are available from his website - under 'other publications' [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Jason Hise Guest Posted: Thu Sep 07, 2006 11:46 pm    Post subject: Re: Ideal min/max I did read the article you are all linking to, and it isn't what I am remembering. The article I am remembering did not require the loki library and only mentioned the solution briefly. I do not remember what the majority of the article was about. Typelists were not required to make it work. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Andrei Alexandrescu (See Guest Posted: Thu Sep 07, 2006 11:46 pm    Post subject: Re: Ideal min/max Bob wrote: Quote: Jason Hise wrote: I remember reading about an elegant solution mentioned by Andrei Alexandrescu for generating ideal min and max templates, but I can't find where I read it. The solution involved some sort of double nesting of the question colon operator in order to determine the correct return type. I believe it was mentioned in passing in an article of his on some other subject. Does anyone know what this solution was or where I could find it? Andrei used a reasonably liberal interpretation of "elegant". Good point ). Quote: The solution was reasonably elegant and not that much code, as long as it was built on his Loki library. And the tools employed from that library are actually based on both macro and template trickery. In any event, an online version of the article is at http://www.ddj.com/dept/cpp/184403774 Jason is referring to a different solution, which was developed by Eric Niebler following an idea of mine. (He did most of the work.) I'm not sure whether he published it yet. The basic idea is this: #define MIN(a, b) min_impl(true ? (a) : (b), false ? (a) : (b)) Then all of a sudden you have the macro streamline the types for you exactly as operator?: would, but without the double evaluation. So you got the best of both worlds. Given that min_impl's arguments will be of the same type, all you have to do then is to implement two overloads: template <class T> const T& min_impl(const T& a, const T& b) { ... } template <class T> T& min_impl(T& a, T& b) { ... } A lingering problem is that the first overload is selected for rvalues, too, which means that somebody could save a dud object by writing const int& dud = MIN(4, 5); Eric went ahead and solved that problem, too, at the expense of implementation simplicity: the code size and complexity blow up. In the end I'm more fond of the approach of my older article because it can (as a poster mentioned) employ the semantics of min and max to refine the result type (e.g., min of unsigned int and unsigned char is unsigned char). The version above is most faithful to what a < b ? a : b would do, and that's nice, too. But, I agree: if min and max are this complicated to implement properly, that becomes more of an embarrassment than a interesting challenge. Unfortunately, I seem to recall from an email exchange that the version based on rvalue references is still not as trivially simple as it ought to be. Andrei [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Eric Niebler Guest Posted: Fri Sep 15, 2006 1:48 am    Post subject: Re: Ideal min/max Sorry for the delayed response.... Andrei Alexandrescu (See Website For Email) wrote: Quote: Bob wrote: Jason Hise wrote: I remember reading about an elegant solution mentioned by Andrei Alexandrescu for generating ideal min and max templates, but I can't find where I read it. The solution involved some sort of double nesting of the question colon operator in order to determine the correct return type. I believe it was mentioned in passing in an article of his on some other subject. Does anyone know what this solution was or where I could find it? I made a brief mention about Andrei's and my solution in the comment section of my article "Conditional Love" on The C++ Source: http://www.artima.com/cppsource/foreach.html Perhaps that's what you're thinking of. Quote: Andrei used a reasonably liberal interpretation of "elegant". Good point ). The solution was reasonably elegant and not that much code, as long as it was built on his Loki library. And the tools employed from that library are actually based on both macro and template trickery. In any event, an online version of the article is at http://www.ddj.com/dept/cpp/184403774 Jason is referring to a different solution, which was developed by Eric Niebler following an idea of mine. (He did most of the work.) I'm not sure whether he published it yet. The basic idea is this: #define MIN(a, b) min_impl(true ? (a) : (b), false ? (a) : (b)) Then all of a sudden you have the macro streamline the types for you exactly as operator?: would, but without the double evaluation. So you got the best of both worlds. Given that min_impl's arguments will be of the same type, all you have to do then is to implement two overloads: template <class T const T& min_impl(const T& a, const T& b) { ... } template <class T T& min_impl(T& a, T& b) { ... } A lingering problem is that the first overload is selected for rvalues, too, which means that somebody could save a dud object by writing const int& dud = MIN(4, 5); Eric went ahead and solved that problem, too, at the expense of implementation simplicity: the code size and complexity blow up. Actually, the full, 100% standard compliant solution is not very complicated at all, and you can see it here: http://tinyurl.com/j4b23. The complexity comes from finding work-arounds for broken compilers, and sadly, regarding the tricks I use, all compilers are broken at the moment. At http://tinyurl.com/ep8rt, in the file minmax_macro.zip, you can find a version that works on gcc, msvc and edg-based compilers. Quote: In the end I'm more fond of the approach of my older article because it can (as a poster mentioned) employ the semantics of min and max to refine the result type (e.g., min of unsigned int and unsigned char is unsigned char). The version above is most faithful to what a < b ? a : b would do, and that's nice, too. But, I agree: if min and max are this complicated to implement properly, that becomes more of an embarrassment than a interesting challenge. Unfortunately, I seem to recall from an email exchange that the version based on rvalue references is still not as trivially simple as it ought to be. But a solution that uses rvalue references *and* return type deduction is about as simple as falling off a bar stool. :-) -- Eric Niebler Boost Consulting www.boost-consulting.com [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         C++Talk.NET Forum Index -> C++ Language (Moderated) All times are GMT Page 1 of 1   Jump to: Select a forum C/C++----------------C LanguageC Language (Moderated)C++ Language (Moderated)C++ language (comp.lang.c++)C++ language, library and standards Non-English C/C++ Newsgroups----------------C++ (German)C++ (French)  You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum Powered by phpBB © 2001, 2006 phpBB Group SEO toolkit © 2004-2006 webmedic.