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

Как более менее правильно написать итератор(не STL). - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 68, средняя оценка - 4.79
Chelioss
179 / 179 / 4
Регистрация: 08.01.2011
Сообщений: 1,131
17.09.2011, 23:44     Как более менее правильно написать итератор(не STL). #1
Вот, например, пишу класс и всегда помню советы типа "скрывайте реализацию класса" или "если функция по идее не должна изменять данные класса, то сделайте ее const ".
Почитал про итератор тут http://www.insidecpp.ru/patterns/iterator/
Прочитал то, что пишет ValeryLaptev Итератор ?
Почитал на wiki.
В книге Дейтелов почти ничего про это нет.
Но не понял как пишется более менее нормально итератор.
Единственную реализацию итератора, которую знаю, эта которая по первой ссылке.
Но т.к. я не знаю как правильно писать итератор, то мне кажется эта реализация кривыми. Может там все грамотно написано, но я не могу это принять.
Т.е. если я буду писать итератор, то я буду писать то, что сразу в голову придет, не задумываясь правильно я делаю. Буду писать говнокод.
Где можно посмотреть нормальную реализацию итератора? Хотелось бы в двух видах, т.е. в виде iter.next()(функция) и ++iter(как указатель), как в первой ссылке.
И где почитать можно на русском.
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.09.2011, 23:44     Как более менее правильно написать итератор(не STL).
Посмотрите здесь:

C++ Как правильно написать???
C++ Написать свой итератор, чтобы алгоритмы STL работали с моим классом
как можно более просто написать эту программку(более понятным языком для начинающего) C++
C++ Функция, дружественная классу, вложенному в шаблонный класс, или как написать итератор.
C++ Почему не запоминается правильно итератор вектора?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ValeryLaptev
Эксперт C++
1005 / 784 / 46
Регистрация: 30.04.2011
Сообщений: 1,595
17.09.2011, 23:50     Как более менее правильно написать итератор(не STL). #2
Chelioss, в книге Банды четырех, вестимо...
Chelioss
179 / 179 / 4
Регистрация: 08.01.2011
Сообщений: 1,131
17.09.2011, 23:53  [ТС]     Как более менее правильно написать итератор(не STL). #3
Цитата Сообщение от ValeryLaptev Посмотреть сообщение
Chelioss, в книге Банды четырех, вестимо...
Как книга называет правильно?
ValeryLaptev
Эксперт C++
1005 / 784 / 46
Регистрация: 30.04.2011
Сообщений: 1,595
18.09.2011, 00:03     Как более менее правильно написать итератор(не STL). #4
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Вот еще из моих материалов.
Надеюсь, что даже в таком виде это поможет разобраться.

Итератор для последовательного контейнера

Для дека нам потребуются конструкторы и деструктор. Минимально необходимое множество операций включает операции добавления элемента в начало и конец дека, операции удаления первого и последнего элемента. Еще необходимы функция проверки, есть ли в контейнере элементы, и функция, выдающая количество элементов в контейнере. Обычно в состав методов включают и методы получения значений первого и последнего элемента контейнера. Рассмотрим более подробно операцию доступа к элементам контейнера.
Так как внутренняя структура элемента скрыта, поскольку прописана в приватной части класса-дека, программа-клиент не сможет работать с элементами контейнера посредством указателей. Для перебора элементов контейнер должен обеспечить последовательный доступ к элементам другим способом. Это можно сделать двояким образом:
1. либо реализовать методы доступа непосредственно как методы контейнера;
2. либо инкапсулировать все операции доступа в отдельный класс-итератор.
Второе решение предпочтительней хотя бы потому, что позволяет отделить интерфейс доступа от интерфейса контейнера. Это позволит в дальнейшем иметь один и тот же универсальный интерфейс доступа для разных типов контейнеров. Таким образом, итераторы играют очень важную роль при инкапсуляции информации контейнеров.

