Does a std::map where the key is a pointer dereference pointers, or do you need a custom comparator?

Question

I have a question on how pointers to a custom object are handled when used as Keys in an map. More specifically if I define

std::map< CustomClass*, int > foo;

Would the default C++ implementation work to handle these pointers? Or do I need to define a custom comparator function to handle it? In general, is it good practice to use pointers to objects as keys?

Recalcitrate

Anything that supports less<T> can be used in a map. See #1099466 – Transarctic

One possible downside to using pointers as keys in maps is that the order of the items is non-deterministic (depends on their memory address). If you need to iterate over the items in a deterministic order, you can't use pointers as keys. This can be important in multiplayer games. – Alegre

Answer 1

The default implementation will compare the addresses stored by the pointers, so different objects will be considered as different keys. However, the logical state of the object will not be considered. For example, if you use std::string * as the key, two different std::string objects with the same text of "Hello" would be considered a different key! (When stored in the map by their addresses)

It's ok to use pointers as keys so long as you understand the important difference above.

Cyndi

Yes thats a great point! The assumption is my case though are pointers to unique objects. – Recalcitrate

If comparing pointers is undefined/unspecified behaviour; how comes you can use pointers as keys for a map? – Apply

@Apply std::less is well defined for pointers and guaranteed to give a global total order while plain comparison operator < is not (the behavior is unspecified in C++) – Viscid

@WeijunZhou yes I had recently found that out. I think I am going to create a proper Cpp book/ tutorial that will teach beginners the right thing from day one. – Apply

Answer 2

Pointers will be handled but compared as pointers (memory order). You have to pass custom less functor if you wish to compare the objects:

template<class T> struct ptr_less 
{
    bool operator()(T* lhs, T* rhs) 
    {
        return *lhs < *rhs; 
    }
};
map<Object*, int, ptr_less<Object>> myMap;

Dragonfly

This should be chosen as the correct answer. Comparing pointers is (almost always surely) meaningless and will certainly lead to bugs that are extremely hard to detect. – Gothurd

It's fine if you just want to use the pointer as a key for a quick lookup into a map. Often maps are just used as lookup tables and the order isn't terribly relevant. – Rubrician

@Andy: I never said it is not, if you know what you are doing (I said: Pointers will be handled but compared as pointers = memory order). I only added possible solution if you expected to compare the objects, nothing more, nothing less. – Dragonfly

No offense @Dragonfly - comment was meant for comment above mine. – Rubrician

The answer should have been: you can, but you either should not (use unordered_map instead) or you don't know what are you doing (again, either unordered_map or the functor). The only possible counter argument I can think of is: it is going to be small anyway (OK, in that case, map is acceptable). – Dragonfly

Hmm. Isn''t comparison of pointers not in array bounds unspecified behaviour? – Apply

Answer 3

C++ standard provided specialisation of std::less for pointers, so yes you can safely use them as map keys etc.

Shorten

Answer 4

Leaving aside from the legality of this and any possible semantic misunderstandings, addressed already, I cannot think of any reason to use std::map here rather than std::unordered_map. There are early intercepts of this in Boost and Visual C++ if you are on a pre-C++11 compiler.

Since you appear to be using a pointer to represent a unique object, something like boost::flyweight could be applicable.

Cadet

Unfortunately I haven't entered the C++11 realm yet! – Recalcitrate

Answer 5

Pointers can be used as keys but especially with a std::map (or std::set) I would not advise it. The behavior of the program is not deterministic i.e. when one iterates over the map the order in which the items in the map are iterated is not guaranteed to be the same. It really depends on the memory address of the object (key). Take a look at this example, as you can see irrespective of the insertion order into the map the items are iterated in a deterministic way when the key is a string rather than a pointer.

http://ideone.com/VKirct

#include <iostream>
#include <map>
using namespace std;

class SomeClass {
    public:
    SomeClass(const std::string& name): m_name(name) {}
    std::string GetName()const {return m_name; }
    bool operator <(const SomeClass& rhs) const { return m_name < rhs.m_name; }
    private:
    std::string m_name;
};

auto print_seq  = [](const auto& seq) { for (const auto& itr: seq) {std::cout << itr.second << " , ";} std::cout << std::endl;};

int main() {
    // your code goes here
    std::map<SomeClass*, std::string> pointer_keyed_map;
    SomeClass s3("object3");
    SomeClass s1("object1");
    SomeClass s2("object2");
    pointer_keyed_map.insert(std::make_pair(&s1, s1.GetName()));
    pointer_keyed_map.insert(std::make_pair(&s2, s2.GetName()));
    pointer_keyed_map.insert(std::make_pair(&s3, s3.GetName()));
    std::cout << "Pointer based keys: object order" << std::endl;
    print_seq(pointer_keyed_map);

    std::map<SomeClass, std::string> int_keyed_map;
    int_keyed_map.insert(std::make_pair(s3, s3.GetName()));
    int_keyed_map.insert(std::make_pair(s1, s1.GetName()));
    int_keyed_map.insert(std::make_pair(s2, s2.GetName()));
    std::cout << "String based keys: object order" << std::endl;
    print_seq(int_keyed_map);
    return 0;
}

Roddy

Answer 6

It's okay to do that, but it doesn't seem to make sense.
What I mean is that map or set stores objects as long as the objects are different, but after storing the pointer, it may cause instability problem, because the pointer has no meaning, what is meaningful is the value stored in the address that the pointer points to, so it is better to write some compare functions to compare the value in the object. Not the address of the object.

Sleepless