C++ map::find 或 map::iterator 哪个更有效 w.r.t 复杂性

Question

正如我们所知，map::find 返回一个迭代器，指向它找到键位置的位置。同样作为二分搜索操作，复杂度为 O(logn)。所以它似乎在内部维护了一个迭代器，它将在成功时返回。那么哪个更有效 find 或 iterator 因为我认为两者在运行时会提供相同的复杂性(我可能是不正确的)。那么您能否建议在哪里使用查找以及在哪里使用迭代器。在其中一个实现中，我需要查看特定键的映射(因为它可以包含 N 个键，我们只对其中的 m 个键感兴趣)。所以不管是find还是iterator会更有效率。还有什么是处理查找失败案例的好方法，因为我不想在代码中放置太多 if else 案例，这会增加复杂性。

Answer 1

我不完全确定你的意思，但使用 std::map<...>::find()将比使用 std::lower_bound() 更有效在 map 的迭代器上:内部树上的二进制搜索只是导航树并且有 O(log(n))性能 n是 map 的大小。 std::lower_bound()也会进行二进制搜索，但需要使用 operator++()和/或 operator--()移动迭代器。因此，它将有 O(n)表现。我认为它甚至不应该编译，但我不完全确定它是否无法编译。