Search by value in a multimap in O(log(n)) complexity

How can I efficiently search for a value in a multimap with a time complexity of O(log(n))?

I have a multimap where the keys represent locations and the values represent city names. I want to efficiently search for a specific city name in the multimap based on the given city name.

This is the data structure:

 std::multimap < Location, std::string, LessX > _mmapCitiesX; 

Here is the search function that I have implemented (this is working):

City CitiesManager::findCity(const std::string& cityName) const { auto it = std::find_if(_mmapCitiesX.begin(), _mmapCitiesX.end(), [&](const City& city) { return city.second == cityName; }); if (it == _mmapCitiesX.end()) { throw std::runtime_error(cityName + " isn't found in the city list. Please try again"); } return *it; } 

(City is std::pair<Location, std::string>, and Location is a struct with x,y cords)

To reduce complexity , I attempted to use the std::equal_range, but it didn't work...

here is my attemp:

City CitiesManager::findCity(const std::string& cityName) const { auto range = std::equal_range(_mmapCitiesX.begin(), _mmapCitiesX.end(), cityName, [](const City& city, const std::string& name) { return city.second < name; }); if (range.first == range.second) { throw std::runtime_error(cityName + " isn't found in the city list. Please try again"); } return *(range.first); } 

I get error:

C2664 'bool CitiesManager::findCity::<lambda_1>::operator ()(const City &,const std::basic_string<char,std::char_traits,std::allocator> &) const': cannot convert argument 1 from 'const _Ty' to 'const City &'

edit: This is LessX, I need it because I want to sort the locations by x-chords, and therefore I choose to use Location as key.

struct LessX { bool operator()(const Location& left, const Location& right) const { return left._x < right._x; } }; 

I would appreciate any help