减去地图迭代器 [英] Subtracting map iterators

问题描述

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

I have a program where I have two std::map iterators say left and right respectively. I want to find the number of elements in the range [left,right].

我天真地做了这样的事情:int len = right - left.我以为会很好，但是给我一个错误

I naively did something like this : int len = right - left. I thought it would be just fine but it gave me an error

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

Then I discovered distance(left, right) method thank to a post on Stack Overflow but unfortunately it has a linear time complexity.

是否可以为此提供O(1)解决方案?

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

推荐答案

是否可以为此获得O(1)解决方案?

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

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

No. a std::map has a BidirectionalIterator. A BidirectionalIterator does not support random access and can only be incremented or decremented. That means if you want to move 5 positions forward you have to call ++iterator_name 5 times. If you need random access then you will need to pick a container that supports that like a std::array or std::vector.

这篇关于减去地图迭代器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！