In this tutorial, we will dicsuss about the lower_bound() & upper_bound() functions of set in C++

C++ Set lower_bound()

The STL provides a function, lower_bound(), in its set class. This function accepts a value as an argument and returns an iterator pointing to the first element that is not less than the specified value. If the given element exists in the set, then it will return an iterator pointing to that particular element.

Let’s consider an example where we have a set of integers:

std::set<int> setObj = {10, 20, 33, 44, 55};

If we call the lower_bound() function and pass the value 33 to it, it will return an iterator pointing to the value 33, because it already exists in the set.

auto itr = setObj.lower_bound(33);
// itr now points to 33

However, if we pass the value 30 to lower_bound(), it will return an iterator pointing to the first element that is not less than 30. In this case, that is 33.

auto itr2 = setObj.lower_bound(30);
// itr2 now points to 33

As another example, if we pass a value of 40, it will return an iterator pointing to the first element that is not less than 40. In our case, that would be 44.

auto itr3 = setObj.lower_bound(40);
// itr3 now points to 44

C++ Set upper_bound()

The set class in the STL provides a function called upper_bound(). It accepts a value as an argument and returns an iterator pointing to the first element that is greater than the specified value.

Let’s consider an example where we have a set of integers:

std::set<int> setObj = {10, 20, 33, 44, 55};

If we call the upper_bound() function and pass the value 33 to it, even though the value 33 already exists in the set, it will return an iterator pointing to the first element that is greater than the specified value. In our case, that would be 44.

auto itr = setObj.upper_bound(33);
// itr now points to 44

Let’s see the complete example,

#include <iostream>
#include <set>

int main()
{
    std::set<int> s = {11, 22, 33, 44, 55};

    // Using lower_bound
    int value1 = 33;
    auto it_low = s.lower_bound(value1);

    if (it_low != s.end())
    {
        std::cout << "Lower bound of " << value1 << " is: " << *it_low << std::endl;
    }
    else
    {
        std::cout << "Lower bound of " << value1 << " exceeds the set." << std::endl;
    }

    // Using upper_bound
    int value2 = 33;
    auto it_up = s.upper_bound(value2);

    if (it_up != s.end())
    {
        std::cout << "Upper bound of " << value2 << " is: " << *it_up << std::endl;
    }
    else
    {
        std::cout << "Upper bound of " << value2 << " exceeds the set." << std::endl;
    }

    return 0;
}

Output:

Lower bound of 33 is: 33
Upper bound of 33 is: 44

Summary

These functions are useful because they operate in logarithmic time, O(log n). Sometimes, when we’re searching for a value and it doesn’t exist, we want to find the nearest value. In these scenarios, both the lower_bound and upper_bound() functions are very useful.

Ritika Ohri

Hi, I am Ritika Ohri, founder of this blog. I craft comprehensive programming tutorials and also manage a YouTube channel. You can also connect with me on Linkedin.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.