16.6 – Контейнерные классы
В реальной жизни мы постоянно используем контейнеры. Сухие завтраки поставляются в коробках, страницы в вашей книге находятся внутри обложки и переплета, и вы можете хранить любое количество предметов в контейнерах в своем гараже. Без контейнеров было бы крайне неудобно работать со многими из этих объектов. Представьте, что вы пытаетесь прочитать книгу без какого-либо переплета или съесть хлопья, которые не были в коробке, и без тарелки. Это был бы бардак. Ценность контейнера в основном заключается в его способности помогать организовывать и хранить предметы, помещенные в него.
Точно так же контейнерный класс – это класс, предназначенный для хранения и организации нескольких экземпляров другого типа (либо другого класса, либо базового типа). Существует множество различных типов контейнерных классов, каждый из которых имеет различные преимущества, недостатки и ограничения в использовании. Безусловно, наиболее часто используемым контейнером в программировании является массив, примеры которого вы уже видели. Хотя C++ имеет встроенную поддержку массивов, программисты часто используют вместо него контейнерные классы массивов (std::array или std::vector) из-за дополнительных преимуществ, которые они предоставляют. В отличие от встроенных массивов, классы-контейнеры массивов обычно обеспечивают динамическое изменение размера (при добавлении или удалении элементов), запоминают свой размер при передаче в функции и выполняют проверку границ. Это не только делает классы-контейнеры массивов более удобными, чем обычные массивы, но и более безопасными.
Классы-контейнеры обычно реализуют довольно стандартный минимальный набор функций. Большинство хорошо определенных контейнеров будут включать функции, которые:
- создают пустой контейнер (через конструктор);
- вставляют новый объект в контейнер;
- удаляют объект из контейнера;
- сообщают количество объектов, находящихся в настоящее время в контейнере;
- очищают контейнер от всех объектов;
- предоставляют доступ к хранимым объектам;
- сортируют элементы (необязательно).
Иногда некоторые классы-контейнеры опускают некоторые из этих функций. Например, классы-контейнеры массивов часто опускают функции вставки и удаления, потому что они медленные, и разработчик класса не хочет поощрять их использование.
Классы-контейнеры реализуют связь «член чего-либо». Например, элементы массива являются членами (принадлежат) массива. Обратите внимание, что мы используем термин «член» в общепринятом смысле, а не в смысле члена класса C++.
Типы контейнеров
Классы контейнеров обычно бывают двух разных видов. Контейнеры значений – это композиции, в которых хранятся копии хранимых объектов (и, таким образом, контейнеры несут ответственность за создание и уничтожение этих копий). Контейнеры ссылок – это агрегации, которые хранят указатели или ссылки на другие объекты (и, следовательно, не несут ответственности за создание или уничтожение этих объектов).
В отличие от реальной жизни, где контейнеры могут содержать любые типы объектов, которые вы в них помещаете, в C++ контейнеры обычно содержат только один тип данных. Например, если у вас есть массив чисел int, он будет содержать только числа int. В отличие от некоторых других языков, многие контейнеры C++ не позволяют произвольно смешивать типы. Если вам нужны контейнеры для хранения чисел int и double, вам, как правило, придется написать для этого два отдельных контейнера (или использовать шаблоны, что является расширенной функцией C++). Несмотря на ограничения использования, контейнеры чрезвычайно полезны и делают программирование проще, безопаснее и быстрее.
Контейнерный класс массива
В этом примере мы собираемся написать класс массива значений int с нуля, который реализует большую часть общих функций, которые должны иметь контейнеры. Этот класс массива будет контейнером значений, в котором будут храниться копии элементов. Как следует из названия, контейнер будет содержать массив чисел int, аналогичный std::vector<int>.
Сначала создадим файл IntArray.h:
#ifndef INTARRAY_H
#define INTARRAY_H
class IntArray
{
};
#endifНашему классу IntArray нужно будет отслеживать два значения: сами данные и размер массива. Поскольку мы хотим, чтобы наш массив мог изменяться в размере, нам нужно будет выполнить какое-то динамическое размещение, что означает, что для хранения данных нам придется использовать указатель.
#ifndef INTARRAY_H
#define INTARRAY_H
class IntArray
{
private:
int m_length{};
int *m_data{};
};
#endifТеперь нам нужно добавить несколько конструкторов, которые позволят нам создавать объекты IntArray. Мы собираемся добавить два конструктора: один, который создает пустой массив, и второй, который позволит нам создать массив заранее определенного размера.
#ifndef INTARRAY_H
#define INTARRAY_H
#include <cassert> // for assert()
class IntArray
{
private:
int m_length{};
int *m_data{};
public:
IntArray() = default;
IntArray(int length):
m_length{ length }
{
assert(length >= 0);
if (length > 0)
m_data = new int[length]{};
}
};
#endifНам также понадобятся функции, которые помогут очистить объекты IntArray. Сначала мы напишем деструктор, который просто освобождает любые динамически размещенные данные. А затем напишем функцию с именем erase(), которая сотрет массив и установит значение длины в 0.
~IntArray()
{
delete[] m_data;
// здесь нам не нужно устанавливать m_data в значение null
// или m_length в 0, так как объект в любом случае будет
// уничтожен сразу после этой функции
}
void erase()
{
delete[] m_data;
// Нам нужно убедиться, что мы установили здесь m_data
// равным nullptr, иначе это оставит указатель
// указывающим на освобожденную память!
m_data = nullptr;
m_length = 0;
}Теперь давайте перегрузим operator[], чтобы мы могли получить доступ к элементам массива. Мы должны проверить индекс, чтобы убедиться, что он корректен, что лучше всего сделать с помощью функции assert(). Также добавим функцию доступа для получения длины массива. Пока всё:
#ifndef INTARRAY_H
#define INTARRAY_H
#include <cassert> // для assert()
class IntArray
{
private:
int m_length{};
int *m_data{};
public:
IntArray() = default;
IntArray(int length):
m_length{ length }
{
assert(length >= 0);
if (length > 0)
m_data = new int[length]{};
}
~IntArray()
{
delete[] m_data;
// здесь нам не нужно устанавливать m_data в значение null
// или m_length в 0, так как объект в любом случае будет
// уничтожен сразу после этой функции
}
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() const { return m_length; }
};
#endifНа данный момент у нас есть класс IntArray, который мы уже можем использовать. Мы можем размещать объекты IntArray заданного размера и можем использовать operator[] для извлечения или изменения значений элементов.
Однако есть еще кое-что, что мы не можем сделать с нашим объектом IntArray. Мы по-прежнему не можем изменить его размер, по-прежнему не можем вставлять или удалять элементы и по-прежнему не можем отсортировать его.
Во-первых, давайте напишем код, который позволит нам изменять размер массива. Для этого мы напишем две разные функции. Первая функция, reallocate(), уничтожает все существующие элементы в массиве при изменении его размера, но она будет быстрой. Вторая функция, resize(), сохраняет все существующие элементы в массиве при изменении его размера, но она будет медленной.
// reallocate изменяет размер массива. Любые существующие элементы
// будут уничтожены. Эта функция работает быстро.
void reallocate(int newLength)
{
// Сначала мы удаляем все существующие элементы
erase();
// Если теперь наш массив будет пустым, возвращаемся отсюда
if (newLength <= 0)
return;
// Затем нам нужно разместить новые элементы
m_data = new int[newLength];
m_length = newLength;
}
// resize изменяет размер массива. Любые существующие элементы
// будут сохранены. Эта функция работает медленно.
void resize(int newLength)
{
// если массив уже имеет нужную длину, мы закончили
if (newLength == m_length)
return;
// Если мы изменяем размер до пустого массива, делаем это и возвращаемся
if (newLength <= 0)
{
erase();
return;
}
// Теперь мы можем предположить, что newLength - это как минимум 1 элемент.
// Этот алгоритм работает следующим образом:
// Сначала размешаем новый массив.
// Затем копируем элементы из существующего массива в новый массив.
// Как только это будет сделано, можно уничтожить старый массив
// и заставить 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().
void insertBefore(int value, int index)
{
// Проверяем значение нашего индекса на корректность
assert(index >= 0 && index <= m_length);
// Сначала создаем новый массив на один элемент больше старого массива
int *data{ new int[m_length+1] };
// Копируем все элементы до индекса
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);
// Если это последний элемент в массиве,
// делаем массив пустым и выходим
if (m_length == 1)
{
erase();
return;
}
// Сначала создаем новый массив на один элемент меньше старого массива
int *data{ new int[m_length-1] };
// Копируем все элементы до индекса
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); }_м); }Ниже приведен наш контейнерный класс IntArray целиком.
IntArray.h:
#ifndef INTARRAY_H
#define INTARRAY_H
#include <cassert> // для assert()
class IntArray
{
private:
int m_length{};
int *m_data{};
public:
IntArray() = default;
IntArray(int length):
m_length{ length }
{
assert(length >= 0);
if (length > 0)
m_data = new int[length]{};
}
~IntArray()
{
delete[] m_data;
// здесь нам не нужно устанавливать m_data в значение null
// или m_length в 0, так как объект в любом случае будет
// уничтожен сразу после этой функции
}
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)
{
// если массив уже имеет нужную длину, мы закончили
if (newLength == m_length)
return;
// Если мы изменяем размер до пустого массива, делаем это и возвращаемся
if (newLength <= 0)
{
erase();
return;
}
// Теперь мы можем предположить, что newLength - это как минимум 1 элемент.
// Этот алгоритм работает следующим образом:
// Сначала размешаем новый массив.
// Затем копируем элементы из существующего массива в новый массив.
// Как только это будет сделано, можно уничтожить старый массив
// и заставить 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] };
// Копируем все элементы до индекса
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);
// Если это последний элемент в массиве,
// делаем массив пустым и выходим
if (m_length == 1)
{
erase();
return;
}
// Сначала создаем новый массив на один элемент меньше старого массива
int *data{ new int[m_length-1] };
// Копируем все элементы до индекса
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() const { return m_length; }
};
#endifА теперь давайте протестируем его, чтобы убедиться, что он работает:
#include <iostream>
#include "IntArray.h"
int main()
{
// Объявляем массив из 10 элементов
IntArray array(10);
// Заполняем массив числами от 1 до 10
for (int i{ 0 }; i<10; ++i)
array[i] = i+1;
// Изменим размер массива до 8 элементов
array.resize(8);
// Вставляем число 20 перед элементом с индексом 5
array.insertBefore(20, 5);
// Удаляем элемент с индексом 3
array.remove(3);
// Добавляем 30 и 40 в конец и начало
array.insertAtEnd(30);
array.insertAtBeginning(40);
// Распечатываем все числа
for (int i{ 0 }; i<array.getLength(); ++i)
std::cout << array[i] << ' ';
std::cout << '\n';
return 0;
}Эта программа дает следующий результат:
40 1 2 3 5 20 6 7 8 30Хотя написание контейнерных классов может быть довольно сложным, хорошая новость заключается в том, что вам нужно написать их только один раз. Как только контейнерный класс заработает, вы можете повторно использовать его так часто, как захотите, без каких-либо дополнительных усилий по написанию кода.
Также стоит прямо упомянуть, что даже несмотря на то, что наш пример класса-контейнера IntArray хранит значения встроенного типа данных (int), мы могли бы так же легко использовать пользовательский тип (например, класс Point).
Еще один момент: если класс из стандартной библиотеки соответствует вашим потребностям, используйте его вместо создания своего собственного. Например, вместо IntArray лучше использовать std::vector<int>. Он протестирован в боевых условиях, эффективен и прекрасно сочетается с другими классами стандартной библиотеки. Но иногда вам может понадобиться специализированный контейнерный класс, которого нет в стандартной библиотеке, поэтому полезно знать, как создать свой собственный контейнер, когда вам это нужно. Мы поговорим о контейнерах стандартной библиотеки, когда рассмотрим еще несколько базовых тем.