ВНИМАНИЕ
Именно таким образом реализованы итераторы в стандартной библиотеке шаблонов STL. Это одно из решений, оказавших существенное влияние на состав и структуру стандартной библиотеки.

Класс-итератор можно реализовать как отдельный независимый класс. Но так как итератор должен иметь доступ к внутренней структуре элемента контейнера, он должен с этим классом «дружить». Очевидно, что итератор очень тесно связан с внутренней организацией контейнера, поэтому лучше его реализовать как вложенный класс [1-9.7] класса-контейнера, как и класс-узел. Поскольку программе-клиенту потребуется создавать объекты-итераторы, этот класс должен быть определен в открытой части класса контейнера.
Назовем класс-итератор именем iterator. Мы нарушили собственное правило начинать имя класса с буквы Т только потому, что при создании итератора программа-клиент обязана будет указать префикс — имя объемлющего класса, например
C++
1
TDeque::iterator it;
Таким образом, мы расширяем наше правило: открытые вложенные классы мы будем называть английским словом, полностью написанным строчными (маленькими) буквами.
Значение итератора представляет собой позицию в контейнере. Набор операций с итераторами фактически уже описан нами выше (см. выше раздел «Доступ к элементам контейнера»), однако полезно еще раз на этом остановиться. Итак, класс-итератор должен обеспечивать следующий минимальный набор операций:
- * — получение элемента в текущей позиции итератора;
- = — присваивание итератора;
- == и != — проверка совпадения позиций, представленных двумя итераторами;
- ++ — перемещение итератора к следующему элементу контейнера.
Итератор с таким набором операций в стандартной библиотеке называется прямым. Если мы добавим операцию перемещения к предыдущей позиции (декремент --), то получим итератор, который в стандартной библиотеке называется двунаправленным. Отметим, что набор операций двунаправленного итератора соответствует множеству операций с указателями при переборе элементов массива. Это позволяет одинаковым образом обращаться и с массивами, и контейнерами. Однако надо отметить, что встроенные указатели, по выражению Д.Элджера [25], являются «глупыми», тогда как итератор мы можем сделать настолько «умным», насколько пожелаем.

Для того, чтобы начать перебирать элементы контейнера, итератору надо присвоить первоначальное значение на первый элемент контейнера. Обычно для этого в контейнер включают метод begin(), который в качестве результата возвращает итератор, установленный в начало последовательности элементов контейнера.

Метод end() возвращает итератор, установленный в конец последовательности элементов контейнера. Что считать концом последовательности, составляет важный вопрос реализации. По примеру STL (STL — прекрасный пример для подражания!) будем считать, что концом последовательности является позиция за последним элементом последовательности. Таким образом, пара методов begin(), end() определяет полуоткрытый интервал, который содержит первый элемент, но выходит за пределы последнего элемента. Это в точности соответствует ситуации, описанной нами при реализации конструктора класса TArray (см. листинг 3.3).

Полуоткрытый интервал обладает двумя достоинствами:
- не нужно специально обрабатывать пустой интервал, так как в пустом интервале begin() равно end();
- упрощается проверка завершения перебора элементов контейнера — цикл продолжается до тех пор, пока итератор не достигнет позиции end().
Для реализации полуоткрытого интервала в контейнер обычно добавляют «пустой» фиктивный элемент, не содержащий данных.

Реализация контейнера-дека
Обратимся теперь непосредственно к реализации. Сначала покажем составляющие класса TDeque, а затем всю его структуру. В листинге 3.19 представлена приватная часть класса.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Листинг 3.19. Приватная часть класса TDeque
private:
    class Elem                          // элемент дека
    {   friend class TDeque;                    
        friend class iterator;
        Elem(const double &a):item(a){ }
        Elem(){}                 
        ~Elem(){}               // объявлять необязательно
        double item;            // информационная часть элемента
        Elem *next;             // следующий элемент    
        Elem *prev;             // предыдущий элемент
    };
    // запрещаем копировать и присваивать деки
    TDeque& operator=(const TDeque &);  
    TDeque(const TDeque &); 
    long count;                 // количество элементов
    Elem *Head;                 // Начало дека
    Elem *Tail;                 // указатель на запредельный элемент 
    // для итератора
    iterator head;
    iterator tail;
