ссылка для скачивания
В архиве три файла для C++ (требуется поддержка компилятором C++11):
1. Qt
2. Visual C++
3. C++Builder
Версия для Visual C++ является базовой. В версии для Qt добавлена поддержка строковых литералов для QString и работа с QList. В версии для C++Builder добавлена поддержка строковых литералов для UnicodeString.
Реализация динамического массива на C++, обеспечивающего стабильность указателей.
Под
стабильностью указателей понимается неизменность адресов в памяти, где
располагаются объекты, являющиеся элементами массива. Т.е.
указатель-переменная, созданный отдельно от массива и указывающий на
любой его элемент, сохранит актуальность независимо от того, какие
действия производятся с этим массивом.
Немного об идее.
Идея родилась по ходу разработки конкретного кода, где использовались указатели на элементы динамического массива std::vector и, соответственно, потребовалось сохранять валидность этих указателей при изменении размера вектора. А vector так не умеет. Стал смотреть альтернативы - std::list стабилен, но не имеет индексации - поэтому сразу в топку, std::deque работает через чанки, т.е. разрозненные последовательности элементов, но стабильности в нем нет, там тоже бывают реаллокации. Ну. и в C++Builder, в котором проект я разрабатывал, своих нормальных вариантов тоже нет, TList просто недоразумением показался (C++Builder 6 еще был со старым TList, хотя и новый не лучше). Так вот зародилась идея сделать динамический массив стабильных элементов. Ну, а потом еще выяснилось, что в Qt, на котором я писал программы раньше, начиная с 6 версии фактически ликвидирован класс QList, который превратился в мурзилку для QVector. Суть такая, что в Qt 5 для всех объектов, кроме простых типов, QList как раз и работал без реаллокации элементов, котрые хранились просто в "куче", а для для всеми любимых realloc существал QVector. Потом кто-то из разработчиков Qt изучил тысячи строк кода и внезапно обнаружил, что многие используют QList там, где следовало бы применить QVector, и не нашел ничего лучше как просто превратить QList в QVector. Так что для Qt 6, если вдруг потребуется динамический массив без реаллокаций, то тоже можно применять класс nx_array.
Не имея желания изобретать велосипед, я взял за основу стандартные std::list и std::vector. Вся идея очень проста: у класса nx_array два поля данных: data_list[] типа std::list и ptr_vector[]
типа std::vector. Элементы массива статично лежат в data_list[], т.е. в
"куче", без реаллокаций, а ptr_vector[] хранит указатели на
эти элементы. Через эти указатели и реализован доступ по индексу.
Немного о реаллокациях и стабильности указателей.
Как уже было сказано, указатель-переменная, созданный отдельно от массива и указывающий на
любой его элемент, сохранит актуальность независимо от того, какие
действия производятся с этим массивом. Однако, это не означает, что элемент массива не может быть удален или перемещен с изменением адреса, что неминуемо приведет к инвалидации указателя. И, само собой, это не означает, что указатель будет как-либо привязан к индексации массива. Например:
nx_array<QString> my_array;
my_array += "B"; // добавили элемент my_array[0] со значением "B"
QString* item_ptr = &(my_array[0]); // item_ptr хранит адрес my_array[0]
// добавляем в массив новый my_array[0]:
my_array.addItem("A", 0); // item_ptr хранит прежний адрес, который теперь указывает на my_array[1]
Методы класса.
Методы nx_array условно разделяются на три категории:
1. Собственные методы класса, необходимые для комфортной работы. Эти методы отличаются своими названиями, записываемыми без символа подчеркивания, где каждое следующее слово пишется с заглавной буквы, например, метод добавления элемента - addItem().
2. Реализация некоторых стандартных методов STL, дающая возможность при желании быстро заменить в готовой программе объекты std::vector на nx_array, не исправляя вызовы методов класса. Речь идет о всем знакомым методах push_back(), pop_back() и т.д.
3. Методы, являющиеся общими для nx_array и STL, они, всё по той же логики совместимости с std::vector, имеют названия из STL: например, функция, возвращающая размер массива, т.е. количество его элементов, называется size(), а функция возвращающая ссылку на элемент массива с проверкой индекса - at(index).
Конструкторы класса
1. Конструктор без параметров и конструктор с параметрами размера и зарезервированного пространства (резервирование относится только к внутреннему массиву ptr_vector, а не к основному хранилищу объектов):
nx_array<int> arr1; // пустой массив
nx_array<int> arr2(5); // массив с 5 элементами
nx_array<int> arr3(3, 10); // 3 элемента, резерв = 10
2. Конструктор из std::initializer_list:
nx_array<int> arr1{1, 2, 3}; // массив с тремя элементами
nx_array<int> arr2({1, 2, 3}, 10); // резерв = 10nx_array<QString> arr1{"a", "b", "c"}; // массив с тремя элементами
nx_array<QString> arr2({"a", "b", "c"}, 10); // резерв = 10
nx_array<QString> arr3{{"a", "b", "c"}, 10}; // тоже самое
3. Конструктор из rvalue-контейнера
nx_array<
int>
arr1(
std::
vector<
int>{
1,
2,
3});
// Перемещение из временного вектора
nx_array<
int>
arr2(
std::
list<
int>{
4,
5,
6});
// Перемещение из временного списка
В следующих конструкторах последний bool-параметр означает выбор между копированием (=false) и перемещением (=true):
4. Конструктор из контейнеров:
std::list<int> lst = {1, 2, 3};
nx_array<int> arr1(lst, 10); // Копирование из std::list, резерв = 10
nx_array<int> arr2(lst, 10, true); // Перемещение, резерв = 105. Конструктор из итераторов:
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); // перемещение, резерв = 106. Конструктор копирования и перемещения:
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); // Явное перемещение7. Конструкторы из конкретных контейнеров:
std::array<int, 3> std_arr = {1, 2, 3};
nx_array<int> arr_a(std_arr, 5); // Копирование, резерв = 5std::vector<int> vec = {1, 2, 3};
nx_array<int> arr_v(vec, 10, true); // Перемещение, резерв = 10 8. Конструктор из простого массива:
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 класса nx_array через
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) - присоединение другого массива путем копирования элементов. Поддерживаются массивы типа nx_array , vector, list, deque и QList
void addArray(const Container&& container, int position = END_POS) - присоединение другого массива путем перемещения элементов функцией std::move. Функция аналогичная методу mergeArray(), но требует указания std::move в явном виде при вызове. При вызове для типов данных nx_array или std::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) - метод, аналогичный предыдущему, но для nx_array . Поскольку nx_array хранит данные в std::list, то для него также доступно перемещение элементов через list.splice
void mergeArray(Container& container, int position = END_POS) - присоединение другого массива путем перемещения элементов функцией std::move. Поддерживаются массивы типа vector, deque и QList. Не используется для list и nx_array , поскольку для них существует более эффективная функция spliceArray()
Операторы, используемые в nx_array.
Как и в случае с функциями добавления элементов, операторы различают копирование и перемещение объектов через 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 на nx_array.
Методы, возвращающие итераторы: begin(), end(), rbegin(), rend(), cbegin(), cend(), crbegin(), crend()
UPD
Добавлено публичное поле isDeleteItemsOnDestroy типа bool. Поле используется для массива, хранящего указатели, применительно к которым следует выполнить команды delete при удалении массива (объекта класса nx_array) из памяти. Поле isDeleteItemsOnDestroy немного схоже с свойством OwnObjects класса TList из Delphi и C++Builder. Однако, в отличие от OwnObjects оно управляет исключительно поведением деструктора ~nx_array(), а не каких-либо других методов класса. Если требуется выполнить команды delete применительно к удаляемым элементам динамического массива nx_array, которые являются указателями на объекты классов, то для этого специально реализованы отдельные методы, имеющие постфикс "_with_delete":
clear_with_delete()
iterator erase_with_delete(const_iterator pos)
removeItem_with_delete(size_type index)
removeRange_with_delete(size_type start, size_type finish = END_POS)
replace_with_delete(size_type index, T new_item)
