Проблемы реализации итератора

Question

Я написал следующий код, пытаясь создать двусвязный список с внутренним STL-подобным итератором.Я просто предоставлю в заголовочный файл нерелевантные части, обрезанные на данный момент.

Мои вопросы ...

1. STL использует итераторы в определенномВ частности, вы перемещаетесь по контейнеру STL от итератора .begin () до, но не включая итератор .end ().Для этого итератор .end () должен быть один за концом контейнера.Как бы я реализовал этот вид семантики, учитывая то, с чего я начал (это основной вопрос)?

2. Чего-то не хватает в интерфейсе в его нынешнем виде (в отношениикласс итератора и все, что должно быть в нем)?

Вот код:

template <typename T>
class Node
{
    T data;
    Node<T>* next;
    Node<T>* prev;
};

template <typename T>
class LinkedList
{
    public:

        class Iterator
        {
            public:

                Iterator() {}
                explicit Iterator(const Node<T>& init) { current = init; }

                //Dereference operator - return the current node's data.
                inline T& operator*() { return current->data; }

                //Prefix returns by reference.
                inline Iterator& operator++()   { current = current->next; return *this; } 
                inline Iterator& operator--()   { current = current->prev; return *this; }

                //Postfix returns non-reference and has int parameter to differentiate function signature.
                inline Iterator operator++(int) { Iterator res = *this; current = current->next; return res; }
                inline Iterator operator--(int) { Iterator res = *this; current = current->prev; return res; }

            private:

                Node<T>* current;
        };

        Iterator begin() { return Iterator(m_start); }
        Iterator end()   { return Iterator(m_end);   }

    private:
        Node<T>* m_start;
        Node<T>* m_end;
};

Я знаю, что у меня могут возникнуть или не возникнуть проблемы соператоры ++ / -, но это не особенно беспокоит меня, так как я разберусь с ними, когда у меня будет достаточно кода для некоторого тестирования.Не стесняйтесь оставлять подсказки, если вы склонны:)

Answer 1

1. Итератор, возвращаемый end(), должен быть декремментируемым, в противном случае вы не можете выполнить итерацию по списку в обратном порядке. Вы могли бы сделать это, если бы Iterator сохранял два указателя: на текущий узел (который будет NULL для конца) и на предыдущий узел (который позволяет найти последний узел с данными в нем, даже если current == NULL.

   class Iterator
   {
       public:
   
           Iterator() {}
           explicit Iterator(Node<T>* curr, Node<T>* prev):
               current(curr), previous(prev) {}
   
           //Dereference operator - return the current node's data.
           inline T& operator*() { return current->data; }
   
           //Prefix returns by reference.
           inline Iterator& operator++()   
           { 
               previous = current;
               current = current->next; 
               return *this; 
           } 
           inline Iterator& operator--()   
           { 
               current = previous; 
               previous = current->previous;
               return *this; 
           }
   
           //Postfix should be implemented in terms of prefix operators
           inline Iterator operator++(int) { Iterator res = *this; ++*this; return res; }
           inline Iterator operator--(int) { Iterator res = *this; --*this; return res; }
   
       private:
   
           Node<T>* current;
           Node<T>* previous;
   };
   
   Iterator begin() { return Iterator(m_start, 0); }
   Iterator end()   { return Iterator(0, m_end);   }
   

   В качестве альтернативы вы можете иметь свой список, содержащий дозорный узел, который обозначает «один конец» списка. Этот узел не должен иметь член данных, хотя. Это может быть достигнуто путем разбиения класса Node на не шаблонную базу с указателями только на следующий и предыдущий узел.

   Например, похоже, что реализация списка GCC хранит указатель на страж, так что его next указывает на первый элемент в списке, а его prev указывает на последний элемент в списке (или оба указывают себе, если список пуст).

2. Вам не хватает operator->, operator== и operator!=, определения типа классификации, которые могут быть унаследованы от std :: iterator , реализация const_iterator (итератор должен быть неявно преобразован в const_iterator).

Answer 2

1. Я думаю, что NULL подойдет просто великолепно.
2. Возможно, вы захотите написать что-то вроде for (iterator it = list.begin(); it != list.end(); it++), поэтому вам также необходимо определить операторы сравнения.

Answer 3

1. Предыдущий указатель первого узла равен NULL, как и следующий указатель последнего узла.Указатель current от одного конца до конца будет NULL.

2. operator->