alg_hw_2_data_struct
IArray.h - виртуальный класс, реализующий интерфейс array.
SingleArray.h, VectorArray.h, FactorArray.h, MatrixArray.h - реализация соответствующих структур с добавлением методов add и remove по индексу.
List.h - односвязный список реализующий интерфейс очереди.
PriorityQueue.h - очередь с приоритетом (вектор списков).
main.cpp - в данном файле реализовал тесты, для проверки времени выполнения операций с разными типами структур данных и для проверки очереди с приоритетами.
tab_data_struct - таблица с временем выполнения различных операция для разных типов Array.
Пояснения по массивам.
SingleArray. Массив простой, лишней памяти не занимает. доступ к элементу за 0(1). добавление элемента приводит к перезаписи массива. Можно использовать только для небольшого количества элементов.
VectorArray. Улучшенный вариант обычного массива. За счет аллоцирования заранее большего куска памяти, удается снизить количество перезаписей данных при добавлении элементов. Возможна ситуация, когда массив будет занимать лишнюю память, и не использовать ее. доступ к элементу за 0(1).
FactorArray. Улучшенный Vectorarray. каждый раз занимаем большее количество памяти, тем самым уменьшаем количество копирований элементов. доступ к элементу за 0(1). Минус с аллокацией лишней памяти. Например, для 10001 элемента может быть занята 20000 памяти.
MatrixArray. Структура специфичная. Имеет смысл использовать под конкретную задачу, где надо аллоцировать память кусками по N и не требуется удалять и ставлять элементы в середину.