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>


Thanks in advance,
Rui Maciel
 
Ad

Advertisements

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
 
Ad

Advertisements

A

AndrewDover

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/
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Top