Generic compare function
in [C++]
|
From: Piotr Wyderski on 8 Jan 2010 01:40 red floyd wrote: > #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; > } Two less-es, which is a completely unnecessary overhead. :-) Instead, one can think of expressing the less family in terms of compare -- always exactly one invocation. In case of longer structures a direct 3-way comparison is much faster (one full scan + the first found non-equal element handling instead of two full scans). Best regards Piotr Wyderski -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Adam Badura on 8 Jan 2010 01:50 This is a reply which was sent to "Francis Glassborow" and was accidentally posted also here. Adam Badura -- [ 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 8 Jan 2010 08:28 On Jan 8, 7:44 am, Goran <goran.pu...(a)gmail.com> wrote: > On Jan 8, 8:51 am, Le Chaud Lapin <jaibudu...(a)gmail.com> wrote: > > > You can see in the following STL code from VS2008 that the _Pred() > > function is being invoked twice for a comparison: > > > template<class _Pr, class _Ty1, class _Ty2> inline > > bool __CLRCALL_OR_CDECL _Debug_lt_pred(_Pr _Pred, const _Ty1& _Left, > > const _Ty2& _Right, > > const wchar_t *_Where, unsigned int _Line) > > { // test if _Pred(_Left, _Right) and _Pred is strict weak ordering > > if (!_Pred(_Left, _Right)) > > return (false); > > else if (_Pred(_Right, _Left)) > > _DEBUG_ERROR2("invalid operator<", _Where, _Line); > > return (true); > > } > > Hmmm... I think MS people should check this. That second comparison > should be out of the picture in optimized builds, because it only has > debugging purposes. Quick look at sources tells me that ain't the > case. Implementation quality issue? I do not understand the standard library very well, but it looks like this is more a deliberate design issue than implementation issue: http://www.sgi.com/tech/stl/less.html Apparently, the idea is that, if A < B, then logically, B must be greater than A, so the designers of standard library help the programmer by requiring that s/he only supply operator <, and the library will take care of the rest. As Adam pointed out, this "taking care of the rest" is the crux of the issue. By prescribing that comparisons must rely on operator <, and not (-, 0, +), the double-comparison for testing order becomes inevitable. On a semi-related note regarding a fat string class to conform to the model Adam proposes, whereby comparison of two strings is done using only state entirely contained within either string: int s = signum(s1, s2); // s becomes (+, 0, -) ....I realized this morning that all my fretting to keep such a String class "skinny" compared to std::string might be unwarranted. I figured that, while my String was guaranteed to be fat, std::string might not be so skinny itself. So I checked: int main () { cout << "sizeof(String) == " << sizeof(String) << endl; cout << "sizeof(std::string) == " << sizeof(std::string) << endl; } Output Debug Mode, Visual Studio 2008: sizeof(String) == 28 sizeof(std::string) == 32 Output Release Mode, Visual Studio 2008: sizeof(String) == 28 sizeof(std::string) == 28 Of course, there will be trade-offs. I imagine my String will be slower in some situations and might not provide some desirable feautures of std::string, but at least this shows thave a sizeof (A_String_Class) >, say, 12, is not so bad. -Le Chaud Lapin- -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Adam Badura on 8 Jan 2010 08:26 > The standard library provides std::less as the entry point for a > general comparison, and uses it as the default in many places. > Your point then, as I understand it, is why is it a two-way comparison > instead of a three-way one, and why does std::sort take a 'less' > function returning bool (true/false) instead of a 'compare' function > returning int (<0/=0/>0) that the good old qsort uses; is this correct? I cannot say in name of Tony Delroy but as it goes for me it is more or less what I meant. I am wondering why STD does not provide a generalized way to specify "three-way" comparators just like it does for "two-way" ones. Types which support such comparison (and this includes almost all if not all standard types and many user types) would be easier and more efficient in use with such "three-way" comparator. > A comparison primitive had better be more efficient, IMO. When you > need a 'stricter' version returning one of the three values, you can > always use a separate sign function. I myself didn't opt to have strict -1, 0, +1 return values but rather general -, 0, +. But it might be done by yet another layer of abstraction. Those types which easily support strict return values would do so and other would provide weaker version and the strict on would be added by sign function. Adam Badura -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Francis Glassborow on 9 Jan 2010 08:24
Le Chaud Lapin wrote: > On Jan 8, 7:44 am, Goran <goran.pu...(a)gmail.com> wrote: >> On Jan 8, 8:51 am, Le Chaud Lapin <jaibudu...(a)gmail.com> wrote: >> >>> You can see in the following STL code from VS2008 that the _Pred() >>> function is being invoked twice for a comparison: >>> template<class _Pr, class _Ty1, class _Ty2> inline >>> bool __CLRCALL_OR_CDECL _Debug_lt_pred(_Pr _Pred, const _Ty1& _Left, >>> const _Ty2& _Right, >>> const wchar_t *_Where, unsigned int _Line) >>> { // test if _Pred(_Left, _Right) and _Pred is strict weak ordering >>> if (!_Pred(_Left, _Right)) >>> return (false); >>> else if (_Pred(_Right, _Left)) >>> _DEBUG_ERROR2("invalid operator<", _Where, _Line); >>> return (true); >>> } >> Hmmm... I think MS people should check this. That second comparison >> should be out of the picture in optimized builds, because it only has >> debugging purposes. Quick look at sources tells me that ain't the >> case. Implementation quality issue? > > I do not understand the standard library very well, but it looks like > this is more a deliberate design issue than implementation issue: > > http://www.sgi.com/tech/stl/less.html > > Apparently, the idea is that, if A < B, then logically, B must be > greater than A, so the designers of standard library help the > programmer by requiring that s/he only supply operator <, and the > library will take care of the rest True (in what world would A<B not imply B>A) The next step is to realise that !(A<B) and !(B<A) can be true. Values for A and B that satisfy that are members of an equivalence set (note that they might not be identical) -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] |