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

You can't. Even if you fix your call site, you are ignoring the preconditions of std::equal_range, so your program is ill-formed.

If you want to lookup by both location and name, you need a data structure that provides such a lookup. boost::bimap or boost::multi_index are containers that can provide that.