элемент списка и итератор к следующему элементу

Question

Я не понимаю, что Бьерн имеет на виду заявление:

Список итератор должен быть что-то более сложное, чем просто указатель на элемент, потому что элемент списка в целом не знать, где следующий элемент этого списка. Таким образом, список итератор может быть указателем на ссылку

Я знаю узел, что список имеет указатели на следующие и предыдущие узлы. Так как это «вообще не знает»?

Answer 1

Для контраста, давайте рассмотрим итератор для std::vector. Хотя вы, вероятно, не хотят чтобы, вы могли бы в принципе реализовать его как простой указатель:

template <class T> 
class vector { 
    T *data; 
    size_t current_size; 
    size_t alloc_size; 
public: 
    typedef T *iterator; 
    iterator begin() { return data; } 
    iterator end() { return data+current_size; } 
    // ... 
}; 

и поскольку данные в векторе смежный, когда вы делаете (например) ++ на итератор, он поступил бы правильно (вы попадете в следующий элемент в векторе).

Со связанным списком это не может быть так просто - если вы использовали typedef, чтобы сделать итератором псевдоним для T *, это не сработает правильно. Когда вы попытались сделать ++ на итераторе, он просто увеличит указатель, а не приведет вас к следующему элементу связанного списка, как это необходимо.

Вам нужно создать некоторый интеллект в классе итератора, поэтому оператор ++ (на одном примере) знает, как «преследовать» указатель вместо того, чтобы просто увеличивать.

template <class T> 
class list { 

    class node { 
     T data; 
     node *next; 
     node *prev; 
    }; 
public: 
    class iterator { 
     node *pos; 
    public: 
     iterator operator++() { 
      return pos = pos->next; 
     } 
     iterator operator--() { 
      return pos = pos->prev; 
     } 
    }; 
}; 

Answer 2

Не путайте узел списка с элементом списка. Это может быть указателем, но узлом, который содержит элементы и следующие/предыдущие ссылки. Если бы это был просто указатель на элемент, вы не смогли бы передвигаться с ним. (Хотя это вряд ли будет просто указателем, так как обычно приходится перегружать operator ++ для получения следующего указателя вместо того, чтобы увеличивать себя).

Это неверно для интрузивных списков, где node == element, но это не std :: list.

// illustrative 
template <typename ElementType> 
struct list_node { 
    ElementType element; 
    list_node *next, *prev; 
};