C++ map<std::string> vs map<char *> performance (I know, "again?")

You are using a const char * as a lookup key for find(). For the map containing const char* this is the correct type that find expects and the lookup can be done directly.

The map containing std::string expects the parameter of find() to be a std::string, so in this case the const char* first has to be converted to a std::string. This is probably the difference you are seeing.

As sth noted, the issue is one of specifications of the associative containers (sets and maps), in that their member search methods always force a conversion to the key_type, even if an operator< exists that would accept to compare your key against the keys in the map despite their different types.

On the other hand, the functions in <algorithm> do not suffer from this, for example lower_bound is defined as:

template< class ForwardIt, class T >
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value );

template< class ForwardIt, class T, class Compare >
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );

So, an alternative could be:

std::vector< std::pair< std::string, int > >

And then you could do:

std::lower_bound(vec.begin(), vec.end(), std::make_pair("hello", 0), CompareFirst{})

Where CompareFirst is defined as:

struct CompareFirst {
     template <typename T, typename U>
     bool operator()(T const& t, U const& u) const { return t.first < u.first; }
};

Or even build a completely custom comparator (but it's a bit harder).

A vector of pair is generally more efficient in read-heavy loads, so it's really to store a configuration for example.

I do advise to provide methods to wrap the accesses. lower_bound is pretty low-level.