Thread: Help using std::set and operator<

  1. #1
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391

    Help using std::set and operator<

    Hi all,

    If I'm placing things in a set, and I don't care whether or not they're sorted ( I just want to take advantage of the set's ability to make the "key" the object itself), must I overload the operator<? I've overloaded operator== so it knows whether or not two objects are the same.

    Thoughts?

    Thanks in advance.

    EDIT: With a bit of testing, I've discovered the compiler complains when I take away the operator<. Is there a way around this, or must it be present to use the insert() function?
    Last edited by dudeomanodude; 04-15-2008 at 08:41 AM.
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  2. #2
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    yes, it must be present.
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  3. #3
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391
    yes, it must be present.
    So I'm supposing my completely arbitrary operator< that I've written will suffice.

    Thanks Sebastiani.
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  4. #4
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    Why not just use a vector?

  5. #5
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by dudeomanodude View Post
    So I'm supposing my completely arbitrary operator< that I've written will suffice.
    No, you can't use an arbitrary comparison. It must actually produce a valid ordering, or the set will break. For instance, if a < b and b < c, then a < c. If your operator does not obey this, then things will blow up.

  6. #6
    The larch
    Join Date
    May 2006
    Posts
    3,573
    The set needs the items to be ordered so that it would be able to find items faster than in linear time. If they are in random order, how do you hope to get away without examining each item in turn to locate it? So, I guess the comparison operator must define some sort of real and consistent ordering.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  7. #7
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    If you want fast lookup but don't need them sorted, an unordered_set might be better than a vector or a set.

  8. #8
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391
    Sorry, it's only arbitrary in the sense that it doesn't effect my program one way or the other. It is definitely a valid comparison. Here's the operator for what I'm doing:
    Code:
    bool operator<( const Coord& lhs, const Coord& rhs ){
    
    
      return lhs.x_coord < rhs.x_coord ||
    
    	    ( lhs.x_coord == rhs.x_coord && lhs.y_coord < rhs.y_coord ) ||
    
    	    ( lhs.x_coord == rhs.x_coord && lhs.y_cooord == rhs.y_coord && lhs.height < rhs.height );
    
    }
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  9. #9
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by dudeomanodude View Post
    Sorry, it's only arbitrary in the sense that it doesn't effect my program one way or the other. It is definitely a valid comparison. Here's the operator for what I'm doing:
    That's a decent enough comparison. Lexical order is always a good fallback.

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    You could avoid the repeated comparison of lhs.x_coord == rhs.x_coord with a little boolean algebra
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #11
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by laserlight View Post
    You could avoid the repeated comparison of lhs.x_coord == rhs.x_coord with a little boolean algebra
    I like to let the compiler do my boolean algebra for me

    EDIT: Having said that, the way I usually write a lexical comparison is:

    Code:
    if(a1 < b1) return true;
    if(a1 > b1) return false;
    if(a2 < b2) return true;
    if(a2 > b2) return false;
    ... etc
    Of course this means you need a valid operator>() for the elements but if they are POD you definitely have that.

  12. #12
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391
    Code:
    bool operator<( const Coord& lhs, const Coord& rhs ){
    
      return lhs.x < rhs.x || ( lhs.x == rhs.x &&
                 ( lhs.y < rhs.y || ( lhs.y == rhs.y && lhs.height < rhs.height ) ) );
    }
    Ha! Actually it's sad it took me as long as it did to work the boolean algebra out. Thanks for keeping me sharp laserlight!
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. overload operator<
    By Unregistered in forum C++ Programming
    Replies: 3
    Last Post: 12-12-2001, 03:54 PM