c++ - 恒定时间访问是否​​意味着在某些时候是连续的内存？

Question

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

以 std::deque 为例:它不保证它的所有元素都连续存储(即在同一个内存数组中)，但是说 std::deque 满足Random Access Iterator 的要求，内存在某个点连续，与实现无关？

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

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++ 随机访问迭代器类似的机制(考虑到即使指针不这样做， block 也总是 指向同一容器的迭代器中同一内存数组中的地址)？

编辑:澄清一下，此处的常数时间用于表示常数时间随机访问

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)。

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