Menu
Perhaps I'm misunderstanding the technical definition of lower bound but I would expect if I had a set a = { 0, 3, 4 } and computed the a.lower_bound(2) that the result would be 0. I.e. I would expect std::set::lower_bound to be close to the mathematical concept of infimum
And yet the standard library defines it as the largest number not less than (effectively >=) x.
What is the reasoning behind this?
822
Time Complexity of set::lower_bound() is O(logn), where n is the size of the set.
lower_bound returns an iterator pointing to the first element in the range [first,last) which has a value not less than 'val'. and if the value is not present in the vector then it returns the end iterator.
lower_bound in c++ stl returns an iterator even when the element is not present.
lower_bound() returns an iterator to begin of the range. If all elements are lower than the searching element: lower_bound() returns an iterator to end of the range( No lower bound exists).
The "[lower|upper]_bound" functions are meant to return a place in a set where you could insert a key that would not violate the ordering of the set. Because an iterator of an STL set points to before the next element, if lower_bound(2) returned an iterator to 0, then inserting 2 would violate the order of your set, it would now be {2, 0, 3, 4}. Upper bound serves to show the last place you could insert without violating set order.
This is most useful if your set may have duplicate key entries. Consider {0, 3, 3, 4}. lower_bound(3) would return an iterator to here: {0, *, 3, 3, 4}, while upper_bound(3) would return it here: {0, 3, 3, *, 4}.
77
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
