Finding the largest element in a vector / array vs vector

[hbcpp]

I have a school assignment, even though the class teaches C, my teacher said it is ok for me to use C++ since I have been programming in C++ for a while now.

So in the assignment, I have to store multiple elements in a variable and then find the largest for later use.

The number of elements of elements is given by the user so I decided to use a raw array, and everything is working fine.

double vec[number_of_elements];

But I have been having second thoughts so that maybe I have to make it a more C++ish assignment and use a std::vector instead.

std::vector<double> vec(number_of_elements);

To find the largest element in the array I use this code:

double maxValue(double vec[], int array_size)
{
    double val_max = vec[0];

    for(int i = 0; i < array_size; ++i)
    {
        if(val_max < vec[i])
        {
            val_max = vec[i];
        }
    }

    return val_max;
}

And for the vector I would just use:

double max_val = * std::max_element(vec.begin(), vec.end());

So which approach would be better, knowing that I find std::vector approach cleaner but that I want to show the teacher that I know the sorting algorithm to find the largest element??

Is there any performance notes between the two that I should take into consideration??

[lastchance]

I think you would impress the teacher most (and provide a cross-check between distinct codes) if you actually handed in BOTH.

At first sight, I feel that std::max_element() ought to be slightly quicker, as (1) the STL is a highly-optimised selling-point feature of C++; (2) if there was no rearrangement of instructions then it is quicker just to step through points in contiguous memory than continually call the [] operation; (3) there exist opportunities for divide-and-conquer parallelisation.

However, in reality, (a) compilers have very impressive optimisation ability that make it impossible to second-guess how they will actually rearrange this; (b) comparison operations like this are so fast that any time differences would be impossible to measure (by contrast with complex mathematical functions like exp() say).

At the end of the day, the single statement max_element() makes it immediately clear what your intent is, and clearer code makes for less opportunities for bugs and easier reading by other people. Incidentally, you can use max_element for normal arrays V[] as well as vectors:
double max_val = * std::max_element(V, V+array_size);

A place where vectors score particularly highly is where array sizes change during a run; for example, reading files where the total number of elements is not known in advance. They also perform "safer" dynamic allocation and deallocation when a run-time size of an array is constant but not known in advance. Places where they aren't quite so convenient - interfacing with other languages, or distributed-memory parallelisation - aren't likely to concern you.


And one final shout-out for another type of array - if you have a
valarray<double> V(N);
then you can get the maximum by a simple method: V.max(). This is much closer to what happens in other languages with arrays.

[keskiverto]

What lastchance said.
When you show your loop, you reveal whether you comprehend the necessary logic.
When you use standard algorithm, you demonstrate your ability to use C++ effectively.

Your function works with vector too (with tiny change):

double maxValue( const std::vector<double>& vec )
{
    double val_max = vec[0]; // What could go wrong on this line?

    for ( int i = 0; i < vec.size(); ++i ) // Is the first element necessary?
    {
        if ( val_max < vec[i] )
        {
            val_max = vec[i];
        }
    }
    return val_max;
}

and std::max_element with array:

double vec[number_of_elements];
double max_val = * std::max_element( vec, vec + number_of_elements );

[ne555]

> The number of elements of elements is given by the user
> so I decided to use a raw array, and everything is working fine.
> double vec[number_of_elements];
if you mean like

int number_of_elements;
cin >> number_of_elements;
double vec[number_of_elements];

that's called a variable length array (VLA), and they are not legal in c++ (but they are on c)


> the single statement max_element() makes it immediately clear what your intent is
such as the single statement maxValue

also

#include <iterator>
std::max_element(begin(vec), end(vec));

will work with `vec' as a vector or an array (not a VLA)

[hbcpp]

Thank you guys for the replies, I much appreciate them.

[dhayden]

What else are you doing with those numbers? If you aren't doing anything with them then the right thing to do is to not store them in an array at all.

Is there any performance notes between the two?

The STL probably won't compare the zero'th item to itself. Also it will handle the case of an empty range and return the second iterator, which is out of bounds. Also it does the more useful thing of returning an iterator to the largest item rather than the largest item itself. That way you can do other things, like remove the largest item.

[hbcpp]

@dhayden

The numbers are meant to be used to build a histogram.

[dhayden]

The numbers are meant to be used to build a histogram.

Well that's an entirely different problem. If you're given the boundaries of the histogram buckets then you don't need the maximum element. Otherwise you probably need to find the maximum and minimum elements, which should be done in a single pass. So at most it's one pass to find the min and max, and a second pass to place the items in the buckets.

[hbcpp]

I wasn't given the boundaries.

Wha do mean by:

which should be done in a single pass

?

[keskiverto]

While you can get the smallest and largest values separately, essentially with two loops:

double min_val = * std::min_element( vec, vec + number_of_elements );
double max_val = * std::max_element( vec, vec + number_of_elements );

You can also collect both values simultaneously, in one loop.
Standard Library's method: http://www.cplusplus.com/reference/algorithm/minmax_element/

[dhayden]

What do mean by:
which should be done in a single pass

I mean that you can find both the minimum and the maximum values with one "for" loop. See Keskiverto's post above for the standard library functions to find this stuff.

[lastchance]

#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

void histogram( vector<int> A, bool scaled=false, int maxwidth=40 )
{
   if ( scaled )
   {
      double factor = (double)maxwidth / *max_element( A.begin(), A.end() );
      for ( auto &e : A ) e = e * factor + 0.5;
   }

   for ( int i = 0; i < A.size(); i++ ) cout << setw(2) << i << ": " << string( A[i], '*' ) << '\n';
}


int main()
{
   vector<int> data{ 2, 5, 20, 4, 6, 8, 9 };

   cout << "Unscaled:\n";
   histogram( data );

   cout << "\n\nScaled to width 50:\n";
   histogram( data, true, 50 );
}

Unscaled:
 0: **
 1: *****
 2: ********************
 3: ****
 4: ******
 5: ********
 6: *********


Scaled to width 50:
 0: *****
 1: *************
 2: **************************************************
 3: **********
 4: ***************
 5: ********************
 6: ***********************