Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Помогите считать цифры из файла в переменные http://www.cyberforum.ru/cpp-beginners/thread353134.html
У меня есть файл в котором записаны значения переменных, например, в таком формате: 700 5 3 Естественно переменные разделены пробелом. Так вот... Считывать строки слова и т.п. в формате char я...
C++ Максимальная степень двойки "F(a, b) = x - 1, где x - максимальная степень двойки, на которую делится нацело a-b, если a ≠ b и F(a, b) = -1, если a = b." Это как так возможно? Например: a=5, b=2; следовательно a-b=3; число... http://www.cyberforum.ru/cpp-beginners/thread353117.html
сортировка (метод прямого выбора) C++
Народ, подскажите почему неправильно считает количество перестановок М? Уже час голову ломаю(#include <stdio.h> #include <conio.h> #include <vcl.h> #define N 10 #pragma hdrstop ...
C++ ввод букв вместо цифр
Привет. Я новичок. Подскажите как сделать так чтобы, в консольной программе при вводе букв вместо цифр выдавалось сообщение об ошибке.
C++ Считывание чисел из файла с расширением .txt http://www.cyberforum.ru/cpp-beginners/thread352689.html
Решаю на с++ задачу, которая называется «Вырубка деревьев». Входными данными являются два целых числа, записанных через пробел в файле .txt. Помогите считать эти числа из файла и записать их в...
C++ Поиск места в массиве последовательности Написал программу для нахождения позиции в массиве последовательности чисел #include<iostream> #include<algorithm> #include<stdlib.h> using namespace std; int main ()... подробнее

Показать сообщение отдельно
ValeryLaptev
Эксперт С++
1042 / 821 / 48
Регистрация: 30.04.2011
Сообщений: 1,659
18.09.2011, 00:03
Вот еще из моих материалов.
Надеюсь, что даже в таком виде это поможет разобраться.

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

Для дека нам потребуются конструкторы и деструктор. Минимально необходимое множество операций включает операции добавления элемента в начало и конец дека, операции удаления первого и последнего элемента. Еще необходимы функция проверки, есть ли в контейнере элементы, и функция, выдающая количество элементов в контейнере. Обычно в состав методов включают и методы получения значений первого и последнего элемента контейнера. Рассмотрим более подробно операцию доступа к элементам контейнера.
Так как внутренняя структура элемента скрыта, поскольку прописана в приватной части класса-дека, программа-клиент не сможет работать с элементами контейнера посредством указателей. Для перебора элементов контейнер должен обеспечить последовательный доступ к элементам другим способом. Это можно сделать двояким образом:
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                   // количество элементов после удаления
9
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru