如何在std::map中像在std::set中一样找到最小值/最大值？

Question

由于 set 和 map 都是有序容器，所以 std::map 是否可以像 std::set 一样在 O(1) 时间内查找最小值和最大值？

// for std::set
// std::set<int> s;
auto min = *s.begin();

auto max = *s.rbegin();

如何在O(1)时间复杂度内从std::map中获取最大值和最小值？其他问题似乎建议迭代地遍历Map，但是我们不能利用std::map的有序属性更快地得到结果吗？

- nnrales

---

不，我不相信这是可能的。因为地图上的排序取决于键类型。 - user5688956

那我能在O(1)时间内找到最小的键吗？ - nnrales

我之前有一个类似的答案。 - Kerrek SB

@KerrekSB 之前没看到。谢谢，它还有更多细节。 - nnrales

Answer 1

从迭代器中首先解引用键，像这样：

// for std::map<int,string> s
auto minKey = s.begin()->first;
auto maxKey = s.rbegin()->first;

这仅适用于键而非值，因为映射只在其键上排序。

- Sergey Kalinichenko

---

非常感谢。在我看来，一定有比迭代更好的方法。我认为这可能是答案，但想要确认一下。 - nnrales

是的，我只想找到最小的键。 - nnrales

这个答案非常聪明，但是“首先从迭代器中取消引用键，像这样”的措辞让我需要经过几次解释才理解。可能值得再加一句话说明，映射总是按顺序存储的，因此第一个/最后一个元素的键将是最小/最大的。无论如何+1。 - Vality