Где-то в Medium я нашел Google Interview University (взгляните!) И решил последовать некоторым из предоставленных советов; начав с создания собственной реализации базовых структур данных.
Что такое динамический массив?
С точки зрения непрофессионала, динамический массив похож на массив, но с той разницей, что его размер может динамически изменяться во время выполнения.
Элементы массива занимают непрерывный блок памяти, и после создания его размер не может быть изменен. Динамический массив может после заполнения массива выделить больший кусок памяти, скопировать содержимое из исходного массива в это новое пространство и продолжить заполнение доступных слотов.
В бэкэнде динамические массивы выделяют заранее определенный объем памяти при создании, который затем увеличивается в определенном размере, когда это необходимо. Эти параметры, начальный размер и фактор роста являются центральными с точки зрения производительности. Если исходный размер и фактор роста малы, вы будете часто перераспределять память, что плохо; с другой стороны, если они имеют более высокое значение, у вас, вероятно, будет много неиспользуемой памяти, и операция изменения размера может занять больше времени. Здесь очевиден компромисс.
Примеры динамических массивов в распространенных языках: ArrayList в Java и C #, Vector в C ++, List<> в .NET, list в Python и другие.
Реализация
Я начал писать динамический массив целых чисел на C. При этом я заметил, что было бы лучше написать массив класса, который управлял бы структурой данных, поэтому я переключился на C ++. И, поскольку мы уже на C ++, я решил создать класс шаблона, чтобы мы могли управлять динамическим массивом любого типа :).
Это мой класс Array; здесь важными методами являются Array (конструктор), push, pop, set, get и resize. Используемые атрибуты: m_size, текущий размер массива, m_capacity, текущая емкость массива иm_data, указатель на данные массива. Я также объявил некоторые утилитарные методы, такие как size(), capacity() & print().
Конструктор
Устанавливает размер и емкость. Здесь я использовал заранее определенное значение начальной емкости. Размер равен нулю, так как при создании в массиве нет данных. Также выделяется место для массива.
Деструктор
Освобождает выделенную память m_data.
Толкать
Помещает значение в верхнюю часть массива. Перед отправкой убедитесь, что в массиве есть свободное место! В противном случае может возникнуть ошибка сегментации.
Поп
Возвращает значение в верхней части массива и удаляет его из массива, уменьшая его размер на единицу.
Установленный
Устанавливает значение в массиве для данного индекса. Если индекс больше текущей емкости, размер массива изменяется и заполняется нулями, пока индекс не будет достигнут.
Изменить размер
Как следует из названия, он изменяет размер массива, заставляя его увеличиваться в определенном размере. Для этого я использовал функцию realloc. Вы тоже можете использовать malloc/memcpy. Если realloc успешно, m_data указывает на вспомогательный указатель tmp.
Тестирование
Это небольшой пример того, как использовать структуру данных, создавая массив целых чисел и управляя им.
И результат…
Код
Я оставлю полную реализацию в моем Github, не стесняйтесь комментировать или предлагать изменения, если вы видите что-то не так :)
