Реализовать двунаправленный список в духе списка из STL

@ForEveR · Регистрация: 24.06.2010

Author24 — интернет-сервис помощи студентам

Все-таки видимо у меня всегда останутся с этим проблемы.
Само определение скидывать не буду, я пытаюсь сделать, что-то вроде STL-ного списка.
Спросить хочу только одно.

C++

    void push_back(const T& el)
    {
        Node* tmp=new Node(el);
        if(empty())
        {
            head=tmp;
            tail=tmp;
            ++sz;
            return;
        }
        tail->next=tmp;
        tail=tmp;
        ++sz;
    }

После этого список можно прогонять только в одну сторону. С головы в хвост. В хвосте же только последний элемент и в prev ничего нет. В чем мб проблема?
Хотя вообще как я понял это для однонаправленного только катит... А вот как сделать для двунаправленного - второй день догнать не могу.

silent_1991 · 11.02.2011, 20:53

Ну так вы перед тем, как tail'у присваивать tmp, установите в tmp prev-указатель на tail.

Добавлено через 2 минуты
Т.е. так:

C++

1
2
3

tail->next=tmp;
tmp->prev = tail;
tail=tmp;

@ForEveR · 11.02.2011, 20:56 **[ТС]**

silent_1991, Офигеть... столько проколебался а все так просто... шок)

@volovzi · 11.02.2011, 20:56

Ссылки на предыдущий элемент нет, потому что ты её не устанавливаешь.

C++

1
2
3

tail->next = tmp;
tmp->previous = tail;
tail = tail->next;

Добавлено через 30 секунд
Опоздал...

silent_1991 · 11.02.2011, 21:01

ForEveR, когда списки пишешь - очень удобно на бумажке рисовать квадратики и стрелочки, соответствующие установке связок в алгоритме. Вот так нарисовал стрелочки и увидел, что одной не хватает - сразу понятно, что надо добавить. Попробуйте)))

Не по теме:

С "Ну так вы перед..." как-то грубовато вышло, извиняюсь)))

@ForEveR · 11.02.2011, 22:21 **[ТС]**

Ниже код. Есть несколько вопросов.
Не могу понять как сделать push_back/front через итераторы. Не получается. Хотелось бы увидеть простой пример на одну из данных функций.
функция back() - выдает ошибку, ибо end() у меня указывает на элемент за последним, то есть tail->next. Так как tail->next == 0 то --end() не выходит, ибо curr=curr->prev где curr == tail->next, вследствие чего - ошибка. Как исправить?
Ну и плоховато дело с erase. Буду благодарен за помощь.

C++

struct bidirectional_iterator_tag:public std::forward_iterator_tag
{
};
 
template<class T>
class List
{
public:
    class Iterator;
    struct Node;
    typedef Iterator iterator;
    typedef T& reference;
    typedef const T& const_reference;
 
    List():head(0), tail(0), sz(0)
    {
    }
    size_t size() const {return sz;}
    bool empty() const {return sz == 0;}
    iterator begin() {return iterator(head);}
    iterator end() {return iterator(tail->next);}
    void push_back(const_reference el)
    {
        Node* tmp=new Node(el);
        if(empty())
        {
            head=tmp;
            tail=tmp;
            ++sz;
            return;
        }
        tail->next=tmp;
        tmp->prev=tail;
        tail=tmp;
        ++sz;
    }
    void push_front(const_reference el)
    {
        Node* tmp=new Node(el);
        if(empty())
        {
            head=tmp;
            tail=tmp;
            ++sz;
            return;
        }
        head->prev=tmp;
        tmp->next=head;
        head=tmp;
        ++sz;
    }
    reference front()
    {
        return *begin();
    }
    reference back()
    {
        return *(--end());
    }
    const_reference front() const
    {
        return *begin();
    }
    const_reference back() const
    {
        return *(--end());
    }
    void erase(iterator Where)
    {
        if(Where == begin())
        {
            Node* tmp=head;
            head=head->next;
            delete tmp;
            return;
        }
        for(Node* tmp=head; tmp; tmp=tmp->next)
        {
            if(tmp == Where.MyNode())
            {
                Node* ts=tmp;
                tmp=tmp->next;
                delete ts;
            }
        }
    }
private:
    struct Node
    {
        Node(T elem_=T(), Node* next_=0, Node* prev_=0)
            :next(next_),  elem(elem_), prev(prev_)
        {
        }
        Node* next;
        Node* prev;
        T elem;
    };
    Node* head;
    Node* tail;
    size_t sz;
};
 
