c++11 - 什么样的迭代器支持随机访问但不支持 C++ 中的连续存储？

Question

我看到自 C++17 以来有一个新的迭代器，下面通过 cppreference 中的屏幕截图列出。我很困惑。什么样的迭代器是随机访问而不是C++中的连续存储？？否则， ContiguousIterator 不比 RandomAccessIterator 强大？对吧？

然后是链接here

Answer 1

一个具有随机访问迭代器的非连续容器是 std::deque .引用 cppreference 站点:

As opposed to std::vector, the elements of a deque are not stored contiguously: typical implementations use a sequence of individually allocated fixed-size arrays.

The complexity (efficiency) of common operations on deques is as follows:

• Random access - constant O(1)
• Insertion or removal of elements at the end or beginning - constant O(1)
• Insertion or removal of elements - linear O(n)