c++ - 在 C++ 中获取 std::map 的最大键的时间复杂度是多少？

Question

我试图在 std::map 中找到最大值，这将是树中的最后一个节点(因为 std::map 键是排序)。

Cppref 表示 std::map.end() 是常数时间。但是要获得最大的键，我必须获得此迭代器的先前值，即 *std::prev(std::map.end())。

该操作的时间复杂度是多少？

我知道这应该等同于 --std::map.end()，但我也不知道该操作的成本。

Answer 1

使用 std::map::rbegin()相反，它:

Returns a reverse iterator pointing to the last element in the container (i.e., its reverse beginning).

和:

Complexity

Constant.

最后一个词在您耳中听起来应该像音乐一样。

---

std::prev(std::map.end()) 是 constant复杂性。

---

而且，你对等价的理解是错误的。

来自 std::prev备注:

Although the expression --c.end() often compiles, it is not guaranteed to do so: c.end() is an rvalue expression, and there is no iterator requirement that specifies that decrement of an rvalue is guaranteed to work. In particular, when iterators are implemented as pointers, --c.end() does not compile, while std::prev(c.end()) does.