Strict weak ordering

Discussion in 'C++' started by bb, Oct 8, 2007.

  1. bb

    bb Guest

    #include <iostream>
    #include <map>

    using std::cout;
    using std::endl;
    using std::map;
    using std::pair;

    struct myType {
    int m1_;
    int m2_;

    myType(int m1, int m2) : m1_(m1), m2_(m2) {}
    myType(const myType& rhs) : m1_(rhs.m1_), m2_(rhs.m2_) {}

    ~myType() {}

    bool operator<(const myType& rhs) const {
    if ((this->m1_ < rhs.m1_) && (this->m2_ < rhs.m2_)) { return true; }
    return false;
    }
    };

    int main(int argc, char* argv[]) {
    typedef map<myType, int> myMap;

    myType ky1(2,3);
    myType ky2(3,2);

    myMap mymap;

    mymap.insert(myMap::value_type(ky1,10));
    cout << mymap.size() << endl;

    mymap.insert(myMap::value_type(ky2,11)); // updates instead of
    inserting a second entry
    cout << mymap.size() << endl;
    }

    In the above code, the objects ky1 & ky2 are obviously not the same.
    (at least i do not intend them to be so). However, per strict weak
    ordering, stl does assume they are equivalent. Hence, even after the
    second insert, mymap.size() returns 1.

    Is my operator<() implementation is wrong?

    What all should ensure when I use my own type as a key in an
    associative container?

    Thanks in advance.
     
    bb, Oct 8, 2007
    #1
    1. Advertising

  2. bb

    Guest

    On Oct 8, 2:33 pm, bb <> wrote:
    > #include <iostream>
    > #include <map>
    >
    > using std::cout;
    > using std::endl;
    > using std::map;
    > using std::pair;
    >
    > struct myType {
    > int m1_;
    > int m2_;
    >
    > myType(int m1, int m2) : m1_(m1), m2_(m2) {}
    > myType(const myType& rhs) : m1_(rhs.m1_), m2_(rhs.m2_) {}
    >
    > ~myType() {}
    >
    > bool operator<(const myType& rhs) const {
    > if ((this->m1_ < rhs.m1_) && (this->m2_ < rhs.m2_)) { return true; }
    > return false;
    > }
    >
    > };
    >
    > int main(int argc, char* argv[]) {
    > typedef map<myType, int> myMap;
    >
    > myType ky1(2,3);
    > myType ky2(3,2);
    >
    > myMap mymap;
    >
    > mymap.insert(myMap::value_type(ky1,10));
    > cout << mymap.size() << endl;
    >
    > mymap.insert(myMap::value_type(ky2,11)); // updates instead of
    > inserting a second entry
    > cout << mymap.size() << endl;
    >
    > }
    >
    > In the above code, the objects ky1 & ky2 are obviously not the same.
    > (at least i do not intend them to be so). However, per strict weak
    > ordering, stl does assume they are equivalent. Hence, even after the
    > second insert, mymap.size() returns 1.
    >
    > Is my operator<() implementation is wrong?
    >
    > What all should ensure when I use my own type as a key in an
    > associative container?
    >
    > Thanks in advance.


    I think the condition should be:
    (this->m1_ < rhs.m1_) || ((this->m1_ == rhs.m1_) && (this->m2_ <
    rhs.m2_))
     
    , Oct 8, 2007
    #2
    1. Advertising

  3. bb

    Pete Becker Guest

    On 2007-10-08 08:33:11 -1000, bb <> said:

    >
    > bool operator<(const myType& rhs) const {
    > if ((this->m1_ < rhs.m1_) && (this->m2_ < rhs.m2_)) { return true; }
    > return false;
    > }
    > };
    >
    >
    > myType ky1(2,3);
    > myType ky2(3,2);
    >
    >
    > In the above code, the objects ky1 & ky2 are obviously not the same.
    > (at least i do not intend them to be so). However, per strict weak
    > ordering, stl does assume they are equivalent. Hence, even after the
    > second insert, mymap.size() returns 1.
    >


    Your operator< says that they are equivalent, since neither one is less
    than the other. If you don't want them to be equivalent you have to
    figure out which one is less than the other, and then write operator<
    to reflect that design decision.

    --
    Pete
    Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
    Standard C++ Library Extensions: a Tutorial and Reference
    (www.petebecker.com/tr1book)
     
    Pete Becker, Oct 8, 2007
    #3
  4. bb

    bb Guest

    > I think the condition should be:
    > (this->m1_ < rhs.m1_) || ((this->m1_ == rhs.m1_) && (this->m2_ <
    > rhs.m2_))


    I do agree. However, if there are going to be more member variables,
    then operator< is going to become unreadable. I guess there is a
    simpler way?

    Currently, am stringifying all the members (kind of object_id) and
    using it in operator<. It seems to work... not sure if it is the
    proper way.

    Thanks anyway.
     
    bb, Oct 8, 2007
    #4
  5. bb

    Pete Becker Guest

    On 2007-10-08 11:24:52 -1000, bb <> said:

    >> I think the condition should be:
    >> (this->m1_ < rhs.m1_) || ((this->m1_ == rhs.m1_) && (this->m2_ <
    >> rhs.m2_))

    >
    > I do agree. However, if there are going to be more member variables,
    > then operator< is going to become unreadable. I guess there is a
    > simpler way?
    >


    If the comparison involves all the members, then you have to write code
    that looks at all the members. It's only unreadable if you write it
    that way. <g>

    Having said that, if you really do have complex objects that require a
    total order, look at tr1's tuple. It does comparisons for you. (It's
    also in std for the next standard, but your comiler probably doesn't do
    that yet)

    #include <tuple>

    typedef std::tr1::tuple<int, int> my_type;

    my_type obj1(2, 3);
    my_type obj2(3, 2);

    Now, obj1 < obj2 is well-defined, and obj2 < obj1 is also well-defined.
    And that operator< defines a total ordering.

    --
    Pete
    Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
    Standard C++ Library Extensions: a Tutorial and Reference
    (www.petebecker.com/tr1book)
     
    Pete Becker, Oct 9, 2007
    #5
  6. bb

    Ben Pfaff Guest

    bb <> writes:

    >> I think the condition should be:
    >> (this->m1_ < rhs.m1_) || ((this->m1_ == rhs.m1_) && (this->m2_ <
    >> rhs.m2_))

    >
    > I do agree. However, if there are going to be more member variables,
    > then operator< is going to become unreadable. I guess there is a
    > simpler way?


    This kind of comparison chain is pretty readable:

    if (lhs.a != rhs.a)
    return lhs.a < rhs.a;
    else if (lhs.b != rhs.b)
    return lhs.b < rhs.b;
    else if (lhs.c != rhs.c)
    return lhs.c < rhs.c;
    else if (lhs.d != rhs.d)
    return lhs.d < rhs.d;
    else
    return false;
    --
    "Writing is easy.
    All you do is sit in front of a typewriter and open a vein."
    --Walter Smith
     
    Ben Pfaff, Oct 9, 2007
    #6
  7. bb

    bb Guest

    > This kind of comparison chain is pretty readable:
    >
    > if (lhs.a != rhs.a)
    > return lhs.a < rhs.a;
    > else if (lhs.b != rhs.b)
    > return lhs.b < rhs.b;
    > else if (lhs.c != rhs.c)
    > return lhs.c < rhs.c;
    > else if (lhs.d != rhs.d)
    > return lhs.d < rhs.d;
    > else
    > return false;


    I realized. Thanks Ben.
     
    bb, Oct 9, 2007
    #7
  8. bb

    bb Guest

    > Having said that, if you really do have complex objects that require a
    > total order, look at tr1's tuple. It does comparisons for you. (It's
    > also in std for the next standard, but your comiler probably doesn't do
    > that yet)
    >
    > #include <tuple>
    >
    > typedef std::tr1::tuple<int, int> my_type;
    >
    > my_type obj1(2, 3);
    > my_type obj2(3, 2);
    >
    > Now, obj1 < obj2 is well-defined, and obj2 < obj1 is also well-defined.
    > And that operator< defines a total ordering.
    >


    tuple really looks cool. Thanks Pete.
     
    bb, Oct 9, 2007
    #8
    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. Kuan Zhou
    Replies:
    1
    Views:
    5,203
    Paul Uiterlinden
    Jan 24, 2005
  2. totojepast
    Replies:
    0
    Views:
    484
    totojepast
    Jul 10, 2003
  3. Nicholas Zigarovich

    Strange behavior with weak references

    Nicholas Zigarovich, Sep 2, 2003, in forum: Java
    Replies:
    0
    Views:
    380
    Nicholas Zigarovich
    Sep 2, 2003
  4. nbigaouette

    Z-Ordering (Morton ordering) question

    nbigaouette, Nov 5, 2009, in forum: C Programming
    Replies:
    2
    Views:
    2,317
  5. Stephen Evans

    builtin max() and weak ordering

    Stephen Evans, Mar 3, 2011, in forum: Python
    Replies:
    1
    Views:
    214
    Mark Dickinson
    Mar 3, 2011
Loading...

Share This Page