template<class T> class List<T>::Iterator
{
public:
    typedef bidirectional_iterator_tag iterator_category;
    typedef T value_type;
    typedef size_t difference_type;
    typedef T* pointer;
    typedef T& reference;
 
    Iterator(Node* t):
      curr(t)
      {
      }
    Iterator& operator ++()
    {
        curr=curr->next;
        return *this;
    }
    Iterator& operator --()
    {
        curr=curr->prev;
        return *this;
    }
    T& operator *()
    {
        return curr->elem;
    }
    Iterator& operator +(size_t idx)
    {
        for(size_t i=0; i<idx; ++i)
        {
            curr=curr->next;
        }
        return *this;
    }
    bool operator == (const Iterator& other) const 
    {
        return curr == other.curr;
    }
    bool operator != (const Iterator& other) const
    {
        return curr != other.curr;
    }
    Node* MyNode()
    {
        return curr;
    }
private:
    Node* curr;
};

@volovzi · 11.02.2011, 23:47

ForEveR, если я не ошибаюсь, std::list является кольцевым двусвязным списком, и при этом даже когда он пуст, в нём присутствуют два элемента — начало и конец. А новые элементы при добавлении встраиваются между ними. Таким образом решается проблема с итераторами.

@ForEveR · 11.02.2011, 23:55 **[ТС]**

volovzi, Не очень хочется делать список кольцевым... Есть какая-то другая возможность, без переделывания списка?

silent_1991 · 12.02.2011, 00:00

Точно не скажу, но список в стл всё-таки по-моему не кольцевой. А то, что все его элементы вставляются между start (первым элементом) и end (фиктивным элементом, следующим за последним) - это да. Собственно, я и не понимаю, как список с такими параметрами может быть кольцевым (когда есть чёткое начало и, хоть и фиктивный, но всё же конец).

@volovzi · 12.02.2011, 00:01

ForEveR, как сделать без зацикливания так сходу не соображу, надо подумать.

Добавлено через 1 минуту
Вот цитата из СБШ:

Код

a %list conceptually represented as
   *  @code
   *    A <---> B <---> C <---> D
   *  @endcode
   *  is actually circular; a link exists between A and D.  The %list
   *  class holds (as its only data member) a private list::iterator
   *  pointing to @e D, not to @e A!  To get to the head of the %list,
   *  we start at the tail and move forward by one.  When this member
   *  iterator's next/previous pointers refer to itself, the %list is
   *  %empty.  @endif

Список кольцевой, но дополнительный элемент там один, а не два, как я думал.

silent_1991 · 12.02.2011, 00:03

Сообщение от volovzi

Список кольцевой

Да, действительно. Не знал, спасибо.

@ForEveR · 12.02.2011, 00:28 **[ТС]**

То есть, чтобы закольцевать, должен быть фиктивный элемент, при этом фиктивный элемент - элемент за последним и фикт элем->next указывает на голову списка? При этом должен ли head->prev указывать на фикт элемент?

@volovzi · 12.02.2011, 00:29

ForEveR, да, так там сделано.

@ForEveR · 12.02.2011, 00:33 **[ТС]**

volovzi, Это ответ на оба вопроса?

@volovzi · 12.02.2011, 00:39

Ага, на оба.

@ForEveR · 12.02.2011, 00:42 **[ТС]**

Можешь приблизительно показать реализацию и использование такого фиктивного элемента? А то у меня что-то совсем туго...

@volovzi · 12.02.2011, 13:50

Если совсем приблизительно, то будет выглядеть примерно так:

C++

template <typename Value>
class circle_list {
 
// ---- Определения -------------------------------------------------------------------------------
 
public:
    typedef Value value_type;
 
// ---- Узел списка -------------------------------------------------------------------------------
 
private:
    struct node {
        explicit node (const value_type & value) : value(value), next(0), previous(0) {}
        ~node () { delete next; }
    
        value_type value;
        
