Реализация динамического массива на C++ для задач, где требуется хранить в массиве большие объекты классов, при этом существует необходимость создания указателей на элементы, которые будут стабильны при добавлении новых элементов массива и удалении существующих, а также есть необходимость эффективно добавлять элементы не только в начало и конец, но и в середину массива.
Под стабильностью указателей понимается неизменность адресов в памяти, где располагаются объекты, являющиеся элементами массива. Т.е. указатель-переменная, созданный отдельно от массива и указывающий на любой его элемент, сохранит актуальность независимо от того, какие действия производятся с этим массивом. Это не означает, что элемент массива не может быть удален или перемещен с изменением адреса, что неминуемо приведет к инвалидации указателя. И, само собой, это не означает, что указатель будет как-либо привязан к индексации массива. Например:
nx_array<QString> my_array;
my_array += "B"; // добавили элемент
QString* item_ptr = &(my_array[0]); // item_ptr теперь хранит адрес my_array[0]
my_array.addItem("A", 0); // теперь в массиве новый my_array[0],
// а item_ptr хранит адрес my_array[1]
Не имея желания изобретать велосипед, я взял за основу стандартные std::list и std::vector. Вся идея очень проста: у класса NxArray два поля данных: data_list типа list и ptr_vector типа vector. Элементы массива статично лежат в data_list[], т.е. в "куче", без каких-либо реаллокаций, а ptr_vector[] хранит указатели на эти элементы. Соответственно, через эти указатели и реализован доступ.
Методы NxArray условно разделяются на две категории: первая - это собственные методы класса, необходимые для комфортной работы. Эти методы отличаются своими названиями, записываемыми без символа подчеркивания, где каждое следующее слово пишется с заглавной буквы, например, метод добавления элемента - addItem(). Вторая категория - это реализация некоторых стандартных методов STL, дающая возможность при желании быстро заменить в готовой программе объекты vector на NxArray, не исправляя вызовы методов класса. Речь идет о всем знакомым методах push_back(), pop_back() и т.д. Ну, и есть еще третья категория методов - это методы, являющиеся общими для NxArray и STL, они, всё по той же логики совместимости с vector, имеют названия из STL: например, функция, возвращающая размер массива, т.е. количество его элементов, называется size(), а функция возвращающая ссылку на элемент массива с проверкой индекса - at(index).
Конструкторы класса
1. Конструктор без параметров и конструктор с параметрами размера:
nx_array<int> arr1; // пустой массив nx_array<int> arr2(5); // массив с 5 элементами (значения по умолчанию) nx_array<int> arr3(3, 10); // 3 элемента, резерв = 10
2. Конструктор со значением по умолчанию (для целочисленных типов требуется привести параметры к size_t):
nx_array<int> arr(size_t(5), size_t(10), 42); // 5 элементов со значением 42, резерв = 10
3. Конструктор из std::initializer_list:
nx_array<int> arr1{1, 2, 3}; // массив с тремя элементами nx_array<int> arr2({1, 2, 3}, 10); // резерв = 10 nx_array<std::string> arr3{{"a", "b", "c"}, 5, true}; // перемещение элементов
nx_array<QString> arr1{"a", "b", "c"}; // массив с тремя элементами nx_array<QString> arr2({"a", "b", "c"}, 10); // резерв = 10 nx_array<QString> arr3{{"a", "b", "c"}, 10}; // тоже самое QString str1 = "a", str2 = "b", str3 = "c"; nx_array<QString> obj_arr{{str1, str2, str3}, 5, true}; // перемещение из str1, str2, str3, резерв = 5
4. Конструктор из итераторов:
std::vector<int> vec = {1, 2, 3}; nx_array<int> arr1(vec.begin(), vec.end()); // копирование из вектора nx_array<int> arr2(vec.begin(), vec.end(), 10, true); // перемещение, резерв = 10
5. Конструктор из контейнеров:
std::list<int> lst = {1, 2, 3}; nx_array<int> arr1(lst); // Копирование из std::list nx_array<int> arr2(lst, 10, true); // Перемещение, резерв = 10
6. Конструктор из rvalue-контейнеров:
nx_array<int> arr1(std::vector<int>{1, 2, 3}); // Перемещение из временного вектора nx_array<int> arr2(std::list<int>{4, 5, 6}, 10); // Перемещение из временного списка
7. Конструктор копирования и перемещения:
nx_array<int> original{1, 2, 3}; nx_array<int> copy(original); // Копирование nx_array<int> moved(std::move(original)); // Перемещение nx_array<int> moved2(original, 0, true); // Явное перемещение
8. Конструкторы из конкретных контейнеров:
std::array<int, 3> std_arr = {1, 2, 3}; nx_array<int> arr_a(std_arr, 5); // Копирование, резерв = 5
std::vector<int> vec = {1, 2, 3}; nx_array<int> arr_v(vec, 10, true); // Перемещение, резерв = 10
9. Конструктор из простого массива:
int raw_arr[] = {1, 2, 3}; nx_array<int> arr1(3, raw_arr); // Копирование nx_array<int> arr2(3, raw_arr, 10, true); // Перемещение, резерв = 10
// Пример с std::vector: std::vector<int> vec = {4, 5, 6}; nx_array<int> arr3(3, vec.data()); // Копирование из данных вектора
Основные методы класса:
bool isPointerValid(const T* ptr) - ищет переданный в функцию указатель в векторе указателей класса. Несмотря на то, что указатели на элементы массива стабильны и в общем и целом можно без опасений создавать переменные-указатели на эти элементы, но указатель всё же потеряет актуальность в случае удаления элемента из массива. По этой причине реализована эта функция поиска элемента по его адресу.
int getItemIndex(const T* ptr) - по сути та же функция, но возвращает не признак того, найден элемент или нет, а его индекс. Если элемент отсутствует, вернет значение -1.
T* getItemPtr(size_type index) - возвращает адрес элемента массива по его индексу.
T& at(size_type index) - возвращает ссылку на элемент массива по его индексу (т.е. тоже самое, что оператор [index]) с проверкой корректности указанного индекса.
size_type size() - возвращает количество элементов массива
void checkIterator(const const_iterator& it) - функция проверки актуальности итератора
void moveItem(size_type from, size_type to) - перемещает элемент массива на другую позицию
void swapItems(size_type i, size_type j) - меняет два элемента массива местами
void removeItem(size_type index) - удаляет элемент массива по индексу
void removeRange(size_type start, size_type finish = END_POS) - удаляет диапазон элементов массива
void addItem(const T& value, int position = END_POS, bool useExc = false) - добавляет элемент в массив. По умолчанию - в конец массива. Если указан номер элемента, превышающий размер массива, то функция либо добавит элемент в конец (если useExc = false), либо выдаст исключение.
T& emplaceItem(int position = END_POS, Args&&... args) - добавляет элемент с инициализацией
void resize(size_type new_size) - меняет размер массива, т.е. либо удаляет лишние элементы, либо наоборот добавляет пустые элементы в конец массива
void resize(size_type new_size, const T& value) - тоже самое, но со значением по умолчанию для добавляемых элементов
void reverse() - меняет последовательность элементов массива на противоположную
bool sort() - сортирует элементы массива от меньшего к большему. Требует, чтобы типа данных массива поддерживал оператор "<", в противоположном случае функция вернет false
list_type toStdList() - возвращает копию массива в формате std::list
list_type ejectStdList() - возвращает (извлекает) оригинал объекта внутреннего поля std::list класса NxArray через list::splice(), обнуляя исходный массив. Адреса бывших элементов массива сохраняются неизменными, сторонние указатели не теряют актуальности.
list_type toStdList() && - вызывает ejectStdList()
std::vector<T> toStdVector() - возвращает копию массива в формате std::vector
std::vector<T> toStdVector() && - возвращает std::vector с перемещенными из std::list данными (через std::make_move_iterator), обнуляя исходный массив
std::deque<T> toStdDeque() - возвращает копию массива в формате std::deque
std::deque<T> toStdDeque() && - возвращает std::deque с перемещенными из std::list данными (через std::make_move_iterator), обнуляя исходный массив
QList<T> toQList() - возвращает копию массива в формате QList
QList<T> toQList() && - возвращает QList с перемещенными из std::list данными (через std::make_move_iterator), обнуляя исходный массив
void apply(Function func) - применяет функцию ко всем элементам массива
T extract(size_type index) - извлекает элемент (через std::move) с удалением из контейнера. Не работает с типами данных, которые нельзя перемещать
T extract(const_iterator pos) - метод, аналогичный предыдущему, но работающий через итератор, а не по индексу. Является аналогом метода extract() в реализации std::list стандарта C++17
void addArray(const Container& container, int position = END_POS) - присоединение другого массива путем копирования элементов. Поддерживаются массивы типа NxArray, vector, list, deque и QList
void addArray(const Container&& container, int position = END_POS) - присоединение другого массива путем перемещения элементов функцией std::move. Функция аналогичная методу mergeArray(), но требует указания std::move в явном виде при вызове. При вызове для типов данных NxArray или list вместо std::move будут вызваться функции spliceArray.
void addArray(const T* arr, size_type size, int position = END_POS, bool useExc = false) - функция, аналогичная предыдущей, но для добавления копии простого массива. Требует указания его размера. При useExc = true провоцирует исключения при указании нулевого адреса массива или некорректного параметра position
void spliceArray(list_type& lst, int position = END_POS) - присоединение массива std::list через list.splice, т.е. с сохранением присоединяемых элементов в исходных областях памяти. Указатели, созданные для этих элементов до выполнения функции, сохранят актуальность. Присоединяемый массив обнулится
void spliceArray(nx_array& arr, int position = END_POS) - метод, аналогичный предыдущему, но для NxArray. Поскольку NxArray хранит данные в std::list, то для него также доступно перемещение элементов через list.splice
void mergeArray(Container& container, int position = END_POS) - присоединение другого массива путем перемещения элементов функцией std::move. Поддерживаются массивы типа vector, deque и QList. Не используется для list и NxArray, поскольку для них существует более эффективная функция spliceArray()
Операторы, используемые в NxArray.
Как и в случае с функциями добавления элементов, операторы различают копирование и перемещение объектов через rvalue-ссылки (std::move) или функцией list.splice. Для присвоения копий элементов других классов-контейнеров используется оператор "=", а для добавления к существующим элементам таких копий - операторы "+" и "+=". Для присвоения другого контейнера путем перемещения его элементов используется оператор "<<=", для добавления элементов путем перемещения - "<<".
nx_array<QString> arr1 = {"X", "Y"};
nx_array<QString> arr2 = {"Z"};
arr1 += "A" + QString("B") << arr2; // arr1 = {X, Y, A, B, Z}
// arr2 - пуст
arr1 += ("A" + QString("B")) << arr2; // более корректная запись (учитывая, что << имеет более высокий приоритет, чем +)
Оператор [index] работает аналогично стандартному массиву, vector'у и т.п.
Методы, реализованные для удобной замены std::vector на NxArray.
Методы, возвращающие итераторы: begin(), end(), rbegin(), rend(), cbegin(), cend(), crbegin(), crend()
.......