Вся внутренность класса Elem закрыта, поэтому классы TDeque и iterator объявлены друзьями, чтобы иметь доступ к конструкторам и указателю. Можно поступить и по-другому — просто объявить все члены класса Elem открытыми:
C++
1
2
3
4
5
6
7
8
9
class Elem
{ public:   
        Elem(const double &a):item(a){ }
        Elem(){}                 
        ~Elem(){}               // объявлять необязательно
        double item;            // информационная часть элемента
        Elem *next;             // следующий элемент    
        Elem *prev;             // предыдущий элемент
};
В этом случае друзей объявлять не требуется – они и так имеют доступ ко всем элементам класса.
Чтобы не отвлекаться от главной задачи — изучения доступа посредством итератора, — мы объявили конструктор копирования и операцию присваивания закрытыми. Да и нет особой необходимости (пока) присваивать деки. Наличие объявления приводит к тому, что компилятор не будет создавать эти функции по умолчанию. Таким образом, мы запретили создавать копии контейнера-дека и присваивать один дек другому. Следствием является так же и то, что контейнер нельзя передавать по значению в качестве параметра и возвращать в качестве результата.

Далее объявлены поля класса TDeque: счетчик элементов контейнера, реальные указатели на начало и конец списка. Счетчик увеличивается при каждом добавлении элемента и уменьшается при каждом удалении элемента. Поля-указатели никогда не равны 0, так как даже в пустом контейнере присутствует запредельный фиктивный элемент

А вот программе-клиенту указатели недоступны — она работает с итераторами. Следовательно, нужны аналогичные поля для класса-итератора, которые этим классом и инициализируются. Сам класс-итератор (листинг 3.20) прописан в открытой части класса TDeque.
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
Листинг 3.20. Класс iterator
class iterator              
{   friend class TDeque;
    iterator(Elem *el):the_elem(el){}
   public:
    // конструкторы
    iterator():the_elem(0){}
    iterator(const iterator &it):the_elem(it.the_elem){}
    // присваивание итераторов – генерируется по умочанию
    // сравнение итераторов
    bool operator==(const iterator &it) const
    { return (the_elem == it.the_elem); }
    bool operator!=(const iterator &it) const
    { return !(it == *this); }
    // продвижение к следующему элементу – только префиксная форма
    iterator& operator++()
    {   if ((the_elem!=0)&&(the_elem->next!=0))
            the_elem = the_elem->next;
        return *this;
    }
    // продвижение к предыдущему элементу – только префиксная форма
    iterator& operator--()
    {   if ((the_elem!=0)&&(the_elem->prev!=0))
            the_elem = the_elem->prev;
        return *this;
    }
    // получить ссылку на информационную часть 
    // работает справа и слева от знака присваивания
    double& operator*() const
    { if (the_elem != 0) return the_elem->item;
      else { cout << "Null iterator!" << endl; exit(1); }
    }
 private:
    Elem *the_elem;     // вот это итератор скрывает! 
};
Единственный закрытый элемент класса — указатель на элемент контейнера-дека. Именно это должен скрывать итератор, предоставляя пользователю более надежный способ доступа. Однако для первоначальной установки указателя нашему деку требуется конструктор с указателем. Поэтому реализован приватный конструктор, и класс-дек сделан другом класса-итератора.

Хотя мы не обрабатываем ошибки , тем не менее, операции продвижения не приводят к непредсказуемому поведению программы — при некорректном указателе продвижение просто не выполняется и возвращается текущий итератор.

