c++ - 在链表上实现随机访问迭代器

Question

所以我有一个自定义链表。每个节点都是一个结构，它有一个指向下一个节点的 next 指针，并且 last->next 为 null。

struct nodo {
    T value; 
    nodo *next;     

    nodo() : next(0) {}

    nodo(const T &v, nodo *n=0): value(v), next(n){}
};

我想在我的类中实现迭代器，因为我的类支持使用 operator[] 进行随机访问，所以我选择实现随机访问迭代器。现在，我的问题出在以下运算符上:

difference_type operator-(const iterator &other) {

}

它返回此迭代器和其他迭代器之间的元素数，但我不确定实现它的最佳方式是什么。

Answer 1

链表不是随机访问容器。您无法有意义地实现随机访问迭代，也无法实现常规的单链表或双链表的常规 operator[](size_t)。

使用您的列表类的人不会期望随机访问迭代，并且会被它弄糊涂。使用您的“随机访问”迭代器并发现它们不符合标准和约定的人也会感到困惑。

A RandomAccessIterator is a BidirectionalIterator that can be moved to point to any element in constant time.

只有当您的容器可以在恒定时间内按索引访问元素时，您才应该公开随机访问接口(interface)。