C++ STL : Why is there no upper_bound equivalent that retrieves the greatest element smaller then a specific key?

Question

通常，STL 是为提高速度而构建的。然而，在 map 和 set 数据结构上只有 upper_bound 和 lower_bound 并且没有操作来检索具有小于输入键的最大键的条目 k .为什么是这样？我知道我可以简单地做一个 lower_bound并做一个 --it检索它，但根据数据结构，立即搜索正确的条目可能比搜索另一个条目然后返回一步更有效。

例如，std::map使用红黑树，即二叉搜索树。如果 upper_bound 返回的元素是大于根的最小元素，则 --it必须回到根，查询 O(log n) 的额外成本。

如果这是 Java，我会接受设计决定。然而，STL 是为实现最高速度而构建的，那么为什么要省略此操作？

澄清:我不是在谈论 std::upper_bound它可以采用另一个比较器，但是 std::map 的方法和 std::set .

Answer 1

首先，要获得小于键的最大元素，您必须这样做:

auto it = m.lower_bound(k);
--it;

表示找到第一个不小于k的元素，并向后移动一个元素。如果要有一个函数来执行此操作，例如 auto it = m.last_less_element(k);，那么该函数必须以完全相同的方式，即找到第一个不小于k的元素后退一次。这是因为除非找到第一个不小于 k 的元素，否则无法知道不存在大于但小于 k 的元素。因此，拥有这样的功能不会带来性能提升，它只是一种语法快捷方式/便利。即便如此，与查找本身的成本相比，返回一次的成本可以忽略不计。

其次，如果你想从开始迭代到最后一个小于键的元素，那么你会这样做:

for(auto it = m.begin(); it != m.lower_bound(k); ++it) { /* ... */ };

换句话说，lower_bound 和 upper_bound 函数的创建方式是标准迭代器范围的惯用方式，这一点非常重要。仅就此而言，不包含像 last_less_element 这样的特殊函数是合理的，因为它会在 map 或 set 的接口(interface)中引入反惯用函数 类，并且没有性能提升。因此，它会带来痛苦，但没有收获。

最后要注意的是，二叉搜索树(如红黑树)主要用于查找操作，并具有按顺序遍历的边际优势。它们不是按顺序遍历的流线型，如果这是您要执行的主要操作，则不应使用它们。当主要操作是查找操作时，有序映射或集合很有用，偶尔需要按顺序遍历。在相反的情况下应考虑其他替代方案(例如，排序 vector 、树布局 à la von Emde Boas 等)。