By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
448,677 Members | 1,236 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 448,677 IT Pros & Developers. It's quick & easy.

set of unordered objects

P: n/a
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.

Jul 23 '05 #1
Share this Question
Share on Google+
9 Replies


P: n/a
mihai wrote:
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

--
Anti-spam address, change each 'X' to '.' to reply directly.
Jul 23 '05 #2

P: n/a
mihai wrote:
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?

Jul 23 '05 #3

P: n/a

Rolf Magnus wrote:
mihai wrote:
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?


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).

Jul 23 '05 #4

P: n/a
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
Jul 23 '05 #5

P: n/a
In message <11**********************@f14g2000cwb.googlegroups .com>, Mark
Stijnman <m.**********@tnw.utwente.nl> writes

Rolf Magnus wrote:
mihai wrote:
> How can I build a set of unordered objects lets say POINT_2Dobjects? > 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?


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::pair does:
a.x < b.x || (!(b.x < a.x) && a.y < b.y)

--
Richard Herring
Jul 23 '05 #6

P: n/a
Richard Herring wrote:
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.


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::pair does:
a.x < b.x || (!(b.x < a.x) && a.y < b.y)


Kind of lexical order.

Jul 23 '05 #7

P: n/a
In message <d4*************@news.t-online.com>, Rolf Magnus
<ra******@t-online.de> writes
Richard Herring wrote:
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.


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';
}
Better to define it something like std::pair does:
a.x < b.x || (!(b.x < a.x) && a.y < b.y)


Kind of lexical order.


--
Richard Herring
Jul 23 '05 #8

P: n/a
Richard Herring wrote:
In message <d4*************@news.t-online.com>, Rolf Magnus
<ra******@t-online.de> writes
Richard Herring wrote:
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.
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?


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.

Jul 23 '05 #9

P: n/a
In message <d4*************@news.t-online.com>, Rolf Magnus
<ra******@t-online.de> writes
Richard Herring wrote:
In message <d4*************@news.t-online.com>, Rolf Magnus
<ra******@t-online.de> writes
Richard Herring wrote:

>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.

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?


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.
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.


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.
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.


Not equal, equivalent. My point is that this equivalence is not equality
because information is discarded.
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.

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.

--
Richard Herring
Jul 23 '05 #10

This discussion thread is closed

Replies have been disabled for this discussion.