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.

I think that's a hint that your iterator isn't really random access — StoryTeller - Unslander Monica
The point of random access is that the position type, the iterator, can be used from any position to get to any other. If that was truly the case, calculating the difference shouldn't be too difficult. You can easily implement a forward iterator. Why isn't that good enough? — StoryTeller - Unslander Monica
"The point of random access is that the position type, the iterator, can be used from any position to get to any other." This is exactly what I'm looking for — Marco Ripamonti
You've got it backwards. You don't have random access with operator[] and therefore will implement random access iterators - you need to implement random access iterators and then all the rest falls out naturally. Like @StoryTeller is saying, it is not possible for the data structure you've shown to implement random access iterators. You claim to have implemented operator[], how? Is it constant time as is required by random access iterators? — GManNickG

John Zwinck John Zwinck · Accepted Answer · 2018-01-28T09:39:35

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.

Implement Random Access Iterators on a linked list

1 Answers