finding max and min integers - newbie question

[Chris Theis]

once?

This may be solution sometimes, but generally it is bad idea:
- if you put such code to function like find_min_max() - nobody will
expect that this function will modify this vector, and it may get
const argument
- if you will copy instead of in-place sort it can eat much memory
- sorting is much slower than just reading all values once (and 2
comparisons)
- etc.

IMHO worst of all is that you will modify original vector, which may be
not acceptable.

You are of course absolutely right. The sorting will only do the trick in
case modifications of the data structure are allowed!

Chris

 

[Chris Theis]

"At once?" Why would one replace an O(N) operation with an O(N log N)
operation requiring more storage?

At once was actually meant considering only one statement has to issued
instead of two. Although this comes of course at the prerequisite that the
original data structure is alterable. However, why not use an automatically
sorted collection like a set as no constraint on the type of collection was
given.

Chris

 

[Gianni Mariani]

Hi

I'm a learner and I'm trying to work out the simplest way of finding
the maximum and minimum value from a group of integers.

Any help would be appreciated.

John

Below you'll find an STL algorithm look-alike that does the job.

The trick with most of these search for min, max or both is that in the
limiting case of one element, that element is the min and max this
implies that setting the min and max to the first element in the search
leaves the main algorithm simplier in having to deal with that case.

Returning values from the find_min_max algorithm is trickier in that it
is preferable to not limit the utility of the function template. This
leads to returning "iterators" (or pointers) since the objects may not
be copy-constructible. Also, if the object is large and costly to copy,
it is preferable that an iterator or a pointer is returned.

Below there are 2 find_min_max() functions, one that returns a struct
containing results and one that sets parameters to the min and max.
These methods should be easily inlineable which means this should be as
fast or faster than hand-written code.


template <typename w_value_t>
struct pair_return
{
bool found;
w_value_t first;
w_value_t second;

pair_return()
: found( false )
{
}

pair_return( w_value_t l_first, w_value_t l_second )
: found( true ),
first( l_first ),
second( l_second )
{
}
};



template <typename w_iterator_t >
pair_return<w_iterator_t> find_min_max(
w_iterator_t i_begin,
w_iterator_t i_end
)
{

if ( i_begin == i_end )
{
return pair_return<w_iterator_t>();
}

w_iterator_t l_min_iter = i_begin;
w_iterator_t l_max_iter = i_begin;

for ( ++ i_begin; i_begin != i_end; ++ i_begin )
{
if ( ( * l_max_iter ) < ( * i_begin ) )
{
l_max_iter = i_begin;
}
else if ( ( * i_begin ) < ( * l_min_iter ) )
{
l_min_iter = i_begin;
}
}

return pair_return<w_iterator_t>( l_min_iter, l_max_iter );
}

template <typename w_iterator_t, typename w_value_t>
bool find_min_max(
w_iterator_t i_begin,
w_iterator_t i_end,
w_value_t & o_min_val,
w_value_t & o_max_val
)
{
pair_return<w_iterator_t> ret_val = find_min_max( i_begin, i_end );

if ( ! ret_val.found )
{
return false;
}

o_min_val = * ret_val.first;
o_max_val = * ret_val.second;

return true;
}


//
// test code.
//

int vals[] = { 4, 2, 5, 2 };
int val2[] = { 4 };

#define NELEM( X ) ( sizeof(X)/sizeof(*X) )

#include <iostream>

template <typename w_value_t>
void pair_out( const pair_return< w_value_t > & v )
{
if ( v.found )
{
std::cout << "min = " << * v.first
<< " max = " << * v.second << "\n";
}
else
{
std::cout << "list empty\n";
}
}


int main()
{

pair_return<int *> t1 = find_min_max( vals, vals + NELEM( vals ) );

pair_out( t1 );

pair_return<int *> t2 = find_min_max( vals, vals );

pair_out( t2 );

pair_return<int *> t3 = find_min_max( vals, vals + 1 );

pair_out( t3 );

int min;
int max;
if ( find_min_max( vals, vals + NELEM( vals ), min, max ) )
{
std::cout << "min = " << min << " max = " << max << "\n";
}

}

 

[Gianni Mariani]

Kamil Burzynski wrote:
....

