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

Реализовать итератор для самодельного списка - C++

Восстановить пароль Регистрация
 
supra7sky
 Аватар для supra7sky
15 / 15 / 1
Регистрация: 07.02.2013
Сообщений: 123
20.04.2013, 22:18     Реализовать итератор для самодельного списка #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
#include <iostream>
using namespace std;
 
template<class T> class List
{
protected:
    T value;
    List *head,
         *tail,
         *next,
         *previous;
public:
    explicit List() { head = tail = next = previous = NULL; }
    explicit List(int SIZE, const T &OBJECT = T() ); // need real.
    List(const List<T> &OBJECT); // need real.
    //~List();
    // Добавление
    void push_back(const T &);
    void push_front(const T &);
    // Удаление
    void pop_back();
    void pop_front();
    // Поиск
 
    // iterator // keep node?
    class iterator
    {
    public:
        T *node;
    };
};
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ded_Vasilij
 Аватар для Ded_Vasilij
229 / 211 / 15
Регистрация: 01.09.2012
Сообщений: 2,103
20.04.2013, 23:50     Реализовать итератор для самодельного списка #2
итератор для двунаправленного списка
сам недавно делал

class L2_iterator
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
{
    L2* pList;
    L2_elem* current;
public:
    L2_iterator(L2* List) : pList(List), current(List->head) 
    {};
    int count();
    void Start();
    monom& GetValue();
    void Next();
    bool IsFinish();
};
//L2_iterator
void L2_iterator::Start()
{
    current = pList->head;
}
bool L2_iterator::IsFinish()
{
    return current == 0;
}
void L2_iterator::Next()
{
    if (!IsFinish())
        current = current->next;
}
 
monom& L2_iterator::GetValue()
{
    if (IsFinish())
    {
        throw ListError();
    }
    else    
    {
        return current->el;
    }
}
 
int L2_iterator::count()
{
    L2_elem*temp = pList->head;
    int i = 0;
    while (temp->next && temp != current )
    {
        temp = temp->next;
        i++;
    }
    return i;
}
Добавлено через 2 минуты
основная задача итератора бегать по списку, массиву, или еще чему-нубудь, получать значение на заданной позиции. Пример цикла с итератором
C++
1
2
3
L2_iterator I(L);
for (I.Start(L); !I.IsFinish(); I.Next())
   I.GetValue()
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
21.04.2013, 01:07     Реализовать итератор для самодельного списка #3
Итератор это такой шаблон проектирования. Пишется некий класс, с помощью объектов которого можно получать последовательный доступ к содержимому объекта-контейнера.
В С++ все особо цинично, поскольку можно перегружать "+" и "-", позволяя очень читабельно работать с итераторами.
Итераторы часто используются в C++ STL.


Пример самописного итератора (вместе с контейнером двусвязного списка):
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
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
#include <cstdlib>
#include <ctime>
#include <iostream>
 
struct ListNodeBase {
  ListNodeBase *prev, *next;
  ListNodeBase() : prev(this), next(this) {}
  ListNodeBase(ListNodeBase *prev, ListNodeBase *next) : prev(prev), next(next) {
    next->prev = prev->next = this;
  }
  virtual ~ListNodeBase() {
    next->prev = prev;
    prev->next = next;
  }
};
 
template <class T>
struct ListNode : public ListNodeBase {
  T value;
  ListNode(ListNodeBase *prev, ListNodeBase *next, const T &value)
    : ListNodeBase(prev, next), value(value) {}
};
 
struct ListIteratorBase {
  ListIteratorBase() : node(0) {}
  ListIteratorBase(ListNodeBase *node) : node(node) {}
  
  void increment() { node = node->next; }
  void decrement() { node = node->prev; }
  
  bool operator==(const ListIteratorBase &other) const {
    return node == other.node;
  }
  bool operator!=(const ListIteratorBase &other) const {
    return node != other.node;
  }
  ListNodeBase *node;
};
 
 
// двусторонний итератор
template <class ValueType, class PointerType, class ReferenceType>
struct ListIterator : public ListIteratorBase {
  typedef ValueType           Value;
  typedef PointerType         Pointer;
  typedef ReferenceType       Reference;
  typedef ListNode<ValueType> Node;
  typedef ListIterator<ValueType, PointerType, ReferenceType> Self;
  typedef ListIterator<ValueType, ValueType*, ValueType&> Iterator;
  typedef ListIterator<ValueType, const ValueType*,
    const ValueType&> ConstIterator;
  
