Generic compare function
in [C++]
|
From: Adam Badura on 7 Jan 2010 13:49 > How would you actually use such a function? Like I am using any other functions or functors. > How would it be implemented more efficiently than we can do for ourselves? This can be told just about every thing including entire STL for example. So I do not consider it an argument. > How would you determine which ordering was to be > used (many types have more then one logical ordering, and often include > equivalence sets)? Just like it is done with default comparison operators and functors. I don't see any problem here. > Even std::string has multiple orderings depending on the collation rules. And yet somehow this does not prevent us from comparing std::string with operator < for example... > How would you deal with types that have no ordering? > What about types that have equivalence sets but no ordering? Again just like with comparison operators and functors. There would be no overload/specialization/whatever dedicated for them and any use of generic compare function for them would result in compilation error. > It may seem a very simple thing to do but in fact it is very complicated > and far from trivial to provide generically. I don't think so. After all "red floyd" posted and example implementation. And that is just all. A good generic fallback. But types like std::string might use a smarter code to prevent suboptimal double comparison. Compiler might even use extra machine code to provide faster versions for arithmetic types for example. But the bright side is that user of "compare" no longer cares. Using "compare" you ask what you want directly: "what is the order relation of those to objects from totally ordered space?". And asking questions directly is a great thing because it makes it easier to give decent replay as fast as possible. Adam Badura -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Adam Badura on 7 Jan 2010 13:52 > How would you actually use such a function? Like I am using any other functions or functors. > How would it be implemented more efficiently than we can do for ourselves? This can be told just about every thing including entire STL for example. So I do not consider it an argument. > How would you determine which ordering was to be > used (many types have more then one logical ordering, and often include > equivalence sets)? Just like it is done with default comparison operators and functors. I don't see any problem here. > Even std::string has multiple orderings depending on the collation rules. And yet somehow this does not prevent us from comparing std::string with operator < for example... > How would you deal with types that have no ordering? > What about types that have equivalence sets but no ordering? Again just like with comparison operators and functors. There would be no overload/specialization/whatever dedicated for them and any use of generic compare function for them would result in compilation error. > It may seem a very simple thing to do but in fact it is very complicated > and far from trivial to provide generically. I don't think so. After all "red floyd" posted and example implementation. And that is just all. A good generic fallback. But types like std::string might use a smarter code to prevent suboptimal double comparison. Compiler might even use extra machine code to provide faster versions for arithmetic types for example. But the bright side is that user of "compare" no longer cares. Using "compare" you ask what you want directly: "what is the order relation of those to objects from totally ordered space?". And asking questions directly is a great thing because it makes it easier to give decent replay as fast as possible. Adam Badura -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Adam Badura on 7 Jan 2010 13:52 > I'd wager the answer is simple: your generic "compare" function would > simply be implemented in terms of op== and op< (or >), at which point, > you'd have one more (trivial) function name for small-ish number of > use cases. Yes. A generic fallback might be implemented so. Just like the implementation provided by "red floyd". But types like std::string, build-in types and even containers might provide a more efficient implementations. In the end you might as well say it about std::swap which after all is just a simple copy construction and assignment. > For strings and raw memory, there are low-level (C) functions already Yes. But they cannot be used in generic code as they do not work with any type. > (seems to be your case). But they don't work well in face of +/- > complex types that majority of C++ code is supposed to have. Yet somehow swap works well... > BTW, it looks like you're thinking in terms of qsort, which I'd > consider strange for idiomatic C++ code. With C++, if you want > ordering, just use set/multiset/map/multimap and/or populate your > vectors using lower/upper_bound. I can't see why do you need a > comparison function then. For example when implementing some algorithms or containers. Adam Badura -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Tony Delroy on 7 Jan 2010 13:55 > Adam Badura wrote: > > Why C++ does not contain a generic compare function? Such function <snip> > > [lack] results in the need to compare those string twice while a simple > > "compare" function would give us full information at the cost of one > > comparison. On Jan 8, 3:06 am, Francis Glassborow <francis.glassbo...(a)btinternet.com> wrote: > I wonder if you have thought this through. How would you actually use > such a function? As Adam wrote, it's useful when comparing two containers (e.g. strings), where you scan over some long common part, then find a distinguishing character. There's a fair chance that you may know exactly which of <, == and > apply at that point, so it would be nice to have a good way to return that information. If you only indicate say <, then a second comparison may waste time skipping the early common elements before returning to the distinguishing ones.... Many existing "int compare(... a, ... b)" functions only promise to return a negative, 0 or positive value, as subtracting elements may produce that in one step more efficiently than guaranteeing -1, 0, or 1. The latter scheme does make it easy to switch on the resultant value though... switch (a.compare(b)) // or "a <=> b" or similar if an operator were available { case -1: return "less than"; case 0: return "equal"; case 1: return "greater than"; default: std::cerr << "oops\n"; exit(EXIT_FAILURE); } Without a -1, 0, 1 guarantee, something like: int compare_result = a <=> b; if (compare_result < 0) ... else if (compare_result == 0) ... else // compare_result > 0 ...; In another post, I mentioned the ? : operators could be extended... return a <=> b ?< "less than" ?= "equals" : "greater than"; I don't for one moment expect anything like this to be added to the language, but I don't see that the objections you raise undermine this comparison any more than the existing comparison operators (<, <=, ==, !=, >=, >). > How would it be implemented more efficiently than we > can do for ourselves? It only helps efficiency in that it becomes a standard thing for compilers to optimise. Consider this program: int main(int argc, char* argv[]) { return argc < 7 ? 42 : argc == 7 ? 53 : 64; } I picked weird numbers so they'd stand out in x86 assembly... g++ -S -O3 compare.cc # ver. 4.4.1 cmpl $6, %edi movl $42, %eax jle .L3 movb $64, %al cmpl $7, %edi movl $53, %edx cmove %edx, %eax ..L3: rep ret f it helps the compiler a single compare statement, A compiler might be able to perform the comparison once then use the CPU flags to branch or load the appropriate return value without repeating the comparison. Perhaps they do that for simple int/double comparisons already? I've never studied. It couldn't... I don't see much point in providing a compare(a, b) function that works for types where the results would be meaningful (e.g. string, int, double). How would you determine which ordering was to be > used (many types have more then one logical ordering, and often include > equivalence sets)? Even std::string has multiple orderings depending > on the collation rules. How would you deal with types that have no > ordering? What about types that have equivalence sets but no ordering? > > It may seem a very simple thing to do but in fact it is very complicated > and far from trivial to provide generically. -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Adam Badura on 7 Jan 2010 14:32
> #include <functional> > template <typename T> > int compare<T>(const T& left, const T& right) > { > if (std::less(left, right)) > return -1; > else if (std::less(right, left)) > return 1; > else > return 0; > } Yes. Exactly. But if this function is not in std namespace then: 1) Standard types like string or containers will not provide more efficient versions. 2) Standard algorithms/containers will not use it to increase performance. 3) Interaction of code from different vendors is harder. Finally note that the same kind of argument might be used against having std::swap. Adam Badura -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] |