Ah, yes, I didnt saw it. Thats the reason I always put brackets, too
Long time ago I didnt.. but after wasting 2 days hunting such stupid bug
I've learned it

Allelujia - I'm amazed at how many programmers just don't get it.

 

[Ron Natalie]

At once was actually meant considering only one statement has to issued
instead of two. Although this comes of course at the prerequisite that the
original data structure is alterable. However, why not use an automatically
sorted collection like a set as no constraint on the type of collection was
given.

Because frequently the order in the sequence is important as a distinct
entity from the sorting order.

And the question about complexity still holds. he sum of the insertions into the set are
the same order as the sort.
\

 

[Jeff Schwab]

At once was actually meant considering only one statement has to issued
instead of two. Although this comes of course at the prerequisite that the
original data structure is alterable. However, why not use an automatically
sorted collection like a set as no constraint on the type of collection was
given.

Thanks for trying to explain, but I'm still not sure what you mean. How
can you retrieve the min and max element in a single statement, even if
you sort the collection?

Also, as Ron said, a sorted collection is heavier and less flexible than
a vector-like sequence, and the complexity of inserting all elements is
still O(N log N).

 

[Chris Theis]

[SNIP]

Thanks for trying to explain, but I'm still not sure what you mean. How
can you retrieve the min and max element in a single statement, even if
you sort the collection?

What I meant is that from a sorted collection the first and the last element
is automatically the min & the max (if sorted ascending). Thus you will not
need to call min_element, max_element of which both will loop over the
container to obtain the respective element. However, the sorting solutions
has of course limited usability due to the requirement that the original
order does not need to be retained.

Also, as Ron said, a sorted collection is heavier and less flexible than
a vector-like sequence, and the complexity of inserting all elements is
still O(N log N).

Regarding the runtime complexity you and Ron are of course right. IMHO the
applicability depends very much on the number of elements you're dealing
with and how much you have to care about performance issues.

Regards
Chris

 

[Andrey Tarasevich]

...
Why not sort the vector and thus you have the min & the max value at once?
...

Because it is an overkill that will generate more heat than light.
Sorting the vector might work in case when one needs to find min/max
elements repeatedly, excluding previously found elements from
consideration. But even in this case sorting the entire vector is
justified only if the number of requests is relatively large (close to
the total number of elements in the vector). Otherwise, turning the
vector into a heap (see 'std::make_heap') might prove to be a more
efficient solution.

 

[Philipp Bachmann]

Why not sort the vector and thus you have the min & the max value at once?

I.m.o. this could be indeed an option. John, the original poster, talks about
"a group of integers". This is open to interpretation and thus open to many
different implementations. It depends on what operations besides finding the
bounds John wants also apply to his "group". So if he e.g. wants to compute
the union or the intersection of two or more "groups", he actually means
"set", which can easily be implemented as "std::set<>" - and now he gets his
bounds for free:

