如何在std::multimap中以O(log(n))复杂度高效查找值？

问题背景 #

现有数据结构是按Location的x坐标排序的std::multimap：

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

其中LessX的定义为：

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

City是std::pair<Location, std::string>的别名。当前已实现线性查找的findCity函数可用，但想要用std::equal_range实现O(log n)复杂度的查找时失败，报错如下：

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 &'

错误原因 #

1. 参数类型与顺序不匹配：std::equal_range会交替用容器元素和查找值调用比较函数，既会检查comp(element, value)，也会检查comp(value, element)。你提供的lambda只接受(const City&, const std::string&)，当传入std::string作为第一个参数时，类型不匹配，直接触发编译错误。
2. 容器排序规则不兼容：更核心的问题是，_mmapCitiesX是按Location的x坐标排序的，而非城市名。std::equal_range依赖容器的有序性，只有当查找逻辑和容器的排序规则兼容时，才能实现O(log n)的复杂度。直接按城市名查找，容器的有序性无法被利用，即使解决编译错误，也无法得到正确的结果，复杂度会退化为线性。

解决方案 #

要实现按城市名的O(log n)查找，最可靠的方式是构建反向索引：维护一个以城市名为键、Location为值的std::multimap（支持同名城市），利用其有序性实现高效查找。

步骤1：添加反向索引成员 #

在CitiesManager中新增一个用于索引城市名的容器：

class CitiesManager {
private:
    std::multimap<Location, std::string, LessX> _mmapCitiesX;
    std::multimap<std::string, Location> _cityNameIndex; // 反向索引
    // ...其他成员
};

步骤2：同步维护两个容器 #

在添加城市时，同时插入原容器和反向索引：

void CitiesManager::addCity(const Location& loc, const std::string& cityName) {
    _mmapCitiesX.emplace(loc, cityName);
    _cityNameIndex.emplace(cityName, loc);
}

步骤3：实现O(log n)的查找函数 #

利用反向索引的equal_range完成高效查找：

City CitiesManager::findCity(const std::string& cityName) const
{
    auto range = _cityNameIndex.equal_range(cityName);
    if (range.first == range.second) {
        throw std::runtime_error(cityName + " isn't found in the city list. Please try again");
    }
    // 从反向索引中获取Location，构造City返回
    return std::make_pair(range.first->second, cityName);
}

可选优化：使用无序容器 #

如果不需要按城市名排序，也可以用std::unordered_multimap作为反向索引，平均查找复杂度为O(1)：

std::unordered_multimap<std::string, Location> _cityNameIndex;

内容的提问来源于stack exchange，提问作者DanielG