std::map, find function does not accept const Key* even though docs and error message seems to say it does

[JockeP77]

When using std::map, find function does not accept const Key* even though docs and error message seems to say it does. Why is this so? Or can you find something wrong with my code below? (Running on Linux)

typedef std::map<MyKey*, MyValue, MyCompare, std::allocator<std::pair<MyKey* const, MyValue> >> MyMap;

void somefunc(const MyKey* myKey) {
  MyMap::iterator myMapIt = mMyMap.find(myKey);
}

//>>>>>>>>> Error messages from the compiler
no matching function for call to 'std::map<MyKey*, MyValue, MyCompare, std::allocator<std::pair<MyKey* const, MyValue> > >::find(const MyKey*&)'

candidates are: typename std::_Rb_tree<_Key, std::pair<const _Key, _Tp>, std::_Select1st<std::pair<const _Key, _Tp> >, _Compare, typename _Alloc::rebind<std::pair<const _Key, _Tp> >::other>::iterator std::map<_Key, _Tp, _Compare, _Alloc>::find(const _Key&) [with _Key = MyKey*, _Tp = MyValue, _Compare = MyCompare, _Alloc = std::allocator<std::pair<MyKey* const, MyValue> >] <near match>

// >>>>>>>>>>> To me they seem VERY equal
std::map<MyKey*, MyValue, MyCompare, std::allocator<std::pair<MyKey* const, MyValue> >>::find(const MyKey*&)
std::map<MyKey*, MyValue, MyCompare, std::allocator<std::pair<MyKey* const, MyValue> >>::find(const MyKey*&) <near match>

[kbw]

A map is defined to by Key/Value pairs. You'll find nothing in the definition that does Key*.
http://www.sgi.com/tech/stl/Map.html

[JockeP77]

Thanks for your reply, however, I have no idea what you mean. You have to explain more.
It works perfectly fine to have a Key that is a pointer.

I noticed that if I write

void somefunc(MyKey* const myKey) {
  MyMap::iterator myMapIt = mMyMap.find(myKey);
}

the code compiles just fine. However, this only promises the user of somefunc that the somefunc code will not change the pointer value itself - it doesn't say anything about changing the actual values that the pointer points to. I feel this is wrong. But perhaps what you really mean, kbw, is that std::map was not designed for use with pointers as keys, even if you can use it like that if you want to.

[kbw]

You don't use it like that. Think of the iterator as the pointer.

void somefunc(const MyKey &myKey)
{
    MyKey::iterator myMapIt = mMyMap.find(myKey);
}

[JockeP77]

How do you mean? In my case MyKey does not support iterators.

[Galik]

I think what might be going on is that std::map::find() takes a const reference. If you pass it a MyKey* then it is receiving a const reference to a MyKey*. That is not the same as a const MyKey*. The type (MyKey*) is not itself const, only the reference to it in the find() function.

EDIT: See if this works:

struct MyKey
{

};

std::map<MyKey*, std::string> myMap1;

void somefunc1(MyKey* const& myKey)
{
	std::map<MyKey*, std::string>::iterator myMapIt = myMap1.find(myKey);
}

std::map<MyKey const*, std::string> myMap2;

void somefunc2(MyKey const* const& myKey)
{
	std::map<MyKey const*, std::string>::iterator myMapIt = myMap2.find(myKey);
}

[kbw]

How do you mean? In my case MyKey does not support iterators.

MyKey isn't the problem. You've passed the wrong type to find().

[JockeP77]

Galik,

thanks for the clarification. However, then I think the compiler error message is a bit misleading, or actually wrong

candidates are: typename std::_Rb_tree<_Key, std::pair<const _Key, _Tp>, std::_Select1st<std::pair<const _Key, _Tp> >, _Compare, typename _Alloc::rebind<std::pair<const _Key, _Tp> >::other>::iterator std::map<_Key, _Tp, _Compare, _Alloc>::find(const _Key&) [with _Key = MyKey*, _Tp = MyValue, _Compare = MyCompare, _Alloc = std::allocator<std::pair<MyKey* const, MyValue> >] <near match>

The "::find(const _Key&)" part, having "_Key = MyKey*" does translate to

::find(const MyKey*&)

and not

::find(MyKey* const&)

Otherwise I think the error should have read

::find(_Key const&)

Don't you agree?

[Galik]

Well... this is how I think it works (I admit I get confused over this too).

The problem is how C resolves the type. Even though logically inserting MyKey* between the const and the & looks like it has become the subject of a const& it doesn't quite work that way.

What happens is that the const latches on to the * changing the semantics. If you went through a typedef you could avoid that:

typedef MyKey* MyKeyPtr;

find(const MyKeyPtr& myKey); // works fine 

But without the typedef, the introduction of the * symbol causes the const to apply to it rather than the &.

The way to spell out to the compiler that you want the const to remain on the & rather than the * is:

find(MyKey* const& myKey); // works fine 

The thing to remember is that it doesn't matter which side of the identifier the const goes but it does matter which side of the * or & it goes.

So to make the pointer or reference const you can do:

const MyKey* mp1; // these two...

MyKey const* mp2; // ...are the same 

Same thing with reference:

const MyKey& mr1; // these two...

MyKey const& mr2; // ...are the same 

But when you want a reference to a pointer:

MyKey*& mpr;

Choosing which one is const is more tricky. Making the pointer const is easy because it is closest to the identifier:

const MyKey*& mpr1; // these two...

MyKey const*& mpr2; // ...are the same 

But making the reference const is harder because you only have one option available to you:

MyKey* const& mpr;

Its all down to order of precedence which is designed to allow the programmer to express all possible combinations of constness.

(hopefully I didn't make any errors in that explanation)

[kbw]

However, then I think the compiler error message is a bit misleading

C++ compiler errros that involve STL have almost always been misleading. As I understand it, it's a work in progress.