c++ - 随机访问迭代器和双端队列

Question

我今天读了一些文章，它说由于 std::deque 确实有一个随机访问迭代器，所以它的项目检索率时间复杂度是 O(1)。虽然我同意项目检索的时间复杂度为 O(1) 的事实，但随机访问迭代器与它有什么关系？

Answer 1

RandomAccessIterator 概念要求+ 和- 操作必须在常数时间内实现:

来自 [iterator.concept.random.access] :

The RandomAccessIterator concept adds support for constant-time advancement with +=, +, -=, and -, as well as the computation of distance in constant time with -. Random access iterators also support array notation via subscripting.

这意味着任何实现随机访问迭代器的符合标准的容器都必须提供恒定时间元素检索。