Реализация шаблона класса “Динамический массив”

Рассмотрим реализацию класса dynamic_array - динамический массив, то есть массив, размер которого может изменяться.

Скачать реализацию класса dynamic_array.

Реализация класса представляет собой шаблон, параметром шаблона является тип хранимых в массиве элементов.

Закрытые поля класса:

m_size - размер массива (количество элементов в массиве, доступных пользователю).

m_capacity - "вместимость" массива, то есть размер выделенной памяти для хранения элементов. При увеличении размера массива если новый размер не превосходит m_capacity, то новые элементы можно создать в массиве без выделения дополнительной памяти.

m_data - указатель на область памяти, где хранятся сами элементы массива.

template <typename T>
class dynamic_array
{
 private:
    int m_size;
    int m_capacity;
    T * m_data;

Конструкторы и деструкторы

Конструктор по умолчанию создает пустой массив, не содержащий элементов.

 public:
    dynamic_array()
    {
        m_size = 0;
        m_capacity = 0;
        m_data = NULL;
    }

Копи-конструктор создает копию существующего массива. Он нужен для того, чтобы при создании копии массива выделить новую память для хранения данных копии массива и скопировать туда все элементы. Если не сделать копи-конструктор, то при создании копии массива поле m_data у копии будет указывать на ту же область памяти, что и у исходного массива. Поэтому если в классе используется динамическое распределение памяти, то всегда необходимо создавать копи-конструктор.

    dynamic_array(const dynamic_array<T> & a)
    {
        m_size = a.m_size;
        m_capacity = m_size;
        m_data = NULL;
        if (m_size != 0)
            m_data = new T[m_size];
        else
            m_data = 0;
        for (int i = 0; i < m_size; ++i)
            m_data[i] = a.m_data[i];
    }

Конструктор, который создает массив заданного размера.

    dynamic_array(int size)
    {
        m_size = size;
        m_capacity = size;
        if (size != 0)
            m_data = new T[size];
        else
            m_data = 0;
    }

Деструктор необходим для того, чтобы освободить выделенную память при удалении объекта.

    ~dynamic_array()
    {
        if (m_data)
            delete[] m_data;
    }

Изменение размера массива

Метод resize изменяет размер массива, новый размер передается параметром size. Если значение size не превосходит значения m_capacity, то этот метод только изменяет значение поля m_size, иначе необходимо перевыделить память - выделяется новая область памяти для хранения элементов, существующие элементы массива копируются из старой области памяти в новую, выделенная ранее память освобождается.

Для того, чтобы память не выделялась слишком часто, размер выделенной памяти удваивается по сравнению со старым размером массива.

    void resize(int size)
    {
        if (size > m_capacity)
        {
            int new_capacity = max(size, m_size * 2);
            T * new_data = new T[new_capacity];
            for (int i = 0; i < m_size; ++i)
                new_data[i] = m_data[i];
            delete[] m_data;
            m_data = new_data;
            m_capacity = new_capacity;
        }
        m_size = size;
    }

Метод push_back добавляет один новый элемент в конец массива.

    void push_back(T val)
    {
        resize(m_size + 1);
        m_data[m_size - 1] = val;
    }

Метод size возвращает размер массива.

    int size() const
    {
        return m_size;
    }

Доступ к элементам массива

Доступ к элементам массива перегрузим оператор []. Это позволит обращаться к элементам класса dynamic_array так же, как к элементам обычного массива: a[i].

    T & operator[] (int i)
    {
        return m_data[i];
    }
}; // Конец класса dynamic_array

Перегрузка оператора вывода

Для вывода массива перегрузим оператор <<. Это необходимо сделать отдельной функцией после реализации класса dynamic_array.

template<typename T>
ostream & operator << (ostream & out, dynamic_array<T> a)
{
    for (int i = 0; i < a.size(); ++i)
        out << a[i] << " ";
    return out;
}