max_element in C++ STL

Parameters

std::max_element() takes the parameters mentioned below:

1. `first` (required): This parameter represents the iterator pointing to the first element of the range in which we want to find the maximum element. It can be the beginning iterator of a container (such as `std::vector`, `std::array`) or a pointer to the first element of an array.
 

2. `last` (required): This parameter represents the iterator pointing to the position one past the last element of the range. It can be the end iterator of a container or a pointer to one past the last element of an array. The range specified by `[first, last)` is a half-open range, meaning that the `last` iterator is not included in the range.
 

3. `comp` (optional): This parameter is a binary function or function object that defines the comparison criteria for determining the maximum element. It takes two elements of the range as arguments & returns `true` if the first element is considered less than the second element according to the desired comparison logic. If `comp` is not provided, the default `operator<` is used for comparison.
 

Let’s look at an example to understand the use of std::max_element() with and without the `comp` parameter:

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

int main() {
    std::vector<int> nums = {5, 2, 9, 1, 7};

    // Using default comparison (operator<)
    auto maxIt = std::max_element(nums.begin(), nums.end());
    std::cout << "Maximum element: " << *maxIt << std::endl;

    // Using custom comparison function
    auto maxIt2 = std::max_element(nums.begin(), nums.end(), [](int a, int b) {
        return a > b;
    });
    std::cout << "Maximum element (custom comparison): " << *maxIt2 << std::endl;

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Maximum element: 9
Maximum element (custom comparison): 1

In the first case, std::max_element() uses the default `operator<` for comparison & returns an iterator pointing to the maximum element (9).

In the second case, a custom comparison function is provided using a lambda expression. The lambda function returns `true` if `a > b`, effectively finding the minimum element instead of the maximum. As a result, the iterator returned points to the minimum element (1).

Return value

std::max_element() returns an iterator pointing to the maximum element in the specified range. The return type of std::max_element() is the same as the type of the input iterators (`ForwardIterator`).

If the range is empty, the function returns the `last` iterator.

If multiple elements in the range have the maximum value, the iterator returned points to the first occurrence of the maximum element.

Let’s discuss an example that shows the return value of std::max_element():

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

int main() {
    std::vector<int> nums = {5, 2, 9, 1, 9, 7};

    auto maxIt = std::max_element(nums.begin(), nums.end());

    if (maxIt != nums.end()) {
        std::cout << "Maximum element: " << *maxIt << std::endl;
        std::cout << "Index of maximum element: " << std::distance(nums.begin(), maxIt) << std::endl;
    } else {
        std::cout << "The range is empty." << std::endl;
    }

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Maximum element: 9
Index of maximum element: 2

In this example, std::max_element() returns an iterator pointing to the first occurrence of the maximum element (9) in the `nums` vector. We can dereference the iterator using `*maxIt` to access the maximum element itself.

We can also use the std::distance() function to find the index of the maximum element by calculating the distance between the beginning of the range & the iterator returned by std::max_element().

Always remember: It's important to check if the returned iterator is equal to the `last` iterator before accessing the maximum element. If the range is empty, dereferencing the `last` iterator would be undefined behavior.

More Examples of std::max_element()

Now, let’s take a few more examples to understand the use of std::max_element() in different situations:

1. Finding the maximum element in an array:

#include <algorithm>
#include <iostream>
int main() {
    int arr[] = {10, 5, 8, 20, 3};
    int size = sizeof(arr) / sizeof(arr[0]);

    int* maxIt = std::max_element(arr, arr + size);

    std::cout << "Maximum element: " << *maxIt << std::endl;

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Maximum element: 20

2. Finding the maximum element in a container using a custom comparison function

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

// Custom comparison function
bool compareAbsolute(int a, int b) {
    return std::abs(a) < std::abs(b);
}

int main() {
    std::vector<int> nums = {-5, 2, -9, 1, 7};

    auto maxIt = std::max_element(nums.begin(), nums.end(), compareAbsolute);

    std::cout << "Maximum element (absolute value): " << *maxIt << std::endl;

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Maximum element (absolute value): -9

3. Finding the maximum element in a range specified by iterators

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

int main() {
    std::vector<int> nums = {5, 2, 9, 1, 7};

    auto maxIt = std::max_element(nums.begin() + 1, nums.end() - 1);

    std::cout << "Maximum element in the range [1, 3): " << *maxIt << std::endl;

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Maximum element in the range [1, 3): 9

These examples explain clearly how std::max_element() can be used with arrays, custom comparison functions, & specific ranges within a container.

Working of std::max_element()

Now, let's learn how std::max_element() works internally to find the maximum element in a range.
 

1. The function starts by initializing two iterators, `first` and `last`, which represent the beginning and end of the range, respectively.
 

2. It assigns the `first` iterator to a variable, say `largest`, which will keep track of the iterator pointing to the maximum element found so far.
 

3. Then, it iterates over the range using a loop, starting from the second element (the element after `first`) up to the `last` element.
 

4. For each element in the range, it compares the element with the element pointed to by the `largest` iterator.

   - If the current element is greater than the element pointed to by `largest`, it updates `largest` to point to the current element.

   - If the `comp` function is provided, it uses `comp` to perform the comparison instead of the default `operator<`.
 

5. After the loop ends, the `largest` iterator will be pointing to the maximum element in the range according to the specified comparison criteria.
 

6. Finally, the function returns the `largest` iterator.

Let’s take a look at a more simplified implementation of std::max_element() to understand its working:

template <class ForwardIterator>
ForwardIterator max_element(ForwardIterator first, ForwardIterator last) {
    if (first == last) {
        return last;
    }

    ForwardIterator largest = first;
    ++first;

    for (; first != last; ++first) {
        if (*largest < *first) {
            largest = first;
        }
    }

    return largest;
}

In this code: 

• The function first checks if the range is empty by comparing `first` and `last`. If they are equal, it means the range is empty, and the function returns `last`.
   
• It initializes `largest` to `first`, assuming the first element is the maximum element so far.
   
• It starts a loop from the second element (`++first`) and iterates until `first` reaches `last`.
   
• Inside the loop, it compares the element pointed to by `largest` with the current element pointed to by `first` using `operator<`.
   
•   - If the current element is greater, it updates `largest` to `first`.
   
• After the loop ends, `largest` will be pointing to the maximum element, and the function returns `largest`.
   

Note: This is a simplified implementation for understanding purposes. The actual implementation of std::max_element() in the C++ Standard Library is more optimized and handles additional cases.

Complexity

Let's analyze the time and space complexity of std::max_element().

Time Complexity

• std::max_element() performs a single pass over the range, comparing each element with the current maximum element.
   
• The number of comparisons made is proportional to the number of elements in the range.
   
• Therefore, the time complexity of std::max_element() is O(n), where n is the number of elements in the range.
   
• This means that the function's running time grows linearly with the size of the input range.

Space Complexity

• std::max_element() uses only a constant amount of extra space.
   
• It does not allocate any additional memory that grows with the size of the input range.
   
• The space required is used for the iterators and any temporary variables, which are independent of the range size.
   
• Therefore, the space complexity of std::max_element() is O(1), indicating constant space usage.

Exceptions

std::max_element() does not throw any exceptions by itself. However, there are a few scenarios where exceptions can be thrown indirectly:

1. If the comparison function (`comp`) throws an exception during the comparison of elements, that exception will propagate out of std::max_element().
 

2. If the iterators passed to std::max_element() are invalid or do not form a valid range, the behavior is undefined. This can lead to exceptions or unexpected results, depending on the implementation.
 

3. If the elements in the range do not meet the requirements of the comparison function (e.g., if `comp` expects a certain type and the elements are of a different type), it may result in compilation errors or unexpected behavior.
 

Let’s look at an example that shows an exception thrown by the comparison function:

#include <algorithm>
#include <iostream>
#include <vector>
// Custom comparison function that throws an exception
bool compareWithException(int a, int b) {
    if (a < 0 || b < 0) {
        throw std::runtime_error("Negative values not allowed");
    }
    return a < b;
}

int main() {
    std::vector<int> nums = {5, 2, 9, -1, 7};

    try {
        auto maxIt = std::max_element(nums.begin(), nums.end(), compareWithException);
        std::cout << "Maximum element: " << *maxIt << std::endl;
    } catch (const std::exception& e) {
        std::cout << "Exception caught: " << e.what() << std::endl;
    }


    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Exception caught: Negative values not allowed

In this example, the custom comparison function `compareWithException` throws a `std::runtime_error` exception when it encounters negative values. When std::max_element() is called with this comparison function and the `nums` vector containing a negative value, the exception is thrown and caught in the `catch` block.

Note: It's important to ensure that the comparison function is well-defined and does not unexpectedly throw exceptions. Also, make sure to handle any potential exceptions thrown by the comparison function appropriately.

Frequently Asked Questions

What happens if the range passed to std::max_element() is empty? 

If the range is empty, std::max_element() returns the last iterator.

Can std::max_element() be used with custom types? 

Yes, std::max_element() can be used with custom types as long as they have a valid comparison operator or a custom comparison function is provided.

How does std::max_element() handle multiple occurrences of the maximum element? 

If there are multiple occurrences of the maximum element, std::max_element() returns an iterator pointing to the first occurrence.

Conclusion

In this article, we discussed the std::max_element() function in C++, which is used to find the maximum element in a given range. We covered its syntax, parameters, and return value with examples to understand the implementation properly. We also looked into the working of std::max_element(), analyzed its time and space complexity, and discussed the exceptions that can be thrown indirectly. std::max_element() provides a convenient and efficient way to find the maximum element in a container or range, which makes it an important function for any C++ programmer.

You can also check out our other blogs on Code360.