Бублик Володимир Васильович Об'єктно- орієнтоване програмування Частина 2. Ієрархічне програмування. Лекція 12. Ітераторні контейнери Лекції для студентів 2 курсу Musei Vaticani

© Бублик В.В. ООП-2. Ієрархічне програмування. Лекція 12. Ітераторні контейнери 2 Ієрархії Вкладення (чорний ящик) Клієнтам композиту(агрегату) його вміст недоступний При необхідності відкривається делегуванням Відкрите успадкування (прозорий ящик) Похідний клас успадковує інтерфейс і реалізацію базового Клієнтам похідного класу доступна поведінка базового Закрите (захищене) успадкування Похідний клас успадковує реалізацію базового Клієнтам похідного класу не доступна поведінка базового

Контейнерна ієрархія: вкладення Композиція: компонент служить частиною контейнера; компонент автоматично створюється конструктром і видаляється деструктором композиту template class SequenceContainingArray { private: Array _myArray; ……………………. }; © Бублик В.В. ООП-2. Ієрархічне програмування. Лекція 12. Ітераторні контейнери 3

Контейнерна ієрархія Агрегація: компонент приєднано до контейнера; але контейнер відповідає за персистентність (тривалість життя) компонентів, програмуючи їх створення і видалення template class SequenceAggregatingArray { private: Array * _pToArray; ……………………. }; © Бублик В.В. ООП-2. Ієрархічне програмування. Лекція 12. Ітераторні контейнери 4

Контейнерна ієрархія Агрегація: компонент приєднано до контейнера; але контейнер відповідає за персистентність (тривалість життя) компонентів, програмуючи їх створення і видалення template SequenceAggregatingArray:: SequenceAggregatingArray: _pToArray (new Array[n]) ……………. template SequenceAggregatingArray:: ~SequenceAggregatingArray { delete [] _pToArray; } © Бублик В.В. ООП-2. Ієрархічне програмування. Лекція 12. Ітераторні контейнери 5

Доступ до компонентів: делегуванням Прямий доступ: індексування послідовності делегується індексуванню в масиві template Elem& SequenceAggregatingArray:: operator[](size_t index) { if (index>size) throw BadSequence(index); return (* _pToArray )[index]; } © Бублик В.В. ООП-2. Ієрархічне програмування. Лекція 12. Ітераторні контейнери 6

Доступ до компонентів: делегуванням Послідовний доступ: початок черги делегується індексуванню за заданим індексом (_top) template const Elem& SequenceAggregatingArray:: head() const { if empty() throw BadSequence(empty); return (* _pToArray )[_top]; } © Бублик В.В. ООП-2. Ієрархічне програмування. Лекція 12. Ітераторні контейнери 7

Точне делегування Прямий доступ для читання: підглядання делегується сталій операції індексування в масиві (модифікатор залишається недоступним) template bool PeekbackStackAggregatingArray:: peekback (size_t index, Elem& result) const { if (index>size) return false; result = (* _pToArray )[index]; return true; } © Бублик В.В. ООП-2. Ієрархічне програмування. Лекція 12. Ітераторні контейнери 8

Використання контейнерів Пошук у контейнері 1.template bool search( const SequenceAggregatingArray&, const Elem&); 2.template bool search( const SequenceContainingArray&, const Elem&); 3.template bool search( const List&, const Elem&); 4.template bool search( const Array&, const Elem&); ………………………………………………………………………………….. Скільки має бути функцій пошуку залежно від типу контейнера? © Бублик В.В. ООП-2. Ієрархічне програмування. Лекція 12. Ітераторні контейнери 9

Узагальнений пошук? - Ні Одна узагальнена функція? template > bool search( const Container &, const Elem&); © Бублик В.В. ООП-2. Ієрархічне програмування. Лекція 12. Ітераторні контейнери 10

Успадкування реалізації Базовий клас недоступний клієнтові похідного класу Доступ до функції базового класу відкривається зміною статусу її імені для всіх сигнатур одночасно class StackAggregatingArray: private Array { protected: Array::operator[]; public: ……………………………. }; © Бублик В.В. ООП-2. Ієрархічне програмування. Лекція 12. Ітераторні контейнери 11

