开发者

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:

  1. 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.
  2. 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 
0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