C++ How to find the biggest key in a std::map?
At the moment my solution is to iterate through the map to solve this.
I see 开发者_运维技巧there is a upper_bound
method which can make this loop faster, but is there a quicker or more succinct way?
The end:
m.rbegin();
Maps (and sets) are sorted, so the first element is the smallest, and the last element is the largest. By default maps use std::less
, but you can switch the comparer and this would of course change the position of the largest element. (For example, using std::greater
would place it at begin()
.
Keep in mind rbegin
returns an iterator. To get the actual key, use m.rbegin()->first
. You might wrap it up into a function for clarity, though I"m not sure if it's worth it:
template <typename T>
inline const typename T::key_type& last_key(const T& pMap)
{
return pMap.rbegin()->first;
}
typedef std::map</* types */> map_type;
map_type myMap;
// populate
map_type::key_type k = last_key(myMap);
The entries in a std::map are sorted, so for a std::map m (assuming m.empty()
is false), you can get the biggest key easily: (--m.end())->first
As std::map is assosiative array one can easily find biggest or smallest key very easily. By defualt compare function is less(<) operator so biggest key will be last element in map. Similarly if someone has different requirement anyone can modify compare function while declaring map.
std::map< key, Value, compare< key,Value > >
By default compare=std::less
Since you're not using unordered_map, your keys should be in order. Depending upon what you want to do with an iterator, you have two options:
- If you want a forwards-iterator then you can use
std::prev(myMap.end())
. Note that--myMap.end()
isn't guaranteed to work in all scenarios, so I'd usually avoid it. - If you want to iterate in reverse then use
myMap.rbegin()
Since the map is just an AVL tree then, it's sorted -in an ascending order-. So, the element with largest key is the last element and you can obtain it using one of the following two methods:
1.
largestElement = (myMap.rbegin())-> first; // rbegin(): returns an iterator pointing to the last element
largestElement = (--myMap.end())->first; // end(): returns an iterator pointing to the theortical element following the last element
精彩评论