В операции разыменования operator * указатель на элемент проверяется на ноль. Эта проверка необходима, так как в классе-итераторе есть конструктор по умолчанию, обнуляющий этот указатель — программа-клиент ведь может объявить итератор, но не инициализировать его.

ПРИМЕЧАНИЕ
Вообще-то говоря, мы можем сделать этот конструктор приватным — тогда пользовательская программа не сможет создавать нулевые итераторы. Естественно, и проверка на ноль тогда будет тоже не нужна.

Все методы удобнее реализовать именно внутри класса, так как при реализации вне класса (и вне класса TDeque), придется писать слишком длинные префиксы.
С учетом всех этих соображений класс TDeque, представленный в листинге 3.21, выглядит следующим образом:
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
Листинг 3.21. TDeque – контейнер-дек
class TDeque
{   class Elem;                     // опережающее объявление
  public:
    class iterator { //… см. листинг 3.20 };    
  public:
    // создаем пустой дек – с фиктивным запредельным элементом
    TDeque():Head(new Elem()), Tail(Head), count(0)  
    { Tail->next=Tail->prev=0; 
      head = iterator(Head);            // инициализация для итератора
      tail = iterator(Tail);            // приватным конструктором
    }
    // создаем дек с единственным элементом 
    TDeque(const double& a):Head(new Elem()), Tail(Head), count(0) 
    { Tail->next=Tail->prev=0;
      head = iterator(Head);
      tail = iterator(Tail);
      push_front(a);
    }
    ~TDeque();
    bool isEmpty() const                    // есть ли элементы в деке
    { bool t = (Head == Tail); return t; }
    long size() const { return count; }     // количество элементов в деке
    // методы доступа   
    iterator begin() { return head; }       // первый элемент
    iterator end()   { return tail; }       // запредельный элемент
    // методы вставки и удаления на концах дека
    void push_front(const double &a);
    void push_back(const double &a);
    void pop_front();
    void pop_back();
  private:
    // … см. листинг 3.19
};
В этом классе надо обратить внимание на несколько моментов. Во-первых, так как приватная часть прописана в конце, то требуется опережающее объявление класса Elem, иначе класс iterator не может объявить свой указатель на элемент. Так как объявлено только имя класса, то создавать объекты не разрешается (компилятору на момент объявления не известен размер объекта), но определять указатель на такой объект вполне можно.
Во-вторых, мы непосредственно в классе объявили два конструктора с практически идентичным телом. Почему бы во втором конструкторе не использовать первый, как мы обычно поступали, например
C++
1
2
3
4
5
TDeque(const double& a) 
{ TDeque t;
  t.push_front(a);
  *this = a;                // "облом" – операция присваивания недоступна
}
Однако мы не можем этого сделать, так как закрыли операцию присваивания.

Рассмотрим теперь реализацию операций вставки и удаления в начале дека (листинг 3.22).
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Листинг 3.22. Операции вставка и удаление в голове дека
// добавить элемент
void TDeque::push_front(const double &a)
{   Elem *p = new Elem(a);          // образовали новый элемент
    p->next = Head; p->prev = 0;    // "привязали" 
    Head->prev = p; Head = p;       // первым в деке
    head = iterator(Head);          // корректируем итератор
    ++count;                        // добавили элемент
}
// удалить элемент
void TDeque::pop_front()
{   if (!isEmpty())                 // если есть элементы
    { Elem *p = Head;               // сохраняем указатель для удаления
      Head = Head->next;            // "отцепляем"
      Head->prev = 0;               // элемент
      head = iterator(Head);            // корректируем итератор
      --count;                      // уменьшаем количество
      delete p;                         // возвращаем память
    }
}
Как видите, реализация не очень сложная. Единственное, на что следует обратить самое пристальное внимание, — это порядок присваивания указателей. Кроме того, операция удаления обязана проверить наличие элементов в деке — если дек пуст, то операция ничего не делает.
В листинге 3.23 показана реализация операций вставки и удаления элементов в конце дека. И здесь тоже необходимо самым внимательнейшим образом отследить порядок работы с указателями. Кроме того, обратите внимание на то, что в данном случае не требуется корректировать итератор, так как указатель Tail фиксирован и никогда не изменяется — он всегда указывает на запредельный элемент.
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
Листинг 3.23. Вставка и удаление элементов в конце дека
// вставка элемента
void TDeque::push_back(const double &a)
{   if (isEmpty()) push_front(a);   // если вставляем первый раз 
    else 
    { Elem *p = new Elem(a);        // создали элемент
        p->next = Tail;             // "привязываем"
        p->prev = Tail->prev;       // перед 
        Tail->prev->next = p;       // фиктивным 
        Tail->prev = p;                 // элементом
    }
    ++count;                        // добавили элемент
};
// удаление элемента
void TDeque::pop_back()
{   if (!isEmpty())                 // если есть элементы
    { Elem *p = Tail->prev;         // сохраняем для удаления
      if (p == 0) pop_front();      // если элемент единственный
      else 
      { p->prev->next = Tail;       // отцепляем 
        Tail->prev = p->prev;       // элемент
        delete p;                   // возвращаем память
      }
      --count;                      // уменьшаем количество
    }
}
И наконец, рассмотрим деструктор, текст которого представлен в листинге 3.24.
C++
1
2
3
4
5
6
7
8
9
10
Листинг 3.24. Деструктор дека
TDeque::~TDeque()
{   Elem *delete_Elem = Head;           // удаляемый элемент
    for(Elem *p = Head; p!=Tail;)       // Пока не уперлись в запредельный
    { p = p->next;                      // подготовили следующий
      delete delete_Elem; --count;      // удалили элемент
      delete_Elem = p;                  // подготовили для удаления
    }
    delete delete_Elem;                 // удалили запредельный
}
В цикле удаляются все «значащие» элементы контейнера. После выхода из цикла у нас остается только запредельный элемент, который мы удаляем отдельным оператором delete.
Проверить работу операций вставки и удаления, а также доступа к элементам по итератору, можно, выполнив программу, представленную в листинге 3.25.
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
Листинг 3.25. Тестовая программа для проверки работы контейнера-дека
int main()
{   TDeque L(8.0);              // создали дек из одного элемента
    // добавляем 5 элементов в начало – стало 6
    L.push_front(1); L.push_front(2); L.push_front(3); 
    L.push_front(4); L.push_front(5);
    cout << L.size()<< endl;        // выводим количество элементов
    TDeque::iterator i;             // объявили итератор
    // вывод элементов контейнера 
    for(i = L.begin(); i != L.end(); ++i)   // изменение итератора
         cout << *i << ' ';         // вывод значения
    cout << endl;
    // добавляем пять элементов в конец дека – стало 11
    L.push_back(1); L.push_back(2); L.push_back(3); 
    L.push_back(4); L.push_back(5);
    // вывод элементов контейнера 
    for(i = L.begin(); i != L.end(); ++i) 
         cout << *i << ' ';  cout << endl;
    cout << L.size()<< endl;        // выводим количество элементов
    // Обратный перебор 
    i = L.end();                // на запредельный элемент
    while(i != L.begin())           // пока не дошли до первого
    { --i;                  // сначала переходим на реальный элемент
      cout << *i << ' ';            // выводим значение
    } 
    cout << endl;
    // удалили 4 элемента в начале дека – осталось 7
    L.pop_front(); L.pop_front(); L.pop_front(); L.pop_front();
    // вывод элементов контейнера
    for(i = L.begin(); i != L.end(); ++i) 
         cout << *i << ' ';  cout << endl;
    cout << L.size()<< endl;            // выводим количество элементов
    // удалили 3 элемента в конце дека – осталось 4
    L.pop_back(); L.pop_back(); L.pop_back(); 
    // вывод элементов контейнера
    for(i = L.begin(); i != L.end(); ++i) 
         cout << *i << ' ';  cout << endl;
    cout << L.size()<< endl;            // выводим количество элементов
    return 0;                   
}       // работает деструктор, удаляя 4 элемента и запредельный элемент
Единственное, на что следует обратить внимание в этой программе, — это обратный перебор элементов дека. Итератор устанавливается на запредельный элемент, и перед выводом значения сначала должен быть переведен на последний реальный элемент. Это делает операция декремента.
Результат программы соответствует комментариям:
C
1
2
3
4
5
6
7
8
9
6                   // количество элементов в деке
5 4 3 2 1 8             // элементы дека
5 4 3 2 1 8 1 2 3 4 5       // прямой перебор элементов дека
11                  // количество элементов
5 4 3 2 1 8 1 2 3 4 5       // обратный перебор элементов дека
1 8 1 2 3 4 5           // удалили 4 элемента в начале
7                   // количество элементов после удаления
1 8 1 2             // удалили 3 элемента в конце
4                   // количество элементов после удаления
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
18.09.2011, 12:50     Как более менее правильно написать итератор(не STL). #5
Цитата Сообщение от Chelioss Посмотреть сообщение
Как книга называет правильно?
Гамма Э., Хелм Р., Джонсон Р., Влиссидес Дж. - Приемы объектно-ориентированного проектирования. Паттерны проектирования
sandye51
программист С++
 Аватар для sandye51
677 / 579 / 39
Регистрация: 19.12.2010
Сообщений: 2,016
18.09.2011, 13:49     Как более менее правильно написать итератор(не STL). #6
вот мой совместимый с 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
template <typename iteratorValueType>
    struct vector_iterator
    {
        typedef iteratorValueType value_type;
        typedef iteratorValueType& reference;
        typedef iteratorValueType* pointer;
        typedef std::random_access_iterator_tag iterator_category;
        typedef std::ptrdiff_t difference_type;
        typedef std::ptrdiff_t distance_type;
 
