You need to enable JavaScript to run this app. C++以pair为键的map的lower_bound与upper_bound规则疑惑
优惠活动
大模型
产品
解决方案
定价
更多

C++以pair为键的map的lower_bound与upper_bound规则疑惑

核心问题来源

你遇到的认知冲突完全源于两方面:一是参考教程对标准库函数规则的错误编造,二是没有从关联容器的通用比较逻辑出发理解pair的排序特性。
首先要明确一个最基础的原则:C++所有有序关联容器(包括std::map)的lower_bound、upper_bound行为,完全由容器配置的键比较器决定,不存在针对pair类型的特殊自定义规则。

先理清两个基础规则

1. std::pair的默认比较逻辑

std::pair<int, int>的默认<运算符实现严格字典序比较,判断规则没有任何特殊拆分:

  • 先比较两个pair的第一分量,只要第一分量不相等,就直接返回第一分量的比较结果
  • 只有当两个pair的第一分量完全相等时,才会比较第二分量,返回第二分量的比较结果
    举几个直观的对比结果:
  • {2, 3} < {2, 5}:第一分量相等,3<5,结果为真
  • {2, 100} < {3, 0}:第一分量2<3,不管第二分量差多少,结果都为真
  • {1, 1000} < {2, 2}:第一分量1<2,结果为真

2. 两个函数的通用定义(和键类型无关)

对有序关联容器来说,两个函数的行为是完全统一的:

  • lower_bound(k):返回容器中第一个**不小于k(即不满足elem < k)**的键对应的迭代器
  • upper_bound(k):返回容器中第一个**严格大于k(即满足k < elem)**的键对应的迭代器

结合你的示例验证

你插入5组键值对之后,map会按照默认的pair比较规则,把所有键按升序排列,实际的键序列是:

[{2, 3}, {2, 5}, {5, 0}, {7, 1}, {9, 3}]

第一个测试场景:lower_bound({2,4})

遍历键序列依次判断:

  • 第一个键{2,3}:和{2,4}比,第一分量相等,3<4,因此{2,3} < {2,4},不符合“不小于k”的条件
  • 第二个键{2,5}:和{2,4}比,第一分量相等,5>4,因此满足“不小于k”的要求,作为lower_bound的返回值,和实际运行结果完全一致。

第二个测试场景:upper_bound({2,2})

按照通用规则,需要找第一个满足{2,2} < elem的键:

  • 第一个键{2,3}:和{2,2}比,第一分量相等,2<3,因此{2,2} < {2,3}成立,这就是第一个满足条件的元素,所以upper_bound直接返回{2,3},和实际运行结果完全一致。

参考教程的错误点

你参考的教程对函数规则的描述存在根本性错误:

  1. 它编造的“upper_bound需要返回第一分量大于x、且第二分量大于y的pair”的规则完全不符合标准实现。这个规则错误地把pair的整体字典序“大于”关系,拆解成了“两个分量同时严格大于查询值的两个分量”——实际上只要字典序整体大于,不管第二分量的大小,都符合条件。
    比如查询upper_bound({2,5})的时候,字典序里第一个比{2,5}大的键是{5,0}:因为第一分量2<5,所以{2,5} < {5,0}成立,哪怕{5,0}的第二分量0远小于5,也会被作为upper_bound的返回值,完全不符合教程里编的规则。
  2. 教程提到的“不存在符合条件的pair时返回指向{map.size(), 0}的迭代器”也是错误描述。标准std::map在找不到符合要求的元素时,会直接返回容器的end()迭代器,根本不存在预置的{size, 0}键值对。

内容的提问来源于stack exchange,提问作者Setu Kumar Basak

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.15 14:15:04