Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #13917 > unrolled thread

std::map: best way to get biggest key?

Back to article view | Back to comp.lang.c++

Contents

  std::map: best way to get biggest key? Rui Maciel <rui.maciel@gmail.com> - 2012-02-11 21:44 +0000
    Re: std::map: best way to get biggest key? Leigh Johnston <leigh@i42.co.uk> - 2012-02-11 21:57 +0000
      Re: std::map: best way to get biggest key? Rui Maciel <rui.maciel@gmail.com> - 2012-02-11 22:09 +0000
        Re: std::map: best way to get biggest key? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2012-02-11 23:28 +0100
          Re: std::map: best way to get biggest key? Rui Maciel <rui.maciel@gmail.com> - 2012-02-12 15:07 +0000
            Re: std::map: best way to get biggest key? Dombo <dombo@disposable.invalid> - 2012-02-12 17:00 +0100
            Re: std::map: best way to get biggest key? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2012-02-12 18:41 +0100
            Re: std::map: best way to get biggest key? Ian Collins <ian-news@hotmail.com> - 2012-02-13 07:13 +1300
            Re: std::map: best way to get biggest key? Jorgen Grahn <grahn+nntp@snipabacken.se> - 2012-02-12 19:40 +0000
            Re: std::map: best way to get biggest key? Joshua Maurice <joshuamaurice@gmail.com> - 2012-02-12 13:25 -0800
        Re: std::map: best way to get biggest key? Dombo <dombo@disposable.invalid> - 2012-02-11 23:29 +0100
        Re: std::map: best way to get biggest key? Paavo Helde <myfirstname@osa.pri.ee> - 2012-02-11 16:39 -0600
          Re: std::map: best way to get biggest key? Rui Maciel <rui.maciel@gmail.com> - 2012-02-12 15:16 +0000
            Re: std::map: best way to get biggest key? Goran <goran.pusic@gmail.com> - 2012-02-12 08:41 -0800
            Re: std::map: best way to get biggest key? Leigh Johnston <leigh@i42.co.uk> - 2012-02-12 18:48 +0000

#13917 — std::map: best way to get biggest key?

The typical way to get the biggest key of a std::map is to rely on the 
default sorting for std::map (based on std::less) and simply check the key 
of the last element of a map, as:

<code>
std::map<key,value> my_map;
//...
key largest_key = my_map.rbegin()->first
<code>


Yet, this trick is a bit flimsy and isn't very elegant.  Does anyone know if 
there is a better way to extract the biggest key of a std::map?


Thanks in advance,
Rui Maciel

[toc] | [next] | [standalone]

#13919

On 11/02/2012 21:44, Rui Maciel wrote:
> The typical way to get the biggest key of a std::map is to rely on the
> default sorting for std::map (based on std::less) and simply check the key
> of the last element of a map, as:
>
> <code>
> std::map<key,value>  my_map;
> //...
> key largest_key = my_map.rbegin()->first
> <code>
>
>
> Yet, this trick is a bit flimsy and isn't very elegant.  Does anyone know if
> there is a better way to extract the biggest key of a std::map?

Why do you think it is a "trick"?  Why do you think it is a "bit 
flimsy"?  Why do you think it "isn't very elegant"?

/Leigh

[toc] | [prev] | [next] | [standalone]

#13922

Leigh Johnston wrote:

> Why do you think it is a "trick"?  Why do you think it is a "bit
> flimsy"?  Why do you think it "isn't very elegant"?

It requires that the key comparison function used in a map sorts the keys in 
such a way that the last key/value pair includes the biggest key.  If a map 
is created with some other key comparison function then this trick fails.


Rui Maciel

[toc] | [prev] | [next] | [standalone]

#13925

On 11.02.2012 23:09, Rui Maciel wrote:
> Leigh Johnston wrote:
>
>> Why do you think it is a "trick"?  Why do you think it is a "bit
>> flimsy"?  Why do you think it "isn't very elegant"?
>
> It requires that the key comparison function used in a map sorts the keys in
> such a way that the last key/value pair includes the biggest key.  If a map
> is created with some other key comparison function then this trick fails.

