C++ Data Structures 1.1 Sequential: Dynamic Array

C++ Data Structures 1.1 Sequential: Dynamic Array

Масиви! най-простата и най-разпространена структура от данни. В тази публикация ще проучим как да изградим масив, който се съхранява динамично в Heap с динамичен размер, обикновено наричан„вектор“в C++ STL или „ArrayList“ в API на Java Oracle. Нашият масив ще може вътрешно да увеличава и намалява размера си, ще съхранява всякакъв тип данни, използвайки шаблони с отменени методи от чист виртуален клас (интерфейс) и накрая ще реализира концепцията за кръгъл масив и други функции на 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, подадени в метода, и актуализира капацитета_ и length_, тогава r_list array_ се присвоява на NULL, за да се избегне увисването на указателя, защото работим с необработени указатели. След като деструкторът на r_list бъде извикан (извън обхвата), той не унищожава масива, към който сочи нашият указател array_.

конструкторът на копиране копира масив_ на аргумента в друго разпределение на паметта и копира всеки елемент в масив_, това копие въвежда концепцията за кръгово масив, защо всяка стойност в масива по ред се присвоява на позицията на “(front_index + i )% капацитет_” на аргумента array_? това е много просто, но може да бъде объркващо. Първият елемент в списъка е front_index и понякога front_index не е 0 (ще обясня това по-късно в тази публикация), това се прави зад кулисите и потребителят няма достъп до тази променлива front_index, за потребител първият елемент е с индекс 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)...

• push( X ): Тази функция член вмъква стойност в началото на array_, това е малко сложно за изпълнение и разбиране. ако front_index е 0, тогава новата стойност на front_index ще бъде капацитетът на масива - 1, в противен случай просто намалете индекса на front_index с 1 и след това елементът на новата позиция на front_index се присвоява към аргумента, предаден в метода.

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

• pop(): Този метод, вместо изтриване, прави недостъпен последния елемент от списъка, намалява „length_“ на „array_list‹S ›”, защото имаме контрол върху достъпните елементи в списъка с get_at или оператора [], стойността, която току-що извадихме никога не е бил изтрит, ние просто намалихме размера на array_list и ако потребител се опита да получи достъп до тази стойност, get_at изхвърля изключението извън границите, ако добави (нови данни) се извика, тази стойност ще бъде заменена с нови данни, много лесно и просто. Сега реших да добавя този случай, когато дължината намалява повече от една пета от текущия капацитет на array_list, свийте капацитета на масива чрез наполовина извикване на частния метод за преоразмеряване (засега не се притеснявайте какво прави частният метод за преоразмеряване).
• pull(): Тук правим същото като pop, но вместо това увеличаваме стойността на front_index с 1 и ако front_index е равно на capacity_ -1, тогава front_index сега е 0, следвайки концепцията за кръгъл масив.

Методът член is_empty връща булево, проверявайки дали length_ е равно на 0, а методът член empty() просто задава length_ на 0 и front_index също до 0, създавайки илюзията на потребителя, че масивът е празен.

Трябва да дефинираме оператор за присвояване на копие, за да следваме 3-те правила на C++ програмиране с класове, в метода винаги трябва първо да проверим операцията за самоприсвояване, като получим адреса на това (текущ обект array_list или лявата страна на обекта на оператора) и адреса на аргумента, ако адресите са еднакви, просто върне текущия обект array_list. Второ, ако копието се побира в нашия масив, копирайте елементите, подреждайки масива и актуализирайкидължина_.

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

ако копието не пасва, изтрийте нашия array_ и създайте нов масив със същия капацитет на копието, след което копирайте елементите, организиращи елементите, така че front_index да е равен на 0.

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

В оператора за присвояване на преместване ние просто прехвърляме собствеността върху array_, length_, capacity_ и front_index, след което присвояваме към NULL r_list.array_ и избягване на проблеми с висящия указател, когато r_list излезе извън обхвата, изтрива r_list.array_, който сочи към NULL, а не към нашия *array_.

//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_);