C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  chained comparsion - one expression, one return          C++Talk.NET Forum Index -> C++ Language (Moderated) View previous topic :: View next topic   Author Message Kodt Guest Posted: Tue Sep 06, 2005 10:58 am    Post subject: chained comparsion - one expression, one return Imagine you need to write a comparsion function int compare(Foo const& a, Foo const& b) or bool operator<(Foo const& a, Foo const& b) implementing a lexicographical order on a set of Foo's members. And you would like to do this as clear as possible: you hate multiple exits, gotos and macros. Thus, a common way bool operator<(Foo const& a, Foo const& b) { if(a.x < b.x) return true; if(b.x < a.x) return false; if(a.y < b.y) return true; if(b.y < a.y) return false; // et cetera return false; } is rejected. What could you do? Here is a solution. It uses lazy evaluation of && or || (also known as "and-then", "or-else") to stop comparsion, and a result of comparsion is passed as out-parameter. The building block of our approach is template bool chain_order(T const& a, T const& b, bool& r) { return (r = (a<b)) || (b // r = true when and only when a // return true wnen a!=b } easily customized with predicates, template bool chain_order(T const& a, T const& b, bool& r, P p) { return (r = p(a,b)) || p(b,a); } and similar version for int comparsion template<class T> bool chain_compare(T const& a, T const& b, int& r) { return (r = a<b ? -1 : b } template bool chain_compare(T const& a, T const& b, int& r, Cmp cmp) { return (r = cmp(a,b)) != 0; } Now, we can build the target function int compare(Foo const& a, Foo const& b) { int r; chain_compare(a.x, b.x, r) || chain_compare(a.y, b.y, r) || ..... chain_compare(a.z, b.z, r); return r; } or bool operator<(Foo const& a, Foo const& b) { bool r; chain_order(a.x, b.x, r) || chain_order(a.y, b.y, r, greater ..... chain_order(a.z, b.z, r); return r; } What do you think on this? [ Russian-speaking people can also discuss this in the RSDN forum, where I posted it first time: http://www.rsdn.ru/Forum/?mid=1364242 ] [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Edson Manoel Guest Posted: Tue Sep 06, 2005 4:02 pm    Post subject: Re: chained comparsion - one expression, one return Although a clever solution, I think it just obfuscated the problem. The first solution using multiple exits was much clearer! [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top John Potter Guest Posted: Tue Sep 06, 2005 4:14 pm    Post subject: Re: chained comparsion - one expression, one return On 6 Sep 2005 06:58:02 -0400, "Kodt" <nickolay.merkin (AT) gmail (DOT) com> wrote: Quote: Imagine you need to write a comparsion function int compare(Foo const& a, Foo const& b) or bool operator<(Foo const& a, Foo const& b) implementing a lexicographical order on a set of Foo's members. And you would like to do this as clear as possible: you hate multiple exits, gotos and macros. Thus, a common way bool operator<(Foo const& a, Foo const& b) { if(a.x < b.x) return true; if(b.x < a.x) return false; if(a.y < b.y) return true; if(b.y < a.y) return false; // et cetera return false; } is rejected. What could you do? One fairly nice method which has been posted here is to simply use ?: return a.x < b.x ? true : b.x < a.x ? false : a.y < b.y ? true : b.y < a.y ? false : a.z < b.z; Or return a.x < b.x ? -1 : b.x < a.x ? 1 : a.y < b.y ? -1 : b.y < a.y ? 1 : a.z < b.z ? -1 : b.z < a.z ? 1 : 0; John [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Tony Delroy Guest Posted: Wed Sep 07, 2005 12:59 am    Post subject: Re: chained comparsion - one expression, one return It's scary to think you might not be joking, and scary to think I'm replying if you are. I'll bite anyway. Quote: Thus, a common way bool operator<(Foo const& a, Foo const& b) { if(a.x < b.x) return true; if(b.x < a.x) return false; if(a.y < b.y) return true; if(b.y < a.y) return false; // et cetera return false; } is rejected. What could you do? bool operator<(Foo const& a, Foo const& b) { return a.x < b.x || a.x == b.x && a.y < b.y; } If you think knowledge that || is lower precendence than && is rare where you work... ... then you may want to put ( and ) around the &&-ed comparisons. Tony [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Greg Herlihy Guest Posted: Wed Sep 07, 2005 1:04 am    Post subject: Re: chained comparsion - one expression, one return Kodt wrote: Quote: Imagine you need to write a comparsion function int compare(Foo const& a, Foo const& b) or bool operator<(Foo const& a, Foo const& b) implementing a lexicographical order on a set of Foo's members. And you would like to do this as clear as possible: you hate multiple exits, gotos and macros. Thus, a common way bool operator<(Foo const& a, Foo const& b) { if(a.x < b.x) return true; if(b.x < a.x) return false; if(a.y < b.y) return true; if(b.y < a.y) return false; // et cetera return false; } is rejected. What could you do? Then I would write the routine to be "as clear as possible" so it would not be "rejected" a second time. Of course, I may not have to write it myself if I can just copy it. I would be wise then to briefly assess the proposed solution to see whether I could do any better. Quote: Here is a solution. It uses lazy evaluation of && or || (also known as "and-then", "or-else") to stop comparsion, and a result of comparsion is passed as out-parameter. The building block of our approach is template bool chain_order(T const& a, T const& b, bool& r) { return (r = (a // r = true when and only when a // return true wnen a!=b } This chain_order routine accepts two items to compare, a and b, and returns the result of the comparison (less than, equal to, greater than). To convey the result to the caller, chain_order accepts a boolean r parameter that, when used in tandem with the function result, synthesizes a "triboolean" value indicating whether a is less than, equal to, or greater than b, by returning true and setting r to true, by returning false and setting r to false, or by returning true and setting r to false, respectively. Of course returning false and setting r to true would be a nonsensical result, as anyone who finds the first three possible results self-describing, would no doubt understand. Now aside from the fact that "r" and chain_order would probably be better renamed as a noun and as a verb respectively, better names alone would not mitigate the complexity of this routine's interface. In short, chain_order simply provies more information than is needed, and in a format that I for one find unintuitive. The chain_order routine only needs to perform a less-than comparison - all other relative comparisons (greather than, equal to, less than or equal to, etc) can be synthesized from that one operation. The STL sorting routines are based on that fact. And as an added benefit, the caller does not have to pay (in terms of complexity or performance) for uneeded information. Instead the solution is to put together "building blocks" of simple routines in order to create an implementation of arbitrary complexity. Quote: easily customized with predicates, template bool chain_order(T const& a, T const& b, bool& r, P p) { return (r = p(a,b)) || p(b,a); } and similar version for int comparsion template bool chain_compare(T const& a, T const& b, int& r) { return (r = a } Why does the chain_order routine - that was written expressly to compare two items - need to be further customized in order to compare the two items? Why not write the customized version of the chain_order in the first place? One could argue that the problem being solved is a special case of a more generic problem, so that this extra level of abstraction is justified. But that doesn't seem to be the case with implementing a < operator. As far as I can tell, the customization step seems to be another way to add more layers of code to this solution, simply for the sake of coding. Quote: template bool chain_compare(T const& a, T const& b, int& r, Cmp cmp) { return (r = cmp(a,b)) != 0; } Now, we can build the target function int compare(Foo const& a, Foo const& b) { int r; chain_compare(a.x, b.x, r) || chain_compare(a.y, b.y, r) || ..... chain_compare(a.z, b.z, r); return r; } or bool operator<(Foo const& a, Foo const& b) { bool r; chain_order(a.x, b.x, r) || chain_order(a.y, b.y, r, greater ..... chain_order(a.z, b.z, r); return r; } What do you think on this? Based on my brief assessment, I think that this implementation of a < operator falls short of its goal of being "as clear as possible." If, for no other reason, that it simply has too much code. As bad as macros, gotos, multiple exits [insert bad practice here] may be, there is nothing worse in a program than unneeded code. Why? Because the only code that will never have any macros, spaghetti logic or any bugs at all, is, to paraphrase Steve Jobs, the code that was never written. So how could a program ever end up with excess code? There is one simple reason: programmers like to write code. So much so, that they may write too much of it on occassion. And just as smoking or drinking alchohol are probably not in anyone's long term health interests, writing a lot of code is probably not in a programmer's longer term interests either (since it likely means more time spent debugging and maintaining the code down the road). But for many people the short term benefits outweigh whatever the longer term risk may be. A fact that explains why some people smoke or drink, and why some programs are larger than they need to be. To return to the original question: since I didn't find the proposed approach crystal in its clarity, I would choose to provide my own implementation for the < operator: bool operator<(Foo const& a, Foo const& b) { return a.x != b.x ? a.x < b.x : a.y != a.y ? a.y < b.y : a.z < b.z; } Now even the most discriminating code critic will find no macros, multiple exits or gotos in this "one-expression one-return" routine with which to find fault. Although in all honesty, I would observe that this version is no more correct, and is at best a marginal improvement over the one rejected. Nevertheless I would certainly choose the above solution over the approach proposed - because the solution above has, after all, just a single line of code. Greg [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Marc Mutz Guest Posted: Wed Sep 07, 2005 9:57 am    Post subject: Re: chained comparsion - one expression, one return John Potter wrote: <snip> Quote: One fairly nice method which has been posted here is to simply use ?: return a.x < b.x ? true : b.x < a.x ? false : a.y < b.y ? true : b.y < a.y ? false : a.z < b.z; Or return a.x < b.x ? -1 : b.x < a.x ? 1 : a.y < b.y ? -1 : b.y < a.y ? 1 : a.z < b.z ? -1 : b.z < a.z ? 1 : 0; snip Although I must confess to a certain tendency of my code to use nested ternaries, too (nice table-like layout), I must admit that this use makes it spaghetti :) Sorry. Marc, having used std::lexicographical_compare for such things in the past (works only with elelments having the same type, though) [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Dietmar Kuehl Guest Posted: Wed Sep 07, 2005 9:57 am    Post subject: Re: chained comparsion - one expression, one return John Potter wrote: Quote: One fairly nice method which has been posted here is to simply use ?: I haven't seen this posted but I prefer this: return std::tr1::tie(a.x, a.y, a.z) < std::tr1::tie(b.x, b.y, b.z); Of course, it assumes that you have got a library supporting TR1. -- <http://www.eai-systems.com> - Efficient Artificial Intelligence [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Mirek Fidler Guest Posted: Wed Sep 07, 2005 2:04 pm    Post subject: Re: chained comparsion - one expression, one return Kodt wrote: Quote: Imagine you need to write a comparsion function int compare(Foo const& a, Foo const& b) or bool operator<(Foo const& a, Foo const& b) First of all, it is a pity when comparison has to be done using bool predicate - when composing things together, operator< has to be be called many more times than would be with classical signed compare. Anyway, in my petty library I am just experimenting with Compare approach that works like this: struct ComposedFoo : Comparable Foo1 x; Foo2 y; Foo3 z; int Compare(const ComposedFoo& b) { CompareCombine m; return m(x, b.x)(y, b.y)(z, b.z); } }; This expects Foo1, Foo2 and Foo3 to have either Compare defined or are fundamental type and adds (via Comparable) all needed comparison operators. CompareCombine is defined like this: struct CombineCompare { int result; CombineCompare& Put(int q) { if(!result) result = q; return *this; } CombineCompare& operator()(const int& a, const int& b) { return Put(NumberCompare__(a, b)); } // .... + other fundamental types..... template <class T> CombineCompare& operator()(const T& a, const T& b) { return Put(a.Compare(b)); } operator int() const { return result; } CombineCompare() { result = 0; } }; Possible drawback might seem that all elements have to be compared, but in fact compiler optimizes this out. Well, this is not a final solution, as we need better support for existing types without the Compare method (and I am not sure about cleanest solution there), but I think it demonstrates the method... Mirek [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top John Potter Guest Posted: Thu Sep 08, 2005 9:19 am    Post subject: Re: chained comparsion - one expression, one return On 7 Sep 2005 10:04:23 -0400, Mirek Fidler <cxl (AT) volny (DOT) cz> wrote: Quote: Kodt wrote: Imagine you need to write a comparsion function int compare(Foo const& a, Foo const& b) or bool operator<(Foo const& a, Foo const& b) First of all, it is a pity when comparison has to be done using bool predicate - when composing things together, operator< has to be be called many more times than would be with classical signed compare. However for simple types, the easiest way to generate the classical signed compare is: int comp (int a, int b) { return (b < a) - (a < b); } For types smaller than int, a - b may be used, but others must avoid overflow. For more complex types such as string where there is an overhead for finding the place to do the simple compare, the classical form can be used to advantage. Most algorithms such as sorts and searches are designed to use a single less compare until the final step. A well written binary search uses lg(N) + 1 compares not 2lg(N). In the case of the thread subject, it may show that a general solution is not possible. The less form is fine for types with no overhead while the classic form is appropriate for special types. John [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top John Potter Guest Posted: Thu Sep 08, 2005 9:20 am    Post subject: Re: chained comparsion - one expression, one return On 7 Sep 2005 05:57:59 -0400, Dietmar Kuehl <dietmar_kuehl (AT) yahoo (DOT) com> wrote: Quote: John Potter wrote: One fairly nice method which has been posted here is to simply use ?: I haven't seen this posted but I prefer this: return std::tr1::tie(a.x, a.y, a.z) < std::tr1::tie(b.x, b.y, b.z); Of course, it assumes that you have got a library supporting TR1. And a maintenance programmer who has way more than a clue. I wonder if the complexity of the library has reached the point where only a smalltalk programmer can appreciate it? John [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Mirek Fidler Guest Posted: Fri Sep 09, 2005 3:21 pm    Post subject: Re: chained comparsion - one expression, one return Quote: However for simple types, the easiest way to generate the classical signed compare is: int comp (int a, int b) { return (b < a) - (a < b); } For types smaller than int, a - b may be used, but others must avoid overflow. BTW, I still wonder whether there is some unconditional (I mean without conditional jumps) form for int that avoids overflow. In the end, you can e.g. achieve saturated aritmetic without conditions using just the right mix of trivial operations... (see http://cvs.sourceforge.net/viewcvs.py/enlightenment/e17/libs/imlib2/src/lib/blend.h?view=markup ) Quote: For more complex types such as string where there is an overhead for finding the place to do the simple compare, the classical form can be used to advantage. Most algorithms such as sorts and searches are designed to use a single less compare until the final step. A well written binary search uses lg(N) + 1 compares not 2lg(N). Well, my problem (I am not sure whether we are reffering the same thing) is with complex composition, like: struct Foo1 { string a; string b; operator<(Foo1 o) { if(a < o.a) return true; if(o.a < a) return false; return b < o.b; } }; struct Foo2 { Foo1 a; Foo1 b; operator<(Foo1 o) { if(a < o.a) return true; if(o.a < a) return false; return b < o.b; } }; struct Foo3 { Foo2 a; Foo2 b; operator<(Foo1 o) { if(a < o.a) return true; if(o.a < a) return false; return b < o.b; } }; Now invoking Foo3::operator< will perform Foo3::a.a.a with Foo3::a.a.b comparison 4 times (if they are equal). With classical signed compare this would result in single comparison. Mirek [ 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.