Using char* as a key in std::map

Question

I am trying to figure out why the following code is not working, and I am assuming it is an issue with using char* as the key type, however I am not sure how I can resolve it or why it is occuring. All of the other functions I use (in the HL2 SDK) use char* so using std::string is going to cause a lot of unnecessary complications.

std::map<char*, int> g_PlayerNames;

int PlayerManager::CreateFakePlayer()
{
    FakePlayer *player = new FakePlayer();
    int index = g_FakePlayers.AddToTail(player);

    bool foundName = false;

    // Iterate through Player Names and find an Unused one
    for(std::map<char*,int>::iterator it = g_PlayerNames.begin(); it != g_PlayerNames.end(); ++it)
    {
        if(it->second == NAME_AVAILABLE)
        {
            // We found an Available Name. Mark as Unavailable and move it to the end of the list
            foundName = true;
            g_FakePlayers.Element(index)->name = it->first;

            g_PlayerNames.insert(std::pair<char*, int>(it->first, NAME_UNAVAILABLE));
            g_PlayerNames.erase(it); // Remove name since we added it to the end of the list

            break;
        }
    }

    // If we can't find a usable name, just user 'player'
    if(!foundName)
    {
        g_FakePlayers.Element(index)->name = "player";
    }

    g_FakePlayers.Element(index)->connectTime = time(NULL);
    g_FakePlayers.Element(index)->score = 0;

    return index;
}

Bondman

Sometimes doing the right thing hurts at first. Change your code to use std:string once, and be happy afterwards. – Glyptography

what kind of complications? there is an implicit conversion from char* to std::string. – Lodestar

You must not use char* as a map key. See my answer why. – Outcaste

This seems to be an unnecessary complication caused by not using std::string. – Dituri

I don't understand, in order to use a binary key, wouldn't the Map need to know if a Key is Equal instead of knowing that a key has a value 'less than' another? – Firkin

You should probably use Source's CUtlRBTree. – Sextan

