std::set with string key and potential efficiency loss

Question

Let's assume I have a most straightforward std::set of all:

std::set<std::string> my_set;

Now, I have a function which accepts const char* and needs to tell me of this string exists or not in the set, implemented in the most straightforward way:

bool exists(const char* str) {
    return my_set.count(str) > 0;
}

Now, this is obvious efficiency loss. A (potential) dynamic memory allocation followed by deallocation happens right here for no reason.

How can we eliminate that? I'd like to compare std::string which I want to be the key type with char*. One way would be to use unique_ptr<char> instead of my key type with custom comparator, but that'd be super awkward.

The problem can be actually generalized to wider case, effectively, "how to invoke comparison with type provided without conversion to key type?"

P.S. I have seen std::string as map key and efficiency of map.find(), but I am not satisfied with the answer, which effectively reiterates that this optimization is not needed, while it is clearly wrong.

Answer 1

You are correct that by default count is going to convert str to a std::string potentially causing a dynamic memory allocation and at least doing an unnecessary copy. Luckily C++14 add overload for count in the form of

template< class K > 
size_type count( const K& x ) const;

That will take any type. To get this overload though you need to have a comparator that defines a member type with the name is_transparent (the type doesn't matter, just that it exists). Instead of having to write one though we can use the new std::less<void> that was also introduced in C++14. This acts as a transparent comparator by providing a templated operator(). That means you just need to change

std::set<std::string> my_set;

to

std::set<std::string, std::less<>> my_set;
// or
std::set<std::string, std::less<void>> my_set;

and then the set will use bool operator<(std::string, const char*) for the comparison and no temporary or copying needs to happen.