В реальной жизни мы постоянно используем контейнеры. Гречка с куриной грудкой в контейнере для еды, страницы в книге с обложкой и переплетом, вещи в тумбочке/рюкзаке и т.д. Без этих контейнеров было бы крайне неудобно работать с объектами, находящимися внутри. Представьте, что вы пытаетесь читать книгу без переплета и обложки, или пытаетесь есть гречку с грудкой, не используя контейнер для еды/миску/тарелку и т.д. Непорядок! Ценность контейнеров заключается в том, что они помогают должным образом организовать и хранить объекты.
Контейнерные классы
Контейнерный класс (или «класс-контейнер») в языке 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; } // Cоздаем новый массив на один элемент меньше нашего старого массива 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; } // Cоздаем новый массив на один элемент меньше нашего старого массива 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++, то вы уже знаете, как создавать свои собственные контейнерные классы.
Можно значительно упростить код если использовать беззнаковый индекс, ведь "под капотом" индекс беззнаковый.
Господа, а ни у кого не появляется вернинга на этой строчке ?
warning c6386 buffer overrun while writing to
Добрый день
Интересный курс.
Спасибо.
Есть вопрос по теме.
А почему мы не удаляем указатель *data на массив в функции remove и в других?
Это разве не приведёт к утечке памяти?
Надо ли использовать delete[] data?
Уже поздно но отвечу: m_data и data это указатели на один и тот же элемент в памяти, следовательно при уничтожении m_data уничтожается и data, и наоборот. Следовательно утечки не возникает
Добрый день!
Спасибо за ваши туториалы очень помогли при изучении С++. Скажите у вас будут туториалы по TCP/IP сокетам?
Привет. В ближайшем времени не планируется. В будущем — возможно.
По сокетам есть годная, небольшая книжка (20 стр), кратко и по делу — kpnc.opennet.ru/sock.pdf.
"Польза кувшина в его пустоте". Лао Цзы.
Эт точно 🙂