Успадкування реалізації Успадкування реалізації стає небажаною конструкцією За винятком особливих ситуацій, які будуть розглянуті в курсі Методів об'єктно-орієнтованого програмування, для успадкування реалізації точніше використовувати вкладення, причому агрегація указником виявляється найбільш гнучкою © Бублик В.В. ООП-2. Ієрархічне програмування. Лекція 12. Ітераторні контейнери 12

Повне успадкування Похідний клас успадковує як інтерфейс, так і реалізацію (якщо вона наявна) базового класу Архітектура стає простішою, якщо базовий клас чисто абстрактний, тобто не має реалізації Одночасне успадкування інтерфейсу і реалізації вимагає точної узгодженості класів, а тому посилює їх спряженість (залежність один від одного) © Бублик В.В. ООП-2. Ієрархічне програмування. Лекція 12. Ітераторні контейнери 13

Узагальнений пошук? - Ні Одна узагальнена функція? template > bool search( const Container &, const Elem&); Тип контейнера довелося б зафіксувати на момент компіляції коду © Бублик В.В. ООП-2. Ієрархічне програмування. Лекція 12. Ітераторні контейнери 14

Індивідуальний ітератор Вбудований в тіло контейнера © Бублик В.В. ООП-2. Ієрархічне програмування. Лекція 12. Ітераторні контейнери 15

Відкрите успадкування Уточнення поведінки абстрактного базового класу в похідних класах peekback © Бублик В.В. ООП-2. Ієрархічне програмування. Лекція 12. Ітераторні контейнери 16

Ієрархія контейнерів Успадкування інтерфейсу стеків © Бублик В.В. ООП-2. Ієрархічне програмування. Лекція 12. Ітераторні контейнери 17

Ієрархія контейнерів Успадкування інтерфейсу і реалізації списків © Бублик В.В. ООП-2. Ієрархічне програмування. Лекція 12. Ітераторні контейнери 18

Ітератор Основний механізм обробки вмісту контейнерів template class Iterator { public: virtual Iterator(); virtual void start() const; virtual void next() const; virtual bool done() const; virtual const Elem& current() const; virtual ~Iterator(); }; © Бублик В.В. ООП-2. Ієрархічне програмування. Лекція 12. Ітераторні контейнери 19

Індивідуальний ітератор списків © Бублик В.В. ООП-2. Ієрархічне програмування. Лекція 12. Ітераторні контейнери 20

Індивідуальний ітератор списків class List { public: class ListIterator; List(const Elem& elem); virtual void cons(const Elem& elem); virtual const Elem& head() const; virtual void pop(); virtual ~List(); virtual ListIterator iterate() const;………………. }; © Бублик В.В. ООП-2. Ієрархічне програмування. Лекція 12. Ітераторні контейнери 21

Індивідуальний ітератор списків class List::ListIterator { private: mutable List::Node * _first; mutable List::Node * _current; public: const Elem& get() const; void begin (const List & list) const; void next() const; bool done() const; }; © Бублик В.В. ООП-2. Ієрархічне програмування. Лекція 12. Ітераторні контейнери 22

Mix-in ітератор (домішок) Виділення інтерфейсу ітератора © Бублик В.В. ООП-2. Ієрархічне програмування. Лекція 12. Ітераторні контейнери 23

Mix-in ітератор (домішок) Ітератор списків class IteratedList: virtual public List, public Iterator { public: IteratedList(Elem x); virtual void start() const; virtual void next() const; virtual bool done() const; virtual const Elem& current() const; virtual ~IteratedList(); }; © Бублик В.В. ООП-2. Ієрархічне програмування. Лекція 12. Ітераторні контейнери 24

Вбудований домішок © Бублик В.В. ООП-2. Ієрархічне програмування. Лекція 12. Ітераторні контейнери 25

Ітераторні алгоритми (reuse) ostream& operator<<(ostream & os, const Iterator& it) { it.start(); while (!it.done()) { cout<<it.current()<<':'; it.next(); } cout<<endl; return os; } © Бублик В.В. ООП-2. Ієрархічне програмування. Лекція 12. Ітераторні контейнери 26

