key compare problem in stl map

N

NewToCPP

I am having problem with key compare in stl map. Below is part of my
code .. could anyone tell me what might be wrong here...

I am using VC++ 6.0

code:
=====
class MyKey
{

public:
unsigned long value;
unsigned long type
bool operator<(const MyKey& right)
{
return ( type< right.type) &&
( value < right.value );
}
};

class MapTest
{
public:
std::map<MyKey, MyClass* > myMap;

MapTest();
~MapTest();
void addElement(MyClass* pClass);
OmciCommonMe* findElement(MyKey key);
};




Error:
-------
c:\program files\microsoft visual studio\vc98\include\functional(86) :
error C2678: binary '<' : no operator defined which takes a left-hand
operand of type 'const class MyKey' (or there is no acceptable
conversion)
c:\program files\microsoft visual
studio\vc98\include\functional(86) : while compiling class-template
member function 'bool __thiscall std::less<class MyKey>::eek:perator
()(const class MyKey &,const class MyKey &) const'
 
J

Jim Langston

NewToCPP said:
I am having problem with key compare in stl map. Below is part of my
code .. could anyone tell me what might be wrong here...

I am using VC++ 6.0

code:
=====
class MyKey
{

public:
unsigned long value;
unsigned long type
bool operator<(const MyKey& right)
{
return ( type< right.type) &&
( value < right.value );
}
};

class MapTest
{
public:
std::map<MyKey, MyClass* > myMap;

MapTest();
~MapTest();
void addElement(MyClass* pClass);

Where is the code for addElement?
OmciCommonMe* findElement(MyKey key);

Where is the code for findElement?
Error:
-------
c:\program files\microsoft visual studio\vc98\include\functional(86) :
error C2678: binary '<' : no operator defined which takes a left-hand
operand of type 'const class MyKey' (or there is no acceptable
conversion)
c:\program files\microsoft visual
studio\vc98\include\functional(86) : while compiling class-template
member function 'bool __thiscall std::less<class MyKey>::eek:perator
()(const class MyKey &,const class MyKey &) const'

It would help if you showed us the acutal code that was cuasing the error.
 
J

JE

NewToCPP said:
I am having problem with key compare in stl map. Below is part of my
code .. could anyone tell me what might be wrong here...
bool operator<(const MyKey& right)
{
return ( type< right.type) &&
( value < right.value );
}
<snip>

1. You need _const_, better as a free-standing function than as a
member function:
bool operator<(const MyKey& lhs, const MyKey& rhs);

2. You _must_ have "strict weak ordering", or bad things will happen.

Best regards, JE
 
D

Daniel T.

NewToCPP said:
I am having problem with key compare in stl map. Below is part of my
code .. could anyone tell me what might be wrong here...

I am using VC++ 6.0

code:
=====
class MyKey
{

public:
unsigned long value;
unsigned long type
bool operator<(const MyKey& right)

that should be:
bool operator<( const MyKey& right ) const
{
return ( type< right.type) &&
( value < right.value );
}

//Better yet, make it a free function.

friend bool operator<( const MyKey& left, const MyKey& right ) {
return type < right.type && value < right.value;
}
 
S

Salt_Peter

NewToCPP said:
I am having problem with key compare in stl map. Below is part of my
code .. could anyone tell me what might be wrong here...

I am using VC++ 6.0

code:
=====
class MyKey
{

public:
unsigned long value;
unsigned long type
bool operator<(const MyKey& right)
{
return ( type< right.type) &&
( value < right.value );
}
};

class MapTest
{
public:
std::map<MyKey, MyClass* > myMap;

MapTest();
~MapTest();
void addElement(MyClass* pClass);
OmciCommonMe* findElement(MyKey key);
};




Error:
-------
c:\program files\microsoft visual studio\vc98\include\functional(86) :
error C2678: binary '<' : no operator defined which takes a left-hand
operand of type 'const class MyKey' (or there is no acceptable
conversion)

The solution is to provide either a const member op< or a global friend
op< as already mentioned
Since presumeably you'll want private data in a critical Key:

class MyKey
{
unsigned long type;
unsigned long value;
public:
MyKey(long t, long v) : type(t), value(v) { }
unsigned long getType() const { return type; }
unsigned long getValue() const { return value; }
friend bool operator<(const MyKey&, const MyKey&);
};

bool operator<(const MyKey& lhv, const MyKey& rhv)
{
// the following comparison will FAIL
eturn (lhv.type < rhv.type) && (lhv.value < rhv.value );
}

The above return says that left is less than right only if *both*
members are less. Not good.
Don't forget that you are using a map. If the op< fails to process the
key order, inserts will be dropped silently on duplicates. Which is
what would happen here.

The operator needs to
a) check whether the left type is less than the right type, if not...
OR
b) are they equal? if so... AND
c) then return whether the left value is less than the right value

