C++ Finding the index of the largest element in an array, even if there is multiple max elements

Question

I found a way to search for the index of the largest element in an array. However, it doesn't work properly when the array has more than one element with the same max value. The way I used to find the index is with std::max_element(), but this might not be the solution.

#include <iostream>

using namespace std;

int main()
{
    int age[8];
    int num = sizeof(age) / sizeof(int);

    cout << "Type the age from 8 employees\n";
    
    for (int i = 0; i < 8; i++)
    {
        cout << "Age " << i+1 << ": ";
        cin >> age[i];
    }
    cout << "______________________________________________________" << endl;   
    cout << "\nOlder age found in position: " << max_element(age, age + num + 1) - age;

I hope I can resolve this using int array[] since I started programming a few days ago, but if I have to use another type of array, let me know so I can go and learn about it.

Answer 1

The problem with your program is the second argument to max_element(), it should be a pointer to one passed the last element. It should be either age + 8 or &age[8], 8 being the size of your array. Both are the address to one passed the last element of the array, as required. In C++, last or end is one passed the last value.

Here is a simplified example of how to use max_element() with pointers. To make it simpler, I initialized a couple of arrays with values instead of reading them from the stdin like you are doing:

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int age_uniq[8] = {67, 34, 22, 54, 78, 49, 4, 9};
    int age_rep[8] = {79, 34, 22, 54, 78, 49, 79, 9};
    
    int* oldest = max_element(age_uniq, age_uniq+8);
    cout << "oldest: " << *oldest << ", index = " << oldest - age_uniq << "\n";
    
    oldest = max_element(age_rep, age_rep+8);
    cout << "oldest: " << *oldest << ", index = " << oldest - age_rep << "\n";
}

This code works as expected, and when it has more than one max value, it returns the first.

The first thing to notice is that max_element() returns a forward iterator, which in this case is an integer pointer, since that's what your passing to it.

The second thing that you need to learn is pointer arithmetic. When you subtract two pointers of the same type, in this case pointers to int, it already takes into account the size of an integer, and it gives you the distance between the pointers. Therefore, oldest - age gives you the index of oldest.

Also, sizeof(age) gives you the size in bytes of the pointer, which depending on the system where you run your program may be 32, 64, or something else. It is not the size of your array, which in this case is 8. Similarly, sizeof(int) gives you the size of an int, which will vary depending on the system that you're running your program.

Answer 2

However, it doesn't work properly when the array has more than one element with the same max value...

You have not given any clarification on the current behaviour and expected behaviour when array has more than one element with the same max value. I am assuming that the expected behaviour is to get the last max element index, when there are more than one occurrence of max element in the array, because the max_element() will give the iterator to first max element as it use operator< to compare the elements of container, which you are already doing in your program.

Your program is having undefined behaviour because its accessing array element beyond the size of array:

max_element(age, age + num + 1)

here, the max_element() will end up accessing array beyond its size -

age + num + 1 -> age + 8 + 1 -> age + 9

You should not add 1 to age + num.

There is a overload of max_element() library function which takes the comparison function object as argument, which returns ​true if the first argument is less than the second. The signature of the comparison function should be equivalent to the following:

 bool cmp(const Type1 &a, const Type2 &b); 

So, you can write your own comparator function which will return true when the first argument is <= second, like this:

bool mycompare (const int& lhs, const int& rhs) {
    // Using <= operator, so that we get last occurrence of max element in  
    // the array if max element has more than one occurrence in the given array
    return lhs <= rhs;
}

and pass it to max_elemene() library function

std::max_element(age, age + num, mycompare)
                                 ^^^^^^^^^

Make these changes in your program and check.

I hope I can resolve this using int array[] since I started programming a few days ago, but if I have to use another type of array, let me know so I can go and learn about it.

The C++ has Containers Library, go through it. For the time being, sequence container array and vector will be of our interest. When working in C++ language, it is discouraged to use plain C style array, instead, you should use either array or vector based on your requirement. I will suggest you to use the vector so that you can give different set of inputs and no need to take care of size every time if the input size is different.

