c++ - C++ map::find 或 map::iterator 更有效的复杂性

Question

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

Answer 1

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

Answer 2

首先，他们做两件不同的事情。其次，这取决于实施。

Answer 3

根据经验：如果您可以在通用算法（std::find此处）和同名容器特定算法（此处）之间进行选择std::map<...>::find，则使用容器特定算法。

如果它不比通用版本更有效，那么没有人会打扰实现一个特定于容器的容器，那将是浪费时间。