Форум программистов, компьютерный форум CyberForum.ru

Шаблонные двусвязные списки. - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.80
lemegeton
 Аватар для lemegeton
2909 / 1338 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
27.01.2012, 11:04     Шаблонные двусвязные списки. #1
Два велосипеда из закрома ов родина. Не пропадать же добру. А поделюсь -- так может какой студиозус найдет и порадуется.

Полнофункциональный, с итераторами.

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
159
160
161
162
163
164
165
166
167
168
#include <cstddef>
 
struct ListNodeBase {
  ListNodeBase() : prev(this), next(this) {}
  ListNodeBase(ListNodeBase *prev_, ListNodeBase *next_) : prev(prev_), next(next_) {
    prev->next = next->prev = this;
  }
  virtual ~ListNodeBase() {
    prev->next = next;
    next->prev = prev;
  }
  ListNodeBase *prev, *next;
};
 
template <class T>
struct ListNode : public ListNodeBase {
  ListNode(ListNodeBase *prev_, ListNodeBase *next_, const T &data_)
    : ListNodeBase(prev_, next_), data(data_) {}
  T data;
};
 
class ListIteratorBase {
 public:
  ListIteratorBase() : node_(NULL) {}
  ListIteratorBase(ListNodeBase *node) : node_(node) {}
  void increase() { node_=node_->next; }
  void decrease() { node_=node_->prev; }
  bool operator==(const ListIteratorBase &other) {
    return node_ == other.node_;
  }
  bool operator!=(const ListIteratorBase &other) {
    return !operator==(other);
  }
  ListNodeBase *node_;
};
 
template <class T, class R, class P>
class ListIterator : public ListIteratorBase {
 public:
  typedef ListIterator<T, T&, T*>             Iterator;
  typedef ListIterator<T, const T&, const T*> ConstIterator;
  typedef ListIterator<T, R, P>               Self;
  typedef T                                   ValueType;
  typedef R                                   ReferenceType;
  typedef P                                   PointerType;
  typedef ListNode<ValueType>                 Node;
  
  ListIterator() : ListIteratorBase() {}
  ListIterator(ListNodeBase *node) : ListIteratorBase(node) {}
  ListIterator(const Iterator &other) : ListIteratorBase(other.node_) {}
 
  ReferenceType operator*() const { return static_cast<Node*>(node_)->data; }
  ReferenceType operator->() const { return operator*(); }
  Self &operator++() {
    increase();
    return *this;
  }
  Self &operator--() {
    decrease();
    return *this;
  }
  Self operator++(int) {
    Self result(*this);
    increase();
    return result;
  }
  Self operator--(int) {
    Self result(*this);
    decrease();
    return result;
  }
  Self operator+(size_t n) {
    Self result(*this);
    while (n-- > 0) result.increase();
    return result;
  }
  Self operator-(size_t n) {
    Self result(*this);
    while (n-- > 0) result.decrease();
    return result;
  }
};
 
template <class T>
class List {
 public:
  typedef T             ValueType;
  typedef T&            ReferenceType;
  typedef const T&      ConstReferenceType;
  typedef T*            PointerType;
  typedef const T*      ConstPointerType;
  typedef ListNode<T>   Node;
  typedef ListIterator<T, T&, T*>             Iterator;
  typedef ListIterator<T, const T&, const T*> ConstIterator;
 
  List() : base_() {}
  List(const List &other) : base_() {
    insert(begin(), other.begin(), other.end());
  }
  ~List() { clear(); }
  List &operator=(const List &other) {
    if (this != &other) {
      clear();
      insert(begin(), other.begin(), other.end());
    }
    return *this;
  }
  Iterator begin() { return base_.next; }
  ConstIterator begin() const { return base_.next; }
  Iterator end() { return &base_; }
  ConstIterator end() const { return const_cast<ListNodeBase*>(&base_); }
  bool isEmpty() const { return &base_ == base_.next; }
  void clear() {
    while (!isEmpty()) {
      ListNodeBase *next = base_.next->next;
      delete base_.next;
      base_.next = next;
    }
  }
  size_t size() {
    size_t result = 0;
    for (Iterator i = begin(); i != end(); ++i) ++result;
    return result;
  }
  ReferenceType front() { return *begin(); }
  ConstReferenceType front() const { return *begin(); }
  ReferenceType back() { return *(--end()); }
  ConstReferenceType back() const { return *(--end()); }
 