        node * next;
        node * previous;
    };
 
// ---- Итераторы ---------------------------------------------------------------------------------
 
public:
    struct iterator {
        iterator () : m_node(0) {}
        explicit iterator (node * n) : m_node(n) {}
        
        value_type & operator * () { return m_node->value; }
        value_type * const operator -> () { return &m_node->value; }
        
        iterator & operator ++ () { return *this = iterator(m_node->next); }
        iterator & operator -- () { return *this = iterator(m_node->previous); }
        
        bool operator == (const iterator & i) const { return m_node == i.m_node; }
        bool operator != (const iterator & i) const { return m_node != i.m_node; }
    
        node * m_node;
    };
 
// ---- Создание и уничтожение --------------------------------------------------------------------
    
public:
    circle_list () : m_last(new node(value_type())), m_size(0) { m_last->previous = m_last->next = m_last; }
 
    ~circle_list () {
        if (m_last != 0) m_last->previous->next = 0;
        
        delete m_last;
    }
 
// ---- Модификации -------------------------------------------------------------------------------
    
    void push_back (const value_type & value) {
        node * new_node = new node(value);
        
        new_node->previous = m_last->previous;
        new_node->next = m_last;
        
        m_last->previous->next = new_node;
        m_last->previous = new_node;
        
        if (is_empty()) m_last->next = new_node;
        
        ++m_size;
    }
    
    iterator erase (iterator & position) {
        node * node_to_delete = position.m_node;
        node * result = node_to_delete->next;
        
        node_to_delete->previous->next = node_to_delete->next;
        node_to_delete->next->previous = node_to_delete->previous;
        
        node_to_delete->next = 0;
        delete node_to_delete;
        
        return position = iterator(result);
    }
 
// ---- Последовательный доступ -------------------------------------------------------------------
 
    iterator begin () { return ++iterator(m_last); }
    iterator end () { return iterator(m_last); }
 
// ---- Информация --------------------------------------------------------------------------------
    
    bool is_empty () const { return m_size == 0; }
    int size () const { return m_size; }
 
// ---- Переменные --------------------------------------------------------------------------------
    
private:
    node * m_last;
    
    int m_size;
};

Здесь многое упрощено, в частности, функция «erase», которая в оригинале работает немного не так.

Добавлено через 11 часов 36 минут
Хм, я erase неправильно написал. Так будет неправильно работать.

Добавлено через 43 минуты
Сложность в том, что, функция «erase» удаляет узел, на который в данный момент ссылается итератор, и из-за этого итератор в дальнейшем не может быть изменён из-за того, что его узел ссылается на нули.
Как это реализовано в СБШ пока не понял. Видимо, там какой-то небольшой сборщик мусора, который удаляет уже неиспользуемые узлы.

Добавлено через 19 минут
Придумал, как мне кажется, приемлимое решение: итератор запоминает указатели на следующий и предыдущий узлы на стадии инициализации, и поэтому удаление текущего узла на работа не сказывается:

C++

template <typename Value>
class circle_list {
 
// ---- Определения -------------------------------------------------------------------------------
 
public:
    typedef Value value_type;
 
// ---- Узел списка -------------------------------------------------------------------------------
 
private:
    struct node {
        explicit node (const value_type & value) : value(value), next(0), previous(0) {}
        ~node () { delete next; }
    
        value_type value;
        
        node * next;
        node * previous;
    };
 
// ---- Итераторы ---------------------------------------------------------------------------------
 
public:
    struct iterator {
        iterator () : current(0), next(0), previous(0) {}
        explicit iterator (node * n) : current(n), next(n->next), previous(n->previous) {}
        
        value_type & operator * () { return current->value; }
        value_type * const operator -> () { return &current->value; }
        
        iterator & operator ++ () { return *this = iterator(next); }
        iterator & operator -- () { return *this = iterator(previous); }
        
        bool operator == (const iterator & i) const { return current == i.current; }
        bool operator != (const iterator & i) const { return current != i.current; }
    
        node * current;
        node * next;
        node * previous;
    };
 
// ---- Создание и уничтожение --------------------------------------------------------------------
    
public:
    circle_list () : m_last(new node(value_type())), m_size(0) { m_last->previous = m_last->next = m_last; }
 
