如何在 std::map 中查找最大的键？ - C++

Question

目前我的解决方案是通过遍历地图来解决这个问题。

我看到有一个 upper_bound 方法可以使这个循环更快，但是否有更快或更简洁的方法？

- gak

Answer 1

终止：

m.rbegin();

Maps（和set）是排序的，因此第一个元素是最小的，最后一个元素是最大的。默认情况下，map使用std::less，但您可以切换比较器，这当然会改变最大元素的位置。 （例如，使用std::greater会将其放置在begin()。）

请记住，rbegin返回一个迭代器。要获取实际键，请使用m.rbegin()->first。您可能会将其包装成一个函数以提高清晰度，但我不确定是否值得。

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);

- GManNickG

---

也许值得检查空映射。 - user2672165

+1，非常好的回答。在你的回答之后，我进行了一些研究，并且我会添加crbegin到你的回答中，以使其更好（如果我们需要一个const迭代器，在某些情况下可能很重要）。 - Ginés Hidalgo

Answer 2

std::map中的条目是有序的，因此对于一个std::map m（假设m.empty()为false），您可以轻松获取最大的键：(--m.end())->first

- user200783

---

end() 不能在没有断言的情况下向后迭代。 - G Huxley

@GHuxley - 你确定你的映射是非空的吗？ - user200783

也许你正在使用一个不会为这种错误使用而断言的STL实现。 - G Huxley

@GHuxley - 抱歉，我不明白为什么反向迭代end()是错误的。根据这个答案，“关联容器的迭代器属于双向迭代器类别”，那么为什么不能递减呢？ - user200783

@user200783- 双向end()迭代器的递减仅适用于某些上下文而不适用于其他上下文。如果您希望end()始终起作用，则需要使用std::prev(m.end())。请参考此处的注释：https://en.cppreference.com/w/cpp/iterator/prev - G Huxley

Answer 3

由于地图只是一棵AVL树，因此它是按升序排序的。因此，具有最大键的元素是最后一个元素，您可以使用以下两种方法之一获取它：

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 

- Mostafa Wael

Answer 4

由于std::map是关联数组，因此可以很容易地找到最大或最小的键。默认情况下，比较函数是less(<)操作符，因此最大的键将是映射中的最后一个元素。同样，如果有人有不同的要求，可以在声明映射时修改比较函数。

std::map<key, Value, compare<key,Value>>

默认情况下compare=std::less

- Vivek

Answer 5

由于您没有使用unordered_map，所以您的键应该是有序的。根据您对迭代器的需求，您有两个选项：

1. 如果您想要一个正向迭代器，那么您可以使用std::prev(myMap.end())。请注意，--myMap.end()并不保证在所有情况下都有效，所以我通常会避免使用它。
2. 如果您想要逆向迭代，则使用myMap.rbegin()

- G Huxley