16.6 – Контейнерные классы

Добавлено 27 июля 2021 в 02:46

В реальной жизни мы постоянно используем контейнеры. Сухие завтраки поставляются в коробках, страницы в вашей книге находятся внутри обложки и переплета, и вы можете хранить любое количество предметов в контейнерах в своем гараже. Без контейнеров было бы крайне неудобно работать со многими из этих объектов. Представьте, что вы пытаетесь прочитать книгу без какого-либо переплета или съесть хлопья, которые не были в коробке, и без тарелки. Это был бы бардак. Ценность контейнера в основном заключается в его способности помогать организовывать и хранить предметы, помещенные в него.

Точно так же контейнерный класс – это класс, предназначенный для хранения и организации нескольких экземпляров другого типа (либо другого класса, либо базового типа). Существует множество различных типов контейнерных классов, каждый из которых имеет различные преимущества, недостатки и ограничения в использовании. Безусловно, наиболее часто используемым контейнером в программировании является массив, примеры которого вы уже видели. Хотя 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>. Он протестирован в боевых условиях, эффективен и прекрасно сочетается с другими классами стандартной библиотеки. Но иногда вам может понадобиться специализированный контейнерный класс, которого нет в стандартной библиотеке, поэтому полезно знать, как создать свой собственный контейнер, когда вам это нужно. Мы поговорим о контейнерах стандартной библиотеки, когда рассмотрим еще несколько базовых тем.

Теги

C++ / CppLearnCppДля начинающихКласс (программирование)ОбучениеОбъектно-ориентированное программирование (ООП)Программирование

На сайте работает сервис комментирования DISQUS, который позволяет вам оставлять комментарии на множестве сайтов, имея лишь один аккаунт на Disqus.com.

В случае комментирования в качестве гостя (без регистрации на disqus.com) для публикации комментария требуется время на премодерацию.