Does constant time access imply contiguous memory at some point?

Question

As the title says, I was wondering if constant-time/O(1) access to a container does imply that memory is necessarily contiguous at some point. When I say contiguous I mean if pointers can be compared with relational operators at some point without invoking undefined behavior.

Take eg std::deque: it does not guarantee that all its elements are stored contiguously (i.e in the same memory array), but is it correct to say that as std::deque satisfy the requirements of a Random Access Iterator, memory will be contiguous at some point independently of the implementation?

I am new to C++ so in case what I said above does not make sense: suppose I was going to implement random access iterators in 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;

be used to generically express a similar mechanism to that of C++ random access iterators (considering that even if pointer do not, block will always point to addresses in the same memory array in iterators of the same container)?

EDIT: just to clarify, constant-time here is used to denote constant-time random access

"memory will be contiguous at some point independently of the implementation" - meaning what? contiguous memory is an implementation feature. — user2100815
As I clearly stated, I want to know if that's an implication, like a empirical thing. — Isaac Monteiro

Miles Budnek Miles Budnek · Accepted Answer · 2017-12-10T21:01:02

No. Consider a fixed-size linked list like the following:

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;
    }

};

Lookup time is constant. It does not depend on the number of elements stored in the container (only the constant NODE_COUNT).

Now, this is a strange data structure, and I can't think of any legitimate reason to use it, but it does serve as a counterexample to the claim that there need be a single contiguous block of memory that would be shared by all iterators to elements in the container (i.e. the block pointer in your example random_access_iterator struct).

Does constant time access imply contiguous memory at some point?

1 Answers