set of unordered objects

[mihai]

How can I build a set of unordered objects lets say POINT_2D objects?
The POINT_2D class does not have a consistent operator<.

Have a nice day,
Mihai.

 

[Larry I Smith]

How can I build a set of unordered objects lets say POINT_2D objects?
The POINT_2D class does not have a consistent operator<.

Have a nice day,
Mihai.

Either create an 'operator<' for POINT_2D (whatever that is),
or use 'vector' or 'list' instead of 'set'.

Regards,
Larry

 

[Rolf Magnus]

How can I build a set of unordered objects lets say POINT_2D objects?
The POINT_2D class does not have a consistent operator<.

I'm not sure what you mean. In a set (if you mean std::set, which I assume
since you mention operator<), the elements are always ordered. Are you sure
you really want a set?

 

[Stephen Howe]

How can I build a set of unordered objects lets say POINT_2D objects?

See if your compiler vendor provides unordered_set (hash_set) or equivalent
defined by an == operator. I know it is non-standard (and eventually will be
standard) but this container matches your requirements.

Stephen Howe

 

[Mark Stijnman]

I'm not sure what you mean. In a set (if you mean std::set, which I assume
since you mention operator<), the elements are always ordered. Are you sure
you really want a set?

I'm assuming he wants a set to be guaranteed of there not being any
duplicates. In order to do so, the std::Set stores obects in order, so
it can quickly find out if the element is already in the set. So, if
you really want the property of no duplicate items, define a consistent
operator<, for instsance, pointA.length()<pointB.lenght(), where
length() would return sqrt(x*x + y*y).

 

[Richard Herring]

I'm assuming he wants a set to be guaranteed of there not being any
duplicates. In order to do so, the std::Set stores obects in order, so
it can quickly find out if the element is already in the set. So, if
you really want the property of no duplicate items, define a consistent
operator<, for instsance, pointA.length()<pointB.lenght(), where
length() would return sqrt(x*x + y*y).

That won't work for std::set, which needs a strict weak ordering.

With your definition, you can have objects a, b for which none of a<b,
b<a, a==b is true, which will sooner or later lead to great confusion.

Better to define it something like std:air does:
a.x < b.x || (!(b.x < a.x) && a.y < b.y)

 

[Rolf Magnus]

That won't work for std::set, which needs a strict weak ordering.

With your definition, you can have objects a, b for which none of a<b,
b<a, a==b is true, which will sooner or later lead to great confusion.

Do you have an example of a combination of two vectors of which neither is
shorter than the other and still their length is not equal?

Better to define it something like std:air does:
a.x < b.x || (!(b.x < a.x) && a.y < b.y)

Kind of lexical order.

 

[Richard Herring]

Do you have an example of a combination of two vectors of which neither is
shorter than the other and still their length is not equal?

No, why would I?

If a = (0,1) and b = (1,0), then for most useful definitions of points
in 2D space they are not equal. Nevertheless if operator< is defined in
terms of length() neither of the assertions a<b, b<a is true, so they
are in the same equivalence class. Consequently:

#include <cmath>
#include <iostream>
#include <ostream>
#include <set>

struct Point {
Point(int xx, int yy) : x(xx), y(yy) {}
double length() const { return std::sqrt(x*x + y*y); }
int x, y;
};

bool operator<(Point const & a, Point const & b)
{ return a.length() < b.length(); }

int main()
{
Point a(0,1);
Point b(1,0);
std::set<Point> s;
s.insert(a);
std::cout << s.count(b) << '\n';
}

 

[Rolf Magnus]

No, why would I?

Because you claim that this is possible.

If a = (0,1) and b = (1,0), then for most useful definitions of points
in 2D space they are not equal.

Above, you wrote: "That won't work for std::set" and "With your definition,
you can have objects a, b for which none of a<b, b<a, a==b is true", and
that's not right. We can argue about the usefulness of that operator<, but
that's another story.

Nevertheless if operator< is defined in
terms of length() neither of the assertions a<b, b<a is true,

Yes, that's because they are considered equal in that case.

so they are in the same equivalence class. Consequently:

#include <cmath>
#include <iostream>
#include <ostream>
#include <set>

struct Point {
Point(int xx, int yy) : x(xx), y(yy) {}
double length() const { return std::sqrt(x*x + y*y); }
int x, y;
};

bool operator<(Point const & a, Point const & b)
{ return a.length() < b.length(); }

int main()
{
Point a(0,1);
Point b(1,0);
std::set<Point> s;
s.insert(a);
std::cout << s.count(b) << '\n';
}

If you have std::set<std::string> and use a case-insensitive comparison, you
can also try to put two different strings in a set and only one will be
stored.

 

[Richard Herring]

Because you claim that this is possible.

No, I do not. I claim that you can have two vectors of which neither is
shorter than the other yet their *directions* are not equal.

Above, you wrote: "That won't work for std::set" and "With your definition,
you can have objects a, b for which none of a<b, b<a, a==b is true", and
that's not right.

But it is. That operator < defines equivalence classes which don't
correspond to vector equality. Therefore (the conventional meaning of)
== is inconsistent with <.

We can argue about the usefulness of that operator<, but
that's another story.

It's fine (ie it's a strict weak ordering) so far as the inner workings
of std::set go, but it defines an equivalence which doesn't match the
usual interpretation of vector equality. When looking things up in sets
or maps, it's the equivalence, not the ordering, which is important.

Yes, that's because they are considered equal in that case.

Not equal, equivalent. My point is that this equivalence is not equality
because information is discarded.

If you have std::set<std::string> and use a case-insensitive comparison, you
can also try to put two different strings in a set and only one will be
stored.

Of course. The difference is that case-insensitive "equality" is
sometimes a useful way of defining equivalence classes for strings.
Direction-insensitive "equality" is not a correspondingly useful concept
for vectors.