Slight problem using user-defined types with STL sets

[Debo]

Hello all,

I've got a fairly basic question about STL sets and operator overloading
in general.

I'm working with a data type that's essentially a 2-element vector. A
simplified (hacked) version would be something like this:

struct twotuple
{
...

int x;
int y;
};


Now, what I want to be able to do is to use a set to take the union of a
whole bunch of vectors, so that similar vectors will only be stored once.
For instance:

----------------------
set<twotuple> s;

twotuple t1(1, 2);
twotuple t2(2, 1);
twotuple t3(1, 2);

s.insert(t1);
s.insert(t2);
s.insert(t3);
-----------------------

should result in there only being two vectors stored in s (namely, t1 and
t2). I'm under the impression that a set determines equality based on operator<;
I'm guessing that it does something like

if (!(a < b) && !(b<a))

to see if two user-defined structures are equal. My question is, how
should I overload operator< in this case for two-tuples? It seems obvious,
but you can't just ensure that the x and y of one tuple are both less than
the x and y of another tuple, because that will result in 'fake'
equalities in some cases (eg (1 2) and (2 1) will fulfill
!(a < b) && !(b < a) ).

I'm sorry if the answer to this is dead obvious and I'm just being dense.
Any help would be appreciated.

-Debo

 

[Jonathan Turkanis]

Hello all,

I've got a fairly basic question about STL sets and operator overloading
in general.

I'm working with a data type that's essentially a 2-element vector. A
simplified (hacked) version would be something like this:

struct twotuple
{
...

int x;
int y;
};


Now, what I want to be able to do is to use a set to take the union of a
whole bunch of vectors, so that similar vectors will only be stored once.
For instance:

----------------------
set<twotuple> s;

twotuple t1(1, 2);
twotuple t2(2, 1);
twotuple t3(1, 2);

s.insert(t1);
s.insert(t2);
s.insert(t3);

operator<;

I'm guessing that it does something like

if (!(a < b) && !(b<a))

This is the test for equivalence of keys.

to see if two user-defined structures are equal. My question is, how
should I overload operator< in this case for two-tuples? It seems obvious,
but you can't just ensure that the x and y of one tuple are both less than
the x and y of another tuple, because that will result in 'fake'
equalities in some cases (eg (1 2) and (2 1) will fulfill
!(a < b) && !(b < a) ).

Try a lexicographical ordering, e.g.

bool operator<(const twotuple& lhs, const twotuple& rhs)
{
return lhs.x < rhs.x ||
!rhs.x < lhs.x && lhs.y < rhs.y;
}

This says "lhs is less than rhs with respect to the first coordinate, or lhs and
rhs are equivalent with respect to the first coordinate but lhs is less than rhs
with respect to the second coordinate."

Jonathan

 

[Debo]

On Sun, 28 Nov 2004, Jonathan Turkanis wrote:

JT> Try a lexicographical ordering, e.g.
JT>
JT> bool operator<(const twotuple& lhs, const twotuple& rhs)
JT> {
JT> return lhs.x < rhs.x ||
JT> !rhs.x < lhs.x && lhs.y < rhs.y;
JT> }
JT>
JT> This says "lhs is less than rhs with respect to the first coordinate, or lhs and
JT> rhs are equivalent with respect to the first coordinate but lhs is less than rhs
JT> with respect to the second coordinate."
JT>
JT> Jonathan

That worked perfectly; thanks so much!

-Debo

 

[Swampmonster]

On Sun, 28 Nov 2004, Jonathan Turkanis wrote:

JT> Try a lexicographical ordering, e.g.
JT>
JT> bool operator<(const twotuple& lhs, const twotuple& rhs)
JT> {
JT> return lhs.x < rhs.x ||
JT> !rhs.x < lhs.x && lhs.y < rhs.y;
JT> }
JT>
JT> This says "lhs is less than rhs with respect to the first coordinate, or lhs and
JT> rhs are equivalent with respect to the first coordinate but lhs is less than rhs
JT> with respect to the second coordinate."
JT>
JT> Jonathan

That worked perfectly; thanks so much!

-Debo

Hm. I'd prefer to write this something like this:

class my_vec
{
public:
class special_order;
friend class my_vec::special_order;

my_vec( int x_, int y_ )
: x( x_ ), y( y_ )
{}

class special_order
{
public:
bool operator()( const my_vec& a, const my_vec& b )
{
// just use std:air's implementation of
// "operator <" to define or "lexical" order...
return
std::make_pair( a.x, a.y ) <
std::make_pair( b.x, b.y );
}
};

protected:
int x;
int y;
};

void something()
{
std::set<my_vec, my_vec::special_order> my_set;

my_set.insert( my_vec( 1, 1 ) );
my_set.insert( my_vec( 1, 2 ) );
my_set.insert( my_vec( 2, 1 ) );
my_set.insert( my_vec( 1, 1 ) );
assert( my_set.size() == 3 );
}

Works perfectly well too
The reasons why I'd prefer that way are not easy to explain, but I'd not
define an "operator <" just to have a std::set function - unless I
need that "operator <" and it's semantics are natural and clear I'd just
not do it...
Bye, monster