Generic compare function
in [C++]
|
From: Maxim Yegorushkin on 11 Jan 2010 07:15 On 11/01/10 19:32, Joe Gottman wrote: > Maxim Yegorushkin wrote: >> On 07/01/10 09:32, Adam Badura wrote: >>> Why C++ does not contain a generic compare function? Such function >>> would return a negative value if left< right, zero if left == right >>> and a positive value if left> right. It could be either overloaded >>> for user types or like swap use some template magic. >> >> It can be as simple as: >> >> // Returns -1, 0 and 1 for t < u, t == u and t > u respectively >> // Overload for your own types as necessary. >> template<class T, class U> >> int compare(T t, U u) >> { >> return (t > u) - (t < u); >> } >> > > The problem with this is that operator - is not defined for bool. This is why these two bools get promoted to int before doing the substruction. -- Max [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Maxim Yegorushkin on 11 Jan 2010 07:16 On 11/01/10 19:24, Adam Badura wrote: >> It can be as simple as: >> >> // Returns -1, 0 and 1 for t< u, t == u and t> u respectively >> // Overload for your own types as necessary. >> template<class T, class U> >> int compare(T t, U u) >> { >> return (t> u) - (t< u); >> } > > It is not about how short that function could be. > And beside your function (as the default one) has following > drawbacks: > 1) It requires both operator< and operator>. Providing both is not > hard if > one can be provided however STD seems to entirely depend only on< and > ==. Good point. It could be then: return (u < t) - (t < u). > 2) It will not work with overloaded versions of those operators which > do not > return bool but for example an int which is 0 for false and and > undetermined > positive number for true. True. Too bad for those eccentric operators. :) > 3) I think STD prefers to use std::less (and std::greater in this case > as > well) rather then row operators. But I am not sure here. The above works well for built-in arithmetic types. For user-defined types it is assumed that the user wants to provide a more efficient implementation that avoids doing two less-than comparisons in the first place. Something like: struct X { std::string a; bool b; int c; double d; int compare(X const& other) const { // assuming compare(std::string, std::string) overload if(int r = compare(a, other.a)) return r; if(int r = compare(b, other.b)) return r; if(int r = compare(c, other.c)) return r; return compare(d, other.d); } }; // overload the free-standing compare inline int compare(X const& a, X const& b) { return a.compare(b); } -- Max [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Seungbeom Kim on 11 Jan 2010 07:14 Maxim Yegorushkin wrote: > On 07/01/10 09:32, Adam Badura wrote: >> Why C++ does not contain a generic compare function? Such function >> would return a negative value if left< right, zero if left == right >> and a positive value if left> right. It could be either overloaded >> for user types or like swap use some template magic. > > It can be as simple as: > > // Returns -1, 0 and 1 for t < u, t == u and t > u respectively > // Overload for your own types as necessary. > template<class T, class U> > int compare(T t, U u) > { > return (t > u) - (t < u); > } This version performs the comparison twice, which defeats the purpose of having one compare function in the first place. Suppose t and u are std::string objects several hundred or thousand characters long that differ only at the end... -- Seungbeom Kim [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Maxim Yegorushkin on 12 Jan 2010 06:58 On 12/01/10 00:14, Seungbeom Kim wrote: > Maxim Yegorushkin wrote: >> On 07/01/10 09:32, Adam Badura wrote: >>> Why C++ does not contain a generic compare function? Such function >>> would return a negative value if left< right, zero if left == right >>> and a positive value if left> right. It could be either overloaded >>> for user types or like swap use some template magic. >> >> It can be as simple as: >> >> // Returns -1, 0 and 1 for t < u, t == u and t > u respectively >> // Overload for your own types as necessary. >> template<class T, class U> >> int compare(T t, U u) >> { >> return (t > u) - (t < u); >> } > > This version performs the comparison twice, which defeats the purpose > of having one compare function in the first place. Suppose t and u are > std::string objects several hundred or thousand characters long that > differ only at the end... This logic could apply to std::swap() if the was not an overload: void std::swap(std::string& a, std::string& b) { a.swap(b); } Whose only purpose is optimization. Following std::swap() optimization pattern in a real system there should be an overload: int compare(std::string& a, std::string& b) { return a.compare(b); } Interesting enough, using compare() (or compare<> functor) instead of std::less<> in std::set/map<> would give it a speed boost for operations like find() because to determine whether elements are equal it calls std::less<> twice . That results in two strncmp() calls while returning from find() when keys are strings, whereas using compare that would require only one strncmp() call. -- Max [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Seungbeom Kim on 12 Jan 2010 19:36
Maxim Yegorushkin wrote: > On 12/01/10 00:14, Seungbeom Kim wrote: >> Maxim Yegorushkin wrote: >> >> This version performs the comparison twice, which defeats the purpose >> of having one compare function in the first place. Suppose t and u are >> std::string objects several hundred or thousand characters long that >> differ only at the end... > > This logic could apply to std::swap() if the was not an overload: > > void std::swap(std::string& a, std::string& b) > { > a.swap(b); > } > > Whose only purpose is optimization. Following std::swap() optimization > pattern in a real system there should be an overload: > > int compare(std::string& a, std::string& b) > { > return a.compare(b); > } The question is, what do we get by choosing "less", instead of "compare", as /the/ primitive and requiring overloads for optimization? We have seen that "less" could be easily and efficiently provided in terms of "compare", but not vice versa. With "less" as the primitive, some algorithms may suffer the performance penalty mentioned below, or an overload of "compare" has to be provided separately from "less" by the class designer. With "compare" as the primitive, just one "compare" function is all that's needed from the class designer, and "less" or "greater" or "equal_to" can all be implemented easily and efficiently in terms of "compare". Of course, thing could have been a lot easier with an operator like "<=>", which would have encouraged the designers of the standard library to use this as the primitive for general comparison, and allowed class designers to provide overloads of the operator. > > Interesting enough, using compare() (or compare<> functor) instead of > std::less<> in std::set/map<> would give it a speed boost for operations > like find() because to determine whether elements are equal it calls > std::less<> twice . That results in two strncmp() calls while returning > from find() when keys are strings, whereas using compare that would > require only one strncmp() call. Right, and that is the motivation for "compare" (as I understand it). -- Seungbeom Kim [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] |