    ~circle_list () {
        m_last->previous->next = 0;
        
        delete m_last;
    }
 
// ---- Модификации -------------------------------------------------------------------------------
    
    void push_back (const value_type & value) {
        node * new_node = new node(value);
        
        new_node->previous = m_last->previous;
        new_node->next = m_last;
        
        m_last->previous->next = new_node;
        m_last->previous = new_node;
        
        ++m_size;
    }
    
    void push_front (const value_type & value) {
        node * new_node = new node(value);
        
        new_node->previous = m_last;
        new_node->next = m_last->next;
        
        m_last->next->previous = new_node;
        m_last->next = new_node;
        
        ++m_size;
    }
    
    void pop_front () {
        node * node_to_delete = m_last->next;
    
        m_last->next = node_to_delete->next;
        node_to_delete->next->previous = m_last;
        
        node_to_delete->next = 0;
        delete node_to_delete;
    }
    
    void pop_back () {
        node * node_to_delete = m_last->previous;
        
        m_last->previous = node_to_delete->previous;
        node_to_delete->previous->next = m_last;
        
        node_to_delete->next = 0;
        delete node_to_delete;
    }
    
    iterator insert (iterator position, const value_type & value) {
        node * new_node = new node(value);
        node * current_node = position.current;
        
        new_node->next = current_node->next;
        new_node->previous = current_node;
        
        current_node->next->previous = new_node;
        current_node->next = new_node;
        
        return iterator(new_node);
    }
    
    iterator erase (iterator position) {
        node * node_to_delete = position.current;
        node * result = node_to_delete->next;
        
        node_to_delete->previous->next = node_to_delete->next;
        node_to_delete->next->previous = node_to_delete->previous;
        
        node_to_delete->next = 0;
        delete node_to_delete;
        
        return iterator(result);
    }
    
    void clear () {
        m_last->previous->next = 0;
        delete m_last->next;
        
        m_last->previous = m_last->next = m_last;
        m_size = 0;
    }
    
// ---- Доступ к элементам ------------------------------------------------------------------------
 
    value_type & front () { return m_last->next->value; }
    const value_type & front () const { return m_last->next->value; }
    
    value_type & back () { return m_last->previous->value; }
    const value_type & back () const { return m_last->previous->value; }
 
// ---- Последовательный доступ -------------------------------------------------------------------
 
    iterator begin () { return ++iterator(m_last); }
    iterator end () { return iterator(m_last); }
 
// ---- Информация --------------------------------------------------------------------------------
    
    bool is_empty () const { return m_size == 0; }
    int size () const { return m_size; }
 
// ---- Переменные --------------------------------------------------------------------------------
    
private:
    node * m_last;
    
    int m_size;
};

@ForEveR · 13.02.2011, 00:59 **[ТС]**

volovzi, Однако действительно красиво. Попробую, спасибо

Добавлено через 34 минуты
Очень сильно помогло. Спасибо! Даже с алгоритмами пашет. Прекрасно. Буду доделывать дальше. Буду спрашивать, если не смогу справится. Спасибо огромное)

@volovzi · 13.02.2011, 01:06

Да не за что, самому интересно.

Добавлено через 4 минуты
Только нужно в удаления и добавлениях исправить корректировку размера списка, я там в нескольких местах забыл это сделать.

@ForEveR · 13.02.2011, 01:50 **[ТС]**

volovzi, Я пока с конструкторами занимаюсь. Ща разберусь и дальше продолжу) Спасибо огромное за помощь

Добавлено через 13 минут
Не могу понять вот такой фигни...
Есть два конструктора.

C++

    explicit List(size_t n, const T& value=T()):sz(0),head(new Node(T()))
    {
        head->prev=head->next=head;
        for(size_t i=0; i<n; ++i)
            push_back(value);
    }
    template<class iterator_>
    List(iterator_ first, iterator_ last):head(new Node(T())), sz(0)
    {
        head->prev=head->next=head;
        for(iterator_ beg=first; beg != last; ++beg)
            push_back(*beg);
    }

Почему он при вызове

C++

1	List<int> Lst(5, 3);

Упорно пытается вызвать мне второй конструктор? Я прям-таки в шоке. Соответственно не работает, ибо *int ничего не выйдет.

Добавлено через 6 минут
Решилось все вот таким способом

