How to find by a const pointer key in a map with non-const pointer keys

Question

The following C++ code does not compile because it's passing a non-const pointer to a find() function which expects a const pointer.

#include <map>

std::map<int*, double> mymap;

double myfind(const int * mykey)
{
    return mymap.find(mykey)->second;
}

Is there a way how to make the finding work without changing the type of the map or making variable mykey non-const? After all the function find() does not modify the pointed object, it just compares the pointers.

Serajevo

Use const_cast – Skin

@t.niese Why would you change that? How would it solve the underlying problem? – Calandracalandria

After many years, the flaws of the STL interfaces are still there; esp. the typing of associative containers, the lack of binary search... – Calandracalandria

Why not changing the key type instead? – Vermicelli

@Calandracalandria not with C++14's transparent comparators. It's the difference between std::less<int *> and std::less<const int *> – Kipkipling

@Kipkipling You pointed me in the right direction by mentioning transparent comparators. – Serajevo

Answer 1

I think I have found a solution, but it requires C++14 transparent comparators.

#include <map>
#include <iostream>

struct CompareIntPtrs
{
    using is_transparent = void; // enabling C++14 transparent comparators

    bool operator()(const int * l, const int * r) const
    {
        return l < r;
    }
};

std::map<int*, double, CompareIntPtrs> mymap;

double myfind(const int * key)
{
    return mymap.find(key)->second;
}

int main()
{
    int x {6};
    mymap[&x] = 66; // inserting to the map
    const int * px = &x; // creating a "const int *" variable

    std::cout << myfind(px) << std::endl; // using "const int *" for finding in map with "int*" keys
    std::cout << mymap.find(px)->second << std::endl; // we could even skip using myfind()
}

An excellent article about C++14 transparent comparators can be found here. To be completely honest, by adding the comparator, the type of mymap slightly changed which I originally didn't want to, but it's the best solution I could find.

If C++14 is not available, there are at least two evils we can choose from. The first one is to copy mymap to a new std::map<const int*, double> in myfind, which is horribly unefficient. The second one is casting away constness by using a const_cast<int*>(mykey) which should be avoided if possible.

Serajevo

Answer 2

A key in a map is semantically immutable, all map operations that allow direct access to keys do that by const-qualifying the key type (e.g. value_type is defined as pair<const Key, T>).

In case of int* key type however you'd get a const pointer to non-const int (int*const), which isn't very nice (it still works, since only the pointer value is used as the key, but the semantics of immutability become diluted, which can lead to bugs).

Instead of casting away constness, just change the map to map<const int*, double>.

Then it will work for const int* as well as int* keys.

#include <map>

std::map<const int*, double> mymap;

double myfind(const int * mykey)
{
    return mymap.find(mykey)->second; // just works
}

double myfind(int * mykey)
{
    return mymap.find(mykey)->second; // also works
}

Quennie

The semantic value of the key cannot be changed in arbitrary ways in an associative container because the container uses the comparison (resp. the hash) to order the objects (resp. store them in an array). But the semantic value of the key here is the pointer value. You can change the int without breaking the container. – Calandracalandria

Answer 3

Try const_cast which allows you to change constness (or volatility) of variable.

#include <map>

std::map<int*, double> mymap;

double myfind(const int * mykey)
{
    return mymap.find(const_cast<int*>(mykey))->second;
}

Skin

Yes but const_cast is usually a sign of a bad interface – Calandracalandria

I don't recommend any cast, but it is one of possibility ;) – Skin

Answer 4

You may have a const-correctness issue. const int * may not be what you think it is. It is a pointer to a constant integer. This is not the same as the key type of your map, which is a pointer to a (non-constant) integer. And neither are the same as int * const which is a constant pointer to a (non-constant) integer. The issue isn't whether the key value itself is mutable or immutable, it's whether the things you're storing pointers to are mutable or immutable.

For example, this compiles:

std::map<int *, double> mymap;
double myfind(int * const mykey) {
    return mymap.find(mykey)->second;
}

As does this:

std::map<const int *, double> mymap;
double myfind(const int *mykey) {
    return mymap.find(mykey)->second;
}
double myfind2(const int * const mykey) {
    return mymap.find(mykey)->second;
}

Do you see the difference? In your original code, the compiler is quite right to flag an error. If your function takes a const int *, then you are in effect promising not to modify the int pointed to by the pointer I pass in. But if you use such a pointer as int * in the key of a std::map, you may be allowing someone to modify that int.

In this particular case, we know that std::map::find() will not assign to a pointer argument, but the compiler doesn't, which is why const_cast<> exists as pointed out in other answers.

Nature

I understand the difference between const int * and int * const. But you made a good point in the last paragraph. We know that std::map::find() will not modify the pointed integer, but the compiler does not know it. And in this question I asked how to let the compiler know it. – Serajevo

@Serajevo and the answer to that is also in the last paragraph: const_cast<> – Nature

Yes, const_cast<> is one multiple possibilities. But casting away const is not a good practice. A custom comparator (if available) can do the same thing without violating recommendations. – Serajevo

Completely agree it's not a good practice, but I think unless you change the key type of the map, that is in the end what you're doing, regardless of which hoops you jump through to get there. The heart of my answer, which I think is important and valid for readers, is that const int * is a semantically different thing from int *. To that I don't really have anything to add or contribute; I regret that this did not appeal to the downvoter. – Nature