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

Any particular reason why you don't just use `std::string` as the key? — nneonneo, Oct 15 '12 at 18:25
My professor wrote the above `cmp_str` function and I raised the question, he didn't have an answer to the question. I ran a few tests and wasn't able to come across edge case the broke, but I'm still flummoxed to how it works, as I'd assume it would just insert another entry into the table. — travis, Oct 15 '12 at 18:28
See: http://stackoverflow.com/questions/3240718/how-does-the-stl-mapfind-function-work-without-the-equality-operator — Joe, Oct 15 '12 at 18:29
Basically, it knows keys are equal if cmpstr returns false in both directions. — Joe, Oct 15 '12 at 18:29

Luchian Grigore · Answer 1 · 2012-10-15T18:32:31.737

6

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.

edited Oct 15 '12 at 18:32

answered Oct 15 '12 at 18:27

Luchian Grigore

253,575
64
457
625

score 6 · Accepted Answer · answered Oct 15 '12 at 18:27

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.

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

2 Answers2