translation:
bool operator<(const MyKey& lhv, const MyKey& rhv)
{
return ((lhv.type < rhv.type) || ((lhv.type == rhv.type) &&
(lhv.value < rhv.value )) );
}

and just for the hell of it, here is a test:

int main()
{
std::map<MyKey, std::string > m;
m.insert( std::make_pair(MyKey(0,0), "string_00") );
m.insert( std::make_pair(MyKey(1,2), "string_12") );
m.insert( std::make_pair(MyKey(2,2), "string_22") );
m.insert( std::make_pair(MyKey(1,1), "string_11") );
m.insert( std::make_pair(MyKey(2,1), "string_21") );
m.insert( std::make_pair(MyKey(3,3), "string_33") );

typedef std::map<MyKey, std::string >::iterator MIter;
for(MIter miter = m.begin(); miter != m.end(); ++miter)
{
std::cout << (*miter).first.getType() << "\t";
std::cout << (*miter).first.getValue() << "\t";
std::cout << (*miter).second << std::endl;
}
}

/*
0 0 string_00
1 1 string_11
1 2 string_12
2 1 string_21
2 2 string_22
3 3 string_33
*/
 
N

NewToCPP

Thanks to everyone for the replies.

I used friend function as suggested. It works. Why does it have problem
when I have the overloaded "operator<" in the class.



Below is the code that I used when I had the problem. IN the new code
I have operator< as friend. It works.


#include <map>

class MyKey
{


public:
unsigned long value;
unsigned long type;


MyKey(long t, long v) : type(t), value(v) { }

bool operator<(const MyKey& right)
{
return ( (type < right.type) || ((type == right.type) && (value <
right.value )) );
}

};


class MapTest
{
public:
std::map<MyKey, int> myMap;

typedef std::map<MyKey, int>::iterator MIter;
MapTest();
~MapTest();
void addElement(const MyKey&, int);
int findElement(const MyKey&);
void deleteElement(const MyKey&);


};



MapTest::MapTest()
{

}

MapTest::~MapTest()
{
}


void MapTest::addElement(const MyKey& key, int value)
{

myMap.insert(std::pair<MyKey, int>(key, value));
}

int MapTest::findElement(const MyKey& key)
{
MIter miter;

if ((miter = myMap.find(key)) != myMap.end())
return (*miter).second;

return -1;
}

void MapTest::deleteElement(const MyKey& key)
{
myMap.erase(key);
}

int main()
{

MapTest test;

test.addElement(MyKey(0,1), 10);

int mainVal = test.findElement(MyKey(0,1));
mainVal = test.findElement(MyKey(1,0));
mainVal = test.findElement(MyKey(1,1));
return 0;
}
 
P

Pete C

NewToCPP said:
Thanks to everyone for the replies.

I used friend function as suggested. It works. Why does it have problem
when I have the overloaded "operator<" in the class.

There would have been no problem if you had written it as a const
member function in the class:

bool operator<(const MyKey& right) const
{ // etc

but by declaring it as non-const, you are saying that the act of
comparing one MyKey object to another can potentially change the value
of the key itself! The STL map needs its key values to remain constant.
For comparison, try changing your friend comparison function to:
bool operator<(MyKey& lhs, const MyKey& rhs);
(notice how lhs is no longer const). This is equivalent to what you
were trying to do with the non-const member function, and you should
get the same error message as before.
 
S

Salt_Peter

NewToCPP said:
Thanks to everyone for the replies.

I used friend function as suggested. It works. Why does it have problem
when I have the overloaded "operator<" in the class.



Below is the code that I used when I had the problem. IN the new code
I have operator< as friend. It works.


#include <map>

class MyKey
{


public:
unsigned long value;
unsigned long type;


MyKey(long t, long v) : type(t), value(v) { }

bool operator<(const MyKey& right)

It is absolutely essential that you understand the difference between:
bool operator<(const MyKey& right) { ... }
.... and ...
bool operator<(const MyKey& right) const { ... }

The const specifier is the most important keyword in that line. It
prevents the 'this' parameter from being passed to the operator<
function. The implementation of std::map will not call an operator<
that *might* modify the very Keys it uses to order during a comparison.
It'll look for an operator< where all parameters are constant.
This is not about code or semantics - its about a fundamental logic.
Imagine what would happen if a user of the std::map class was allowed
,even by accident, to modify the Key or both Keys during a comparison.
Lets face it: what exactly is the purpose of operator< ?

I have a quiz for you:

#include <iostream>
#include <ostream>

class N
{
int n;
public:
N(int x) : n(x) { }
int& getn() { return n; }
};

int main()
{
N instance(99);
std::cout << "instance.getn() = ";
std::cout << instance.getn() << std::endl;

instance.getn() = -1; // what the hell?
std::cout << "instance.getn() = ";
std::cout << instance.getn() << std::endl;
}

/*
instance.getn() = 99
instance.getn() = -1 // this should not be allowed
*/

How can i prevent a user of class N above to write the nasty
side-effect that allows a getter to set a private variable like that?
 
S

Salt_Peter

NewToCPP said:
by making:

const int& getn() { return n; }

wrong answer: i can *still* modify the private integer

const int* p_n = &instance.getn();
int* pp = const_cast<int*>(p_n);
*pp = -1; // still screwed

And if you think the above is just a bug, its not - its serious stuff.
Its called a side-effect in C++.

correct answer:

class N
{
int n;
public:
N(int x) : n(x) { }
int& getn() const { return n; } // const function
};

The difference between getn() and getn() const is that the constant
function has _no_way_ to access the object (in this case - instance).
The original non-constant function has one hidden parameter, the 'this'
parameter, const functions don't get the 'this' parameter. A const
function therefore is incapable of modifying the object its a member
of, it can only read it. That is guarenteed.

I'm not even allowed to do the following if getn() is const:
const int& r_n = instance.getn(); // error - invalid initialization of
reference

This is important because thats how a programmer builds safety into his
design. Which is exactly what those who wrote std::map did.
Now go back and read the comments about the member operator< that must
be constant.
 
?

=?ISO-8859-15?Q?Juli=E1n?= Albo

Salt_Peter said:
class N
{
int n;
public:
N(int x) : n(x) { }
int& getn() const { return n; } // const function
};

The difference between getn() and getn() const is that the constant
function has _no_way_ to access the object (in this case - instance).
The original non-constant function has one hidden parameter, the 'this'
parameter, const functions don't get the 'this' parameter. A const

A const function has a this. The difference is that in a non const function
this is a pointer to an instance of the class, and in a const function is a
pointer to a const instance of the class.
I'm not even allowed to do the following if getn() is const:
const int& r_n = instance.getn(); // error - invalid initialization of
reference

This error is in the getn function, not in his usage: you are trying to
initialize an int & (the return value) from a const int (the n in the const
instance pointed by 'this').

And if you change getn to return a const int & instead of int &, you are
again exposed to manipulation via const_cast. C++ language protections in
general protect against mistakes, not against deliberate misuse.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,902
Latest member
Elena68X5

Latest Threads

Top