Структуры данных C++ 1.1 Sequential: динамический массив

Структуры данных C++ 1.1 Sequential: динамический массив

Массивы! самая простая и распространенная структура данных. В этом посте мы собираемся изучить, как построить массив, который динамически хранится в куче с динамическим размером, обычно называемым «вектором» в C++. STL или "ArrayList" в Java Oracle API. Наш массив сможет внутренне увеличивать и уменьшать свой размер, он будет хранить данные любого типа, используя шаблоны с переопределенными методами из чистого виртуального класса (интерфейс), и, наконец, он будет реализовывать концепцию круговой массив и другие функции C++11.

Для начала давайте определим, что такое массив. Массив — это просто список последовательных элементов, хранящихся по порядку, это означает, что мы можем получить доступ к любому элементу в списке с позицией элемента или также называемым индексом. В информатике счет начинается с 0, если мы хотим получить доступ к первому элементу списка, мы просто ссылаемся на индекс 0.

Давайте углубимся в детали, компилятор! Когда вы создаете массив во время компиляции (также называемое ранним связыванием) в C++, вы должны объявить тип и размер данных (также называемый длиной), это связано с к тому факту, что компилятору необходимо заранее знать, сколько последующих слотов памяти должно быть зарезервировано для массива, и каждый слот должен иметь возможность хранить один единственный экземпляр типа данных, например, массив символов и размер 10 , компилятор получает размер символа (2 байта) с помощью оператора sizeof и резервирует необходимый объем памяти, умножая 2 байта на 10 (20 байт).

Тогда как работает индексация? почему индексирование выполняется в O(1)? На самом деле это довольно просто, компилятор считывает заданный индекс, умножает его на размер типа данных, который содержит массив, и, наконец, добавляет результат в ячейку памяти первого элемента массива. Это довольно прямолинейно, массив с индексом 0 — это просто 0 + адрес памяти массива, поэтому первый элемент всегда имеет индекс 0.

Теперь возьмемся за код. Класс array_list‹S› будет иметь параметр шаблона (по умолчанию int). Я реализую все виртуальные функции из последовательности интерфейса (append, pop, pull, push, insert_at, is_empty, empty, get_at, size и оператор []). Вы можете найти код на моем GitHub учетная запись репозитория (HEADER_FILE SOURCE_FILE).

Позже я объясню, что каждая реализация виртуальной функции делает с классом array_list‹S›. Это определение класса будет следовать Правилу трех программирования на C++ (деструктор, конструктор копирования и оператор присваивания копирования).

О классе, следуя концепции инкапсуляции, чтобы создавать абстракции для пользователя, класс array_list имеет все элементы данных закрытыми.

• S * array_ : Указатель на наш динамический массив S-типов в куче.
• int capacity_: внутренняя емкость массива.
• int front_index : первый элемент списка или начальная точка списка (я объясню это позже) 0 по умолчанию.
• int length_: длина списка или общее количество элементов, хранящихся в данный момент в списке.

Поскольку мы выделяем динамическую память, мы должны освободить память, выделенную в деструкторе, при вызове деструктора array_ удаляется и устанавливается в NULL следующим образом.

//destructor......ARRAY_LIST<TYPE>
~array_list(
{
    delete [] array_;  //free [capacity_] 
    array = nullptr;   //pointer dangling
}

Начнем с конструкторов, наш массив будет иметь размер по умолчанию 10, первый конструктор принимает size_t (целое число без знака или только положительные целые числа от 0 до 4294967296), которое определяет емкость списка, значение по умолчанию будет равно 10. front_index равен 0, и в списке еще нет элементов, поэтому length_ также равен 0. Эти конструкторы являются явными, это означает, что объект создается только в том случае, если мы явно вызываем конструктор. см. исходный код.

1) array_list<int> a(); ---> CREATES AN ARRAY OF TEN INTEGERS
2) array_list<char> b(20); ---> CREATES AN ARRAY OF 20 CHARACTERS

Код здесь:

Кроме того, класс array_list‹S› имеет еще два конструктора, которые принимают одно значение типа данныхS, первый принимает либо значение r, либо l value, он создает динамически выделяемый массив в Heap размером 10 и добавляет значение r с помощью std::move к первому элементу списка, length_ присваивается 1, учитывая тот факт, что в нашем списке уже есть один элемент, front_index равен 0, что указывает на то, что первый элемент списка находится в нулевом индексе массива.

С другой стороны, другой конструктор передает одно значение типа S, чтобы заполнить им массив, и значение size_t, определяющее length_ и capacity_. класса, которые имеют одинаковое значение в этом случае.

array_list<std::string> b("Red");
array_list<char> a('a', 5); ---> ['a', 'a', 'a', 'a', 'a']

