4

I have a complex struct i want to put as a key of the std::map to make a list of all unique objects fast:

union somecomplexstruct { struct { more_structs val1, val2; even_more_structs val3, val4; lots_of_more_structs val5; }; unsigned int DATA[3]; }; typedef map<somecomplexstruct, int, greater<somecomplexstruct> > somecomplexstructMap;

But it says error: error C2784: 'bool std::operator >(const std::vector<_Ty,_Alloc> &,const std::vector<_Ty,_Alloc> &)' : could not deduce template argument for 'const std::vector<_Ty,_Alloc> &' from 'const somecomplexstruct'

How do i make my struct work there?

Edit: Got it working, thanks to everyone! Heres the code:

inline bool operator>(const somecomplexstruct &v1, const somecomplexstruct &v2){ if(v1.DATA[0] > v2.DATA[0]) return 1; if(v1.DATA[0] < v2.DATA[0]) return 0; if(v1.DATA[1] > v2.DATA[1]) return 1; if(v1.DATA[1] < v2.DATA[1]) return 0; return v1.DATA[2] > v2.DATA[2]; }
Improve this question
4
  • 3
    That definition of operator> is not good. If v1.DATA = {1,0,0}; v2.DATA = {0,1,0};, it claims that both v1>v2 and v2>v1. Commented Oct 29, 2010 at 17:53
  • Note that, while I have yet a platform where this doesn't work in practice, writing one value to a union and then accessing it as another value technically leads to undefined behavior. Commented Oct 30, 2010 at 12:44
  • what do you mean, my code is flawed? how i fix it? Commented Oct 30, 2010 at 15:36
  • do you mean about that i should use #pragma pack(1) to ensure the structs wont get padded? Commented Nov 7, 2010 at 13:54

4 Answers 4

Reset to default
9

std::greater<> invokes operator>() to do its work, so you need to overload that if you want to use std::greater<>.

It should look like this: 

inline bool operator>(const somecomplexstruct& lhs, const somecomplexstruct& rhs) { // implement your ordering here. }
Improve this answer
Sign up to request clarification or add additional context in comments.

17 Comments

Hmm, i cant quite get the logic in that function, when i need to only create unique objects list, should i change my map somehow, because this operator > doesnt make much sense. Or does it even matter what i put inside that function, because its only used for sorting, but not for testing if the object is equal to some other object in the list already? So if i want, i could as well just return 1 in that function always? OR does this affect performance or something? I am having hard time creating the test to see if the data is greater than other data.or should i even care if its "perfect"or not?
@Newbie: std::map uses the ordering in order to efficiently determine whether it has a given key in the map. It's normally implemented as a balanced binary search tree. If you can't provide an order, then you could instead provide a hash function and use the non-standard boost::unordered_map, or hash_map if your C++ implementation offers it. If you can't provide either an order or a hash function, then you can't efficiently test for duplicates, and you might as well just use a vector<pair<Key, Value> > and search it linearly.
@Newbie: the most common way to produce an order is a so-called "lexicographic order". So if struct X contains a Y and a Z, then X's order function is something like if (lhs.y < rhs.y) return true; if rhs.y < lhs.y) return false; return (lhs.z < rhs.z);. You can extend this for things with multiple members, and you'll have to define an ordering similarly for any structs contained in the one you care about.
Most probably you've written a wrong comparator. Search or post a separate question on how to write a comparator for your key structure.
By the way, { return &v1 > &v2; } is NOT a good comparator. The map can and will make copies of its inserted arguments, and those copies won't compare the same way as the original if their addresses are used, causing undefined behavior.
|
3

With your operator> function, consider what happens if you compare {1, 0, 0} and {0, 1, 0}. If you compare a > b, it returns true from the first comparison. If you compare b > a it returns true from the second comparison. So its fails the reflexive property for comparisons, scrambling the map. In order for map to work properly, you must define your operator> such that a > b == !(b > a) for all possible non-equal pairs of values that might be compared.

edit

The easiest/best way to ensure that your operator is properly reflexive is to ensure the for every test that might return true, you also have a test with the same condition and the operands swapped that returns false. So if you have

if(v1.DATA[1] > v2.DATA[1]) return 1;

in your function, you need

if(v2.DATA[1] > v1.DATA[1]) return 0;

or the equivalent somewhere.

Improve this answer

Comments

2

Here is lexicographical comparator for a complex structure

struct D { struct A { bool operator <(const A &) const; } a; struct B { bool operator <(const B &) const; } b; struct C { bool operator <(const C &) const; } c; template <class T> ne(const T & a, const T & b) { if (a < b) return true; if (b < a) return true; return false; } bool operator < (const D & that) const { if (ne(a, that.a)) return a < that.a; if (ne(b, that.b)) return b < that.b; return c < that.c; } };
Improve this answer

3 Comments

Thanks. I'll fix consts, and leave members for the sake of shorter declarations.
I get this error: error C2678: binary '!=' : no operator found which takes a left-hand operand of type 'const D::A' (or there is no acceptable conversion) from that struct
Sorry for that, I applied a quick fix, to prevent this error.
0

If your map contains only pointers to your struct, you don't have to do all that complicated operator overloading.

Therefore your typedef looks like this:

typedef map<somecomplexstruct*, int, greater<somecomplexstruct*> > somecomplexstructMap;

Structs typically have only public data members and no need for operator overloading.

This means though that you have to be careful about when and how you release the memory for the pointers. There's pros and cons to each approach, as with everything.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.