std::multimap<int,X*>键为何为const int？如何正确查找指定键值对？

我有一个std::multimap<int, X*>容器（X是自定义类型），想要查找其中特定的键值对并获取对应的迭代器，但遇到了编译问题：

示例代码(A)（编译失败） #

#include <map>
#include <algorithm>

class X {};

int main()
{
    X myX;
    std::multimap<int, X*> myMap;
    auto it = std::find(myMap.begin(), myMap.end(), std::make_pair(5, &myX));
    
    return 0;
}

编译报错（gcc 12.2.1，-std=gnu++2a）：

no match for ‘operator==’ (operand types are ‘std::pair<const int, X*>’ and ‘const std::pair<int, X*>’)

显然是因为multimap中存储的键是const int，和std::make_pair生成的pair<int, X*>类型不匹配导致的。

示例代码(B)（编译成功） #

使用std::find_if配合lambda可以正常编译：

auto it = std::find_if(myMap.begin(), myMap.end(), [&myX](std::pair<const int, X*>& node){ 
    return 5 == node.first && (&myX) == node.second; 
} );

问题1：为什么multimap中的键类型是const int而非int？ #

std::multimap属于有序关联容器，内部依赖键的有序性维护结构（通常是红黑树）。如果允许修改容器内的键，会直接破坏容器的有序性，导致后续查找、插入等操作全部失效。因此标准规定，关联容器存储的键值对是std::pair<const Key, Value>类型，键被设为const，禁止用户直接修改容器内的键值。

问题2：有没有比使用(B)中的lambda函数，或先按键查找再遍历对应值更自然的修复方法？ #

有两种更直接的方式：

• 构造匹配类型的pair进行查找
  直接构造std::pair<const int, X*>类型的对象作为std::find的参数，让类型完全匹配：

auto target = std::pair<const int, X*>(5, &myX);
auto it = std::find(myMap.begin(), myMap.end(), target);

或者用std::make_pair结合std::as_const（C++17及以上）生成带const键的pair：

auto target = std::make_pair(std::as_const(5), &myX);
auto it = std::find(myMap.begin(), myMap.end(), target);

• 利用multimap的有序性优化查找效率
  std::find会遍历整个容器，效率较低。可以先用std::multimap::equal_range快速定位所有键为5的元素区间，再在这个小范围内查找目标指针，效率更高：

auto [range_begin, range_end] = myMap.equal_range(5);
auto it = std::find_if(range_begin, range_end, [&myX](const auto& node) {
    return node.second == &myX;
});

这种方式避免了遍历整个容器，更适合元素较多的场景。

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