Динамичен масив

Dynamic Array (Vector)

В тази тема ще разгледаме какво е динамичен масив, как той съхранява данните, какви операции поддържа и с какви сложности се изпълнява всяка от тях. В края на темата сме предоставили пълна имплементация като шаблонен клас, както и код, с който да тествате ваша такава.

Автор: Александър Георгиев

Понякога няма да знаем колко елемента най-много може да въведе потребителят, или ще искаме да ползваме възможно най-малко памет за да ги запазим. Това, обаче, е трудно за имплементация, тъй като трябва да се занимаваме с динамично заделяне на памет и да се грижим тя да бъде освободена, след като сме спрели да я ползваме. Тъй като това е от една страна досадно, от друга все пак много често срещано, вместо това ще направим структура данни, която да прави това вместо нас.

Примерна задача

В училището на Ели има 1 ≤ N ≤ 100,000 човека. Някои от тях се познават с други, като Ели знае, че съществуват 1 ≤ M ≤ 1,000,000 такива приятелства. Тя иска да напише програма, която бързо отговаря кои са приятелите на даден човек.

Динамичен масив

Това е масив, който има същите свойства като обикновения масив, но ползва само толкова памет, колкото му е нужна. За удобство, той обикновено пази и точно колко елемента съдържа, тъй като това е друго нещо, което почти винаги имаме и при нормалните масиви. В чуждата литература най-често ще го срещнете като "vector" или "dynamic array".
В случая той чудесно би решил дадения проблем, тъй като просто за всеки човек можем да пазим кои са неговите приятели. Забележете, че тривиалното решение, в което за всеки човек заделяме максималния брой клетки, които може да са му нужни (N), би ни трябвал масив arr[N][N]. Това е ужасно много памет.

Начин на работа

В началото масивът ще съдържа 0 клетки (или фиксиран, малък брой клетки). При добавяне на елементи той заделя памет, когато такава му е нужна (разширяване на масива), и освобождава, когато не е (смаляване на масива). Тъй като на практика много рядко се случва да се използват много елементи от масив, а след това те да бъдат изхвърлени, то няма да имплементираме автоматичното смаляване. Ако такова се налага, ще предоставим метод, с който програмистите сами да го правят.

Нека разгледаме в малко по-голям детайл заделянето на паметта. Първо, нека си представим, че имаме динамичен масив, в който вече сме вкарали N елемента. Тъй като искаме да имаме константен достъп до тях (като е при обикновения масив), то те трябва да са в последователни адреси на паметта. Това можем да гарантираме само ако заделяме паметта за всички елементи наведнъж. Следователно, имаме едно единствено парче памет, с размер, достатъчен за N елемента от типа на масива.

Когато искаме да добавим нов елемент, то той трябва да е на позиция N+1 в блока памет. Ако сме заделили, обаче, блок памет само за N елемента, това няма как да стане (нямаме лесен начин, по който да поискаме паметта точно след наличното ни парче). Затова трябва да заделим ново парче памет за N+1 елемента, да копираме всичките N досегашни елемента в новата памет, да добавим новия елемент накрая, и да освободим старото парче памет.

Доста работа (при това бавна), за да добавим един единствен елемент, нали? За да се справим с това, ще жертваме малко памет. Вместо да заделяме памет за точно N+1 елемента, защо не заделим малко повече? Така при добавяне на следващите няколко елемента, ние ще имаме "резерв", който да ползваме за тях, като си спестяваме цялото ново заделяне, копиране и освобождаване. Разбира се, този резерв може да остане неизползван накрая (все пак не знаем колко елемента ще имаме). Но тази памет е нещо, което сме готови да прежалим, в името на по-добра скорост.

Като цяло, колкото по-голям е този резерв, толкова по-бърза е програмата ни (но и толкова повече памет хаби тя). Ако този резерв е една допълнителна клетка (тоест заделяме новото парче с N+2 вместо N+1 клетки), нашият динамичен масив става два пъти по-бърз! Но ако имаме три допълнителни клетки, то той е цели четири пъти по-бърз. Спокойно той може да е сто пъти или милион пъти по-бърз, но така резервът, ако остане неизползван, ще хаби много памет. Хм, как да решим тогава каква константа да ползваме за "резерв"?

