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

@ForEveR · 11.02.2011, 20:37

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

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

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
    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++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
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 минуту
Вот цитата из СБШ:

Code
1
2
3
4
5
6
7
8
9
10
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++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
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++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
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++
1
2
3
4
5
6
7
8
9
10
11
12
13
    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);

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

Новые блоги и статьи Все статьи Все блоги /
Поиск всех путей на ориентированном графе. Linux dcc0 02.07.2026 Переработка старого кода из моей статьи. Через несколько переработок от PHP кода к C89 (надеюсь, 89). Но довольно запутанно получилось. Код для Linux. Но если убрать time и то, что с ним. . .	Сам себя обучал rest api anaschu 02.07.2026 Педагогический лайфхак: Почему чистый REST API для ученика намного круче, чем готовые библиотеки Когда мы отказались от капризного JAR-файла AnyLogic и переписали код на стандартный HttpClient,. . .
rest api anylogic - выполнение модели на своём русском сайте anaschu 02.07.2026 Как подружиться с AnyLogic Cloud API, победить провайдеров и развернуться Java-бэкенд в Docker на бесплатном хостинге: Двухдневный лог борьбы Всем привет! Хочу поделиться свежим (и довольно. . .	Где деньги лежат kumehtar 02.07.2026 Это - японская подводная лодка I-52 (тип C2, кодовое имя Momi) вышла из Японии в марте 1944 года с миссией в оккупированную немцами Францию (Лорьян). Это была одна из «Янаги»-миссий по обмену. . .
Krabik для WoW 3.3.5a, многоязычный AmbA 02.07.2026 Допилил бота, думаю что окончательно. Изменения: - добавлена многоязычность - добавлено снятие скриншотов - добавлено поддержание бафов хождения по воде (для жреца, дк и шамана) - и так, по. . .	Алиса нашла кучу ошибок компиляции и запуска в проекте, который без проблем компилировался и запускался))) anaschu 30.06.2026 Я пока посмеюся, но завтра проверю. А вообще интерсно. Дал алисе файл, в котором точно нет ошибок компиляции и запуска, и попросил их найти. Нашла кучу))) Критические ошибки, мешающие компиляции и. . .

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

Решение