不严格大于的 C++ STL 算法 upper_bound()

Question

与 lower_bound 不同，upper_bound 不会返回元素的迭代器，如果它比较等于值，但只有当它比较严格更大时。

如果我想要一个大于或等于的 upper_bound 算法，是否有替代方案。

Answer 1

您可以将迭代器减 1。

auto begin = ...;
auto end = ...;
auto it = std::upper_bound(begin, end, target);
if (it == begin)
  return it;
-- it;
if (*it < target)
  return ++it;
else
  return it;

迭代器的位置会是这样的，假设你要搜索2:

1 1 1 2 2 2 2 3 3 3 3
      ^     ^ ^
      lb    | ub
            this function


1 1 1 1 3 3 3 3
        ^
        lb & ub & this function