        explicit vector_iterator(const pointer value = pointer()) :
        _value(const_cast<pointer>(value))
        {
        }
 
        vector_iterator& operator ++ ()
        {
            ++_value;
            return *this;
        }
 
        vector_iterator operator ++ (int)
        {
            return vector_iterator(_value++);
        }
 
        vector_iterator& operator -- ()
        {
            --_value;
            return *this;
        }
 
        vector_iterator operator -- (int)
        {
            return vector_iterator(_value--);
        }
 
        bool operator < (const vector_iterator& value) const
        {
            return _value < value._value;
        }
 
        bool operator != (const vector_iterator& value) const 
        {
            return _value != value._value;
        }
 
        bool operator == (const vector_iterator& value) const 
        {
            return _value == value._value;
        }
 
        difference_type operator - (const vector_iterator& value) const 
        {
            return _value - value._value;
        }
 
        vector_iterator operator - (distance_type value) const
        {
            return vector_iterator(_value - value);
        }
 
        vector_iterator operator + (distance_type value) const 
        {
            return vector_iterator(_value + value);
        }
 
        reference operator * ()
        {
            return *_value;
        }
 
        pointer operator -> ()
        {
            return _value;
        }
 
    private:
        pointer _value;
    };
Chelioss
179 / 179 / 4
Регистрация: 08.01.2011
Сообщений: 1,131
18.09.2011, 17:04  [ТС]     Как более менее правильно написать итератор(не STL). #7
У меня есть вопрос про итератор по первой ссылке.
Тип T - это понятно. Будет, например, int, тогда везде вместо T "подставиться", грубо говоря, int.
Например, в методе begin контейнера создается итератор и в зависимости от типа указателя, итератор подменяет T на какой-то тип. Итератор it в main от метода begin получает итератор определенной T специализации и итератор it принимает такой тип T.
А что за тип node? Откуда он берется? Как его компилятор определяет?
По идее же конструктор iterator должен принимать T * n, а он принимает какой-то тип node * n.
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
18.09.2011, 17:16     Как более менее правильно написать итератор(не STL). #8
Chelioss, итератор определяется для структуры данных (контейнера), а не для типа, который хранится в этом контейнере.
Chelioss
179 / 179 / 4
Регистрация: 08.01.2011
Сообщений: 1,131
18.09.2011, 17:20  [ТС]     Как более менее правильно написать итератор(не STL). #9
Цитата Сообщение от fasked Посмотреть сообщение
Chelioss, итератор определяется для структуры данных, а не для типа, который хранится в этой структуре.
Не совсем понял.
1)Вот что по первой ссылке будет вставляться вместо node, если контейнер содержит в себе элементы string? Я так понимаю, что вместо T будет тип string, а что вместо node?
2)Если я пишу свой шаблонный итератор, то мне тоже надо делать два типа, т.е. node и T?
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
18.09.2011, 17:24     Как более менее правильно написать итератор(не STL). #10
Цитата Сообщение от Chelioss Посмотреть сообщение
Вот что по первой ссылке будет вставляться вместо node, если контейнер содержит в себе элементы string?
вместо node будет подставлен list_node <string>
Цитата Сообщение от Chelioss Посмотреть сообщение
Если я пишу свой шаблонный итератор, то мне тоже надо делать два типа, т.е. node и T
Зависит от контейнера. В общем случае итератор должен "шагать" по элементам согласно определенному порядку.
Если контейнер - это вектор (элементы в памяти хранятся последовательно), то node не нужен, так как достаточно двигать указатель на элемент. Если связный список, то node это узел списка. А без него "шагать" не получится.
Chelioss
179 / 179 / 4
Регистрация: 08.01.2011
Сообщений: 1,131
18.09.2011, 17:36  [ТС]     Как более менее правильно написать итератор(не STL). #11
1)А можно написать вместо класса итератора по первой ссылке класс итератор с 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
template <class T>
class iterator
{
public:
 
