Давно уже подкопились задачи, где требуется хранить в массиве большие объекты классов, при этом существует необходимость создания указателей на элементы, которые стабильны при добавлении новых элементов и удалении существующих, а также есть необходимость эффективно добавлять элементы не только в начало и конец, но и в середину массива.
Под стабильность. указателей понимается неизменность адресов в памяти, где располагаются объекты, являющиеся элементами массива. Т.е. указатель-переменная, созданный отдельно от массива и указывающий на любой его элемент, сохранит актуальность независимо от того, какие действия производятся с этим массивом. Это не означает, что элемент массива не может быть удален или перемещен с изменением адреса, что неминуемо приведет к инвалидации указателя. И, само собой, это не означает, что указатель будет как-либо привязан к индексации массива. Например:
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]
Понятно, что задача специфическая, но при этом нельзя сказать, что уникальная. Из классов-контейнеров, которые нам предлагает стандартная библиотека, у нас, как известно, есть в распоряжении 3 варианта: vector, list и deque. Также в отдельных средах разработки реализованы свои классы-контейнеры: от TList в незабвенном C++Builder до QList в Qt. Но из всех этих контейнеров требованиям, поставленным в задаче, отвечает лишь list, поскольку только он хранит элементы массива в "куче", т.е. в разрозненных участках памяти, что отличает его от стандартного массива, последовательности элементов указателя и последовательных контейнеров типа vector. Последовательность элементов позволяет реализовать более быстрый доступ к элементам массива, поэтому считается предпочтительной. Такие контейнеры как deque и QList также базируются на этом, хотя и используют разделение массива на фрагменты, чтобы снизить число реаллокаций. Но это же является причиной, почему эти котейнеры годятся не для всех задач: реаллокации в них всё равно происходят, особенно при добавлении элементов между существующими элементами массива.
Ну а если говорить про list, то этот контейнер нельзя по сути назвать динамическим массивом, поскольку отличительная особенность любого массива - это доступ по индексу, т.е. наличие оператора квадратные скобки - [index]. У list же, как известно, доступ к элементам происходит через итератор. Хотя работа через итераторы не является особенностью list. Поскольку другие контейнеры работают с последовательностями в памяти, то и у них все основные методы реализованы через итераторы, а не через индексы, хотя и есть произвольный доступ к элементам через оператор [index]. Я же считаю, что нормальный динамический массив как раз должен иметь функционал для работы по индексам, что является более простым и естественным вариантом для любого массива.
Соответственно, учитывая всё вышесказанное, я взялся за создание собственного класса-контейнера NxArray (для удобства объявления переменных класс формально называется nx_array, но я при описании буду использовать неформальное название NxArray).
Не имея желания изобретать велосипед, я взял за основу стандартные list и vector. Вся идея очень проста: у класса NxArray два поля данных: типов list и vector. Элементы массива статично лежат в list, т.е. в "куче", без каких-либо реаллокаций, а vector хранит указатели на эти элементы. Соответственно, через эти указатели и реализован доступ.
Методы NxArray условно разделяются на две категории: первая - это собственные методы класса, необходимые для комфортной работы. Эти методы отличаются своими названиями, записываемыми без символа подчеркивания, где каждое следующее слово пишется с заглавной буквы, например, метод добавления элемента - addItem(). Вторая категория - это реализация некоторых стандартных методов STL, дающая возможность при желании быстро заменить в готовой программе объекты vector на NxArray, не исправляя вызовы методов класса. Речь идет о всем знакомым методах push_back(), pop_back() и т.д. Ну, и есть еще третья категория методов - это методы, являющиеся общими для NxArray и STL, они, всё по той же логики совместимости с vector, имеют названия из STL: например, функция, возвращающая размер массива, т.е. количество его элементов, называется size(), а функция возвращающая ссылку на элемент массива с проверкой индекса - at(index).
Начнем описание с конструкторов класса. Несмотря на заявленную совместимость с STL для удобства замены vector на NxArray, эта совместимость не касается конструкторов, которые имеют отличия. Причина тут весьма проста: дело в том, что любое изменение размера массива в большую сторону приводит к реаллокации, т.е. все элементы копируются в новый участок памяти. Для того, чтобы этого не происходило, vector имеет метод reserve(), но его проблемматично использовать в ряде случаев, когда количество элементов заранее неизвестно даже приблизительно (например, когда зависит от условий, определяемых пользователем ПО). Выделять же бездумно память на громоздкие объекты, не зная наверняка, хватит ее или нет, не самое лучшее решение. По этой причине vector не предусматривает выделение памяти при инициализации. Совершенно иная ситуация с vector'ом, являющимся полем класса NxArray: поскольку сами объекты хранятся в "куче" и управляются через list, для этих объектов никакое резервирование априори не требуется, а вот внутренний vector, хранящий указатели, можно смело раздувать с необходимым запасом, ведь его элементы равны размеру адреса ячейки памяти. По этой причине в классе NxArray есть не только функция reserve(), но и резервирование, реализованное через конструктор:
nx_array(size_type initial_count = 0, size_type reserve_count = 0)
nx_array(size_type count, size_type reserve_count, const T& value)
nx_array(const nx_array& other_array)
nx_array(nx_array&& other_array)
Вот, собственно, 4 конструктора. В простейшем случае можно объявить пустой массив без резервирования:
nx_array<QString> my_array;
Здесь конструктор внешне совпадает с реализацией std::vector, поскольку количество зарезервированных элементов по умолчанию равно размеру массива (в данном случае - нулю) и их можно не указывать. Но если мы захотим задать значение по умолчанию для всех элементов, то в этом случае нам придется явно указать значение второго параметра, и тут конструктор уже не совпадет с реализацией vector'а:
nx_array<QString> my_array(10, 0, "A");
nx_array<QString> my_array(10, 10, "A"); // равнозначно
vector<QString> my_vector(10, "A"); // у vector'а конструктор без резервирования
Несмотря на то, что количество зарезервированных элементов в первой строке равно значению по умолчанию (ноль), по факту в любом случае оно станет равным 10, поскольку не может быть меньше количества элементов массива. Так или иначе, второй параметр функции предётся указывать в явном виде.
Основные методы класса:
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 removeMultiple(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()
.......
