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

R

Rui Maciel

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>

Rui Maciel

V

Victor Bazarov

Rui said:
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

A

AndrewDover

I believe you wanted the pair which had the minimum float from the
map.

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/