 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
mihai
Guest
|
 Posted: Sat Apr 23, 2005 4:24 pm Post subject: set of unordered objects |
 |
|
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.
|
|
| Back to top |
|
 |
Larry I Smith
Guest
|
| Posted: Sat Apr 23, 2005 4:43 pm Post subject: Re: set of unordered objects |
|
|
mihai wrote:
| Quote: | 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.
|
|
| Back to top |
|
|
Rolf Magnus
Guest
|
| Posted: Sat Apr 23, 2005 4:49 pm Post subject: Re: set of unordered objects |
|
|
mihai wrote:
| Quote: | 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?
|
|
| Back to top |
|
|
Stephen Howe
Guest
|
| Posted: Sat Apr 23, 2005 5:06 pm Post subject: Re: set of unordered objects |
|
|
| Quote: | 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
|
|
| Back to top |
|
|
Mark Stijnman
Guest
|
| Posted: Sat Apr 23, 2005 5:07 pm Post subject: Re: set of unordered objects |
|
|
Rolf Magnus wrote:
| Quote: | 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()
length() would return sqrt(x*x + y*y).
|
|
| Back to top |
|
|
Richard Herring
Guest
|
| Posted: Tue Apr 26, 2005 10:00 am Post subject: Re: set of unordered objects |
|
|
In message <1114276026.840701.134470 (AT) f14g2000cwb (DOT) googlegroups.com>, Mark
Stijnman <m.a.stijnman (AT) tnw (DOT) utwente.nl> writes
| Quote: |
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()
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
Better to define it something like std::pair does:
a.x < b.x || (!(b.x < a.x) && a.y < b.y)
--
Richard Herring
|
|
| Back to top |
|
|
Rolf Magnus
Guest
|
| Posted: Tue Apr 26, 2005 12:18 pm Post subject: Re: set of unordered objects |
|
|
Richard Herring wrote:
| Quote: | 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()
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
|
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?
| Quote: | 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.
|
|
| Back to top |
|
|
Richard Herring
Guest
|
| Posted: Tue Apr 26, 2005 12:48 pm Post subject: Re: set of unordered objects |
|
|
In message <d4lbbi$clv$05$1 (AT) news (DOT) t-online.com>, Rolf Magnus
<ramagnus (AT) t-online (DOT) de> writes
| Quote: | 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()
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
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
are in the same equivalence class. Consequently:
#include
#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
s.insert(a);
std::cout << s.count(b) << 'n';
}
| Quote: | 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
|
|
| Back to top |
|
|
Rolf Magnus
Guest
|
| Posted: Thu Apr 28, 2005 5:41 pm Post subject: Re: set of unordered objects |
|
|
Richard Herring wrote:
| Quote: | In message <d4lbbi$clv$05$1 (AT) news (DOT) t-online.com>, Rolf Magnus
[email]ramagnus (AT) t-online (DOT) de[/email]> 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()
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
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.
| Quote: | 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
that's not right. We can argue about the usefulness of that operator<, but
that's another story.
| Quote: | Nevertheless if operator< is defined in
terms of length() neither of the assertions a
|
Yes, that's because they are considered equal in that case.
| Quote: | so they are in the same equivalence class. Consequently:
#include
#include
#include
#include
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
s.insert(a);
std::cout << s.count(b) << 'n';
}
|
If you have std::set
can also try to put two different strings in a set and only one will be
stored.
|
|
| Back to top |
|
|
Richard Herring
Guest
|
| Posted: Fri Apr 29, 2005 8:53 am Post subject: Re: set of unordered objects |
|
|
In message <d4r6uj$9l6$00$3 (AT) news (DOT) t-online.com>, Rolf Magnus
<ramagnus (AT) t-online (DOT) de> writes
| Quote: | Richard Herring wrote:
In message <d4lbbi$clv$05$1 (AT) news (DOT) t-online.com>, Rolf Magnus
[email]ramagnus (AT) t-online (DOT) de[/email]> 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()
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
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.
| Quote: | 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
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 <.
| Quote: | 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.
| Quote: |
Nevertheless if operator< is defined in
terms of length() neither of the assertions a
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.
| Quote: |
so they are in the same equivalence class. Consequently:
#include
#include
#include
#include
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
s.insert(a);
std::cout << s.count(b) << 'n';
}
If you have std::set
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
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