(Just a sketch - I didn't try to compile...)

typedef int element_t;
const element_t initial[] = { -7, 42, 13 };
std::set< element_t > s(initial,initial+sizeof(initial)/sizeof(initial[0]));
if(s.end()!=s.begin())
std::cout<<"Min = "<<*s.begin()<<", Max = "<<*(s.end()-1)<<"."<<std::endl;

You need a "std::set<>" if you indend to apply set-related operations -
otherwise the performance of e.g. the calculation of the union will degrade.

Cheers,
Philipp.

 

[red floyd]

const element_t initial[] = { -7, 42, 13 };
std::set< element_t > s(initial,initial+sizeof(initial)/sizeof(initial[0]));
if(s.end()!=s.begin())
std::cout<<"Min = "<<*s.begin()<<", Max = "<<*(s.end()-1)<<"."<<std::endl;

Is a std::set<>::iterator a random access iterator?

Wouldn't this:

std::cout << "Min = " << *s.begin()
<< ", Max = " << " << *s.rbegin()
<< "." << std::endl;

be better (in case it isn't a RA iterator)?

 

[Ron Natalie]

Is a std::set<>::iterator a random access iterator?

It's only required to be a bi-directional iterator.

 

[Christoph Rabel]

I'm a learner and I'm trying to work out the simplest way of finding
the maximum and minimum value from a group of integers.

While the following isn't the simplest way of finding the
min & max, it is a very fast way.

The simple approach already shown in this thread needs to
compare about 2 * N times, while the following approach only
needs to compare 3/2 * N times.

It compares two integer in the container and then the lower
with min and the higher with max.


pair<int, int> find_min_max(vector<int> const& data)
{
// Maybe throw here
assert(data.size());

int min = data[0];
int max = data[0];

int pos = data.size() % 2;

for (; pos < data.size()
{
if (data[pos] < data[pos + 1])
{
if (data[pos] < min) min = data[pos];
if (data[pos + 1] > max) max = data[pos + 1];
}
else
{
if (data[pos + 1] < min) min = data[pos + 1];
if (data[pos] > max) max = data[pos];
}
pos += 2;
}
return pair<int, int> (min, max);
}

hth

Christoph

 

[Old Wolf]

I'm a learner and I'm trying to work out the simplest way of finding

Assuming they are already in a non-empty vector (std::vector<int>) called
"vec":

#include <algorithm>
int minValue = *(std::min_element(vec.begin(), vec.end()));
int maxValue = *(std::min_element(vec.begin(), vec.end()));

This takes about twice as long as finding them both simultaneously (as in
Hendrik's solution), but it is simple ...

Here is an alternative (note: this is more for my own benefit,
when people point out how to improve on it, than to actually
answer the OP's question)

#include <utility>

template<typename It, typename Comp>
std:air<It, It> min_max_elements (It begin, It end, Comp comp)
{
std:air<It, It> m(begin, begin);

for (; begin != end; ++begin)
{
if (comp(*begin, *m.first))
m.first = begin;
if (!comp(*begin, *m.second))
m.second = begin;
}
return m;
}


Example fragment of usage:
int arr[] = { 5, 3, 1, 2, 4 };
std:air<int *, int *> minmax
= min_max_elements(arr, arr+5, std::less<int>());
std::cout << "min = " << *minmax.first << ", "
<< "max = " << *minmax.second << '\n';

 

[Philipp Bachmann]

Red Floyd and Ron,

thanks for pointing this out!

Cheers,
Philipp.

 

[Chris Theis]

I'm a learner and I'm trying to work out the simplest way of finding
the maximum and minimum value from a group of integers.

While the following isn't the simplest way of finding the
min & max, it is a very fast way.
[SNIP]
pair<int, int> find_min_max(vector<int> const& data)
{
// Maybe throw here
assert(data.size());

int min = data[0];
int max = data[0];

int pos = data.size() % 2;

for (; pos < data.size()
{
if (data[pos] < data[pos + 1])
{
if (data[pos] < min) min = data[pos];
if (data[pos + 1] > max) max = data[pos + 1];
}
else
{
if (data[pos + 1] < min) min = data[pos + 1];
if (data[pos] > max) max = data[pos];
}
pos += 2;
}
return pair<int, int> (min, max);
}

The approach is indeed nice. But why not simply write:

template <typename T>
pair<T, T> FindMinMax( const vector<T>& Data)
{
assert(Data.size());

T MinVal, MaxVal;
MinVal = MaxVal = Data[0];

for( int Pos = Data.size() % 2; Pos < Data.size(); Pos +=2 ) {
if( Data[Pos] < Data[Pos + 1]) {
MinVal = min( Data[Pos], MinVal);
MaxVal = max( Data[Pos+1], MaxVal);
}
else {
MinVal = min( Data[Pos + 1], MinVal);
MaxVal = max( Data[Pos], MaxVal);
}
}
return pair<T, T> (MinVal, MaxVal);
}

or even shorter (though more for lovers of the obfuscated C contest)

template <typename T>
pair<T, T> FindMinMax( const vector<T>& Data)
{
assert(Data.size());
T MinVal, MaxVal;
MinVal = MaxVal = Data[0];

for( int Pos = Data.size() % 2; Pos < Data.size(); (Data[Pos] < Data[Pos +
1]) ? (MinVal = Data[Pos] < MinVal ? Data[Pos] : MinVal), (MaxVal =
Data[Pos + 1] > MaxVal ? Data[Pos + 1] : MaxVal) : (MinVal = Data[Pos + 1] <
MinVal ? Data[Pos + 1] : MinVal, MaxVal = Data[Pos] > MaxVal ? Data[Pos] :
MaxVal), Pos +=2 ) {}

return pair<T, T> (MinVal, MaxVal);
}

Regards
Chris

 

[Risto Lankinen]

Hi!

or even shorter (though more for lovers of the obfuscated C contest)

template <typename T>
pair<T, T> FindMinMax( const vector<T>& Data)
{
assert(Data.size());
T MinVal, MaxVal;
MinVal = MaxVal = Data[0];

for( int Pos = Data.size() % 2; Pos < Data.size(); (Data[Pos] < Data[Pos +
1]) ? (MinVal = Data[Pos] < MinVal ? Data[Pos] : MinVal), (MaxVal =
Data[Pos + 1] > MaxVal ? Data[Pos + 1] : MaxVal) : (MinVal = Data[Pos + 1] <
MinVal ? Data[Pos + 1] : MinVal, MaxVal = Data[Pos] > MaxVal ? Data[Pos] :
MaxVal), Pos +=2 ) {}

return pair<T, T> (MinVal, MaxVal);
}

Excellent answer to a newbie question (see message title).

Alas, while at it, why didn't you use recursion instead of the
loop, and additional function arguments instead of the local
variables? The whole function body could then have been
expressed with just one return statement - the ultimate in
conciseness and simplicity for the benefit of all newbies!



- Risto -

 

[Karl Heinz Buchegger]

Alas, while at it, why didn't you use recursion instead of the
loop, and additional function arguments instead of the local
variables? The whole function body could then have been
expressed with just one return statement - the ultimate in
conciseness and simplicity for the benefit of all newbies!

Now that you say it:

int FindMin( int* Data, int Size )
{
return ( Size == 1 ) ? *Data : min( *Data, FindMin( Data++, Size-1 ) );
}

FindMax left as an exercise to the OP



Translation to std::vector and iterators left as an exercise to Chris

 

[Chris Theis]

Hello!

[SNIP]

Excellent answer to a newbie question (see message title).

The second way to implement Christoph's solution is certainly not for
newbies but rather for competitors of the obfuscated C(++) contest as I
already indicated. Anyway, Christoph already wrote in his post, that this
solution is not the simplest but a fast one. If you read the rest of the
postings you'll find that the obvious and trivial solution to this problem
has been posted days ago.

Alas, while at it, why didn't you use recursion instead of the
loop, and additional function arguments instead of the local
variables? The whole function body could then have been
expressed with just one return statement - the ultimate in
conciseness and simplicity for the benefit of all newbies!

Which is certainly a good idea and Karl Heinz already supplied the solution


Cheers
Chris

 

[tom_usenet]

Hi

I'm a learner and I'm trying to work out the simplest way of finding
the maximum and minimum value from a group of integers.

Any help would be appreciated.

You can use std::min_element or std::max_element, but here is a
similar generic algorithm that combines them:

#include <utility>
#include <iterator>
#include <functional>

template <class FwdIt, class Comp>
std:air<FwdIt, FwdIt>
min_max_element(FwdIt begin, FwdIt end, Comp comp)
{
if (begin == end)
return std:air<FwdIt, FwdIt>(end, end);
FwdIt min = begin;
FwdIt max = begin;
for(++begin; begin != end; ++begin)
{
if (comp(*begin, *min))
min = begin;
else if (comp(*max, *begin))
max = begin;
}
return std:air<FwdIt, FwdIt>(min, max);
}

template <class FwdIt>
inline std:air<FwdIt, FwdIt> min_max_element(FwdIt begin, FwdIt end)
{
return min_max_element(
begin,
end,
std::less<typename std::iterator_traits<FwdIt>::value_type>()
);
}

To use it:

int array[100] = {lots of numbers};

std:air<int*, int*> min_max = min_max_element(array, array + 100);
int min = *min_max.first;
int max = *min_max.second;

Tom

C++ FAQ: http://www.parashift.com/c++-faq-lite/
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html

 

[Chris Theis]

[SNIP]

Translation to std::vector and iterators left as an exercise to Chris

The following pops out of my head as a first idea

int FindMin( vector<int>::iterator Begin, vector<int>::iterator End ) {
return (Begin != End) ? min( *Begin, FindMin( Begin + 1, End) ) :
*(Begin-1);
}

However, there might be more efficient solutions

Chris