Ссылка на двойной список ссылок

Question

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

Моя проблема с этим кодом является с последними строками, когда я должен реализовать T & назад и определить конец iterator.What я в настоящее время не работаю

#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 

Edit: добавлена ​​--operator

Answer 1

Ваша проблема с итератором back() немного сложнее, чем кажется на первый взгляд. back() тесно связан с end(), однако ваша реализация end() не будет работать правильно, что я объясню в одно мгновение. Ваш класс iterator на самом деле не предназначен для представления значения 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 имеет значение null, поэтому m_back+1 - это неопределенное поведение! К сожалению. Но, как вы знаете, end() пустого контейнера должен быть вполне допустимым итератором.

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

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

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