Slight problem using user-defined types with STL sets

Discussion in 'C++' started by Debo, Nov 29, 2004.

  1. Debo

    Debo Guest

    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
    Debo, Nov 29, 2004
    #1
    1. Advertising

  2. "Debo" <> wrote in message
    news:p...
    > 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<;

    Actually it uses std::less<twotuple>, which delegates to 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
    Jonathan Turkanis, Nov 29, 2004
    #2
    1. Advertising

  3. Debo

    Debo Guest

    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
    Debo, Nov 29, 2004
    #3
  4. Debo

    Swampmonster Guest

    Debo wrote:
    >
    > 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::pair'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
    Swampmonster, Dec 12, 2004
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. grahamo
    Replies:
    4
    Views:
    985
    Thomas Wintschel
    Feb 23, 2004
  2. JNY

    slight rounding problem

    JNY, Jan 11, 2005, in forum: C Programming
    Replies:
    2
    Views:
    309
    Joe Wright
    Jan 12, 2005
  3. JNY

    slight rounding problem

    JNY, Jan 12, 2005, in forum: C Programming
    Replies:
    2
    Views:
    280
    Keith Thompson
    Jan 12, 2005
  4. Oodini
    Replies:
    1
    Views:
    1,750
    Keith Thompson
    Sep 27, 2005
  5. W. eWatson
    Replies:
    3
    Views:
    413
    W. eWatson
    Mar 6, 2009
Loading...

Share This Page