# Min, max, sort in vector STL

• 02-28-2008
codeguy
Min, max, sort in vector STL
I have a vector of integers. I wanted to take out the minimum and maximum numbers from the set.

Is there an easy way to do this? Or do I need to sort the vector first? Is there a sort function for vectors? So I can just pop the "begin" and "end".

Thanks,
codeguy
• 02-28-2008
laserlight
You can find the minimum and maximum in linear time, so sorting is unnecessary. std::min_element and std::max_element could be used, or you could write the loop yourself and thus only make one pass over the vector.
• 02-28-2008
hk_mp5kpdw
You can use std::min_element() and std::max_element() for unsorted vectors. Or just use std::sort() to sort the vector.

Drat. Beaten by moments![/edit]
• 02-28-2008
matsp
Sorting the vector would be one way - the other way is to "walk the vector" and track the highest/lowest value - if you have no need to sort the vector for other reasons, a linear walk is highly likely to be the fastest solution. (walking the vector is O(n), where a quicksort is O(n * log n)).

--
Mats
• 02-28-2008
iMalc
Quote:

Originally Posted by codeguy
I have a vector of integers. I wanted to take out the minimum and maximum numbers from the set.

Is there an easy way to do this? Or do I need to sort the vector first? Is there a sort function for vectors? So I can just pop the "begin" and "end".

If you're calling it a set, then presumably you're treating it like a set, in which case why don't you actually just use a std::set?! Then you can access the smallest and largest in linear time with begin() and rbegin().
Can you do without random access? Would it be convenient if the items were always in order?
• 02-28-2008
laserlight
Quote:

If you're calling it a set, then presumably you're treating it like a set, in which case why don't you actually just use a std::set?! Then you can access the smallest and largest in linear time with begin() and rbegin().
Actually, I believe that would be constant time, not linear time.

But then "set" could just be accidental terminology.
• 02-28-2008
iMalc
Quote:

Originally Posted by laserlight
Actually, I believe that would be constant time, not linear time.

But then "set" could just be accidental terminology.

Yes of course - Thought one thing but wrote another! :rolleyes:
• 02-29-2008
carlorfeo
Quote:

Originally Posted by iMalc
why don't you actually just use a std::set?!

I agree that would be the easiest solution if you have no restrictions to use a <vector>.

Quote:

Originally Posted by codeguy
I have a vector of integers. I wanted to take out the minimum and maximum numbers from the set.

Is your vector filled at compile time?
Otherwise (if data are inserted in runtime) you might use two variables to keep track of the lowest/highest values during each insertion. (and deletion, if it occours)