Deepankar Arya Deepankar Arya - 9 days ago 6
C++ Question

C++ set lower_bound() iterator

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 ?

qxz qxz
Answer

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.

Comments