Ітераторні алгоритми(reuse) bool search (Iterator& whre, const Elem& what) { whre.start(); while (!whre.done()) { if (what==whre.current()) return true; whre.next(); } return false; } © Бублик В.В. ООП-2. Ієрархічне програмування. Лекція 12. Ітераторні контейнери 27

Нові застосування ітераторів (reuse) Вхідний і об'єктний коди клієнтських функцій використовують лише інтерфейс ітератора і не залежать від типу ітерованого контейнера © Бублик В.В. ООП-2. Ієрархічне програмування. Лекція 12. Ітераторні контейнери 28

Вхідні і вихідні ітератори class Itor { public: virtual ~Itor(){}; virtual void begin() const = 0; virtual const Elem& get()const =0; virtual void put(const Elem &) = 0; virtual bool done() const = 0; virtual void next() const = 0; }; © Бублик В.В. ООП-2. Ієрархічне програмування. Лекція 12. Ітераторні контейнери 29

Модифікація вмісту контейнера // Збільшення на одиницю void plus1 (Itor& it) { for (it.begin(); !it.done(); it.next()) { it.put(it.get()+1); } return; } © Бублик В.В. ООП-2. Ієрархічне програмування. Лекція 12. Ітераторні контейнери 30

Віртуальний конструктор Q: Як бути при необхідності створення нового екземпляру ітерованого контейнера? A: new IteratedList? Q: Як створити копію контейнера саме того типу, з яким зараз працює абстрактний ітератор? A: Абстрактні класи не можна інстанціонувати Q: Застосувати віртуальний конструктор копіювання Itor(const Itor&)? A: Конструктор не може бути віртуальним (чому?) Wag the dog! © Бублик В.В. ООП-2. Ієрархічне програмування. Лекція 12. Ітераторні контейнери 31

Клонування Коваріантний результат функції Інтерфейс: virtual Itor* clone () const=0; Поліморфна реалізація IteratedList* clone() const { return new IteratedList(*this); } © Бублик В.В. ООП-2. Ієрархічне програмування. Лекція 12. Ітераторні контейнери 32

Клонувальний ітератор © Бублик В.В. ООП-2. Ієрархічне програмування. Лекція 12. Ітераторні контейнери 33

Застосування клонувань: сортування void sort (Itor& it) { for (it.begin(); !it.done(); it.next()){ Itor * pjt = it.clone(); Itor * pkt = it.clone(); for (pkt->next(); !pkt->done(); pkt->next()) if (pjt->get()>pkt->get()) { Elem tmp = pjt->get(); pjt->put(pkt->get()); pkt->put(tmp); } delete pjt; delete pkt; } © Бублик В.В. ООП-2. Ієрархічне програмування. Лекція 12. Ітераторні контейнери 34

Захищений абстрактний клас class Itor { public: virtual ~Itor(){}; virtual Itor* clone() const=0; virtual void begin() const = 0; virtual const Elem& get() const =0; virtual void put(const Elem &) = 0; virtual bool done() const = 0; virtual void next() const = 0; protected: Itor(){}; }; © Бублик В.В. ООП-2. Ієрархічне програмування. Лекція 12. Ітераторні контейнери 35

Висновок Ітератори дозволяють програмувати алгоритми, незалежні від контейнерів, до яких їх будуть застосовувати, що забезпеує можливість нових застосувань (reuse) цих алгоритмів Програмуйте, спираючись на інтерфейс (у нашому випадку на абстрактний клас Iterator), а не реалізацію (у нашому випадку класи IteratedArray, IteratedList, … ) © Бублик В.В. ООП-2. Ієрархічне програмування. Лекція 12. Ітераторні контейнери 36

Побічний результат: віртуальний конструктор // Абстрактний клас із псевдоконструктором class Abstract { public: virtual Abstract& clone() const=0; }; // Конкретний клас із реалізацією псевдоконструктора class Concrete: public Abstract { public: Concrete& clone() const { return *(new Concrete); } }; © Бублик В.В. ООП-2. Ієрархічне програмування. Лекція 12. Ітераторні контейнери 37

Успішного іспиту! © Бублик В.В. ООП-2. Ієрархічне програмування. Лекція 12. Ітераторні контейнери 38