C++ 设置 lower_bound() 迭代器

Question

我想在 C++ 中的 std::set 中找到严格小于给定元素的最大元素。一些问题建议找到 lower_bound 迭代器并将其递减，即

set<int> st;
// Add elements
int x;
// calculate x
auto it = st.lower_bound(x);
if(it != st.begin()) {
    it--;
}

Documentation不清楚 lower_bound 返回什么类型的迭代器(例如 Forward，Bidirectional)，那么我们怎么知道递减这个迭代器是有效的？我们还可以估计递减 std::set 迭代器的复杂性吗？

Answer 1

根据documentation of set::lower_bound on cplusplus.com ，在“返回值”下:

Member types iterator and const_iterator are bidirectional iterator types pointing to elements.

因此您始终能够递减迭代器(当然是在您的 begin 检查之后)。

递减迭代器的复杂性将始终(摊销)为常量。参见 this answer .