C++ STL: Why is there no upper_bound equivalent that retrieves the greatest element smaller then a specific key?

Question

Usually, STL is built for speed. However, there is only upper_bound and lower_bound on map and set data structures and no operation to retrieve the entry with the greatest key that is less than an input key k. Why is this? I know I can simply do an lower_bound and do a --it to retrieve this, but depending on the data structure it might be more efficient to search for the correct entry right away instead of searching for another one and then going back one step.

For example, std::map uses a Red-black tree, i.e. a binary search tree. If the element that is returned by upper_bound is the smallest element that is greater than the root, then --it must walk back to the root, enquiring O(log n) additional cost.

If this was Java, I would be fine with the design decision. However, STL is built for maximum speed, so why was this operation left out?

Clarification: I am not talking about std::upper_bound which can take another comparator but the methods of std::map and std::set.

Answer 1

First of all, to obtain the greatest element that is less than the key, you would have to do:

auto it = m.lower_bound(k);
--it;

which means to find the first element that is not less than k and move back one element. If there was to be one function to do this, e.g., auto it = m.last_less_element(k);, then that function would have to be implemented in the exact same way, that is, find the first element not less than k and move back once. This is because there is no way to know that there isn't an element greater but still less than k unless you find the first element not less than k. So, there is no performance gain to have from having such a function, it would merely be a syntactic shortcut / convenience. And even then, the cost of moving back once is negligible in comparison to the cost of the look-up itself.

Second, if you wanted to iterate from the beginning to the last element less than the key, then you would do:

for(auto it = m.begin(); it != m.lower_bound(k); ++it) { /* ... */ };

In other words, the way the lower_bound and upper_bound functions are made, they are idiomatic of standard iterator ranges, and that is very important. On that ground alone, it is justifiable to not include a special function like last_less_element as it would introduce a counter-idiomatic function in the interface of the map or set classes, and with no performance gain. So, it would cause pain, yet, no gain.

And as a final note, binary search trees (like a Red-black trees) are made for look-up operations mainly, with a marginal benefit of in-order traversals. They are not streamlined for in-order traversals, they shouldn't be used if that is the main operation you want to do. Ordered maps or sets are useful when the main operations are look-up operations, with an occasional need for an in-order traversal. Other alternatives should be considered in the reverse situation (e.g., sorted vectors, tree layouts à la von Emde Boas, etc.).