У реальному житті ми постійно використовуємо контейнери. Гречка з курячою грудкою в контейнері для їжі, сторінки в книзі з обкладинкою і палітуркою, речі в тумбочці/рюкзаку і т.д. Без цих контейнерів було б вкрай незручно працювати з об’єктами, що знаходяться всередині. Уявіть, що ви намагаєтеся читати книгу без палітурки і обкладинки, або намагаєтеся їсти гречку з грудкою, не використовуючи контейнер для їжі/тарілку/миску тощо. Непорядок! Цінність контейнерів полягає в тому, що вони допомагають належним чином організувати і зберігати об’єкти.
Контейнерні класи
Контейнерний клас (або “клас-контейнер”) в мові C++ — це клас, призначений для зберігання і організації декількох об’єктів певного типу даних (користувацьких чи фундаментальних). Існує багато різних контейнерних класів, кожен з яких має свої переваги, недоліки або обмеження у використанні. Безумовно, найбільш використовуваним контейнером в програмуванні є масив, який ми вже використовували у багатьох прикладах. Хоча в мові C++ є звичайні стандартні масиви, більшість програмістів використовують контейнерні класи-масиви: std::array або std::vector через переваги, які вони надають. На відміну від стандартних масивів, контейнерні класи-масиви мають можливість динамічної зміни свого розміру, коли елементи додаються або видаляються. Це не тільки робить їх більш зручними, ніж звичайні масиви, а й безпечнішими для використання.
Зазвичай, функціонал класів-контейнерів мови C++ наступний:
Створення пустого контейнера (через конструктор).
Додання нового об’єкта в контейнер.
Видалення об’єкта з контейнеру.
Перегляд кількості об’єктів, які знаходяться на даний момент в контейнері.
Очистка контейнера від всіх об’єктів.
Доступ до збережених об’єктів.
Сортування об’єктів/елементів (не завжди).
Іноді функціонал контейнерних класів може бути не настільки великим, як це зазначено вище. Наприклад, контейнерні класи-масиви часто не мають функціоналу додання/видалення об’єктів, тому що вони і так повільні, і розробник просто не хоче збільшувати навантаження.
Типом відносин в класах-контейнерах є «член чогось». Наприклад, елементи масиву «є членами» масиву (належать йому). Зверніть увагу, ми тут використовуємо термін «член чогось» не в сенсі члена класу C++.
Типи контейнерних класів
Контейнерні класи зазвичай бувають двох типів:
Контейнери значення — це композиції, які зберігають копії об’єктів (і відповідальні за створення/знищення цих копій).
Контейнери посилання — це агрегації, які зберігають вказівники або посилання на інші об’єкти (і не відповідальні за створення/знищення цих об’єктів).
На відміну від реального життя, коли контейнери можуть зберігати будь-які типи об’єктів, які в них поміщають, в мові C++ контейнери зазвичай містять тільки один тип даних. Наприклад, якщо у вас цілочисельний масив, то він може містити тільки цілочисельні значення. На відміну від деяких інших мов програмування, C++ не дозволяє змішувати різні типи даних всередині одного контейнера. Якщо вам потрібні контейнери для зберігання значень типів int і double, то вам доведеться написати два окремих контейнери (або використовувати шаблони, про які ми поговоримо на відповідному уроці). Незважаючи на обмеження їх використання, контейнери надзвичайно корисні, так як роблять програмування простішим, безпечнішим і швидшим.
Контейнерний клас-масив
Зараз ми напишемо цілочисельний клас-масив з нуля, реалізуючи функціонал контейнерів в мові С++. Цей клас-масив буде типу контейнера значення, в якому зберігатимуться копії елементів, а не самі елементи.
Спочатку створимо файл ArrayInt.h:
|
1 2 3 4 5 6 7 8 |
#ifndef ARRAYINT_H #define ARRAYINT_H class ArrayInt { }; #endif |
Наш ArrayInt повинен відслідковувати два значення: дані і свою довжину. Оскільки ми хочемо, щоб наш масив міг змінювати свою довжину, то нам потрібно використовувати динамічне виділення пам’яті, що означає, що ми будемо використовувати вказівник для зберігання даних:
|
1 2 3 4 5 6 7 8 9 10 11 |
#ifndef ARRAYINT_H #define ARRAYINT_H class ArrayInt { private: int m_length; int *m_data; }; #endif |
Тепер нам потрібно додати конструктори, щоб мати можливість створювати об’єкти класу ArrayInt. Ми додамо два конструктори: перший створюватиме порожній масив, другий — масив заданого розміру:
|
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 |
#ifndef ARRAYINT_H #define ARRAYINT_H #include <cassert> // для assert() class ArrayInt { private: int m_length; int *m_data; public: ArrayInt(): m_length(0), m_data(nullptr) { } ArrayInt(int length): m_length(length) { assert(length >= 0); if (length > 0) m_data = new int[length]; else m_data = nullptr; } }; #endif |
Нам також потрібні функції, які виконуватимуть очистку ArrayInt. По-перше, додамо деструктор, який просто звільнятиме будь-яку динамічно виділену пам’ять. По-друге, напишемо функцію erase(), яка виконуватиме очистку масиву і скидатиме його довжину на 0:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
~ArrayInt() { delete[] m_data; // Тут нам не потрібно присвоювати значення null для m_data чи виконувати m_length = 0, тому що об'єкт і так буде знищений } void erase() { delete[] m_data; // Тут нам потрібно вказати m_data значення nullptr, щоб на виході не було "висячого" вказівника m_data = nullptr; m_length = 0; } |
Тепер перевантажимо оператор індексації [], щоб мати доступ до елементів масиву. Ми також повинні виконати перевірку коректності переданого індексу, що найкраще зробити за допомогою стейтмента assert. Також додамо функцію доступу для повернення довжини масиву:
|
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 |
#ifndef ARRAYINT_H #define ARRAYINT_H #include <cassert> // для assert() class ArrayInt { private: int m_length; int *m_data; public: ArrayInt(): m_length(0), m_data(nullptr) { } ArrayInt(int length): m_length(length) { assert(length >= 0); if (length > 0) m_data = new int[length]; else m_data = nullptr; } ~ArrayInt() { delete[] m_data; } void erase() { delete[] m_data; // Вказуємо m_data значення nullptr, щоб на виході не було "висячого" вказівника m_data = nullptr; m_length = 0; } int& operator[](int index) { assert(index >= 0 && index < m_length); return m_data[index]; } int getLength() { return m_length; } }; #endif |
Тепер у нас вже є клас ArrayInt, який ми можемо використовувати. Ми можемо виділити масив певного розміру і використовувати оператор [] для вилучення або зміни значень елементів.
Тим не менш, є ще кілька речей, які ми не можемо виконати з нашим ArrayInt. Це автоматична зміна розміру масиву, додання/видалення елементів і сортування елементів.
По-перше, давайте реалізуємо можливість масиву змінювати свій розмір. Ми напишемо дві різні функції для цього. Перша функція — reallocate(), при зміні розміру масиву знищуватиме всі існуючі елементи (це швидко). Друга функція — resize(), при зміні розміру масиву зберігатиме всі існуючі елементи (це повільно).
|
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 |
// Функція reallocate() змінює розмір масиву. Всі існуючі елементи всередині масиву будуть знищені. Процес швидкий void reallocate(int newLength) { // Видаляємо всі існуючі елементи всередині масиву erase(); // Якщо наш масив повинен бути пустим, то виконуємо повернення тут if (newLength <= 0) return; // Далі нам потрібно виділити нові елементи m_data = new int[newLength]; m_length = newLength; } // Функція resize() змінює розмір масиву. Всі існуючі елементи зберігаються. Процес повільний void resize(int newLength) { // Якщо масив вже потрібної довжини, то виконуємо return if (newLength == m_length) return; // Якщо потрібно зробити масив пустим, то робимо це і потім виконуємо return if (newLength <= 0) { erase(); return; } // Тепер припустимо, що newLength складається, принаймні, з одного елементу. Виконується наступний алгоритм дій: // 1. Виділяємо новий масив. // 2. Копіюємо елементи з існуючого масиву в наш щойно виділений масив. // 3. Знищуємо старий масив і даємо команду m_data вказувати на новий масив. // Виділяємо новий масив. int *data = new int[newLength]; // Потім нам потрібно розібратися з кількістю скопійованих елементів в новий масив. // Нам потрібно скопіювати стільки елементів, скільки їх є в меншому з масивів if (m_length > 0) { int elementsToCopy = (newLength > m_length) ? m_length : newLength; // Почергово копіюємо елементи for (int index=0; index < elementsToCopy ; ++index) data[index] = m_data[index]; } // Видаляємо старий масив, тому що він нам вже не потрібний delete[] m_data; // І використовуємо замість старого масиву новий! Зверніть увагу, m_data вказує на ту ж адресу, на яку вказує наш новий динамічно виділений масив. // Оскільки дані були динамічно виділені, то вони не будуть знищені, коли вийдуть з області видимості m_data = data; m_length = newLength; } |
Фух! Було непросто!
Функціонал більшості контейнерних класів-масивів на цьому закінчується. Однак, якщо ви хочете побачити, як реалізувати можливість додання/видалення елементів, то ми зараз це розглянемо. Наступні два алгоритми дуже схожі на функцію resize():
|
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 |
void insertBefore(int value, int index) { // Перевірка коректності переданого індексу assert(index >= 0 && index <= m_length); // Створюємо новий масив на один елемент більше старого масиву int *data = new int[m_length+1]; // Копіюємо всі елементи аж до index-а for (int before=0; before < index; ++before) data[before] = m_data[before]; // Додаємо наш новий елемент в наш новий масив data [index] = value; // Копіюємо всі значення після доданого елементу for (int after=index; after < m_length; ++after) data[after+1] = m_data[after]; // Видаляємо старий масив і використовуємо замість нього новий масив delete[] m_data; m_data = data; ++m_length; } void remove(int index) { // Перевірка на коректність переданого індексу assert(index >= 0 && index < m_length); // Якщо це останній елемент масиву, то робимо масив пустим і виконуємо return if (m_length == 1) { erase(); return; } // Створюємо новий масив на один елемент менше нашого старого масиву int *data = new int[m_length-1]; // Копіюємо всі елементи аж до index-а for (int before=0; before < index; ++before) data[before] = m_data[before]; // Копіюємо всі значення після видаленого елементу for (int after=index+1; after < m_length; ++after ) data[after-1] = m_data[after]; // Видаляємо старий масив і використовуємо замість нього новий масив delete[] m_data; m_data = data; --m_length; } // Декілька додаткових функцій просто для зручності void insertAtBeginning(int value) { insertBefore(value, 0); } void insertAtEnd(int value) { insertBefore(value, m_length); } |
Ось наш контейнерний клас-масив ArrayInt повністю.
ArrayInt.h:
|
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 |
#ifndef ARRAYINT_H #define ARRAYINT_H #include <cassert> // для assert() class ArrayInt { private: int m_length; int *m_data; public: ArrayInt(): m_length(0), m_data(nullptr) { } ArrayInt(int length): m_length(length) { assert(length >= 0); if (length > 0) m_data = new int[length]; else m_data = nullptr; } ~ArrayInt() { delete[] m_data; } void erase() { delete[] m_data; // Тут потрібно вказати m_data значення nullptr, щоб на виході не було "висячого" вказівника m_data = nullptr; m_length = 0; } int& operator[](int index) { assert(index >= 0 && index < m_length); return m_data[index]; } // Функція reallocate() змінює розмір масиву. Всі існуючі елементи всередині масиву будуть знищені. Процес швидкий void reallocate(int newLength) { // Видаляємо всі існуючі елементи всередині масиву erase(); // Якщо наш масив повинен бути пустим, то виконуємо повернення тут if (newLength <= 0) return; // Потім виділяємо нові елементи m_data = new int[newLength]; m_length = newLength; } // Функція resize() змінює розмір масиву. Всі існуючі елементи зберігаються. Процес повільний void resize(int newLength) { // Якщо масив потрібної довжини, то виконуємо return if (newLength == m_length) return; // Якщо потрібно зробити масив пустим, то робимо це і потім виконуємо return if (newLength <= 0) { erase(); return; } // Тепер припустимо, що newLength складається, принаймні, з одного елементу. Виконується наступний алгоритм дій: // 1. Виділяємо новий масив. // 2. Копіюємо елементи з існуючого масиву в наш щойно виділений масив. // 3. Знищуємо старий масив і даємо команду m_data вказувати на новий масив. // Виділяємо новий масив int *data = new int[newLength]; // Потім нам потрібно розібратися з кількістю скопійованих елементів в новий масив. // Нам потрібно скопіювати стільки елементів, скільки їх є в меншому з масивів if (m_length > 0) { int elementsToCopy = (newLength > m_length) ? m_length : newLength; // Почергово копіюємо елементи for (int index=0; index < elementsToCopy ; ++index) data[index] = m_data[index]; } // Видаляємо старий масив, тому що він нам вже не потрібний delete[] m_data; // І використовуємо замість старого масиву новий! Зверніть увагу, m_data вказує на ту ж адресу, на яку вказує наш новий динамічно виділений масив. // Оскільки дані були динамічно виділені, то вони не будуть знищені, коли вийдуть з області видимості m_data = data; m_length = newLength; } void insertBefore(int value, int index) { // Перевірка коректності переданого індексу assert(index >= 0 && index <= m_length); // Створюємо новий масив на один елемент більше старого масиву int *data = new int[m_length+1]; // Копіюємо всі елементи аж до index-а for (int before=0; before < index; ++before) data [before] = m_data[before]; // Додаємо наш новий елемент в наш новий масив data [index] = value; // Копіюємо всі значення після доданого елементу for (int after=index; after < m_length; ++after) data[after+1] = m_data[after]; // Видаляємо старий масив і використовуємо замість нього новий масив delete[] m_data; m_data = data; ++m_length; } void remove(int index) { // Перевірка на коректність переданого індексу assert(index >= 0 && index < m_length); // Якщо це останній елемент масиву, то робимо масив пустим і виконуємо return if (m_length == 1) { erase(); return; } // Створюємо новий масив на один елемент менше нашого старого масиву int *data = new int[m_length-1]; // Копіюємо всі елементи аж до index-а for (int before=0; before < index; ++before) data[before] = m_data[before]; // Копіюємо всі значення після видаленого елементу for (int after=index+1; after < m_length; ++after ) data[after-1] = m_data[after]; // Видаляємо старий масив і використовуємо замість нього новий масив delete[] m_data; m_data = data; --m_length; } // Декілька додаткових функцій просто для зручності void insertAtBeginning(int value) { insertBefore(value, 0); } void insertAtEnd(int value) { insertBefore(value, m_length); } int getLength() { return m_length; } }; #endif |
Тепер протестуємо програму:
|
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> #include "ArrayInt.h" int main() { // Оголошуємо масив з 10-ма елементами ArrayInt array(10); // Заповнюємо масив числами від 1 до 10 for (int i=0; i<10; i++) array[i] = i+1; // Змінюємо розмір масиву до 7 елементів array.resize(7); // Додаємо число 15 перед елементом з індексом 4 array.insertBefore(15, 4); // Видаляємо елемент з індексом 5 array.remove(5); // Додаємо числа 35 і 50 в кінець і в початок array.insertAtEnd(35); array.insertAtBeginning(50); // Виводимо всі елементи масиву на екран for (int j=0; j<array.getLength(); j++) std::cout << array[j] << " "; return 0; } |
Результат:
50 1 2 3 4 15 6 7 35
Хоча написання контейнерних класів може бути дещо складним, але хороша новина полягає в тому, що вам їх потрібно написати тільки один раз. Як тільки контейнерний клас працює, ви можете його повторно використовувати де-завгодно без будь-яких додаткових дій/зусиль з боку програмування.
Також варто відзначити, що, хоча наш контейнерний клас ArrayInt містить фундаментальний тип даних (int), ми також могли б легко використовувати і користувацький тип даних.
Примітка: Якщо клас зі Стандартної бібліотеки C++ повністю відповідає вашим потребам, то використовуйте його замість написання свого контейнерного класу. Наприклад, замість ArrayInt краще використовувати std::vector<int>, так як реалізація std::vector<int> протестована/перевірена вже багатьма роками, ефективна і відмінно працює з іншими класами зі Стандартної бібліотеки C++. Але так як не завжди може бути можливим використовувати класи зі Стандартної бібліотеки C++, то ви вже знаєте, як створювати свої власні контейнерні класи.
Оцінити статтю:
(1 оцінок, середня: 5,00 з 5)
Loading...