c++ - 如何使用 std::map 获取双向迭代器的索引？

Question

What is the most effective way to get the index of an iterator of an std::vector?解释了如何为 std::vector 或 std::list 做这件事，但是 std::map 呢？

Answer 1

最简洁的方法是使用 std::distance 函数:

auto index = std::distance(myMap.begin(), myMapItr);

但是，这会在 O(n) 时间内运行，这对于大型 map 而言效率低下。

如果您需要确定迭代器在映射或其他有序集合中的索引，您可能需要搜索包含 order statistic tree 的库，这是一种改进的二叉搜索树，支持高效(O(1) 或 O(log n))时间查找树中特定值的索引。

或者，如果您在树上手动迭代，您可以只在每次从一个元素遍历到下一个元素时递增的迭代器旁边放置一个计数器。这给出了迭代器索引的 O(1) 时间查找，但不是完全通用的。

希望这对您有所帮助!