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

R

Rui Maciel

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
 
R

Rui Maciel

Leigh said:
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
 
A

Alf P. Steinbach

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
 
D

Dombo

Op 11-Feb-12 23:09, Rui Maciel schreef:
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.
 
R

Rui Maciel

Alf said:
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
 
R

Rui Maciel

Paavo said:
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 = 2*i;
greater = 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
 
D

Dombo

Op 12-Feb-12 16:07, Rui Maciel schreef:
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.
 
G

Goran

Paavo said:
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 = 2*i;
                greater = 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.
 
A

Alf P. Steinbach

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
 
I

Ian Collins

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.
 
J

Jorgen Grahn

.
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
 
J

Joshua Maurice

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.
 

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

Members online

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top