Просто! Няма да ползваме константа! Вместо това ще гледаме колко клетки вече имаме в масива, и на базата на тази информация ще определим колко резервни да оставим. Това, донякъде, трябва да е интуитивно. Ако имаме масив с десет клетки и добавяме нова, то едва ли бихме ползвали резерв от милион, нали? Но ако имаме масив със сто милиона клетки, то резерв от един милион би бил обоснован.

!	Това решение е много известно, тъй като е доказано, че амортизираната сложност за добавяне на нов елемент е едва `O(1)` - точно толкова, колкото би била и в нормален масив!

Като решение, всеки път, когато не ни достига място, ще заделяме парче памет, което е два пъти по-голямо от досега заделеното. Това работи добре едновременно когато имаме малки масиви (ако имаме 10 клетки, още 10 резервни не са нито твърде много нито твърде малко), както и когато имаме големи масиви (ако имаме 1 милион клетки, още 1 милион резервни не е твърде много).

Имплементация

А сега да се захващаме за работа и да имплементираме това чудо на техн... на структурите данни!

Данни

Ще ни трябват три неща - указател към парчето данни, големина на парчето данни, и брой елементи, които вече са в масива. Допълнително, ще работим с абстрактен тип (дефиниран с typedef), който можем лесно да променяме в зависимост какво ни трябва (int, double, т.н.).

typedef
 int
 DataType;

struct Vector {
    DataType*
 data;
    int
 size,
 capacity;
};

Инициализация

В началото броят елементи и размерът на заделената памет (капацитетът) са нула, а указателят към данните не сочи никъде.

void
 init(Vector& v) {
    v.data =
 NULL
;
    v.size =
 v.capacity =
 0
;
}

size()

Връща колко елемента има във вектора. Всъщност не се нуждаем от функция за това (поне при тази имплементация), можем директно да ползваме v.size в кода си.

int
 size(Vector& v) {
    return
 v.size;
}

empty()

Показва дали векторът е празен. Отново, можем да минем и без тази функция.

bool
 empty(Vector& v) {
    return
 !
v.size;
}

clear()

"Изчиства" всички елементи от вектора. В случая, изтриваме заделената памет. Не бива да забравяме и да нулираме размера на вектора и капацитета му.

void
 clear(Vector& v) {
    delete
[] v.data;
    v.data =
 NULL
;
    v.size =
 v.capacity =
 0
;
}

reserve()

Заделя памет за определен брой елементи. Тази функция ни се налага да ползваме, когато искаме да вкараме нов елемент, но досега заделената памет се е запълнила. Друг случай е, когато знаем колко елементи ще вкараме във вектора (много на брой) и не искаме той многократно да променя размера си, заделя памет, и копира елементите.

void
 reserve(Vector&
 v,
 int capacity) {
    capacity =
 (capacity <
=
 0
 ?
 1
 :
 capacity);
    if
 (capacity <
= v.capacity)
        return
;

    DataType*
 data =
 new
 DataType[capacity];
    v.capacity =
 capacity;
    for
 (int
 i =
 0
;
 i <
 v.size;
 i+
+)
        data[i] =
 v.data[i];
    delete
[] v.data;
    v.data =
 data;
}

resize()

Променя размера на вектора. Това може да е както чрез премахване на някои от последните му елементи (правейки го по-малък), така чрез добавяне на нови елементи накрая (правейки го по-голям). Във втория случай бихме могли да зададем и каква стойност да се ползва за новите елементи. В "демо" версията няма да правим това - за детайли погледнете пълната имплементация в края на темата (файла Vector.h).

void
 resize(Vector&
 v,
 int size) {
    if
 (v.capacity < size)
        reserve(v,
 size);
    v.size =
 size;
}

erase()

Изтрива определен брой (един или повече) последователни елемента от вектора. Интервалът се задава чрез първия и един след последния индекс (или чрез само един индекс - на елемента, който искаме да изтрием, ако той е само един).

void
 erase(Vector&
 v,
 int
 first,
 int
 last =
 -
1) {
    first =
 (first <
 0
 ?
 0
 :
 first);
    last =
 (last <
 0
 ?
 first +
 1
 :
 last);
    if
 (first >
=
 v.size |
|
 last <
= first)
        return
;

    for
 (int
 i =
 last;
 i <
 v.size;
 i+
+)
        v.data[first +
 i -
 last] =
 v.data[i];
    v.size -
=
 last -
 first;
}

