Using char* as a key in std::map, how does it work

Question

This question relates directly to using char as a key in stdmap.

I understand what the compare function passed in does and why its required for char * types as a key. However, I'm uncertain as how the updating actually works.

I'm curious as to the case where you are updating a key. How does std::map know how to compare equality between the const char *, cmp_str only tells map the order in which to inserted keys into the tree.

I've done a little digging into the stl_tree.h code (pulled from here) but wasn't able to find much. My only guess is that its doing a straight memory comparison.

I'm interested in how the underling stl_tree class handles this situation, or if it doesn't handle it correctly all the time, what edge case breaks?

Code

#include <map>
#include <iostream>
#include <cstring>

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

int main ( int argc, char ** argv )
{

    std::map<const char*, int, cmp_str> map;

    map["aa"]  = 1;
    map["ca"]  = 2;
    map["ea"]  = 3;
    map["ba"]  = 4;

    map["ba"]  = 5;
    map["bb"]  = 6;

    map["ba"]  = 7;

    std::map<const char*, int, cmp_str>::iterator it = map.begin();
    for (; it != map.end(); it++ )
    {
        std::cout << (*it).first << ": " << (*it).second << std::endl;
    }

    return 0;

}

Output

aa: 1
ba: 7
bb: 6
ca: 2
ea: 3

Answer 1

The ordered containers all use equivalence classes: Two values a and b are considered equivalent if neither one is smaller than the other: !(a < b) && !(b < a) or, if you insist on the notation using a binary predicate !pred(a, b) && !pred(b, a).

Note, that you need to keep the pointers live in your map: if the pointers go out of scope you will get strange results. Of course, string literals stay valid throughout the life-time of the program.

Answer 2

Well, cmp_str can be used to find identical keys. If both cmp_str::operator(x,y) and cmp_str::operator(y,x) return false, you've found a duplicate key. There's really not much more to it.