Implement Random Access Iterators on a linked list

Question

So I have a custom linked list. Every node is a struct which has a next pointer to a the next node and the last->next is null.

struct nodo {
    T value; 
    nodo *next;     

    nodo() : next(0) {}

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

I want to implement iterators in my class and since my class supports random access with operator[] then I chose to implement Random Access Iterators. Now, my problem is on the following operator:

difference_type operator-(const iterator &other) {

}

It returns the number of elements between this iterator and other iterator, but I'm not sure what's the best to implement it.

Answer 1

Linked lists are not random access containers. You cannot meaningfully implement random access iteration, nor a conventional operator[](size_t) for regular single or double linked lists.

People who use your list class will not expect random access iteration, and will be confused by it. People who use your "random access" iterators and find out they don't conform to standards and conventions will also be confused.

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

Only if your container can access elements by index in constant time should you expose random access interfaces.