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

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

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

Все-таки видимо у меня всегда останутся с этим проблемы.
Само определение скидывать не буду, я пытаюсь сделать, что-то вроде 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);

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

Новые блоги и статьи Все статьи Все блоги /
Перемещение выделенных строк ТЧ из одного документа в другой Maks 30.03.2026 Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .	Functional First Web Framework Suave DevAlt 30.03.2026 Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .	Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .	Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .
Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .	Автозаполнение реквизитов при создании документа Maks 26.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .	Команды формы и диалоговое окно Maks 26.03.2026 1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .

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

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

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

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

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

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

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

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

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

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

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

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

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

Решение