The obvious solution is not to use C style stringsThe reason for this is that std::map's operator< will treat our keys as numeric values, and therfor compare the address where our pointers are pointing. But we want to sort them alphabetically - and therefor we should write our own operator< for this.
It is only proper to use std::less when dealing with numeric values, imo.
std::less is not only proper with numeric values but with any types that define operator< (which is what less calls), e.g std::string.