C++ set lower_bound() iterator

Question

I want to find the greatest element in a std::set in C++ strictly less than a given element. Some questions suggest finding lower_bound iterator and decrementing it i.e.

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

Documentation is unclear as to what type of iterator does lower_bound return (e.g Forward, Bidirectional) so how do we know decrementing this iterator is valid ? Also can we estimate the complexity of decrementing std::set iterator ?

Answer 1

According to the documentation of set::lower_bound on cplusplus.com, under "Return value":

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

so you'll always be able to decrement the iterator (after your begin check, of course).

The complexity of decrementing an iterator will always be (amortized) constant. See this answer.

Answer 2

The return types of std::set::lower_bound are std::set::iterator or std::set::const_iterator, which are member types of std::set, they're both constant bidirectional iterator.