If you want the key that is largest according to to some other ordering 
than the map's, then you have no option but to check all keys.

The map cannot magically know what other ordering you have in mind.

I would think that that should be, like, *obvious*?


Cheers & hth.,

- Alf

[toc] | [prev] | [next] | [standalone]

#13938

Alf P. Steinbach wrote:

> If you want the key that is largest according to to some other ordering
> than the map's, then you have no option but to check all keys.
> 
> The map cannot magically know what other ordering you have in mind.
> 
> I would think that that should be, like, *obvious*?

You missed the point, or you let your need to post petty comments get the 
best of you.

No one asked about magic, or questioned that algorithms are needed to 
perform any computation ono a computer.  I don't know how or why you reached 
that conclusion.

The question, which you failed read or understand, was if there was a better 
way to extract the biggest key of a std::map.  To put it more clearly, the 
question was if there was any standard way (that is, employing components 
from the STL) that made it possible to extract the biggest key from a 
std::map, without relying on the key comparison function used by an std::map 
object.


Rui Maciel

[toc] | [prev] | [next] | [standalone]

#13941

Op 12-Feb-12 16:07, Rui Maciel schreef:
> Alf P. Steinbach wrote:
>
>> If you want the key that is largest according to to some other ordering
>> than the map's, then you have no option but to check all keys.
>>
>> The map cannot magically know what other ordering you have in mind.
>>
>> I would think that that should be, like, *obvious*?
>
> You missed the point, or you let your need to post petty comments get the
> best of you.
>
> No one asked about magic, or questioned that algorithms are needed to
> perform any computation ono a computer.  I don't know how or why you reached
> that conclusion.
>
> The question, which you failed read or understand, was if there was a better
> way to extract the biggest key of a std::map.  To put it more clearly, the
> question was if there was any standard way (that is, employing components
> from the STL) that made it possible to extract the biggest key from a
> std::map, without relying on the key comparison function used by an std::map
> object.

You could take a look at std::max_element() in <algorithm> which allows 
you to pass your own comparison function/functor. Keep in mind that 
std::max_element() has linear complexity; it has to go through all 
elements in the map so it is no faster than just iterating over a std::map.

[toc] | [prev] | [next] | [standalone]

#13946

On 12.02.2012 16:07, Rui Maciel wrote:
> Alf P. Steinbach wrote:
>
>> If you want the key that is largest according to to some other ordering
>> than the map's, then you have no option but to check all keys.
>>
>> The map cannot magically know what other ordering you have in mind.
>>
>> I would think that that should be, like, *obvious*?
>
> You missed the point, or you let your need to post petty comments get the
> best of you.
>
> No one asked about magic, or questioned that algorithms are needed to
> perform any computation ono a computer.  I don't know how or why you reached
> that conclusion.
>
> The question, which you failed read or understand, was if there was a better
> way to extract the biggest key of a std::map.  To put it more clearly, the
> question was if there was any standard way (that is, employing components
> from the STL) that made it possible to extract the biggest key from a
> std::map, without relying on the key comparison function used by an std::map
> object.

Well, if you want the key that is largest according to to some other 
ordering than the map's, i.e. that is largest according to some other 
key comparision function that the map's, then you have no option but to 
check all keys.

Unless you have additional information about the keys, of course.

The map cannot magically know what other ordering you have in mind: it 
cannot know the other key comparision function that you mean when you 
say "biggest".

I still would think that that should be, like, *obvious*?

Sorry about the perceived pettiness. It was not meant to elevate myself 
relative to you. It was and is meant to slap the horse's behind so that 
it moves forward, or in other words, start *thinking*, he he :-) .


Cheers & hth.,

- Alf

[toc] | [prev] | [next] | [standalone]