  ListIterator() : ListIteratorBase() {}
  ListIterator(const Iterator &other) : ListIteratorBase(other.node) {}
  ListIterator(ListNodeBase *node) : ListIteratorBase(node) {}
  
  Reference operator*() const { return ((Node*)node)->value; }
  Pointer operator->() const { return &(operator*()); }
 
  Self &operator++() {
    increment();
    return *this;
  }
  Self &operator--() {
    decrement();
    return *this;
  }
  Self &operator++(int) {
    Self result = *this;
    increment();
    return result;
  }
  Self &operator--(int) {
    Self result = *this;
    decrement();
    return result;
  }
  
};
 
// итератор добавления в конец списка
template <class Container>
struct BackInsertIterator {
 protected:
  Container &container;
 public:
  typedef void Value;
  typedef void Pointer;
  typedef void Reference;
  explicit BackInsertIterator(Container &container)
    : container(container) {}
  BackInsertIterator &operator=(const typename Container::Value &value) {
    container.pushBack(value);
    return *this;
  }
  BackInsertIterator &operator*() { return *this; }
  BackInsertIterator &operator++() { return *this; }
  BackInsertIterator &operator++(int) { return *this; }
};
 
// удобная функция для создания итератора добавления
template <class Container>
BackInsertIterator<Container> getBackInserter(Container &container) {
  return BackInsertIterator<Container>(container);
}
 
template <class T>
class List {
 public:
  typedef T Value;
  typedef T* Pointer;
  typedef T& Reference;
  typedef ListIterator<T, T*, T&> Iterator;
  typedef ListIterator<T, const T*, const T&> ConstIterator;
  
  List() : size(0), base() {}
  List(const List &other) : size(0), base() {
    insert(other.begin(), other.end());
  }
  List &operator=(const List &other) {
    if (this != &other) {
      clear();
      insert(other.begin(), other.end());
    }
    return *this;
  }
  virtual ~List() {
    clear();
  }
  
  Iterator begin() { return (Node*)(base.next); }
  ConstIterator begin() const { return (Node*)(base.next); }
  Iterator end() { return (Node*)(&base); }
  ConstIterator end() const { return (Node*)(&base); }
  
  Iterator insert(Iterator position, const T &value) {
    ++size;
    return new Node(position.node->prev, position.node, value);
  }
  void insert(Iterator position, Iterator first, Iterator last) {
    while (first != last) {
      position = insert(position, *first++);
      ++position;
    }
  }
  Iterator erase(Iterator position) {
    Iterator next = position.node->next;
    delete position.node;
    -- size;
    return next;
  }
  Iterator erase(Iterator first, Iterator last) {
    while (first != last) {
      first = erase(first);
    }
    return first;
  }
  Iterator pushBack(const T &value) {
    return insert(end(), value);
  }
  Iterator pushFront(const T &value) {
    return insert(begin(), value);
  }
  bool isEmpty() const { return base.next == &base; }
  void clear() {
    while (!isEmpty()) {
      delete base.next;
    }
    size = 0;
  }
 private:
  typedef ListNode<T> Node;
  size_t size;
  ListNodeBase base;
};
 
template <class OutputIterator, class Size, class Generator>
void generateN(OutputIterator first, Size n, Generator generator) {
  while (n-- > 0) {
    *first++ = generator();
  }
}
 
 
struct RandomGenerator {
  int min, max;
  RandomGenerator(int min, int max) : min(min), max(max) {}
  int operator()() { return rand() % (max - min) + min; }
};
 
int main(int argc, char **argv) {
  srand(time(0));
 
  List<int> list;
 
  // генерация десяти случайных чисел с добавлением в конец контейнера
  generateN(getBackInserter(list), 10, RandomGenerator(0, 10));
 
  // вывод контейнера на экран  
  for (List<int>::ConstIterator i = list.begin(); i != list.end(); ++i) {
    std::cout << *i << std::endl;
  }
  
  return 0;
}
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11845 / 6824 / 771
Регистрация: 27.09.2012
Сообщений: 16,919
Записей в блоге: 2
Завершенные тесты: 1
21.04.2013, 01:11     Реализовать итератор для самодельного списка #4
Паттерн Iterator
Yandex
Объявления
21.04.2013, 01:11     Реализовать итератор для самодельного списка
Ответ Создать тему
Опции темы

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