Бублик Володимир Васильович Об'єктно-орієнтоване програмування Частина 1. Об'єктне програмування. Лекція 7. Контейнерні класи Лекції для студентів 2 курсу Milan, University

Бублик Володимир Васильович Об'єктно-орієнтоване програмування Частина 1. Об'єктне програмування. Лекція 7. Контейнерні класи Лекції для студентів 2 курсу Milan, University

© Бублик В.В. ООП-1. Об'єктне програмування. Лекція 7. Контейнерні класи 3 Повторення: агрегати Агрегати містять в собі інші об'єкти у вигляді атрибутів або відсилок чи указників на них Звичайно атрибути закриті для доступу зовні Доступ до атрибутів та заміна їх значень виконуються відповідно за допомогою селектора та модифікатора Атрибути можуть бути зв'язані одне з одним, а тому модифікатор кожного з атрибутів повинен зберігати повноцінність інших

© Бублик В.В. ООП-1. Об'єктне програмування. Лекція 7. Контейнерні класи 4 Контейнер Агрегат, здатний містити, як правило, значну кількість схожих (однотипних) об'єктів Спосіб агрегування композиція Види контейнерів: масив, послідовність, список, черга, стек, дек Спосіб доступу: довільний або послідовний

© Бублик В.В. ООП-1. Об'єктне програмування. Лекція 7. Контейнерні класи 5 Масив В стилі С T ar [m] = {a 0, a 1, …, a m-1 }; T * p = new T [n]; Проблеми: Неспроможність відрізнити указник одиночного даного від масиву Нездатність контролювати вихід індексу за межі масиву Перевага Довільний доступ до елементу масиву за індексом

© Бублик В.В. ООП-1. Об'єктне програмування. Лекція 7. Контейнерні класи 6 Приклад1 double a[10] = {0,1,2,3,4,5,6,7,8,9}; cout<<sizeof(a)/sizeof(double)<<endl;//10 g(a); //Масив забув свій розмір void g(double a[]) { cout<<"Can't calculate size"<<endl; cout<< sizeof(a)/sizeof(double)<< endl;//0 }

© Бублик В.В. ООП-1. Об'єктне програмування. Лекція 7. Контейнерні класи 7 Приклад2 double a[10] = {0,1,2,3,4,5,6,7,8,9}; cout<<sizeof(a)/sizeof(double)<<endl;//10 g(a); //Указник не знає, що він масив void g(double * a) { cout<<"Can't calculate size"<<endl; cout<< sizeof(a)/sizeof(double)<< endl;//0 }

© Бублик В.В. ООП-1. Об'єктне програмування. Лекція 7. Контейнерні класи 8 Приклад3 void h(double * a, int n) { for (int i=0; i<n; ++i) a[i]=i; } //Функція приймає адресу за масив double a= 1; h(&a, 1000);

© Бублик В.В. ООП-1. Об'єктне програмування. Лекція 7. Контейнерні класи 9 Створення/видалення Як гарантувати парність new/delete new[]/delete[]? double * u = new double (12345); double * v = new double [12345]; delete [] u; delete v;

© Бублик В.В. ООП-1. Об'єктне програмування. Лекція 7. Контейнерні класи 10 Reuse Не забувайте про майбутні нові застосування (reuse) програмного коду, а тому завжди віддаємо перевагу загальним рішенням проти конкретних const size_t size = 10; typedef double Elem; Elem * arrayOfElem = new Elem [size]; vs. double * arrayOf10Doubles = new double [10];

© Бублик В.В. ООП-1. Об'єктне програмування. Лекція 7. Контейнерні класи 11 Клас масивів typedef double Elem; class Array { public: explicit Array (size_t); ~Array(); //Селектор-модифікатор Elem& operator[] (size_t index); //Селектор const Elem & operator[] (size_t index) const; //Розмірність size_t size() const;

© Бублик В.В. ООП-1. Об'єктне програмування. Лекція 7. Контейнерні класи 12 Масив чисел //Клас для обробки помилкових ситуацій class BadArray; private: //Атрибут розмірності const size_t _size; //Власне масив Elem * _pElem; //Не визначені для контейнерів, тому не реалізовані: Array (const Array&); Array& operator= (const Array&); };

© Бублик В.В. ООП-1. Об'єктне програмування. Лекція 7. Контейнерні класи 13 Конструктор масиву Array::Array (size_t sz): _size(sz), _pElem (new Elem[_size]) { #ifndef NDEBUG cout<<"Array created ["<<_size<<]'<<endl; #endif return; }

© Бублик В.В. ООП-1. Об'єктне програмування. Лекція 7. Контейнерні класи 14 Деструктор Розробник класу гарантує симетричність видалення створенню Array::~Array() { #ifndef NDEBUG cout<<"Array of size ("<<_size<<") deleted"<<endl; #endif delete [] _pElem; }

© Бублик В.В. ООП-1. Об'єктне програмування. Лекція 7. Контейнерні класи 15 Ініціалізація Чим наповнено масив дійсних чисел після його створення? Сміттям Array ar(10); for (int i=0; i<10; ++i) cout<<ar[i]<<,; cout<<endl;