  void pushBack(ConstReferenceType value) {
    new Node(base_.prev, &base_, value);
  }
  void pushFront(ConstReferenceType value) {
    new Node(&base_, base_.next, value);
  }
  ValueType popFront() {
    ValueType value = *begin();
    erase(begin());
    return value;
  }
  ValueType popBack() {
    ValueType value = *(--end());
    erase(--end());
    return value;
  }
  Iterator insert(Iterator before, ConstReferenceType value) {
    return new Node(before.node_->prev, before.node_, value);
  }
  template <class IteratorType>
  Iterator insert(Iterator before, IteratorType first, IteratorType last) {
    while (first != last)
      before = insert(before, *(first++)) + 1;
    return before;
  }
  Iterator erase(Iterator what) {
    Iterator result = what;
    ++result;
    delete what.node_;
    return result;
  }
  Iterator erase(Iterator begin, Iterator end) {
    while (begin != end)
      erase(begin++);
    return end;
  }
 private:
  ListNodeBase base_;
};
Пример использования:
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
#include <iostream>
#include "List.hpp"
 
template <class T, class Container = List<T> >
class Stack {
 public:
  Stack() : container() {}
  void push(const T &value) {
    container.pushBack(value);
  }
  T pop() {
    return container.popBack();
  }
  size_t size() const {
    return container.size();
  }
  void clear() {
    container.clear();
  }
  bool isEmpty() {
    return container.isEmpty();
  }
  const T &top() {
    return container.back();
  }
 private:
  Container container;
};
 
template <class T, class Container = List<T> >
class Queue {
 public:
  Queue() : container() {}
  void enqueue(const T &value) {
    container.pushBack(value);
  }
  T dequeue() {
    return container.popFront();
  }
  size_t size() const {
    return container.size();
  }
  void clear() {
    container.clear();
  }
  bool isEmpty() {
    return container.isEmpty();
  }
  const T &top() {
    return container.front();
  }
 private:
  Container container;
};
 
 
int main(int argc, char *argv[]) {
  List<int> list;
  for (int i = 0; i < 10; ++i)
    if (i % 2)
      list.pushBack(i);
    else
      list.pushFront(i);
  for (List<int>::Iterator i = list.begin(); i != list.end(); ++i)
    std::cout << *i << " ";
  std::cout << std::endl;
  
  Stack<int> stack;
  for (int i = 0; i < 10; ++i)
    stack.push(i);
  while (!stack.isEmpty())
    std::cout << stack.pop() << " ";
  std::cout << std::endl;
 
  Queue<int> queue;
  for (int i = 0; i < 10; ++i)
    queue.enqueue(i);
  while (!queue.isEmpty())
    std::cout << queue.dequeue() << " ";
  std::cout << std::endl;
}


Упрощенный, с комментариями.
Сразу с примером.
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
#include <iostream>
 
// нода связного списка
template <class T>
struct Node {
  // нулевой элемент связного списка указывает на себя
  Node() : prev(this), next(this) {}
  // добавление в связный список конструктором
  Node(Node *next_, const T &data_)
    : prev(next_->prev), next(next_), data(data_) {
    prev->next = next->prev = this;
  }
  // удаление из связного списка деструктором
  virtual ~Node() {
    prev->next = next;
    next->prev = prev;
  }
  Node *prev, *next;
  T data;
};
 
