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

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.

You can use std::min_element() and std::max_element() for unsorted vectors. Or just use std::sort() to sort the vector.

[edit]Drat. Beaten by moments![/edit]

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

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?

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.

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:

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)