std::set and struct - can they work together?
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 2 12 LastLast
Results 1 to 15 of 17

Thread: std::set and struct - can they work together?

  1. #1
    John E is offline Elite Member Power Poster
    Join Date
    Apr 2001
    Location
    Manchester, England
    Posts
    4,235

    std::set and struct - can they work together?

    This works...
    Code:
    std::set<int> IntSet;
    
    int hello = 6;
    IntSet.insert (hello);
    but this doesn't work...
    Code:
    typedef struct {
              void *p;
              unsigned int n;
            } my_struct;
    
    std::set<my_struct> StructSet;
    
    my_struct goodbye;
    goodbye.p = whatever();
    goodbye.n = 1;
    
    StructSet.insert (goodbye);
    If I try to use structs in a std::set I get this error from MSVC:-

    C:\Program Files\Microsoft Visual Studio 8\VC\include\functional(143) : error C2784: 'bool std:: operator <(const std::_Tree<_Traits> &,const std::_Tree<_Traits> &)' : could not deduce template argument for 'const std::_Tree<_Traits> &' from 'const my_struct'

    C:\Program Files\Microsoft Visual Studio 8\VC\include\xtree(1372) : see declaration of 'std:: operator <'

    C:\Program Files\Microsoft Visual Studio 8\VC\include\functional(142) : while compiling class template member function 'bool std::less<_Ty>:: operator ()(const _Ty &,const _Ty &) const'

    with

    [

    _Ty=my_struct

    ]
    std::set is using std:: operator < to determine if the struct is already present in the set - but std:: operator < doesn't seem to work for a struct (presumably, it has no way of knowing how big the struct is). I need to keep std::set for compatibility with something else, so what's the best way to solve this problem? Can I tell std::set to use my own defined comparison operator, instead of std:: operator < ?
    Last edited by John E; July 9th, 2013 at 01:43 AM.
    "A problem well stated is a problem half solved. - Charles F. Kettering

  2. #2
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,250

    Re: std::set and struct - can they work together?

    You don't seem to have overloaded operator< for your struct type in the first place, but yes, you can indeed use another comparator besides operator< if you desire as the second template parameter (and the corresponding constructor parameter) is intended for this. That said, I suspect that you only need to overload operator< to get what you want.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  3. #3
    John E is offline Elite Member Power Poster
    Join Date
    Apr 2001
    Location
    Manchester, England
    Posts
    4,235

    Re: std::set and struct - can they work together?

    Doh! I was thinking that I'd somehow need to change the operator for std::set, rather than defining a new one for my struct type.

    Too early in the morning here....

    Thanks
    "A problem well stated is a problem half solved. - Charles F. Kettering

  4. #4
    Join Date
    Oct 2008
    Posts
    1,089

    Re: std::set and struct - can they work together?

    BTW, if you don't need the set items to be sorted, you can use an unordered_set instead ( either tr1 or c++11 ) to get better overall performance or if you find difficult defining an operator< ( note that this must satisfy the strict weak ordering requirements or you'll get UB otherwise ). Of course, you'll need to define your own hash function though.

  5. #5
    John E is offline Elite Member Power Poster
    Join Date
    Apr 2001
    Location
    Manchester, England
    Posts
    4,235

    Re: std::set and struct - can they work together?

    Thanks Superbonzo. I ended up defining four comparison operators, like so (bear in mind that my actual struct name is pthread_t)

    The struct's 'p' member is the only one that's guaranteed to change for every instance.

    Code:
    bool operator>  (const pthread_t& lhs, const pthread_t& rhs)
    {
    	return ((memcmp(lhs.p, rhs.p, sizeof(void*)) > 0) ? true : false);
    }
    
    bool operator<  (const pthread_t& lhs, const pthread_t& rhs)
    {
    	return ((memcmp(lhs.p, rhs.p, sizeof(void*)) < 0) ? true : false);
    }
    
    bool operator== (const pthread_t& lhs, const pthread_t& rhs)
    {
    	return ((memcmp(lhs.p, rhs.p, sizeof(void*)) == 0) ? true : false);
    }
    
    bool operator!= (const pthread_t& lhs, const pthread_t& rhs)
    {
    	return ((memcmp(lhs.p, rhs.p, sizeof(void*)) == 0) ? false : true);
    }
    Everything seems to compile okay although I haven't had a chance to test them yet.
    "A problem well stated is a problem half solved. - Charles F. Kettering

  6. #6
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,250

    Re: std::set and struct - can they work together?

    Personally, I would dispense with the ternary operator as I think that it would suffice to write:
    Code:
    bool operator<  (const pthread_t& lhs, const pthread_t& rhs)
    {
    	return memcmp(lhs.p, rhs.p, sizeof(void*)) < 0;
    }
    This operator< should be declared in the same namespace as pthread_t though.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  7. #7
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,272

    Re: std::set and struct - can they work together?

    As your struct my_struct contains a member p which is a pointer, be careful if you haven't defined default constructor, copy constructor, destructor and operator= for my_struct.

    For your comparison functions, as p is a pointer are you sure that you want to compare memory addresses?
    Last edited by 2kaud; July 9th, 2013 at 05:09 AM.
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  8. #8
    John E is offline Elite Member Power Poster
    Join Date
    Apr 2001
    Location
    Manchester, England
    Posts
    4,235

    Re: std::set and struct - can they work together?

    Quote Originally Posted by laserlight View Post
    Personally, I would dispense with the ternary operator as I think that it would suffice to write:
    Code:
    bool operator<  (const pthread_t& lhs, const pthread_t& rhs)
    {
    	return memcmp(lhs.p, rhs.p, sizeof(void*)) < 0;
    }
    I assumed the compiler would optimize it away but you're right, the simplified code is just as easy to read.


    Quote Originally Posted by 2kaud View Post
    For your comparison functions, as p is a pointer are you sure that you want to compare memory addresses?
    In this case I think it'll be okay. The actual aim is only to decide if two instances are in fact the same object or different objects. There's no real sense in which one instance can either be greater or less than the other instance.
    "A problem well stated is a problem half solved. - Charles F. Kettering

  9. #9
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Posts
    12,057

    Re: std::set and struct - can they work together?

    Quote Originally Posted by 2kaud View Post
    For your comparison functions, as p is a pointer are you sure that you want to compare memory addresses?
    I was going to post the same thing. That doesn't make any logical sense.

  10. #10
    John E is offline Elite Member Power Poster
    Join Date
    Apr 2001
    Location
    Manchester, England
    Posts
    4,235

    Re: std::set and struct - can they work together?

    Think of the void* as being a handle. I only need to know if the handles are the same or different. There's no literal sense in which one handle can be greater than the other.
    "A problem well stated is a problem half solved. - Charles F. Kettering

  11. #11
    Join Date
    Oct 2008
    Posts
    1,089

    Re: std::set and struct - can they work together?

    AFAIK, using "memcmp(lhs.p, rhs.p, sizeof(void*)) < 0" is not much more portable than just "lhs.p < rhs.p", and both are not portable as they are not guaranteed to give a total ordering suitable for associative containers ( and I have no idea if this will work for VC++ ). You can use std::less instead, which is guaranteed to work for pointer types:

    Code:
    bool operator<  (const pthread_t& lhs, const pthread_t& rhs)
    {
    	return std::less<void*>()(lhs.p, rhs.p);
    }
    BTW, assuming that those void* uniquely identify the corresponding pthread_t instance, here is the unordered_set solution ( giving you O(1) access times for free ):

    Code:
    // ...
    
    bool operator== (const pthread_t& lhs, const pthread_t& rhs)
    {
        return lhs.p == rhs.p;
    }
    
    namespace std{
    
    template<>
    struct hash<pthread_t>
    {
    	size_t operator()( const pthread_t& v ) const
    	{
    		return hash<void*>()( v.p );
    	}
    };
    
    }
    
    std::unordered_set<pthread_t> some_set;

  12. #12
    Join Date
    Apr 1999
    Posts
    27,423

    Re: std::set and struct - can they work together?

    Quote Originally Posted by John E View Post
    Think of the void* as being a handle. I only need to know if the handles are the same or different. There's no literal sense in which one handle can be greater than the other.
    Then you shouldn't be using ambiguous or vague values to determine where a container will place data.

    The bottom line is this -- unless you can state what element comes before another element in an unambiguous manner (either through operator < or supplying the second template argument to std::set), then you shouldn't use containers that rely on and only work properly with values that adhere to the strict-weak-order principle.

    Also, one tip: If you are to define each of those comparison operators, the only two you need to fully write are the < and == operators:
    Code:
    bool operator <  (const pthread_t& lhs, const pthread_t& rhs)
    {
       return memcmp(lhs.p, rhs.p, sizeof(void*)) < 0;
    }
    
    bool operator == (const pthread_t& lhs, const pthread_t& rhs)
    {
        return memcmp(lhs.p, rhs.p, sizeof(void*)) == 0);
    }
    
    bool operator != (const pthread_t& lhs, const pthread_t& rhs)
    {
        return !(lhs == rhs);
    }
    
    bool operator > (const pthread_t& lhs, const pthread_t& rhs)
    {
       return (rhs < lhs) && (rhs != lhs);
    }
    Note that != and operator > are defined in terms of the other fully implemented operators. You can then create operator <= and operator >= very easily.

    One source of many mistakes when it comes to this are programmers trying to "reverse the polarity" of an already defined operator by recoding the function and figuring out where the not's, and's, and or's go.

    For example, your operator != function -- take what has been coded for operator ==, call the == function, and stick a "!" in front of the return. Bingo, you have your operator !=. This ensures that the operation makes logical sense, and it removes the possibility of bugs, especially if the operator == is complicated.

    Regards,

    Paul McKenzie
    Last edited by Paul McKenzie; July 9th, 2013 at 11:28 AM.

  13. #13
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,250

    Re: std::set and struct - can they work together?

    Quote Originally Posted by Paul McKenzie
    Also, one tip: If you are to define each of those comparison operators, the only two you need to fully write are the < and == operators
    Strictly speaking, operator== can be implemented in terms of operator< so that is not absolutely true, but if you intend to make use of the convenience provided using namespace std::rel_ops; then that is true.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  14. #14
    Join Date
    Apr 1999
    Posts
    27,423

    Re: std::set and struct - can they work together?

    Quote Originally Posted by laserlight View Post
    Strictly speaking, operator== can be implemented in terms of operator< so that is not absolutely true, but if you intend to make use of the convenience provided using namespace std::rel_ops; then that is true.
    Yes, I was thinking of what rel_ops requires. But a few STL algorithms require operator ==, so I'm used to always defining strictly < and ==, and if needed, derive the others given these two operators.

    Regards,

    Paul McKenzie

  15. #15
    John E is offline Elite Member Power Poster
    Join Date
    Apr 2001
    Location
    Manchester, England
    Posts
    4,235

    Re: std::set and struct - can they work together?

    Thanks for all the suggestions guys. It was well worth my original post!

    The decision to use an ordered set in this case wasn't mine but I'll pass on the suggestion to make it an unordered set instead. I don't think there's any particular benefit to having the entries ordered.
    "A problem well stated is a problem half solved. - Charles F. Kettering

Page 1 of 2 12 LastLast

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center