std::less

Ohh..Ok I got it. If use std::less, the order may be messed up but still search and insert will be O(log(N).
Which means if I traverse the map, they won't be ordered. Correct?

if I need to order by id first and the vers, then I need something like

struct key{
	uint32 id;
	uint32 ver;
public:
        bool operator < (const key& in_key) {
             return (id < in_key.id || (id == in_key.id && ver < in_key.ver) )
                  
        }
} ;
typedef struct key key;
std::map<key, uint32, CompareStruct > g_map;

Select allOpen in new window

So basically whether I use my own custom "<" or std::less complexity will always be O(log(N).
Its just that with std::less when I traverse, elements wont be ordered. Correct?

I see. Thanks a lot.

So if I don't care about traversing, I can go with std::less
If I do care about the specific order while traversing, I have to define my own '<'

Either way the complexity will always be O(log(N).

Got it. Thanks a ton jkr

I just tried this and my compiler also complains the insert

struct MyStruct{
        uint32_t node_id;
        uint32_t vers;

        MyStruct(uint32_t id, uint32_t ver) : node_id(id), vers(ver) {}
} ;
typedef struct MyStruct MyStruct;
typedef std::map<MyStruct, uint32_t, std::less<MyStruct> > MyMap_map ;

 MyMap_map t;
MyStruct key (5, 10);
t.insert(std::make_pair(key, 100));  // Compilers fails here.....

Select allOpen in new window

It seems modern compilers are forcing to define operator '<'.  However I see in my application code that in some files, they are using std::less<on structure>.  I don't know how on earth the make is working. is there a magical option we can pass to g++ that prevents this check?

If a compiler were to accept Sara's code, then it would be out of line with the C++ standard since operator < is not defined on your struct. In this case, "modern compiler" should mean at a minimum, any compiler that complies with the C++ 2003 specification.

For your question, "do I have to define my own '<' operator", the answer is yes, you must define the operator '<' if you need such a comparison (as you do if using map).

It seems modern compilers are forcing to define operator '<'

that is not true. I remember the requirement to exist already in std::map of vc6 compiler which was released a little time before c++ standard in 1998. the problem is that std::map uses a binary tree internally which cannot work without a compare function. and std::less always is implemented by using the operator< what would fail for class types if they do not provide it.

note, equality was checked by !(a < b) && !(b < a). that means, the operator== was neither needed nor used by std::map.

Sara

A C++ struct or a class only gets four default operations for free, and '<' is not one of them.

The OP question is "do I have to define my own '<' operator".
http:#a40116764 says: "the < operation can not be deduced by the compiler for neither case. you definitively should add an operator< as by your above code."
I agree with that answer.

Is this a valid std::less I can use on map or do I have to define my own '<' operator

the OP question had two parts where the answer to the second part is "yes" while the answer to the first part is that the std::less<key> is valid for to define a std::map but invalid for use with nearly all operations on the map. this is due to the fact that member functions of a template class only will be compiled when used. solely the instantiation of an empty  std::map would not cause the compiler to compile a function which needs the less operator. you can verify that by defining a std::map with initialization like

struct uip { int x, y; }
uip u= { 0, 0 };
std::map<uip, int> um(u, 9999);  // compiler error

Select allOpen in new window

the last statement doesn't compile because the compiler cannot find a less operator for the key.

note, it doesn't matter whether std::less<type>  explicitly was given as 3rd argument or whether the compiler uses std::less<type> as a default argument.

However I see in my application code that in some files, they are using std::less<on structure>.  I don't know how on earth the make is working. is there a magical option we can pass to g++ that prevents this check?

as explained by phoffric a compiler which accepts a key without explicit or implicit operator< defined is not compliant to c++ standard. even for a structure which has one single (data) member my compiler (vs2010) was not able to deduce a std::less function. if you have seen a structure being used as key without operator< defined, they may have provided a global operator< with two arguments what is equivalent.

bool operator<(const uic & u1, const uic & u2) { return (u1.x < u2.x || (u1.x == u2.x && u1.y < u2.y)); }

Select allOpen in new window

Please make your recommendations as to how this request should be closed

perlperl accepted http:#a40116013 (jkr) as solution what should be respected in my opinion.  however, http:#a40116764 answered the original question. because of that jkr's answer should get the points but my answer should be the accepted solution.

Sara

I will look into this

@sara,
OP: >> Is this a valid std::less I can use on map or do I have to define my own '<' operator.?

I can see how you might take this a two questions. I had taken it as a single question given the OP code post which I thought limited the question to map usage:
>> std::map<key, uint32, std::less<key> > g_map;

As you said, "but invalid for use with nearly all operations on the map". For all practical purposes, a '<' operator must be defined  for the struct key since otherwise, how could you insert an entry into the map? And what good is an empty map?

@phoffric:
yes, I fully agree to you.

the only reason why I pointed to the two parts of the op question was that I had the impression, the author made the conclusion the argument std::less<key> was accepted by the compiler as valid operator as there was no error when defining the map.

And what good is an empty map?

indeed an empty map is of little value, but you could use it to define a map as class member in a header file.

the operator< then could be added in the cpp file.

Sara

@Sara,
Good that you clarified it then to avoid any misconceptions.

eenookami, it isn't my question but perlperl promised "to look into this" in http:#a40154739 .

Sara

Sorry for the late response. Was busy with some deadlines.

SO there are many comments that helps me understanding the overall picture. I am not sure at this point what all should I select.

Admins, can you please pick the right answer accordingly.

I have understand the fact that it is always good to write your own '<' operator for struct or class or any other non-standard data types.

>> it is always good to write your own '<' operator for struct or class or any other non-standard data types.
I think it is better to never define your own '<' operator for struct, unless needed to deal with compiler errors that one is missing.

I think it is better to never define your own '<' operator for struct, unless needed to deal with compiler errors that one is missing.

hmmm. that is probably a too technical sight to the problem. in c++ a struct is same as a class beside that members default to be public. hence instances of a struct are class objects and you should provide all operators which were necessary to make the new type complete for the designed purpose. a structure which should serve as a key in a map, definitively needs an operator< defined. a map obviously should help to find the entries by key and some kind of default less operator (which is not provided by the compiler as we learned) rarely could help with this.

Sara

I feel unfair to pick just one answer :) but I'll go by the Admin request.

Thanks a ton everyone for pitching in.