Note that the minute you set the key to a temporary object aString.c_str(), your map contains an invalid pointer. (don't ask me how I know). I quickly changed my maps back to having string keys. Never mind the copies, and the performance cost, so I read here, is not that big. – Ciapha

Answer 1

You need to give a comparison functor to the map otherwise it's comparing the pointer, not the null-terminated string it points to. In general, this is the case anytime you want your map key to be a pointer.

For example:

struct cmp_str
{
   bool operator()(char const *a, char const *b) const
   {
      return std::strcmp(a, b) < 0;
   }
};

map<char *, int, cmp_str> BlahBlah;

Cataplasm

actually he can just pass the &std::strcmp as the third template parameter – Unregenerate

No, strcmp returns a positive, zero, or negative integer. The map functor needs to return true on less-than and false otherwise. – Recidivism

@Armen: I don't think it works, as the 3rd template parameter expects something like f(a,b) = a<b, not f(a,b) = (-1 if a<b, 1 if a>b, 0 else). – Prodigious

oh, sorry, my bad, didn't think before posting. Let the comment stay there and bring shame to my ancestry :) – Unregenerate

As I tested, it must work with a const after bool operator()(char const *a, char const *b), like bool operator()(char const *a, char const *b) const{ blabla – Bascom

What if I have const char* pointers? I can't find a way to make this work (even changing it), I get an error when I try to initialize the map. – Hanny

See @aschepler's answer below for a version that works with const char * keys; essentially you move const declarations to before the char, and then add const after the function signature. – Warr

Note that operator() should always be a const method in this case. – Kobe

Answer 2

You can't use char* unless you are absolutely 100% sure you are going to access the map with the exact same pointers, not strings.

Example:

char *s1; // pointing to a string "hello" stored memory location #12
char *s2; // pointing to a string "hello" stored memory location #20

If you access map with s1 you will get a different location than accessing it with s2.

Heindrick

Unless you define your own comparator, as explained in accepted answer. – Redundancy

Answer 3

Two C-style strings can have equal contents but be at different addresses. And that map compares the pointers, not the contents.

The cost of converting to std::map<std::string, int> may not be as much as you think.

But if you really do need to use const char* as map keys, try:

#include <functional>
#include <cstring>
struct StrCompare : public std::binary_function<const char*, const char*, bool> {
public:
    bool operator() (const char* str1, const char* str2) const
    { return std::strcmp(str1, str2) < 0; }
};

typedef std::map<const char*, int, StrCompare> NameMap;
NameMap g_PlayerNames;

Recidivism

Thanks for the info. Based on my experience I highly recommend converting to std::string. – Angelesangelfish

I'm using a string to int map as a lookup table for decoding purposes. The lookup table as an std::map<std::string, short> takes about 180 KB, std::map<const char*, short> takes about 64 KB, so only one-third of the size. So if space is at a premium, the savings are significant. – Kumler

I was talking about the "cost" of refactoring existing code, I think. But yes, there could be memory and performance considerations for a large map. – Recidivism

Answer 4

You can get it working with std::map<const char*, int>, but must not use non-const pointers (note the added const for the key), because you must not change those strings while the map refers to them as keys. (While a map protects its keys by making them const, this would only constify the pointer, not the string it points to.)

But why don't you simply use std::map<std::string, int>? It works out of the box without headaches.

Outcaste

Answer 5

You are comparing using a char * to using a string. They are not the same.

A char * is a pointer to a char. Ultimately, it is an integer type whose value is interpreted as a valid address for a char.

A string is a string.

The container works correctly, but as a container for pairs in which the key is a char * and the value is an int.

Cartierbresson

There is no requirement for a pointer to be a long integer. There are platforms (such an win64, if you ever heard of it :-)) where a long integer is smaller than a pointer, and I believe there are also more obscure platforms where pointers and integers are loaded into different registers and treated differently in other ways. C++ only requires that pointers be convertible into some integral type and back; note this does not imply that you could cast any sufficiently small integer to pointer, only the ones you got from converting a pointer. – Twila

@ChristopherCreutzig, thanks for your comment. I edited my answer accordingly. – Cartierbresson

Answer 6

As the others say, you should probably use std::string instead of a char* in this case although there is nothing wrong in principle with a pointer as a key if that's what is really required.

I think another reason this code isn't working is because once you find an available entry in the map you attempt to reinsert it into the map with the same key (the char*). Since that key already exists in your map, the insert will fail. The standard for map::insert() defines this behaviour...if the key value exists the insert fails and the mapped value remains unchanged. Then it gets deleted anyway. You'd need to delete it first and then reinsert.

Even if you change the char* to a std::string this problem will remain.

I know this thread is quite old and you've fixed it all by now but I didn't see anyone making this point so for the sake of future viewers I'm answering.

Regulate

Answer 7

Had a hard time using the char* as the map key when I try to find element in multiple source files. It works fine when all the accessing/finding within the same source file where the elements are inserted. However, when I try to access the element using find in another file, I am not able to get the element which is definitely inside the map.

It turns out the reason is as Plabo pointed out, the pointers (every compilation unit has its own constant char*) are NOT the same at all when it is accessed in another cpp file.

Ehrlich

Answer 8

std::map<char*,int> will use the default std::less<char*,int> to compare char* keys, which will do a pointer comparison. But you can specify your own Compare class like this:

class StringPtrCmp {
    public:
        StringPtrCmp() {}

    bool operator()(const char *str1, const char *str2) const   {
        if (str1 == str2)
            return false; // same pointer so "not less"
        else
            return (strcmp(str1, str2) < 0); //string compare: str1<str2 ?
    }
};

std::map<char*, YourType, StringPtrCmp> myMap;

Bear in mind that you have to make sure that the char* pointer are valid. I would advice to use std::map<std::string, int> anyway.

Tyrannize

Answer 9

You can bind a lambda that does the same job.

#include <map>
#include <functional>
class a{   
    std::map < const char*, Property*, std::function<bool(const char* a, const char* b)> > propertyStore{ 
        std::bind([](const char* a, const char* b) {return std::strcmp(a,b) < 0;},std::placeholders::_1,std::placeholders::_2)
    };
};

Mobcap

Answer 10

There's no problem to use any key type as long as it supports comparison (<, >, ==) and assignment.

One point that should be mentioned - take into account that you're using a template class. As the result compiler will generate two different instantiations for char* and int*. Whereas the actual code of both will be virtually identical.

Hence - I'd consider using a void* as a key type, and then casting as necessary. This is my opinion.

Pompous

They key only needs to support <. But it needs to implement that in a way that's helpful. It isn't with pointers. Modern compilers will fold identical template instances. (I know for sure VC does this.) I would never use void*, unless measuring showed this to solve a lot of problems. Abandoning type-safety should never be done prematurely. – Outcaste