Re: std::sort
Jeff Schwab wrote:
On Nov 26, 2:31 pm, "Victor Bazarov" <v.Abaza...@comAcast.net> wrote:
Jeff Schwab wrote:
Would std::sort ever compare an object with itself?
I don't believe the Standard prohibits that.
I'm not talking
about two distinct, equal-valued objects, but rather this == &that.
The container being sorted is a std::vector.
Objects are never compared using '=='. They are compared using '<'
or the functor provided.
The standard sort algorithm defaults to using std::less. Since we are
sorting a container of pointers, we provide our own comparison
routine, which internally compares the results of the dereferenced
pointers. The pointers themselves are first checked for equality,
since an object is always equal to itself. This is very common, basic
stuff, and I assume you already know it.
Actually, not all objects are equal to themselves. For example, the
floating point "Not-A-Number" (NaN) yields false when compared with
itself using '=='. This is very basic stuff and I assume you already
know it.
The point is not that somewhere in the guts of your functor you use
'==' but that the 'std::sort' never uses '==' on the objects.
I've never seen this, but a coworker says he is. NB: I can't post
sample code that reproduces the issue, nor do I claim any bug in the
STL implementation (GCC 3.4.2). I'm just hoping a definitive answer
resides in one of the brains who frequent this group.
Tell your coworker to provide you with proof.
No need. The following example took ~ 2 min. to write and debug.
Note the explicit operator== to which I referred earlier. I'm using a
POD object type here (int) for simplicity.
And?... What do you expect I should get from your example? What do
you expect yourself to derive from your example? You're testing one
particular implementation of 'std::sort'.
Nothing in the Standard says that 'std::sort' never compares the object
to itself (IOW, passes the same reference to the provided functor). It
is your responsibility to provide the functor that functions correctly
(according to your model) when an object is compared to itself.
Nothing in the Standard says what algorithm is used in 'std::sort'.
#include <iostream>
template<typename T>
bool
deref_less(T* p, T* q)
{
if (p == q) {
std::clog << "warning: object at " << p << " compared to
itself.\n";
}
return *p < *q;
}
#include <algorithm>
#include <vector>
int
main()
{
typedef int Object;
std::vector<Object*> v;
for (int i = 0; i < 1000; ++i) {
v.push_back(new Object(i));
}
std::sort(v.begin(), v.end(), deref_less<Object>);
// cleanup ...
return 0;
}
V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask