恒定时间访问是否意味着某个时刻的连续内存？

Question

正如标题所述，我想知道对容器的constant-time/O(1)访问是否意味着内存在(某些点)上必然是连续的。当我说连续时，我的意思是如果指针可以在某个点上与关系运算符进行比较，而不调用未定义的行为。

例如:deque:它不能保证它的所有元素都是连续存储的(即在同一个内存数组中)，但是如果这样说是正确的，因为std::deque满足了随机访问Iterator的要求，那么在某个时刻内存将与实现无关而是连续的吗？

我是C++新手，所以如果我上面说的没有意义的话:假设我要用C. Can实现随机访问迭代器

typedef struct random_access_iterator {
    void *pointer; /*pointer to element */
    void *block; /* pointer to the memory array
                  * so in case of comparing iterators
                  * where pointer does not point to addresses in the same array
                  * it can be used to comparisons instead*/
    /* implement other stuff */
} RandomIter;

通常用于表示类似于C++随机访问迭代器的机制(考虑到即使指针没有，块也总是指向同一个容器的迭代器中相同内存数组中的地址)？

编辑:为了澄清，这里的常数时间被用来表示固定时间的随机访问。

Answer 1

不是的。考虑一个固定大小的链接列表，如下所示：

struct DumbCounterexample
{
    struct node
    {
        std::vector<int> items;
        std::unique_ptr<node> next;
    };

    std::unique_ptr<node> first;
    size_t size;
    static constexpr size_t NODE_COUNT = 10;

    DumbCounterexample()
        : first{new node},
          size{0}
    {
        node* to_fill = first.get();
        for (size_t i = 0; i < NODE_COUNT - 1; ++i) {
            to_fill->next.reset(new node);
            to_fill = to_fill->next.get();
        }
    }

    int& operator[](size_t i)
    {
        size_t node_num = i % NODE_COUNT;
        size_t item_num = i / NODE_COUNT;
        node* target_node = first.get();
        for (size_t n = 0; n < node_num; ++n) {
            target_node = target_node->next.get();
        }
        return target_node->items[item_num];
    }

    void push_back(int i)
    {
        size_t node_num = size % NODE_COUNT;
        node* target_node = first.get();
        for (size_t n = 0; n < node_num; ++n) {
            target_node = target_node->next.get();
        }
        target_node->items.push_back(i);
        ++size;
    }

};

查找时间是恒定的。它不取决于容器中存储的元素的数量(仅取决于常量NODE_COUNT)。

现在，这是一个奇怪的数据结构，我想不出有什么合理的理由使用它，但它确实可以作为一个反例，说明需要一个连续的内存块，所有迭代器都可以共享到容器中的元素(即示例block结构中的random_access_iterator指针)。