Перед нашим конструктором копирования давайте поговорим о концепции кругового массива. Круговой массив — это просто линейный массив, соединяющий конец с началом, как это делается? Пример даст нам лучшее представление о круговом массиве из 10 элементов, это означает, что у нас есть массив из 10 элементов, который при переходе может переходить с индекса 9 на 0, (10 % 10 = 0) это вычисляется с помощью арифметики модуль операции (%), и чтобы получить элемент по заданному индексу, мы должны определить остаток от деления индекса и 10 (размер массива), например:

>>> circular_array[0] = array[(13) % 8] 
<<< array[0] = 'a'

>>> circular_array[10] = array[(10) % 8]
<<< array[2] = 'c'

>>> circular_array[7] = array[(7) % 8]
<<< array[7] = 'h'

См. следующее изображение:

Нам нужно иметь контроль над нашим массивом, давая пользователю простое использование и понимание динамического массива, поэтому, если пользователю нужен первый элемент списка, мы просто возвращаем первое значение, как в следующем примере в общедоступном методе get_at [ ], мы должны управлять доступом к индексации, генерируя исключения, когда пользователь хочет получить доступ к мусорным индексам в массиве:

Давайте посмотрим на несколько примеров get_at, чтобы лучше все понять:

get_at ARRAY_LIST:
       length_ 6
       capacity_ 8
       front_index 2
(front_index + index)% capacity_
1) get_at 0
<<< array_list[0] = array_[(2 + 0) % 8] 
<<< array_[2]
2) get_at 3
<<< array_list[3] = array_[(2 + 3) % 8]
<<< array_[5]
3) array at 2
<<< array_list[2] = array_[(2 + 2) % 8]
<<< array_[4]

Мы можем видеть массив примера выше.

Конструктор копирования и конструктор перемещения: начнем с… 1) Конструктор перемещения: он передает право собственности на наш массив_ из списка значений r, переданного в метод, и обновляет capacity_ и length_, тогда r_list array_ присваивается значение NULL, чтобы избежать зависания указателя, поскольку мы работаем с необработанными указателями. После вызова деструктора r_list (вне области действия) он не уничтожает массив, на который указывает наш указатель array_.

конструктор копирования копирует массив_ аргумента в другое выделение памяти и копирует каждый элемент в массиве_, это копирование вводит концепцию циклического массив, почему каждое значение в массиве по порядку присваивается позиции «(front_index + i )% capacity_» аргумента array_? это очень просто, но может сбивать с толку. Первым элементом в списке является front_index, а иногда front_index не равен 0 (я объясню это позже в этом посте), это делается за кулисами, и у пользователя нет доступа к этой переменной front_index для user первый элемент имеет индекс 0, второй — индекс 1 и так далее…, но внутри класса первый элемент находится в front_index + 0, второй — в front_index + 1... таким образом, array_ копирует каждый элемент, реорганизуя массив обычным образом.

В примере, когда мы копируем первый элемент списка, мы должны найти первый элемент в копии array_, а затем копировать каждый элемент с приращением i в цикле for.

Публичные методы append, pop, push и pull изменяют длину массива, а иногда и емкость, этот класс массива увеличивает и уменьшает его размер внутри, поэтому пользователю не нужно заботиться об этом запутанном процессе каждый раз, когда вставляется новый элемент. или удалены, этот процесс выполняется за O(n), поскольку каждый элемент списка должен быть скопирован в новый массив.

Методы, вставляющие значения в массив, перегружены для двух случаев: когда у вас есть определенное l-значение и когда вы хотите добавить элемент в массив, передав его в аргументе как r-значение. если вы не понимаете семантику перемещения, я рекомендую эту ссылку, которая довольно хорошо объясняет этот случай в конкретном случае.

• append( Y ): Append вставляет значение в конец массива, в методе мы сначала проверяем, является ли length_ больше или равно capacity_ , так что изменение размера массива должно выполняться вызовом приватной функции resize(я объясню этот метод в конце поста), в противном случае мы вставляем новый элемент по индексу length_ из массива_.

array_[(front_index + length_) % capacity_] = Y //(new value)...

array[front_index] = X   //(new value)...

for (auto i {0}; i < copy.length_ ; ++i ) //copy values ordering
     this->array_[i] = copy.array_[(front + i) % copy.capacity_];

delete [] array_;                   // free memory
array = new Type[copy.capacity_];   // then copy elements....

//append increases by the current half of the capacity of the array
>>> append(A)
<<< (static_cast<int>(1.5 * capacity_);
//push increases by the current half of the capacity of the array
>>> push(A)
<<< resize(static_cast<int>(1.5 * capacity_);
//pop decreases by half of the capacity of the array
>>> pop()
<<< resize(static_cast<int>(0.5 * capacity_);
//pull decreases by half of the capacity of the array
>>> pull()
<<< resize(static_cast<int>(0.5 * capacity_);