#13947

On 02/13/12 04:07 AM, Rui Maciel wrote:
>
> The question, which you failed read or understand, was if there was a better
> way to extract the biggest key of a std::map.  To put it more clearly, the
> question was if there was any standard way (that is, employing components
> from the STL) that made it possible to extract the biggest key from a
> std::map, without relying on the key comparison function used by an std::map
> object.

The key comparison function used by std::map defines "Biggest" in the 
context of that map.

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#13951

On Sun, 2012-02-12, Rui Maciel wrote:
...
> The question, which you failed read or understand, was if there was a better 
> way to extract the biggest key of a std::map.  To put it more clearly, the 
> question was if there was any standard way (that is, employing components 
> from the STL) that made it possible to extract the biggest key from a 
> std::map, without relying on the key comparison function used by an std::map 
> object.

I still get the feeling that you see the ordering of entries in a
std::map as an implementation detail which you aren't meant to
exploit.  If so, that's a misunderstanding -- the ordering is a vital
aspect of std::map. (And now that we have std::unordered_map that's
maybe clearer than it used to be.)

If you do this a lot, it's probably a good idea to implement

  template<class Key, class V> Key largest_key(const std::map<Key, V>&);

and use that.

/Jorgen

-- 
  // Jorgen Grahn <grahn@  Oo  o.   .     .
\X/     snipabacken.se>   O  o   .

[toc] | [prev] | [next] | [standalone]

#13952

On Feb 12, 7:07 am, Rui Maciel <rui.mac...@gmail.com> wrote:
> Alf P. Steinbach wrote:
> > If you want the key that is largest according to to some other ordering
> > than the map's, then you have no option but to check all keys.
>
> > The map cannot magically know what other ordering you have in mind.
>
> > I would think that that should be, like, *obvious*?
>
> You missed the point, or you let your need to post petty comments get the
> best of you.
>
> No one asked about magic, or questioned that algorithms are needed to
> perform any computation ono a computer.  I don't know how or why you reached
> that conclusion.
>
> The question, which you failed read or understand, was if there was a better
> way to extract the biggest key of a std::map.  To put it more clearly, the
> question was if there was any standard way (that is, employing components
> from the STL) that made it possible to extract the biggest key from a
> std::map, without relying on the key comparison function used by an std::map
> object.

So, given a map, and a different sorting criterion, you want the
biggest key of the map under the new sorting criterion.

Iterate over all the keys, keeping track of the "biggest thus far".
std::for_each may be useful in that regard with lambda functions, but
I would just write the loop myself.

[toc] | [prev] | [next] | [standalone]

#13926

Op 11-Feb-12 23:09, Rui Maciel schreef:
> Leigh Johnston wrote:
>
>> Why do you think it is a "trick"?  Why do you think it is a "bit
>> flimsy"?  Why do you think it "isn't very elegant"?
>
> It requires that the key comparison function used in a map sorts the keys in
> such a way that the last key/value pair includes the biggest key.  If a map
> is created with some other key comparison function then this trick fails.

If your definition of 'biggest key' differs from the definition used by 
the key comparison function used by the map, then obviously you have to 
iterate over the map to find the 'biggest key' according to your definition.

[toc] | [prev] | [next] | [standalone]

#13927

Rui Maciel <rui.maciel@gmail.com> wrote in
news:jh6ov5$7am$1@speranza.aioe.org: 

> Leigh Johnston wrote:
> 
>> Why do you think it is a "trick"?  Why do you think it is a "bit
>> flimsy"?  Why do you think it "isn't very elegant"?
> 
> It requires that the key comparison function used in a map sorts the
> keys in such a way that the last key/value pair includes the biggest
> key.  If a map is created with some other key comparison function then
> this trick fails. 

No failing, rbegin() always (if the map is not empty) returns the last key 
- in the sorting order of the map, that is. This *is* the largest value, 
std::map does not know or care about any other sorting criterias you might 
want to use elsewhere in your code.

