gpt4 book ai didi

C++ 映射 lower_bound/upper_bound

转载 作者:行者123 更新时间:2023-12-02 19:34:59 30 4
gpt4 key购买 nike

我了解到 C++map 的底层数据结构是一个自平衡的二叉搜索树。由于在这些数据结构中,查找键的下限和上限有很多用处,您会认为 map lower_bound 和 upper_bound 函数将为您提供这种能力。令人遗憾的是,这些功能无法实现。有谁知道为什么 lower_bound 的行为方式是这样的? (它为您提供了不在给定 key 之前的 key )。

最佳答案

自从 SGI 甚至引入 STL 之前我就一直在使用 C++,并且出于某种原因仍然设法搞砸了使用这些方法,甚至在将它们呈现给类时让自己感到尴尬。我认为我的问题是:

  1. 这些名字在数学上已经具有直观但不同的含义。鉴于数学含义,在大集合或 map 中似乎很奇怪,upper_boundlower_bound实际上是相同或相邻的元素。

  2. 名称“upper_bound”和“lower_bound”听起来好像两者之间存在某种对称性,但实际上并非如此。如果名称类似于 least_ge,我会轻松得多(至少大于或等于)lower_bound 和 least_gt (最小大于)upper_bound。

如果有人有助记符或逻辑可以使这些易于内化,请分享。否则,感觉就像他们写了两个有用的函数,但使用了两个随机的数学术语来命名这些函数,无法从名称中推导出语义。到那时,为什么不使用像egptr这样的虚构名称呢?和 pbase ?我的意思是至少我没有任何预先存在的直觉来克服关于 streambuf 的名字。方法...

无论如何,我认为这是您必须记住的基本规则:

  • lower_bound(X)返回最低元素 v这样 v >= X

  • upper_bound(X)返回最低元素 v这样 v > X

  • 要遍历半开区间 [L,H),从 lower_bound(L) 开始并停止(不处理)lower_bound(H) . 这通常是您想要的,因为在 C++ 中遍历半开区间是最常见的——例如,[ buf , buf+nbytes ), 或 [ 0 , array_size ), 或 [ begin() , end() ).

  • 要遍历闭区间 [L,H],从 lower_bound(L) 开始并停在 upper_bound(H) .

  • 要遍历开区间 (L,H),从 upper_bound(L) 开始并停在 lower_bound(H) .

  • 在非空容器中,lower_bound(X) 的镜像是std::prev(upper_bound(X))upper_bound(X)的镜像是std::prev(lower_bound(X)) .当然,如果一个元素等于begin() , 那么你不能用 std::prev 向后退一步,所以你需要额外的逻辑来处理这个点不能用迭代器值表示的事实。

  • 在多重集/多重映射中,第一个 vlower_bound(v)如果该元素确实是 v .最后vstd::prev(upper_bound(v))如果容器不为空且该元素为 v ,但记得在尝试之前检查容器是否为空 prevend() .

关于C++ 映射 lower_bound/upper_bound,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/61193289/

30 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com