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

Question

获取 std::vector 的迭代器索引的最有效方法是什么？解释了如何做std::vector或者std::list但是呢std::map？

Answer 1

最干净的方法是使用以下std::distance功能：

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

但是，这在 O(n) 时间内运行，这对于大型地图来说效率很低。

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

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

希望这可以帮助！

Answer 2

尝试这个：

int IndexOf(Type *t)
{
    Type** data = vector.data();

    int index = 0;

    while(*data++ != t)
    {
        index ++;
    }

    return index ;
}