// шаблонный класс связного списка
template <class T>
class List {
 public:
  // конструктор
  List() : base(new Node<T>()) {}
  // конструктор копирования
  List(const List<T> &other) : base(new Node<T>()) {
    copyFrom(other);
  }
  // деструктор
  ~List() { clear(); delete base; }
  // оператор присваивания
  List<T> operator=(const List<T> &other) {
    if (&other != this) {
      clear();
      copyFrom(other);
    }
    return *this;
  }
  // проверка на пустоту связного списка
  bool empty() { return base->next == base; }
  // очистка связного списка
  void clear() {
    while (!empty())  delete base->next;
  }
  // вычисление размера связного списка
  size_t size() const {
    size_t size = 0;
    for (Node<T> *node = base->next; node != base; node = node->next)
      ++size;
    return size;
  }
  // копирование связного списка
  void copyFrom(const List<T> &other) {
    for (size_t i = 0; i < other.size(); ++i)      
      pushBack(other.get(i));
  }
  // добавление в конец списка
  void pushBack(const T &value) {
    new Node<T>(base, value);
  }
  // добавление в начало списка
  void pushFront(const T &value) {
    new Node<T>(base->next, value);
  }
  // первый эелемент списка
  const T &front() const {
    return base->next->data;
  }
  // последний элемент списка
  const T &back() const {
    return base->prev->data;
  }
  // возвращение и удаление первого элемента связного списка
  T popFront() {
    T result = front();
    delete base->next;
    return result;
  }
  // возвращение и удаление последнего элемента связного списка
  T popBack() {
    T result = back();
    delete base->prev;
    return result;
  }
  // вставка данных перед индексом
  void insert(size_t beforeIndex, const T &value) {
    Node<T> *before = base->next;
    while (beforeIndex-- > 0) before = before->next;
    new Node<T>(before, value);
  }
  // получение данных по индексу
  T &get(size_t n) {
    Node<T> *result = base->next;
    while (n-- > 0) result = result->next;
    return result->data;
  }
  // константный вариант
  const T &get(size_t n) const {
    Node<T> *result = base->next;
    while (n-- > 0) result = result->next;
    return result->data;
  }
  // получение элемента оператором
  T &operator[](size_t n) { return get(n); }
  // константный вариант
  const T &operator[](size_t n) const { return get(n); }
 
 private:
  // нулевой элемент связного списка
  Node<T> *base;
};
 
int main(int argc, char *argv[]) {
  List<int> a;
  for (size_t i = 0; i < 10; ++i)
    a.pushBack(i);
  a.insert(5, 0);
  
  List<int> b(a);
  a.insert(0, -1);
  b = a;
 
  for (size_t i = 0; i < b.size(); ++i)
    std::cout << b[i] << std::endl;
 
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.01.2012, 11:04     Шаблонные двусвязные списки.
Посмотрите здесь:

ДВУСВЯЗНЫЕ СПИСКИ C++
C++ ДВУСВЯЗНЫЕ СПИСКИ!!!
двусвязные списки C++
Двусвязные списки C++
Очереди и Двусвязные списки! C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
27.01.2012, 12:24     Шаблонные двусвязные списки. #2
List<T> & operator=(const List<T> &other)
Ошибка в прототипе.

Добавлено через 1 минуту
То же касается ещё некоторых методов. Ну и нулевой узел со значением по умолчанию слегка напрягает. Может и ещё чего, сильно не вчитывался.
lemegeton
 Аватар для lemegeton
2909 / 1338 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
27.01.2012, 14:19  [ТС]     Шаблонные двусвязные списки. #3
Цитата Сообщение от Deviaphan Посмотреть сообщение
List<T> & operator=(const List<T> &other)
Ошибка в прототипе.
Добавлено через 1 минуту
То же касается ещё некоторых методов. Ну и нулевой узел со значением по умолчанию слегка напрягает. Может и ещё чего, сильно не вчитывался.
Не вижу ошибки в прототипе.
В нулевом узле данные не инициализируются, поэтому не имеет значения.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
27.01.2012, 14:38     Шаблонные двусвязные списки. #4
Цитата Сообщение от lemegeton Посмотреть сообщение
Не вижу ошибки в прототипе.
Строка 35 в упрощённом варианте.
lemegeton
 Аватар для lemegeton
2909 / 1338 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
27.01.2012, 14:45  [ТС]     Шаблонные двусвязные списки. #5
Цитата Сообщение от silent_1991 Посмотреть сообщение
Строка 35 в упрощённом варианте.
Интересно получилось. У меня в локальной копии есть амперсанд.

Цитата Сообщение от Deviaphan Посмотреть сообщение
То же касается ещё некоторых методов.
В каких еще методах косяки?


Поправить бы это как-нибудь.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
27.01.2012, 15:10     Шаблонные двусвязные списки. #6
Цитата Сообщение от lemegeton Посмотреть сообщение
В каких еще методах косяки?
Ни в каких.) Я popBack прочитал как pushBack.
Yandex
Объявления
27.01.2012, 15:10     Шаблонные двусвязные списки.
Ответ Создать тему

Метки
двунаправленный список, двусвязанный список, двухсвязанный список, списки, шаблонный класс
Опции темы

Текущее время: 03:18. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru