Thread: Min, max, sort in vector STL

  1. #1
    Registered User
    Join Date
    Jan 2008
    Posts
    4

    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

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    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]
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by codeguy View Post
    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?
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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 Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by laserlight View Post
    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!
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  8. #8
    coder
    Join Date
    Feb 2008
    Posts
    127
    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)

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. need help finding the max and min of a 2d array
    By finalreign in forum C Programming
    Replies: 6
    Last Post: 04-29-2009, 11:39 AM
  2. Max Min Problem
    By smithc2005 in forum C Programming
    Replies: 7
    Last Post: 10-22-2008, 10:38 AM
  3. Ranged numbers
    By Desolation in forum Game Programming
    Replies: 8
    Last Post: 07-25-2006, 10:02 PM
  4. Game of life
    By JoshR in forum C++ Programming
    Replies: 30
    Last Post: 04-03-2005, 02:17 PM
  5. Double output!
    By Spurnout in forum C++ Programming
    Replies: 3
    Last Post: 11-02-2002, 03:35 AM