使用 C++ 集查找目标之前的元素

Question

我知道有 lower_bound 和 upper_bound 方法都可以找到不在目标元素之前的第一个元素，包括和排除目标。但是我需要一种方法可以找到 before 目标的最后一个元素。有没有这样的方法或简单的方法可以使用 set?

谢谢！

Answer 1

你可以减少下限吗？

通常您需要检查下界是否产生 begin() 迭代器，在这种情况下您提到的元素不存在。

下面是一些示例代码（未经测试，仅供参考）：

template<typename T>
std::set<T>::iterator get_last_before(std::set<T> & s, const T & t) {
    auto it = s.lower_bound(t);
    if (it == s.begin()) { throw std::runtime_error(); }
    return --it;
}

使用 C++ 集查找目标之前的元素

Find element that goes before target with C++ set

binary-search-tree

c++11