C++ Multiset Upper Bound Function

In C++, the upper_bound function in the multiset container is a predefined function within the STL library. This function is frequently employed to retrieve an iterator that indicates the element in the multiset container which is greater than or equal to the specified val parameter.

In simpler terms, the multiset upperbound method in C++ determines the position of the next element that is greater than the specified value. This function is particularly valuable when dealing with duplicate elements since a multiset can store multiple identical keys. When all elements in the multiset are equal to or less than the specified key, the method points to the end of the multiset using an iterator (mset.end). The upperbound function operates with a time complexity of O(log n), making it an efficient choice for these operations.

Syntax:

It has the following syntax:

multiset_name.upper_bound(key)

iterator upper_bound (const key_type& key);

const_iterator upper_bound (const key_type& key) const;

In this particular format,

• ✅ Key: It denotes the value used for comparison with the components of the multiset. This value is the initial element sought by the function.
• ✅ Return Value: It provides an iterator pointing to the first element greater than the specified key within the multiset. If no such element exists, it returns an iterator pointing to the end of the multiset (mset.end).

C++ Simple Multiset upper_bound function Example

Let's consider an example to illustrate the multiset upper_bound function in C++.

Example

#include <iostream>

#include <set>

using namespace std;   //using standard namespace

int main() {    //main function

    multiset<int> numbers = {10, 20, 20, 30, 40, 50};

    auto it = numbers.upper_bound(20);

    cout << "Multiset elements: ";

    for (int num : numbers)

        cout << num << " ";

    if (it != numbers.end())

        cout << "\nThe upper bound of 20 is: " << *it;

    else

        cout << "\nNo element greater than 20 found.";

    return 0;

}

Output:

Multiset elements: 10 20 20 30 40 50 

The upper bound of 20 is: 30

Explanation:

In this instance, we establish a multiset comprising duplicate numbers. This is accomplished by invoking the upper_bound(20) function, leading to the identification of the initial number exceeding 20, which happens to be 30. The iterator associated with these functions will reference this number and display it as 30. Should there be no additional numbers, a declaration to that effect will be generated.

C++ Example to Find the Next Higher Element Using the upper_bound function

Let's consider a scenario to illustrate the process of determining the succeeding greater element using the upper_bound method in C++.

Example

#include <iostream>

#include <set>

using namespace std;   //using standard namespace

int main() {   //main function

    multiset<string> names = {"Johnson", "Michael", "Peter", "Peter", "Richard"};

    cout << "Multiset elements: ";

    for (auto &n : names)

        cout << n << " ";

    auto it = names.upper_bound("Peter");

    if (it != names.end())

        cout << "\nThe upper bound of Peter is: " << *it;

    else

        cout << "\nNo element greater than Peter found.";

    return 0;

}

Output:

Multiset elements: Johnson Michael Peter Peter Richard 

The upper bound of Peter is: Richard

Explanation:

In this instance, we are examining a multiset containing multiple string items arranged in lexicographical order. The initial name that surpasses "Peter" is "Richard", and it is referenced in the upper_bound("Peter") function call. If the highest element in the set were "Peter", the iterator would lead us to the conclusion of the set.

C++ Multiset upper_bound function example with a loop

Let's consider an example to illustrate the multiset upper_bound method within a loop in C++.

Example

#include <iostream>

#include <set>

using namespace std;   //using standard namespace

int main() {  //main function

    multiset<int> data = {2, 4, 6, 8, 10, 12};

    for (int i = 4; i <= 10; i += 2) {

        auto it = data.upper_bound(i);

        if (it != data.end())

            cout << "The upper bound of " << i << " is " << *it << endl;

        else

            cout << "The upper bound of " << i << " not found" << endl;

    }

    return 0;

}

Output:

The upper bound of 4 is 6

The upper bound of 6 is 8

The upper bound of 8 is 10

The upper bound of 10 is 12

Explanation:

In this instance, we are working with an integer multiset called data, which is set up with values {2, 4, 6, 8, 10, 12}. Subsequently, we have applied the upperbound method within a loop. Following this, the upperbound operation provides the succeeding greater element from the multiset for each key (4, 6, 8, 10). If there is no higher element present in the multiset, it indicates that another upper_bound is not available.

Features of the Multiset upper_bound function in C++

Several features of the multiset upper_bound function in C++ are as follows:

• ✅ It is commonly utilized to return an iterator pointing to the first element, which is greater than the particular key in the STL multiset.
• ✅ We can use the multiset upperbound function with the lowerbound function to perform several tasks to find all occurrences of the specified key.
• ✅ It enables a custom comparator, which allows us to define our own sorting logic when we find the upper_bound function in C++.
• ✅ We can use the multiset upper_bound function in several fields that perform their operations on ordered datasets, such as searching, sorting, range-handling algorithms, and many others.
• ✅ It can be utilized with several STL containers and can be utilized with any data type, including integers, strings, custom objects, and many others.

Conclusion

Ultimately, the C++ multiset::upperbound method proves to be a highly valuable and effective tool. This function returns the initial element in the multiset that is greater than a specified key, in ascending order. It is particularly handy for determining the scope of identical keys or identifying the immediate larger value in scenarios involving collections with repetitive elements. Thanks to its logarithmic time complexity, it enables swift searches within organized data structures. Overall, the upperbound operation enhances the ease of managing associative ordered containers like a multiset.

C++ Multiset upper_bound function FAQ's

The multiset::upper_bound function in C++ is utilized to locate the iterator pointing to the first element in the container that is strictly greater than a specified value.

In C++, the upper_bound method proves to be beneficial for obtaining an iterator pointing to the initial element in the multiset that exceeds the specified key. This function efficiently assists in locating the next highest value within a range of elements.

What occurs when there is no element in C++ that is larger than the specified key?

If no element surpasses the provided key, it will yield an iterator pointing to mset.end, signaling that the search has reached the end of the multiset.

Yes, the upper_bound function can be applied to a multiset in C++ even when it contains duplicate values.

Yes, the C++ upper_bound function functions accurately for duplicate values. It returns the iterator pointing to the first element that is strictly greater than the given key, excluding any elements that are equal to that key.

The time complexity of the multiset::upper_bound function in C++ is logarithmic, denoted as O(log n).

In C++, the upper_bound method operates with a time complexity of O(log n) due to its utilization of a balanced binary search approach (such as a red-black tree) internally for storing elements in memory.

5) How does the functionality of upperbound in a multiset differ from that of lowerbound in C++?

In C++, the lowerbound(key) method provides an iterator pointing to the first element that is equal to or greater than the specified key (≥). In contrast, the upperbound(key) function gives an iterator pointing to the first element that is strictly greater than the key (>).