Read about std::begin, std::end and std::distance. With all these, you don't need to find number of elements in your container and don't need to do pointer arithmetic to calculate the index of max_element() returned iterator.

Putting these altogether, implementation of finding index of largest element (index of last occurrence, when largest element has more than one occurrence in input set of elements):

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

bool mycompare(const int& lhs, const int& rhs) {
    // Comparing with <= operator to get the index of last occurrence of largest
    // element in the array, if it occur multiple times in array.
    return lhs <= rhs;
}

int main() {
    std::vector<int> age;
    int num;

    std::cout << "enter number of elements in age array : " << std::endl;
    std::cin >> num;

    for (int i = 0; i < num; ++i) {
        int input;
        std::cout << "Age " << i + 1 << ": ";
        std::cin >> input;
        age.push_back (input);
    }
    
    std::cout << "The index of largest element is : " 
              << std::distance (age.begin(), 
                           std::max_element (age.begin(), age.end(), mycompare))
              << std::endl;
    
    return 0;
}

Output:

# ./a.out
enter number of elements in age array : 
3
Age 1: 45
Age 2: 23
Age 3: 45
The index of largest element is : 2

# ./a.out
enter number of elements in age array : 
5
Age 1: 32
Age 2: 45
Age 3: 67
Age 4: 88
Age 5: 56
The index of largest element is : 3

If you are aware of Lambda Expression, you can use it in place of mycompare(), like this:

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

int main() {
    std::vector<int> age;
    int num;

    std::cout << "enter number of elements in age array : " << std::endl;
    std::cin >> num;

    for (int i = 0; i < num; ++i) {
        int input;
        std::cout << "Age " << i + 1 << ": ";
        std::cin >> input;
        age.push_back(input);
    }

    std::cout << "The index of largest element is : " 
              << std::distance (age.begin(),
                                std::max_element(age.begin(), age.end(),
                                [](const int& lhs, const int& rhs){
                                      return lhs <= rhs;
                                })) 
              << std::endl;

    return 0;
}

---

Suggestions:

1). Avoid adding using namespace std; in your program. Check this.

Answer 3

You should use std::max_element with programs that use std::vector or more complex ways of listing objects. For this case, you should make your own function to find the index of the max value. There are a lot of algorithms, here is one you can add after your first for cycle:

int num_index = 0; //starts at zero so we can analyze from the first element of the array
for (int i = 0; i < 8; i++)
{
    if (age[num_index] < age[i]) //compare the "big" element with the actual element
    { 
        num_index = i; //if its smaller, the new big number index will update
    }
}

At the end of this cycle, num_index will be containing the number of the index with the biggest value in the array, but only the first one, if there are more index with the same value it won't save them. In order to show you the other indexes that are equal you can do the following:

cout << "______________________________________________________" << endl;
cout << "\nOlder age(s) found in position(s): "; 
for (int i = 0; i < 8; i++)
{
    if (age[num_index] == age[i])
    {
        cout << i+1 << "; "; //print all positions that have max value
    }
}

For the first code segment, you can make a function that would work for any array:

int index_max_value (int *array, int size)
{
    int num_index = 0;
    for (int i = 0; i < size; i++)
    {
        if (array[num_index] < array[i])
        {
            num_index = i;
        }
    }
    return num_index; //returns the first array index that contains the largest element
}

Then you would be adding it in the second code segment, in the if condition:

cout << "______________________________________________________" << endl;
cout << "\nOlder age(s) found in position(s): "; 
for (int i = 0; i < 8; i++)
{
    if (age[index_max_value(age, 8)] == age[i]) //compare which indexes have the same value
    {
        cout << i+1 << "; "; //print all positions that have max value
    }
}

With all of this you won't be needing to use this:

int num = sizeof(age) / sizeof(int);

These websites will help you get more familiarized with the C++ language: Cpp Reference, W3Schools, Cplusplus.