c++ - 减去映射迭代器

Question

我有一个程序，其中有两个 std::map 迭代器分别表示 left 和 right。我想找到 [left,right]. 范围内的元素数

我天真地做了这样的事情:int len = right - left。我认为它会很好但是它 gave me an error

然后我发现了 distance(left, right) 方法，感谢 Stack Overflow 上的一篇文章，但不幸的是它具有线性时间复杂度。

是否有可能为此获得O(1) 解决方案？

Answer 1

Is it possible to get an O(1) solution for this?

没有。 std::map 有一个 BidirectionalIterator . BidirectionalIterator 不支持随机访问，只能递增或递减。这意味着如果你想向前移动 5 个位置，你必须调用 ++iterator_name 5 次。如果您需要随机访问，那么您将需要选择一个支持它的容器，例如 std::array 或 std::vector。