push_back()

Вкарва нов елемент в края на вектора. Забележете, че ако заделената памет вече е запълнена, преди да вкараме елемента, трябва да разширим вектора.

void
 push_back(Vector&
 v,
 const
 DataType& value) {
    if
 (v.size >
= v.capacity)
        reserve(v,
 v.capacity *
 2
);
    v.data[v.size] =
 value;
    v.size+
+
;
}

push_front()

Вкарва нов елемент в началото на вектора. За целта първо го разширяваме (ако трябва), а после преместваме всичките му досегашни елементи с един надясно (за да освободим място за новия в началото), тоест тази операция е "скъпа" откъм време.

void
 push_front(Vector&
 v,
 const
 DataType& value) {
    if
 (v.size >
= v.capacity)
        reserve(v,
 v.capacity *
 2
);
    for
 (int
 i =
 v.size;
 i >
 0
;
 i-
-)
        v.data[i] =
 v.data[i -
 1
];
    v.data[0
] =
 value;
    v.size+
+
;
}

pop_back()

Премахва последния елемент на вектора (ако има такъв).

void
 pop_back(Vector& v) {
    erase(v,
 v.size -
 1
,
 v.size);
}

pop_front()

Премахва първия елемент на вектора (ако има такъв). Забележете, че отново трябва да преместим всички останали елементи след това (тоест и тази операция е "скъпа").

void
 pop_front(Vector& v) {
    erase(v,
 0
,
 1
);
}

front()

Връща елемента в началото на вектора. Ако такъв няма, спира програмата (невалидна операция).

DataType&
 front(Vector& v) {
    assert(v.size >
 0
);
    return
 v.data[0
];
}

back()

Връща елемента в края на вектора. Ако такъв няма, спира програмата (невалидна операция).

DataType&
 back(Vector& v) {
    assert(v.size >
 0
);
    return
 v.data[v.size -
 1
];
}

at()

Връща елемента на произволна позиция. Ако позицията е извън масива (по-малка от нула или по-голяма или равна на размера на вектора) спира програмата (невалидна операция). Можем и да не имплементираме тази функция (ползвайки директно v.data[index]), но така не бихме си гарантирали, че индексът е валиден.

DataType&
 at(Vector&
 v,
 int index) {
    assert(index >
=
 0
 &
&
 index <
 v.size);
    return
 v.data[index];
}

Цялостна имплементация

Цялостна имплементация и тестове: Vector.h | VectorTester.cpp

STL vector

В стандартната библиотека на C++ има чудесна имплементация, която ще ползваме вместо тази, която написахме току-що. Тя е лесно достъпна, по-бърза и много добре тествана, което я прави естествен избор. Намира се в хедъра , като класът е отново темплейтен и се казва vector. За да имате достъп до него, трябва да ползвате using namespace std;. Допълнително, тъй като класът е темплейтен, трябва да го "създадете" както показахме в темата за класове и темплейти.

vector
 <
int
>
 v1;
vector
 <
double
>
 v2;
vector
 <
DataType>
 v3;

Също така, тъй като функциите (вече наричани методи) са част от самия клас, тоест не трябва да подавате вектора като аргумент, ами трябва да ги изпълнявате на самия обект. Например:

vector
 <
int
>
 v;
v.resize(3
,
 42
);
v.push_back(1337
);
cout <
<
 v[2
] <
<
 endl;
cout <
<
 v.at(3
) <
<
 endl;
v.pop_back();

STL-ската имплементация предоставя и няколко допълнителни функционалности, които пропуснахме в нашата имплементация, като например достъп до началото и края на данните (за да могат да бъдат сортирани), вмъкване на елемент на произволна позиция във вектора, и други. Повече за наличните методи ще говорим в темата за STL.

Допълнителни материали

За да предложите корекция, селектирайте думата или текста, който искате да бъде променен,
натиснете Enter и изпратете Вашето предложение.

Страницата е посетена 15058 пъти.

Динамичен масив

Dynamic Array (Vector)

Примерна задача

Динамичен масив

Начин на работа

Имплементация

Данни

Инициализация

size()

empty()

clear()

reserve()

resize()

erase()

push_back()

push_front()

pop_back()

pop_front()

front()

back()

at()

Цялостна имплементация

STL vector

Допълнителни материали

Предложете корекция