Ami*_*mir 4 c++ dictionary lower-bound
map据我了解， in的底层数据结构C++是一个自平衡的二叉搜索树。由于在这些数据结构中，查找键的下限和上限有很多用处，因此您可能会认为映射 lower_bound 和 upper_bound 函数将为您提供这种功能。遗憾的是这些功能无法实现这一点。有谁知道为什么 lower_bound 的行为方式如此？（它为您提供不在给定密钥之前的密钥）。
use*_*445 10
在 SGI 引入 STL 之前我就一直在使用 C++，并且出于某种原因仍然在使用这些方法时搞砸了，包括在向班级展示它们时甚至让自己感到尴尬。我认为我的问题是：
这些名称在数学中已经具有直观但不同的含义。考虑到数学含义，在一个大集合或地图中，upper_bound和lower_bound实际上是相同或相邻的元素似乎很奇怪。
“upper_bound”和“lower_bound”这两个名字听起来好像两者之间存在某种对称性，但其实根本不存在。如果名称类似于least_ge（至少大于或等于）lower_bound 和least_gt（至少大于）upper_bound，我会更容易。
如果有人有一个助记符或逻辑可以使这些内容易于内化，请分享。否则，感觉就像他们写了两个有用的函数，但使用了两个随机的数学术语来命名这些函数，无法从名称中推导出语义。那么，为什么不使用像egptrand这样的虚构名称呢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
在多重集/多重映射中，第一个v是lower_bound(v)该元素是否确实是v。最后一个v是std::prev(upper_bound(v))容器是否不为空而该元素是否为空，但请记住在尝试v之前检查容器是否不为空。prevend()