C++

1	List<int> Lst(static_cast<size_t>(5), 3);

Но все же это дико криво... Как-то ведь можно обойтись без такого чуда?

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	12.02.2011, 00:33 [ТС]	14
	volovzi, Это ответ на оба вопроса? 0

@volovzi 274 / 175 / 12 Регистрация: 14.03.2010 Сообщений: 501
	12.02.2011, 00:39	15
	Ага, на оба. 1

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	12.02.2011, 00:42 [ТС]	16
	Можешь приблизительно показать реализацию и использование такого фиктивного элемента? А то у меня что-то совсем туго... 0

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	13.02.2011, 00:59 [ТС]	18
	volovzi, Однако действительно красиво. Попробую, спасибо Добавлено через 34 минуты Очень сильно помогло. Спасибо! Даже с алгоритмами пашет. Прекрасно. Буду доделывать дальше. Буду спрашивать, если не смогу справится. Спасибо огромное) 0

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	11.02.2011, 20:56 [ТС]	3
	silent_1991, Офигеть... столько проколебался а все так просто... шок) 0

silent_1991 5055 / 3115 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	11.02.2011, 21:01	5
	ForEveR, когда списки пишешь - очень удобно на бумажке рисовать квадратики и стрелочки, соответствующие установке связок в алгоритме. Вот так нарисовал стрелочки и увидел, что одной не хватает - сразу понятно, что надо добавить. Попробуйте))) Не по теме: С "Ну так вы перед..." как-то грубовато вышло, извиняюсь))) 0

@volovzi 274 / 175 / 12 Регистрация: 14.03.2010 Сообщений: 501
	11.02.2011, 23:47	7
	ForEveR, если я не ошибаюсь, std::list является кольцевым двусвязным списком, и при этом даже когда он пуст, в нём присутствуют два элемента — начало и конец. А новые элементы при добавлении встраиваются между ними. Таким образом решается проблема с итераторами. 1

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	11.02.2011, 23:55 [ТС]	8
	volovzi, Не очень хочется делать список кольцевым... Есть какая-то другая возможность, без переделывания списка? 0

silent_1991 5055 / 3115 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	12.02.2011, 00:00	9
	Точно не скажу, но список в стл всё-таки по-моему не кольцевой. А то, что все его элементы вставляются между start (первым элементом) и end (фиктивным элементом, следующим за последним) - это да. Собственно, я и не понимаю, как список с такими параметрами может быть кольцевым (когда есть чёткое начало и, хоть и фиктивный, но всё же конец). 1

@volovzi 274 / 175 / 12 Регистрация: 14.03.2010 Сообщений: 501
	12.02.2011, 00:01	10
	ForEveR, как сделать без зацикливания так сходу не соображу, надо подумать. Добавлено через 1 минуту Вот цитата из СБШ: Код a %list conceptually represented as * @code * A <---> B <---> C <---> D * @endcode * is actually circular; a link exists between A and D. The %list * class holds (as its only data member) a private list::iterator * pointing to @e D, not to @e A! To get to the head of the %list, * we start at the tail and move forward by one. When this member * iterator's next/previous pointers refer to itself, the %list is * %empty. @endif Список кольцевой, но дополнительный элемент там один, а не два, как я думал. 2

silent_1991 5055 / 3115 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	12.02.2011, 00:03	11
	Сообщение от volovzi Список кольцевой Да, действительно. Не знал, спасибо. 0

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	12.02.2011, 00:28 [ТС]	12
	То есть, чтобы закольцевать, должен быть фиктивный элемент, при этом фиктивный элемент - элемент за последним и фикт элем->next указывает на голову списка? При этом должен ли head->prev указывать на фикт элемент? 0

@volovzi 274 / 175 / 12 Регистрация: 14.03.2010 Сообщений: 501
	12.02.2011, 00:29	13
	ForEveR, да, так там сделано. 1

@volovzi 274 / 175 / 12 Регистрация: 14.03.2010 Сообщений: 501
	13.02.2011, 01:06	19
	Да не за что, самому интересно. Добавлено через 4 минуты Только нужно в удаления и добавлениях исправить корректировку размера списка, я там в нескольких местах забыл это сделать. 1

Реализовать двунаправленный список в духе списка из STL

Решение