Difference Between Stdsetlower Bound And Stdlower Bound In C++

In this article, we will discuss the differences between the std::lowerbound and std::set::lowerbound function in C++. But before discussing their differences, we must know about the std::lowerbound and std::set::lowerbound function.

What is std::lower_bound in C++?

The std::lowerbound function detects the first place in a sorted range where a given value could be inserted without causing the ordering to be broken by using a binary search. The Output is an iterator that shows the first value larger than or equal to the one provided in the range [first, last]. Stated otherwise, the function std::lowerbound determines the index of the least element in the sorted range greater than or equal to the input value. All elements preceding this returned iterator must be less than the value. The elements after std::lowerbound may or may not be more than or equal to the value. It enables the use of std::lowerbound for efficient lookups and insertions into stored data

What is std::set::lower_bound in C++?

The lower_bound method of std::set does a binary search to find where a given key would be added to keep the Set's ordering . It returns an iterator thacpp tutorials to the first entry greater than or equal to the searched key.

If the key is not present in the Set, lower_bound returns an iterator to the next most significant element that sorts after the searched key. It finds that the key's "lower boundary" is in the Ordered Set. It allows efficient lookups, even for keys not already in the Set.

Lower_bound will provide an iterator pointing to the end of the set container if the searched key is greater than the largest element in the Set.

What is the difference between std::lower_bound and set::lower_bound?

The following table compares std::lowerbound and std::set::lowerbound in a tabular format.

while std::set::lower_bound is a set member function that utilizes its ordering specifically for lookup/insertion in a set. But both return the "lower boundary" for a value in O(log n) time.

Example:

Let us take a program to illustrate the use of std::lower_bound in C++:

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
 // Create a sorted vector of integers
 std::vector<int> vec = {1, 2, 4, 4, 5, 7, 8, 10};

 // Value to search for
 int target = 6;

 // Use std::lower_bound to find the position of the first element not less than target
 auto it = std::lower_bound(vec.begin(), vec.end(), target);

 // Output the result
 std::cout << "Vector contains: ";
 for (int num : vec) {
 std::cout << num << " ";
 }

 if (it != vec.end()) {
 std::cout << "\nFirst element not less than " << target << " is at position: " << std::distance(vec.begin(), it);
 } else {
 std::cout << "\nNo element not less than " << target << " found in the vector.";
 }

 return 0;
}

Output:

Vector contains: 1 2 4 4 5 7 8 10 
First element not less than 6 is at position: 5

In this example, the target value is 35 , and std::lower_bound is used to find the position where 35 could be inserted in the vector to maintain the sorted order. The Output indicates that element 35 could be inserted at position 3 to keep the sorted order.

Explanation:

• ✅ The program creates a sorted vector of integers.
• ✅ It defines a target value to search for (in this case, target = 6).
• ✅ It uses std::lower_bound to find the iterator pointing to the first element not less than the target.
• ✅ After that, the program outputs the original vector and the position of the first element, which is not less than the target.

Example:

Let us take a program to illustrate the use of std::set::lower_bound in C++:

#include <iostream>
#include <set>

int main() {
 // Create a set of integers
 std::set<int> mySet = {1, 2, 4, 5, 7, 8, 10};

 // Value to search for
 int target = 6;

 // Use std::set::lower_bound to find the iterator pointing to the first element not less than target
 auto it = mySet.lower_bound(target);

 // Output the result
 std::cout << "Set contains: ";
 for (int num : mySet) {
 std::cout << num << " ";
 }

 if (it != mySet.end()) {
 std::cout << "\nFirst element not less than " << target << " is: " << *it;
 } else {
 std::cout << "\nNo element not less than " << target << " found in the set.";
 }

 return 0;
}

Output:

Set contains: 1 2 4 5 7 8 10 
First element not less than 6 is: 7

In this example, the std::set::lower_bound function is used to see where 35 could be inserted in the Set to maintain the sorted order. The Output indicates that element 35 could be inserted at position 4 to keep the sorted order. If the component is not found, it returns an iterator pointing to the first element more significant than the target.

Explanation:

• ✅ The program creates a set of integers. The set is always sorted by default.
• ✅ It defines a target value to search for (in this case, target = 6).
• ✅ It uses std::set::lower_bound to find the iterator pointing to the first element that is not less than the target.
• ✅ After that, the program outputs the original set and the first element, which is not less than the target.

Conclusion:

The std::lowerbound is a generic algorithm that performs binary search to find the insertion point of a key in any sorted container, while std::set::lowerbound is a std::set member function that leverages the sets ordering to efficiently locate a key position or the next most significant element in logarithmic time. The former works universally on sorted ranges; the latter is optimized for operations on std::set containers.