hth
Paavo

[toc] | [prev] | [next] | [standalone]

#13939

Paavo Helde wrote:

> No failing, rbegin() always (if the map is not empty) returns the last key
> - in the sorting order of the map, that is. This is the largest value,
> std::map does not know or care about any other sorting criterias you might
> want to use elsewhere in your code.

The std::map container is sorted, according to the key comparison function 
used.

The rbegin() method returns an iterator pointing to the last element of the 
range, but that range is sorted according to the key comparison function 
used in a std::map.  

So, as it is possible to pass any other key comparison function in a 
std::map definition, rbegin() may or may not point to the element with the 
biggest key.

To demonstrate:

<example>
rui@Kubuntu:tmp$ cat main.c++ 
#include <map>
#include <functional>
#include <iostream>


int main(void)
{
        using namespace std;
        map<int, int> lesser;
        map<int, int, std::greater<int> > greater;

        for(int i = 0; i < 10; i++)
        {
                lesser[i] = 2*i;
                greater[i] = 2*i;
        }

        cout << "lesser:\n";
        for(auto i: lesser)
        {
                cout << "\t(" << i.first << "," << i.second << ")";
        }
        cout << endl;
        cout << "last element: " << "(" << lesser.rbegin()->first << "," << 
lesser.rbegin()->second << ")" << endl;

        cout << "greater:\n";
        for(auto i: greater)
        {
                cout << "\t(" << i.first << "," << i.second << ")";
        }
        cout << endl;
        cout << "last element: " << "(" << greater.rbegin()->first << "," << 
greater.rbegin()->second << ")" << endl;

        return 0;
}
rui@Kubuntu:tmp$ ./main 
lesser:
        (0,0)   (1,2)   (2,4)   (3,6)   (4,8)   (5,10)  (6,12)  (7,14)  
(8,16)  (9,18)
last element: (9,18)
greater:
        (9,18)  (8,16)  (7,14)  (6,12)  (5,10)  (4,8)   (3,6)   (2,4)   
(1,2)   (0,0)
last element: (0,0)
</example>


Rui Maciel

[toc] | [prev] | [next] | [standalone]

#13942

On Feb 12, 4:16 pm, Rui Maciel <rui.mac...@gmail.com> wrote:
> Paavo Helde wrote:
> > No failing, rbegin() always (if the map is not empty) returns the last key
> > - in the sorting order of the map, that is. This is the largest value,
> > std::map does not know or care about any other sorting criterias you might
> > want to use elsewhere in your code.
>
> The std::map container is sorted, according to the key comparison function
> used.
>
> The rbegin() method returns an iterator pointing to the last element of the
> range, but that range is sorted according to the key comparison function
> used in a std::map.
>
> So, as it is possible to pass any other key comparison function in a
> std::map definition, rbegin() may or may not point to the element with the
> biggest key.
>
> To demonstrate:
>
> <example>
> rui@Kubuntu:tmp$ cat main.c++
> #include <map>
> #include <functional>
> #include <iostream>
>
> int main(void)
> {
>         using namespace std;
>         map<int, int> lesser;
>         map<int, int, std::greater<int> > greater;
>
>         for(int i = 0; i < 10; i++)
>         {
>                 lesser[i] = 2*i;
>                 greater[i] = 2*i;
>         }
>
>         cout << "lesser:\n";
>         for(auto i: lesser)
>         {
>                 cout << "\t(" << i.first << "," << i.second << ")";
>         }
>         cout << endl;
>         cout << "last element: " << "(" << lesser.rbegin()->first << "," <<
> lesser.rbegin()->second << ")" << endl;
>
>         cout << "greater:\n";
>         for(auto i: greater)
>         {
>                 cout << "\t(" << i.first << "," << i.second << ")";
>         }
>         cout << endl;
>         cout << "last element: " << "(" << greater.rbegin()->first << "," <<
> greater.rbegin()->second << ")" << endl;
>
>         return 0;}
>
> rui@Kubuntu:tmp$ ./main
> lesser:
>         (0,0)   (1,2)   (2,4)   (3,6)   (4,8)   (5,10)  (6,12)  (7,14)
> (8,16)  (9,18)
> last element: (9,18)
> greater:
>         (9,18)  (8,16)  (7,14)  (6,12)  (5,10)  (4,8)   (3,6)   (2,4)
> (1,2)   (0,0)
> last element: (0,0)
> </example>
>
> Rui Maciel

