减去地图迭代器

Question

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

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

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

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

Answer 1

有可能为此获得O（1）解决方案吗？

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