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

Condyloid

I do think that its a memcmp type operation deep down. – Osborn

Any particular reason why you don't just use std::string as the key? – Marcasite

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. – Condyloid

See: #3241218 – Fabiano

Basically, it knows keys are equal if cmpstr returns false in both directions. – Fabiano

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.

Kamerad

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.

Adhamh