Generic compare function
in [C++]
|
From: Jesse Perla on 13 Jan 2010 05:56 On Jan 13, 7:36 am, Seungbeom Kim <musip...(a)bawi.org> wrote: > Maxim Yegorushkin wrote: > The question is, what do we get by choosing "less", instead of "compare", > as /the/ primitive and requiring overloads for optimization? I think the answer is primarily that the std is trying to have mathematical foundations in order theory. Everything in order theory is about binary predicates. Take set Y, the ordering is a mapping Y x Y: -> {0,1} For an overview of the foundations behind this, the creator of the standard library recently wrote: http://www.elementsofprogramming.com/ -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Maxim Yegorushkin on 13 Jan 2010 05:56 On 13/01/10 12:36, Seungbeom Kim wrote: > 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. Yep, <=> is compare, in terms of which other relational operators can be implemented easily/generically. -- 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 13 Jan 2010 09:22 Jesse Perla wrote: > On Jan 13, 7:36 am, Seungbeom Kim <musip...(a)bawi.org> wrote: >> Maxim Yegorushkin wrote: >> The question is, what do we get by choosing "less", instead of "compare", >> as /the/ primitive and requiring overloads for optimization? > > I think the answer is primarily that the std is trying to have > mathematical foundations in order theory. Everything in order theory > is about binary predicates. Take set Y, the ordering is a mapping Y x > Y: -> {0,1} That may be valuable in math, but computer programming is not just math. For example, in mathematics you can define natural numbers using sets: 0 := { } 1 := {0} = {{ }} 2 := {0, 1} = {{ }, {{ }}} 3 := {0, 1, 2} = {{ }, {{ }}, {{ }, {{ }}}} : : and this is totally equivalent to the conventional definition and fine in mathematics, but nobody does that for computer programming; it would be a huge inefficiency. Because mathematical models don't take efficiency into account. Likewise, in mathematics it may be that all you need is <, and that you can build all the others (<=, >, >=, ==, !=) from it, but it may turn out to be suboptimal in efficiency, as we see in this thread. The C++ standard library could have been much more efficient, while maintaining the equivalence, by using compare (<=>) functions instead of less (<). -- Seungbeom Kim [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Le Chaud Lapin on 14 Jan 2010 02:07 On Jan 13, 8:22 pm, Seungbeom Kim <musip...(a)bawi.org> wrote: > Likewise, in mathematics it may be that all you need is <, and that > you can build all the others (<=, >, >=, ==, !=) from it, but it may > turn out to be suboptimal in efficiency, as we see in this thread. > The C++ standard library could have been much more efficient, while > maintaining the equivalence, by using compare (<=>) functions instead > of less (<). Given the relatively low expenditure of intellectual energy required to discover that (-, 0, +) is far more efficient than operator <, one has to wonder for what reason was operator < chosen in the first place. -Le Chaud Lapin- -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: LR on 15 Jan 2010 09:57
Le Chaud Lapin wrote: > Given the relatively low expenditure of intellectual energy required > to discover that (-, 0, +) is far more efficient than operator <, one > has to wonder for what reason was operator < chosen in the first > place. Perhaps this http://www.stepanovpapers.com/notes.pdf will provide an explanation. LR -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] |