map or set don't know anything about ordering your elements except the
comparison you give to them (or the default, std::less). map and set
are generic, and therefore don't know about numbers either.

I don't see why you expect them to know how elements should be
ordered, or that you might think they should be ordered.

Think about it this way: if your key wasn't a number or a string, how
do map or set even work? Something has to explain ordering to them.
And then, they both only know about __that__ particular ordering. They
aren't trying to guess that you are using std::greater and that there
is a "natural" "smaller" ordering they should ever use. For all they
know, you might pass in a comparison method where 42 is smaller than
anything else.

[toc] | [prev] | [next] | [standalone]

#13948

On 12/02/2012 15:16, Rui Maciel wrote:
> Paavo Helde wrote:
>
>> No failing, rbegin() always (if the map is not empty) returns the last key
>> - in the sorting order of the map, that is. This is the largest value,
>> std::map does not know or care about any other sorting criterias you might
>> want to use elsewhere in your code.
>
> The std::map container is sorted, according to the key comparison function
> used.
>
> The rbegin() method returns an iterator pointing to the last element of the
> range, but that range is sorted according to the key comparison function
> used in a std::map.
>
> So, as it is possible to pass any other key comparison function in a
> std::map definition, rbegin() may or may not point to the element with the
> biggest key.
>
> To demonstrate:
>
> <example>
> rui@Kubuntu:tmp$ cat main.c++
> #include<map>
> #include<functional>
> #include<iostream>
>
>
> int main(void)
> {
>          using namespace std;
>          map<int, int>  lesser;
>          map<int, int, std::greater<int>  >  greater;
>
>          for(int i = 0; i<  10; i++)
>          {
>                  lesser[i] = 2*i;
>                  greater[i] = 2*i;
>          }
>
>          cout<<  "lesser:\n";
>          for(auto i: lesser)
>          {
>                  cout<<  "\t("<<  i.first<<  ","<<  i.second<<  ")";
>          }
>          cout<<  endl;
>          cout<<  "last element: "<<  "("<<  lesser.rbegin()->first<<  ","<<
> lesser.rbegin()->second<<  ")"<<  endl;
>
>          cout<<  "greater:\n";
>          for(auto i: greater)
>          {
>                  cout<<  "\t("<<  i.first<<  ","<<  i.second<<  ")";
>          }
>          cout<<  endl;
>          cout<<  "last element: "<<  "("<<  greater.rbegin()->first<<  ","<<
> greater.rbegin()->second<<  ")"<<  endl;
>
>          return 0;
> }
> rui@Kubuntu:tmp$ ./main
> lesser:
>          (0,0)   (1,2)   (2,4)   (3,6)   (4,8)   (5,10)  (6,12)  (7,14)
> (8,16)  (9,18)
> last element: (9,18)
> greater:
>          (9,18)  (8,16)  (7,14)  (6,12)  (5,10)  (4,8)   (3,6)   (2,4)
> (1,2)   (0,0)
> last element: (0,0)
> </example>

If you want to find the "biggest" element of *any* container you can use 
'std::max_element' from <algorithm> and that applies here if by 
"biggest" you don't mean the 'std::map' element that sorts greatest 
according to the key comparison predicate.  You should pass a custom 
comparison predicate to 'std::max_element' as the 'value_type' of a 
'std::map' is a pair (key and mapped type).

/Leigh

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c++

csiph-web