Two Upper Bound/Lower Bound Implementations in C++

Many of you might have observed that there are two implementations to compute upper_bound and lower_bound on std::set/std::multiset in C++.

The implementations of upper_bound and lower_bound are almost the same. So, without loss of generality, let’s focus on the upper_bound (the same discussion will also be true for lower_bound).

Consider the following example (AlgoTwister 7).

The answer is just_greater1 takes O(N) time to compute upper_bound, while on the other hand, just_greater2 takes O(logN) time.

Why this difference? To understand this, we need to dig into their implementations in the C++ library. But before that, let’s learn about iterators in C++.

Iterators

An iterator is any object that, pointing to some element in a range of elements (such as an array or a container), has the ability to iterate through the elements of that range using a set of operators (with at least the increment (++) and dereference (*) operators).

The most obvious form of iterator is a pointer: A pointer can point to elements in an array and can iterate through them using the increment operator (++). But other kinds of iterators are possible. For example, each container type (such as a list) has a specific iterator type designed to iterate through its elements.

Types of iterators

Based upon the functionality of the iterators, they can be classified into five major categories:

1. Input Iterators: They are the weakest of all the iterators and have very limited functionality. They can only be used in single-pass algorithms, i.e., those algorithms which process the container sequentially, such that no element is accessed more than once.
2. Output Iterators: Just like input iterators, they are also very limited in their functionality and can only be used in the single-pass algorithms, but not for accessing elements, but for being assigned elements.
3. Forward Iterators: They are higher in the hierarchy than input and output iterators, and contain all the features present in these two iterators. But, as the name suggests, they also can only move in a forward direction and that too one step at a time.
4. Bidirectional Iterators: They have all the features of forward iterators along with the fact that they overcome the drawback of forward iterators, as they can move in both directions, that is why their name is bidirectional.
5. Random-Access Iterators: They are the most powerful iterators. They are not limited to moving sequentially, as their name suggests, they can randomly access any element inside the container. They are the ones whose functionality are the same as pointers.

Examples

Containers like vector, deque supports Random-Access Iterators, while containers like the set, multiset, map, multimap, list supports Bidirectional Iterators. On the other hand, containers like the stack, queue, priority_queue doesn’t support any type of iterators.

If you want to read more about iterators, we’d suggest spending some time going through documentation: https://www.cplusplus.com/reference/iterator/

Now, let’s look into the upper_bound implementation used in just_greater1 function in Example 1.

Observe lines no. 6 and 11. std::distance and std::advance take constant time to compute if the iterator is Random-Access Iterator, otherwise, it takes linear time. If we think carefully, that makes sense. Forward and Bidirectional Iterators moves one step at a time. So in order to advance certain steps (line no. 11), they do that one step at a time. Similarly, for distance, they iterate first with one step at a time until it reaches last. But in the case of Random-Access Iterator, we can do the same things in O(1) (think in terms of arrays).

Line 8–18 is similar to the Binary Search algorithm with which we’re familiar.

We can say that the above upper_bound implementations will take O(logN) in the case of vector and deque because they support Random-Access Iterator. But in the case of set, multiset, map, multimap, list, it’ll take O(N) time to compute the same thing. Please note that N is the size of the container.

In the case of set::upper_bound (used in just_greater2 function in Example1), it makes use of the set’s capability to search for value efficiently (logarithmic with regards to the size of the container). STL containers like set, multiset, map, multimap are implemented using Self-Balancing Binary Search Trees. The height of the tree is maintained in logarithmic order of the size of the container. That’s why set::upper_bound runs in O(logN).

We hope this discussion clarifies the differences between the two implementations of upper_bound. The same discussion is also valid for lower_bound implementations.

References

1. https://www.cplusplus.com/reference/iterator/
2. https://www.geeksforgeeks.org/introduction-iterators-c/
3. https://en.cppreference.com/w/cpp/algorithm/upper_bound
4. https://en.cppreference.com/w/cpp/iterator/distance
5. https://en.cppreference.com/w/cpp/iterator/advance
6. https://en.cppreference.com/w/cpp/iterator#:~:text=%5Bedit%5D%20Iterator%20categories,(since%20C%2B%2B17).
7. https://en.cppreference.com/w/cpp/container/set/upper_bound
8. https://www.geeksforgeeks.org/self-balancing-binary-search-trees-comparisons/