双端队列索引迭代器转换

Question

假设我有双端队列元素索引"i"。 Deque 允许在恒定时间内通过索引访问元素。所以看起来我们可以快速找到内存中的元素位置。但是当涉及到一个迭代器时（例如传递给 erase() ），我们需要制作 begin() + i ，这将花费线性时间。是否可以在恒定时间内转换索引 - >迭代器？如果不是，indexing/creating 和迭代器有什么区别？是否可能进行相反的操作：指向 element/iterator 的指针 -> 索引（不迭代到 begin/end）？

Answer 1

we need to make begin() + i which will take linear time.

不，不会的。

支持 operator+ 的迭代器应该在常数时间内完成（这对标准迭代器来说是正确的，用户定义的迭代器可以定义 operator+ 是线性的，但这将是非常规的）。

在恒定时间内不支持它的迭代器需要使用 std::advance 而不是 operator+

来推进

std::deque::iterator 是一个随机访问迭代器，所以 begin() + i 是有效的并且需要常数时间。

Answer 2

Is it possible to convert index -> iterator in constant time?

是的。

iter = deq.begin() + index;

这是常数时间，与你的看法相反。支持 operator+ 的标准库中的任何迭代器（或按照与标准库相同的理念设计的）都在常数时间内执行。事实上，所有作用于标准库迭代器的运算符都是常数时间。任何无法在恒定时间内实现的运算符都不会实现。这就是为什么只有随机访问迭代器（vector、deque、string 等）支持整数加法或相互减法等操作。

Is the opposite operation possible: pointer to element/iterator -> index

是的。

index = iter - deq.begin();

这也是常数时间

双端队列索引迭代器转换

Deque index-iterator conversion

c++

iterator

deque