Указатель назад двусвязного списка

Я должен реализовать этот двусвязный список. Списку нужен передний указатель, указывающий на первый допустимый элемент, и задний указатель, указывающий на последний допустимый элемент.

Моя проблема с этим кодом связана с последними несколькими строками, когда мне нужно реализовать T & back и определить конечный итератор. То, что у меня есть в настоящее время, не работает.

#ifndef List_dllist_h
#define List_dllist_h
#include <iterator>

template <class T>
class DList
{
struct Node
{
    Node(const T& x,Node* y = 0):m_data(x),m_next(y),m_prev(y){}
    T m_data;
    Node* m_next;
    Node* m_prev;
};

Node* m_head;
Node* m_back;

public:

class iterator
{
    Node* m_rep;
public:
    friend class DList;

    inline iterator(Node* x=0):m_rep(x){}
    inline iterator(const iterator& x):m_rep(x.m_rep) {}
    inline iterator& operator=(const iterator& x)
    {
        m_rep=x.m_rep; return *this;
    }
    inline iterator& operator++()
    {
        m_rep = m_rep->m_next; return *this;
    }
    inline iterator operator++(int)
    {
        iterator tmp(*this); m_rep = m_rep->m_next; return tmp;
    }
    inline iterator& operator--()
    {
        m_rep= m_rep->m_prev; return *this;
    }
    inline iterator operator--(int)
    {
        iterator tmp(*this); m_rep= m_rep->m_prev; return tmp;
    }
    inline T& operator*() const { return m_rep->m_data; }
    inline Node* operator->() const { return m_rep; }
    inline bool operator==(const iterator& x) const
    {
        return m_rep == x.m_rep;
    }
    inline bool operator!=(const iterator& x) const
    {
        return m_rep != x.m_rep;
    }

   };


DList() : m_head(0), m_back(0) {}
~DList() { clear(); }


inline T& front() { return *begin(); }
inline const T& front() const { return *begin(); }


inline T& back() { return *--end(); }
inline const T& back() const { return *--end(); }

inline iterator begin() { return iterator(m_head); }
inline iterator end() { return iterator(m_back); }



};
#endif

Изменить: добавлен --operator


c++ iterator doubly-linked-list
person Lin0523    schedule 31.03.2016    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Ваша проблема с итератором back() немного сложнее, чем кажется на первый взгляд. back() тесно связан с end(), однако ваша реализация end() не будет работать правильно, что я объясню чуть позже. Ваш класс итератора на самом деле не предназначен для очень хорошего представления значения end(), как он написан в настоящее время.

Но давайте на мгновение представим, что ваш итератор end() был хорош и хорош. Если бы это было так, ваш back() можно было бы просто записать так:

inline T& back() { return *--end(); }

Это классическое определение back(). Это и есть. Версия const будет аналогичной.

Тот факт, что у вас еще не определен оператор --, не имеет большого значения. Это побочный вопрос, вы можете легко определить его как оператор ++, который вы уже закодировали. Давайте считать, что эта часть сделана. Основная проблема заключается в вашем фактическом значении end():

inline iterator end() { return iterator(m_back +1); }

Это серьезный провал по нескольким причинам. m_back — это указатель на последний элемент в двусвязном списке. m_back будет следующей ячейкой памяти после последнего элемента. Что на самом деле не очень осмысленно, а кроме того совершенно неправильно по следующей простой причине.

Кроме того, когда ваш список пуст, m_back равно нулю, поэтому m_back+1 — это неопределенное поведение! Упс. Но, как вы знаете, end() пустого контейнера должен быть вполне допустимым итератором.

Теперь рассмотрим ситуацию, когда ваш iterator ссылается на последний элемент в двусвязном списке. В этой ситуации увеличение его с помощью оператора ++ должно дать вам значение end(). Потому что это то, что есть. Теперь остановитесь и задумайтесь на мгновение. Это то, что произойдет после того, как ваш operator++() закончит «увеличивать» итератор, который ссылается на последний элемент в вашем двусвязном списке? Конечно, нет.

Кроме того, имейте в виду фундаментальную аксиому, согласно которой значение вашего итератора end() должно оставаться неизменным после того, как новый узел будет push_back() помещен в конец вашего пользовательского контейнера. Но когда это произойдет в вашем коде, у вас будет совершенно новый m_back. И m_back+1 теперь совсем другой. Что случилось с вашим предыдущим "m_back+1"? Оно внезапно превратилось во что-то отличное от значения end(). На самом деле он вообще не указывает ни на какую часть двусвязного списка. Он указывает на место в памяти, которое находится после некоторого существующего элемента в списке.

Итак, проблему с вашим back(), о которой вы спрашивали, довольно легко решить. Но ваша настоящая проблема здесь, которую вам нужно решить, заключается в том, как вам нужно спроектировать значение итератора end() и каким оно должно быть. То, что у вас есть сейчас, не будет работать правильно.

person Sam Varshavchik    schedule 31.03.2016
comment
Спасибо за ваше объяснение. Я добавил --operator и вернулся к *--end(). Я понимаю, почему у меня не работает m_back+1. Но я все еще не понимаю, как закончить работу. - person Lin0523; 31.03.2016
comment
Чтобы заставить end() работать, нужно выяснить, как заставить его соответствовать всем требованиям, которым должно соответствовать конечное значение итератора. Один из распространенных способов, но не единственный, состоит в том, чтобы всегда помещать фиктивный узел в конец списка, чтобы пустой список содержал только фиктивный узел. Указатель на этот фиктивный узел — это ваш итератор end(), и все реальные узлы в списке вставляются перед ним. Или пусть end() будет представлен нулевым указателем, но тогда итератор также должен содержать указатель на свой собственный список, чтобы оператор-- мог работать правильно. Есть много способов сделать это. - person Sam Varshavchik; 31.03.2016