© Бублик В.В. ООП-1. Об'єктне програмування. Лекція 7. Контейнерні класи 16 Масив об'єктів Використання класів замість стандартних типів даних приводить до наповнення масиву об'єктами, створеними конструкторами за замовчуванням typedef Point Elem; Array arrayOfPoints(10);

© Бублик В.В. ООП-1. Об'єктне програмування. Лекція 7. Контейнерні класи 17 Конструктор масиву точок //На що перетвориться конструктор масиву точок? Array::Array (size_t sz): _size(sz), //Виклик _size конструкторів _pElem (new Elem [_size]) // Point(0,0) { #ifndef NDEBUG cout<<"Array created ["<<_size<<]'<<endl; #endif return; }

© Бублик В.В. ООП-1. Об'єктне програмування. Лекція 7. Контейнерні класи 18 Конструктор елемента масиву NB. Клас елемента масиву повинен мати конструктор без параметрів //Ініціалізація //без проблем class Foo { public: Foo(); }; typedef Foo Elem; //Ініціалізація //неможлива class Foox { public: Foox (int x); }; typedef Foox Elem;

© Бублик В.В. ООП-1. Об'єктне програмування. Лекція 7. Контейнерні класи 19 Конструктор масиву NB. Клас елемента масиву повинен мати конструктор без параметрів //Ініціалізація //без проблем class Foo { public: Foo(); }; //Тепер //без проблем class Foox { public: Foox (int x=0); };

© Бублик В.В. ООП-1. Об'єктне програмування. Лекція 7. Контейнерні класи 20 Індексування: селектор/модифікатор Небезпечна, взагалі кажучи, операція, оскільки фактично відкриває повний доступ до закритої частини класу Для контейнерів прийнятна, оскільки контейнери не мають обмежень на призначені для зберігання дані Elem& Array::operator[] (size_t index) { if (index =_size) throw BadArray("Bad index: ", index); return _pElem [index]; }

© Бублик В.В. ООП-1. Об'єктне програмування. Лекція 7. Контейнерні класи 21 Чистий селектор Призначений для доступу передусім до контейнера, переданого параметром за допомогою сталої відсилки const Elem Array::operator[] (size_t index) const { if (index =_size) throw BadArray("Bad index: ", index); return _pElem [index]; }

© Бублик В.В. ООП-1. Об'єктне програмування. Лекція 7. Контейнерні класи 22 Обробник помилок class Array::BadArray { private: string _reason; size_t _index; public: BadArray(string reason="", size_t index=0); ~BadArray(); }; ostream& operator<< (ostream &os, const Array::BadArray& seq);

© Бублик В.В. ООП-1. Об'єктне програмування. Лекція 7. Контейнерні класи 23 Проблема наповненості Масив як контейнер не здатний зберігати менше даних, ніж його ємність: індексування контролює лише вихід індексу за межі масиву, але не перевіряє, чи був елемент попередньо визначений

© Бублик В.В. ООП-1. Об'єктне програмування. Лекція 7. Контейнерні класи 24 Обмежена послідовність Розмістимо n членів послідовності s на перших n місцях масиву a розмірності n

© Бублик В.В. ООП-1. Об'єктне програмування. Лекція 7. Контейнерні класи 25 Діаграма класів Масив агрегований як компонент послідовності

© Бублик В.В. ООП-1. Об'єктне програмування. Лекція 7. Контейнерні класи 26 Послідовність. Версія 1 #include class Sequence { public: explicit Sequence(size_t capacity =_seqBlock); ~Sequence(); Sequence& putAfter (Elem elem, size_t ind=std::numeric_limits ::max()); Sequence& remove (size_t ind=std::numeric_limits ::max());

© Бублик В.В. ООП-1. Об'єктне програмування. Лекція 7. Контейнерні класи 27 Послідовність. Версія 1 const Elem& operator[] (size_t index) const; Elem & operator[] (size_t index); //Поточна ємність size_t capacity() const; //Поточний розмір size_t size() const; //Чи порожня послідовність? bool empty() const; //Очистити послідовність void clear();

© Бублик В.В. ООП-1. Об'єктне програмування. Лекція 7. Контейнерні класи 28 Послідовність. Версія 1 class BadSeq; private: size_t _size; Array _seqArray; //Стандартний розмір блока контейнера static size_t _seqBlock; Sequence (const Sequence&); Sequence& operator=(const Sequence&); };

© Бублик В.В. ООП-1. Об'єктне програмування. Лекція 7. Контейнерні класи 29 Конструктор/деструктор //Створити порожню послідовність Sequence::Sequence(size_t capacity): _size(0),_seqArray(capacity) { return; }; //Деструктору поки що роботи немає. Чому? Sequence::~Sequence() { return; };

© Бублик В.В. ООП-1. Об'єктне програмування. Лекція 7. Контейнерні класи 30 Делегування індексувань Elem & Sequence::operator[] (size_t index) const { if (empty()) throw BadSeq(Empty sequence"); if (index>_size) throw BadSeq (Non existing element"); //Делегування доступу за індексом return _seqArray[index]; }

