stl map: get the <key,value> pair which has the minimum value

Discussion in 'C++' started by Rui Maciel, Dec 1, 2009.

  1. Rui Maciel

    Rui Maciel Guest

    Is there a pure STL way to get the <key, value> pair which has the minimum value of
    the map? I've tried the following but it wasn't very successful.

    <code>
    std::map<size_t,float> distance;
    // fill distance map
    size_t minimum = min_element(distance.begin(), distance.end(),
    distance.value_comp())->first;
    </code>


    Thanks in advance,
    Rui Maciel
     
    Rui Maciel, Dec 1, 2009
    #1
    1. Advertising

  2. Rui Maciel wrote:
    > Is there a pure STL way to get the <key, value> pair which has the minimum value of
    > the map? I've tried the following but it wasn't very successful.
    >
    > <code>
    > std::map<size_t,float> distance;
    > // fill distance map
    > size_t minimum = min_element(distance.begin(), distance.end(),
    > distance.value_comp())->first;
    > </code>


    What does it mean for "the <key, value> pair" to have "the minimum
    value"? The map is sorted on its key. To get the pair with the minimal
    key is to get '*begin()' (if the map is !empty()). Values do not
    participate in sorting. The simplest way to find the element with the
    minimal 'value' would be the linear search (iterating over the entire
    map). It is, of course, O(N).

    You could create another map essentially mirroring the first but with
    inverse ordering of types. It has to be a multimap, of course, since
    you can have duplicate 'float' in the first one. Then the other one
    will keep itself sorted, and you can always extract the *begin() from it
    (which should give you the minimal 'float').

    V
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
     
    Victor Bazarov, Dec 1, 2009
    #2
    1. Advertising

  3. Rui Maciel

    AndrewDover Guest

    I believe you wanted the pair which had the minimum float from the
    map.
    The answer comes from http://www.cplusplus.com/reference/algorithm/max_element/

    bool pairCompare( pair<size_t,float> i, pair<size_t,float> j)
    {
    return i.second < j.second;
    }


    std::map<size_t,float> distance;
    // fill distance map
    distance[ 1 ]= 1.3;
    distance[ 2 ]= 2.3;
    distance[ 3 ]= 0.2; // <- minimum
    distance[ 4 ]= 8.7;

    pair<size_t,float> p1= *distance.begin();

    pair<size_t,float> min = *min_element(distance.begin(), distance.end
    (), pairCompare );

    out << "begin pair is < " << p1.first << "," << p1.second << " > " <<
    endl;
    out << "min float is < " << min.first << "," << min.second << " > " <<
    endl;

    gives:

    begin pair is < 1,1.3 >
    min float is < 3,0.2 >

    Your .value_comp attempt does not do that: see
    http://www.cplusplus.com/reference/stl/map/value_comp/
     
    AndrewDover, Dec 1, 2009
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Patrick Guio
    Replies:
    6
    Views:
    3,227
    chris
    Oct 20, 2004
  2. sam
    Replies:
    1
    Views:
    677
    Gianni Mariani
    May 1, 2005
  3. Replies:
    2
    Views:
    562
    klaus hoffmann
    Feb 22, 2006
  4. Replies:
    2
    Views:
    3,434
    Kai-Uwe Bux
    Nov 6, 2006
  5. Replies:
    1
    Views:
    579
    Daniel Pitts
    Nov 16, 2007
Loading...

Share This Page