Класове и темплейти

Classes and Templates

Имплементация на структури данни.
Какво са класове? Пример за клас, имплементиращ структура данни.
Какво са темплейти? Пример за темплейтен клас, имплементиращ структура данни.

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

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

Проблеми с функционалния дизайн

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

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

Второ, какво става ако искаме да пазим множество от double числа вместо int? Трябва да сменим типа на глобалните масиви, аргументите на функциите, и част от локалните променливи. Това не е толкова много занимавка (няколко минути), но представете се да се налага да го правите всеки път, когато искате да ползвате тази структура данни. Ами ако структурата данни беше по-голяма?
По-нататък ще видим такива с по няколко стотин реда код имплементация. В тях това би било абсурдно да правим всеки път, когато искаме да я ползваме с тип, различен от int.
Друг вариант е да имаме по една версия за всеки тип (int, double, long long, char, ...), но това ще изисква много код, който до голяма степен се повтаря. И няма да може да работи ако искаме да ползваме структурата за нестандартен тип (примерно структура).

Трето, какво става ако искаме два сета - единият с int-ове а другият с double-и? Съвсем мазало.

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

Класове

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

Какво е клас?

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

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

Интересно е, че не трябва да правите почти нищо, за да създадете клас. Допълнителният код, който е нужен за да превърнете функции и данни в клас, е следният:

class ClassName {
    public
:
    // Данни и функции
};

Най-горният ред е нещото, което указва, че данните между къдравите скоби ще са част от клас със зададеното име. Вторият ред (public:) за сега не ви интересува. Той указва, че данните и методите след него ще могат да бъдат достъпвани от "извън" класа. Но тъй като никой друг, освен ние самите, няма да ползва въпросния клас, то може винаги всичко да бъде public.

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

class Set

Вече сме готови да превърнем структурата данни, която написахме в миналата тема, в клас!

class Set {
    public
:

    const
 int
 MAX_SIZE =
 1048576
;

    int
 setSize;
    int
 setValues[MAX_SIZE];

    int getSize() {
        return
 setSize;
    }

    int
 getKth(int k) {
        if
 (k >
=
 0
 &
&
 k < setSize)
            return
 setValues[k];
        return
 -
1
;
    }

    int
 find(int val) {
        int
 left =
 0
,
 right =
 setSize -
 1
;
        while
 (left <
= right) {
            int
 mid =
 (left +
 right) /
 2
;
            if
 (setValues[mid] =
= val)
                return
 mid;
            if
 (setValues[mid] < val)
                left =
 mid +
 1
;
            else
                right =
 mid -
 1
;
        }
        return
 -
1
;
    }

    void
 insert(int val) {
        int
 idx =
 find(val);
        if
 (idx !
=
 -
1)
            return
;
        setValues[setSize+
+
] =
 val;
        for
 (int
 i =
 setSize -
 1
;
 i >
 0
;
 i-
-) {
            if
 (setValues[i -
 1
] < setValues[i])
                break
;
            swap(setValues[i -
 1
],
 setValues[i]);
        }
    }

    void
 erase(int val) {
        int
 idx =
 find(val);
        if
 (idx =
=
 -
1)
            return
;
        for
 (int
 i =
 idx;
 i <
 setSize -
 1
;
 i+
+)
            setValues[i] =
 setValues[i +
 1
];
        setSize-
-
;
    }
};

Отново забележете, че нямаме почти никакви промени. Само че вече няма проблем да имаме повече от една променлива (наричана обект) от тип "множество".

Употреба

Нека имаме следната задача:

На стандартния вход са ви дадени N цели числа. След прочитането на всяко от тях, изпечатайте колко различни четни и колко различни нечетни числа сте прочели до сега.

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

void printEvenAndOdd() {
    Set even,
 odd;
    fscanf(stdin
,
 "%d"
,
 &
n);
    for
 (int
 i =
 0
;
 i <
 n;
 i+
+) {
        int
 curNum;
        fscanf(stdin
,
 "%d"
,
 &
curNum);
        if
 (curNum %
 2
 =
=
 0)
            even.insert(curNum);
        else
            odd.insert(curNum);
        fprintf(stdout
,
 "Number of distinct even: %d, and distinct odd: %d\n"
,
                even.size(),
 odd.size());
    }
}

Лесно, нали? Като не се наложи изобщо да променяме каквото и да е, за да имаме повече от една инстанция на структурата данни.

this

Вътре във всеки обект можем да ползваме указателя this, който има стойност адреса на обекта. Така, например, можем да достъпваме данните чрез, в нашия случай, this->setSize и this->setValues[]. По нататък ще видите за какво се ползва той.

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

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

Set() {
    setSize =
 0
;
}

Освен този конструктор, можете да правите и специфични други такива, на които да подавате информация. Както можете да имате int a(42);, което създава променлива a от тип int със стойност 42, така може да направите конструктор, който да инициализира множеството ви с дадени числа, например Set s({7, 13, 42});.

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

Копиране

Копирането на клас се извършва автоматично, като по подразбиране всички данни се копират дословно. Това е удобно, но в същото време е и нож с две остриета. Както вече споменахме, масивите представляват указател към данни. А при копиране указателите ще бъдат копирани - тоест масивите от втория обект ще сочат към данните от първия - почти винаги не нещото, което искаме. Затова трябва да се постараем допълнително това да се извършва правилно, когато в данните имаме масиви.

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