© Бублик В.В. ООП-1. Об'єктне програмування. Лекція 7. Контейнерні класи 31 Долучення до послідовності Sequence& Sequence::insert(Elem elem, size_t index) { //Замовчуване значення індексу: дописати в кінець if (_size < index) index=_size; //Контейнер переповнено if( _size + 1 > capacity()) throw BadSeq(No more space"); _size++;

© Бублик В.В. ООП-1. Об'єктне програмування. Лекція 7. Контейнерні класи 32 Долучення до послідовності //Зсуваємо залишок послідовності праворуч for (size_t i =_size-1; i > index; i--) _seqArray[i]= _seqArray[i-1]; //Заносимо новий елемент _seqArray [index] = elem; return *this; }

© Бублик В.В. ООП-1. Об'єктне програмування. Лекція 7. Контейнерні класи 33 Необмежена послідовність Можливість замінити менший контейнер більшим за домогою закритого методу enlarge() досягається за рахунок агрегування масиву указником

© Бублик В.В. ООП-1. Об'єктне програмування. Лекція 7. Контейнерні класи 34 Збільшення контейнера void Sequence :: enlarge (int times) { Array *newAr=new Array(times*_seqBlock+capacity()); if (newAr == 0) throw (No more space"); assert(newArray != 0); for (size_t i=0; i<_size; i++) (*newAr)[i] = (*_seqArray)[i]; delete _seqArray; _seqArray = newArray; return; }

© Бублик В.В. ООП-1. Об'єктне програмування. Лекція 7. Контейнерні класи 35 Вправа Спроектувати послідовність на базі масиву, в якій можна буде зберігати об'єкти без попереднього виклику конструкторів без параметрів для заповнення всього масиву

© Бублик В.В. ООП-1. Об'єктне програмування. Лекція 7. Контейнерні класи 36 Повторення Два способи організації циклу над масивом const int n=4; int a[n]; //цикл за індексом for (int i=0; i<n; ++i) a[i]=i; //цикл за ітератором int *pcurrent = a; int *const pend = a + n; while (pcurrent!=pend) cout<<*(pcurrent++)<<endl;

© Бублик В.В. ООП-1. Об'єктне програмування. Лекція 7. Контейнерні класи 37 Ітератори Доповнимо послідовність трьома указниками private: size_t _size; Array * _seqArray; //Указник поточного елементу mutable Elem * _current; //Указник початку послідовності Elem * _start; //Указник кінця послідовності Elem * _end;

© Бублик В.В. ООП-1. Об'єктне програмування. Лекція 7. Контейнерні класи 38 Ітератори І чотирма методами //Почати ітерацію void start() const { _current = _start;} //Зробити наступний крок void next() const { _current++;} //Перевірити на закінчення bool stop() const { return (_current == _end);} //Взяти поточний елемент const Elem& getElem() const { return *_current;}

© Бублик В.В. ООП-1. Об'єктне програмування. Лекція 7. Контейнерні класи 39 Застосування ітераторів ostream& operator<<(ostream &os, const Sequence& seq) { seq.start(); while(!seq.stop()) { cout<<chr<<seq.getElem()<< ; seq.next(); } cout<<endl; return os; }

© Бублик В.В. ООП-1. Об'єктне програмування. Лекція 7. Контейнерні класи 40 Вправа 1.Побудувати контейнер послідовного доступу List у вигляді списку 2.Визначити ітератори так, щоб програми користувачів не залежали від типу контейнера ostream& operator<<(ostream &os, const List& seq) { seq.start(); while(!seq.stop()) { cout<<chr<<seq.getElem()<< ; seq.next(); } cout<<endl; return os; }

© Бублик В.В. ООП-1. Об'єктне програмування. Лекція 7. Контейнерні класи 41 Обмежений стек на базі масиву class Stack { public: explicit Stack(size_t size = _stackBlock); ~Stack(); bool empty() const; bool full() const; size_t capacity() const; const Elem top() const; void pop(); void push(const Elem value);

© Бублик В.В. ООП-1. Об'єктне програмування. Лекція 7. Контейнерні класи 42 Обмежений стек на базі масиву class BadStack; private: static const size_t _stackBlock; //дно стеку static const size_t _bos; //верхівка стеку size_t _top; Array stackArray; Stack(const &Stack); Stack& operator=(const Stack&); };

© Бублик В.В. ООП-1. Об'єктне програмування. Лекція 7. Контейнерні класи 43 Обмежена черга на базі масиву class Queue { public: explicit Queue (size_t size = _queueBlock); ~Stack(); bool empty() const; bool full() const; size_t capacity() const; const Elem front() const; void pop(); void put(const Elem value);

© Бублик В.В. ООП-1. Об'єктне програмування. Лекція 7. Контейнерні класи 44 Обмежена черга на базі масиву class BadQueue; private: static const size_t _bos; static const size_t _QueueBlock; size_t _size; size_t _front; size_t _back; Array _QueueArray; size_t plus1(size_t); };

© Бублик В.В. ООП-1. Об'єктне програмування. Лекція 7. Контейнерні класи 45 Вправа Визначте клас двосторонньої черги на базі масиву

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