    iterator(list_node<T>* n)
    : node_ptr(n)
    {
    }
 
    T* operator * ()
    {
        return node_ptr->get();
    }
 
    T* operator -> ()
    {
        return node_ptr->get();
    }
 
    void operator ++ ()
    {
        node_ptr = node_ptr->next();
    }
 
    iterator operator ++ (int)
    {
        iterator iter(*this);
        ++(*this);
        return iter;
    }
 
    bool operator == (iterator const& i)
    {
        return node_ptr == i.node_ptr;
    }
 
    bool operator != (iterator const& i)
    {
        return !(*this == i);
    }
 
private:
 
    list_node<T> * node_ptr;
};
2)По первой ссылке:
C++
1
string_container::iterator it
где string_container это
C++
1
 typedef list<std::string> string_container;
Т.е. string_container:: указывает шаблону, что вместо node надо использовать list_node <string>
Так?
Если по первому вопросу я правильно сказал, то можно неиспользуя тип node, перед iterator it не писать string_container::?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.09.2011, 17:39     Как более менее правильно написать итератор(не STL).
Еще ссылки по теме:

Ввести строку (не более 100 символов и не менее 30), вывести символы с 7 по 15 C++
C++ STL: Сортировка слов по количеству согласных букв; вывод слов, встречающихся в списке более одного раза
C++ STL итератор на конец контейнера

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
18.09.2011, 17:39     Как более менее правильно написать итератор(не STL). #12
Цитата Сообщение от Chelioss Посмотреть сообщение
А можно написать
Можно, конечно, просто это будет чуть менее гибкий итератор в том плане, что он будет пригоден только для узлов одного типа. По ссылки, если у нескольких типов узлов одинаковый интерфейс, то его можно было бы применять для всех. Хотя мне сложно представить такую ситуацию
Yandex
Объявления
18.09.2011, 17:39     Как более менее правильно написать итератор(не STL).
Ответ Создать тему
Опции темы

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