Set(const
 Set& origin) {
    setSize =
 origin.setSize;
    for
 (int
 i =
 0
;
 i <
 setSize;
 i+
+)
        setValues[i] =
 origin.setValues[i];
}

Другото нещо, което трябва да направим, е operator =, тоест какво да се извърши, когато имаме classObject1 = classObject2;. При него трябва да обърнем малко повече внимание какво се случва ако копираме обект в самия себе си, тоест classObject1 = classObject1;.

Set&
 operator
=
 (const
 Set& origin) {
    if
 (this
 !
=
 &
origin) { // Проверка дали не се присвояваме на себе си
        setSize =
 origin.setSize;
        for
 (int
 i =
 0
;
 i <
 setSize;
 i+
+)
            setValues[i] =
 origin.setValues[i];
    }
    return
 *
this
;
}

Разрушаване

В повечето случаи няма да се налага да правим нищо. Ако, обаче, имаме динамично заделяна памет в обекта (тоест нещо, създадено с malloc() или new), е хубаво (но не задължително!) да я изчистим, преди да разрушим обекта. Ако не го направим би се получило изтичане на памет (memory leak). Този метод се нарича деструктор (destructor). Неговият синтаксис е следният:

~Set() {
    // В този случай не правим нищо, но ако имахме динамично заделена
    // памет например, тук би било удачно да я освободим.
}

Готови сме!

Ако искате сами да пишете класове, трябва да запомните тези четири специфични метода (наричани "голямата четворка"): конструктор, деструктор, копи конструктор и оператор =. Много често ще можете да минете без тях, освен в случаите, когато работите с масиви или динамична памет. Разбира се, понякога бихте желали да имате конструктор, въпреки че нямате масиви или динамична памет сред данните на класа. Пълна имплементация сме дали малко по-долу (включвайки и темплейти), като в следващите няколко теми ще напишем още няколко, които имплементират динамичен масив, лист, опашка, и стек.

Темплейти

Класовете, макар и нещо много мощно, все още не решават втория проблем - какво да правим, когато искаме структурата данни да съдържа друг тип данни? Решението е да ползваме темплейти (templates), които на български можете да срещнете и като "шаблони". От наша гледна точка, те не правят нищо друго, освен да дефинират някакъв псевдоним за типа данни, който ще ползваме, а после да го заменят със съответния тип. Например най-често ще видите да се дефинира име "T", което не е име на никой стандартен тип, но в последствие може да се замести с int, double, или каквото и да е друго (дори друг клас!).

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

За да дефинираме даден клас като темплейтен, то трябва да добавим следния ред преди него:

template
 <
class
 T>

Въпреки малко странния синтаксис, това е единственото нещо, което трябва да запомним. Разбира се, вътре в класа трябва да ползваме "T" на мястото на "int" на всички места, където данните са от неизвестен тип.

template
 <
class
 T>
 class Set {
    public
:

    const
 int
 MAX_SIZE =
 1048576
;

    int
 setSize;
    T setValues[MAX_SIZE];

    int getSize() {
        return
 setSize;
    }

    T getKth(int k) {
        if
 (k >
=
 0
 &
&
 k < setSize)
            return
 setValues[k];
        return
 -
1
;
 // Това в някои случаи може да не работи
    }

    int find(T val) {
        int
 left =
 0
,
 right =
 setSize -
 1
;
        while
 (left <
= right) {
            int
 mid =
 (left +
 right) /
 2
;
            if
 (setValues[mid] =
= val)
                return
 mid;
            if
 (setValues[mid] < val)
                left =
 mid +
 1
;
            else
                right =
 mid -
 1
;
        }
        return
 -
1
;
    }

    void insert(T val) {
        int
 idx =
 find(val);
        if
 (idx !
=
 -
1)
            return
;
        setValues[setSize+
+
] =
 val;
        for
 (int
 i =
 setSize -
 1
;
 i >
 0
;
 i-
-) {
            if
 (setValues[i -
 1
] < setValues[i])
                break
;
            swap(setValues[i -
 1
],
 setValues[i]);
        }
    }

    void erase(T val) {
        int
 idx =
 find(val);
        if
 (idx =
=
 -
1)
            return
;
        for
 (int
 i =
 idx;
 i <
 setSize -
 1
;
 i+
+)
            setValues[i] =
 setValues[i +
 1
];
        setSize-
-
;
    }
};

Употреба

Създаването на обект от темплейтен тип е малко по-странно. Освен класа, трябва по някакъв начин да зададем и какъв да е типът T. Това става с помощта на триъгълни скоби (всъщност символите за по-малко и по-голямо), съдържащи типа. По следния начин бихме заделили два обекта - един за int и един за double:

Set <
int
>
 setOfInts;
Set <
double
>
 setOfDoubles;

Нещо повече, тъй като T може да бъде на практика произволен тип, защо да не направим множество от множества от int-ове (допълнително трябва да дефинираме operator < и operator == в нашия клас за да работи това):

Set <
 Set<
int
>
 >
 setOfSetsOfInt;

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

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

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

Класове и темплейти

Classes and Templates

Проблеми с функционалния дизайн

Класове

Какво е клас?

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

class Set

Употреба

this

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

Копиране

Разрушаване

Готови сме!

Темплейти

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

Употреба

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

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