STL algorithm to find max value in a set or map?

[cayblood]

I have Stroustrup's c++ book, but there are times when it is a little
difficult to decipher. I'm trying to figure out what the "right way"
to find the maximum value in a map is. Here is basically what I would
like to do:

map<string, int> state_frequenci es;
....
int maxval = get_max_value(s tate_frequencie s);

Thanks in advance for your help.

Carl

[Jonathan Mcdougall]

Re: STL algorithm to find max value in a set or map?

cayblood wrote:[color=blue]
> I have Stroustrup's c++ book, but there are times when it is a little
> difficult to decipher. I'm trying to figure out what the "right way"
> to find the maximum value in a map is. Here is basically what I would
> like to do:
>
> map<string, int> state_frequenci es;
> ...
> int maxval = get_max_value(s tate_frequencie s);[/color]

typedef std::map<std::s tring, int> M;

bool value_comparer( M::value_type &i1, M::value_type &i2)
{
return i1.second<i2.se cond;
}

M::iterator itor = std::max_elemen t(m.begin(), m.end(),
value_comparer) ;


Jonathan

[Mike Wahler]

Re: STL algorithm to find max value in a set or map?


"cayblood" <carl.youngbloo d@gmail.com> wrote in message
news:1130991358 .569174.184970@ g49g2000cwa.goo glegroups.com.. .[color=blue]
>I have Stroustrup's c++ book, but there are times when it is a little
> difficult to decipher. I'm trying to figure out what the "right way"
> to find the maximum value in a map is. Here is basically what I would
> like to do:
>
> map<string, int> state_frequenci es;
> ...
> int maxval = get_max_value(s tate_frequencie s);
>
> Thanks in advance for your help.[/color]

#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <utility>

bool pred(const std::pair<std:: string, int>& lhs,
const std::pair<std:: string, int>& rhs)
{
return lhs.second < rhs.second;
}

int main()
{
std::map<std::s tring, int> m;
m["a"] = 42;
m["b"] = 99;
m["c"] = 0;

if(!m.empty())
std::cout << "Largest == "
<< std::max_elemen t(m.begin(), m.end(), pred)->second
<< '\n';
else
std::cout << "Container empty\n";

return 0;
}

-Mike

[Calum Grant]

Re: STL algorithm to find max value in a set or map?

cayblood wrote:[color=blue]
> I have Stroustrup's c++ book, but there are times when it is a little
> difficult to decipher. I'm trying to figure out what the "right way"
> to find the maximum value in a map is. Here is basically what I would
> like to do:
>
> map<string, int> state_frequenci es;
> ...
> int maxval = get_max_value(s tate_frequencie s);
>[/color]

int maxval = state_frequenci es.rbegin()->second;

You need to handle the case where state_frequenci es is empty.

This is more efficient than std::max_elemen t since it just reads the
rightmost item, instead of iterating the entire tree.

Calum

[Thomas J. Gritzan]

Re: STL algorithm to find max value in a set or map?

Calum Grant schrieb:[color=blue][color=green]
>> map<string, int> state_frequenci es;[/color]
>
> int maxval = state_frequenci es.rbegin()->second;
>
> You need to handle the case where state_frequenci es is empty.
>
> This is more efficient than std::max_elemen t since it just reads the
> rightmost item, instead of iterating the entire tree.
>
> Calum[/color]

Wrong.

The items in std::map are not sorted by value (->second), they are
sorted by the key. So the rightmost item does not have the maximum value.

Thomas

[Calum Grant]

Re: STL algorithm to find max value in a set or map?

Thomas J. Gritzan wrote:[color=blue]
> Calum Grant schrieb:
>[color=green][color=darkred]
>>>map<string , int> state_frequenci es;[/color]
>>
>>int maxval = state_frequenci es.rbegin()->second;
>>
>>You need to handle the case where state_frequenci es is empty.
>>
>>This is more efficient than std::max_elemen t since it just reads the
>>rightmost item, instead of iterating the entire tree.
>>
>>Calum[/color]
>
>
> Wrong.
>
> The items in std::map are not sorted by value (->second), they are
> sorted by the key. So the rightmost item does not have the maximum value.[/color]

Normally when one talks about the value of a container, it refers to the
whole thing, not the second element. For example map<string,
int>::value_typ e is pair<string,int >.

The question did not make it sufficiently clear whether the maximum
key_type or mapped_type was required. It just said "value" which I took
to mean the value_type of the container.

Calum