Начало Решаване на проблеми
Изтегляне 4.54 Mb.
|
| Глава 4: Свободна памет и презаредими имена
Тази глава разглежда две фундаментални коннцепции: свободната памет за програмата и презареждането на имената на функциите. Свободната за програмата памет позволява да се отделя памет по време на изпълнение. Реализацията на класа IntArray в глава 1 ни предложи един кратък първи поглед върху този проблем. В тази глава ние ще го разгледаме подробно. Презареждането на имената на функциите позволява на няколко екземпляра на дадена функция, която предлга една обща операция, отнасяща се за аргументи от различен тип, да имат едно и също име. Ако вече сте написали поне един аритметичен израз на някой пограмен език, то вие сте използували предварително дефинирани презаредими функции. В тази глава ние ще видим как да дефинираме наши собствени такива функции. 4.1. Разпределение на свободната памет Всяка програма разполага с известно количество неразпределена свободна памет, която може да използува по време на изпълнението си. Тази налична памет се нарича свободна памет на програмата и чрез използуването й класът IntArray може да отложи разполагането на своите представители масиви в паметта за периода на изпълнението. Нека погледнем как беше направено това:
{ size = sz; ia = new int[ size ]; for ( int i = 0; i < sz; ++i ) ia[ i ] = 0; }
указател към цяло число, ще адресира разположението на масива в свободната памет. Един от аспектите на използуването на свободната памет е, че тя не е именувана. Обектите, разположени в тази памет, се обработват индиректно чрез указатели. Втори аспект на използуването на свободната памет, е, че тя не е инициализирана и следователно винаги трябва да й бъде давана стойност преди употреба. Поради това е написан и цикъла for, чрез който на всеки елемент на ia се дава стойност 0. size, разбира се, съдържа размера на масива. Свободната памет се разпределя чрез прилагане на оператора new към даден типов спецификатор, включително и към име на клас. Може да бъде отделена памет както за единичен обект, така и за масив от обекти. Например, ЇЇЇЇЇЇЇЇЇЇЇЇ ЇЇЇЇЇЇЇЇЇЇЇЇ 136.
указател към този обект и чрез него се инициализира pi. IntArray *pia = new IntArray( 1024 ); отделя памет за обекта клас IntArray. Скобите, които са записани след името на класа, ако ги има, се явяват като аргументи на конструктора на класа. В този случай, pia се инициализира като указател към обект - клас IntArray с 1024 елмента. Ако скобите липсват, както в израза
изисква аргументи или да не дефинира конструктори изобщо. Нека даден масив е разположен в свободната памет посредством типов спецификатор със затворена в скоби размерност. Размерността може да бъде зададена чрез произволен сложен израз. Операторът new връща указател към първият елемент на масива. Например,
char *copyStr ( const char *s ) { char *ps = new char[ strlen(s) + 1 ]; strcpy( ps, s ); retunr ps; }
отделяна памет. Например, IntArray *pia = new IntArray[ someSize ]; разполага в свободната памет масив, който е обект на класа IntArray с някякъв размер. Отделянето на памет по време на изпълнение се нарича денамично разпределяне на паметта. Казваме, че масивът, адресиран чрез ia, е разположен динамично. Отделянето на памет за самия указател ia, обаче, се извършва по време на компилация - това е причината, поради която ia може да бъде именуван обект. Отделянето на памет по време на компилация се нарича статично разпределяне на паметта. Казваме, че указателят ia е разположен статично. Времето на съществуване на един обект, т.е. този период от време, когато се изпълненява програмата и в който паметта е отделена за обекта, се нарича период на активност на обекта. За променливите, дефинирани с файлов обхват, се казва, че притежават статичен период на активност. За тях се отделя памет преди започване на изпълнението на програмата и тя остава свързана с променливата докато програмата приключи работата си. За променливите, дефинирани с локален обхват, се казва, че притежават локален период на активност. За тях се отделя памет при всяко навлизане в локалния им обхват; на излизане от него паметта се освобождава. Всяка локална променлива static има статичен период на активност. ЇЇЇЇЇЇЇЇЇЇЇЇ
ЇЇЇЇЇЇЇЇЇЇЇЇ 137.
че притежават динамичен период на активност. Паметта, отделена чрез използуването на оператора new остава свързана с обекта докато не бъде освободена явно от програмиста. Явното освобождаване се осъществява чрез прилагането на оператора delete към указателя, който адресира димамичния обект. Нека разгледаме един пример. IntArray::grow() разширява масива, адресиран чрез ia, с половината от размера му. Първо, трябва да бъде отделена памет за един нов по-голям масив. След това трябва да се копират стойностите на стария масив, а допълнителните елементи трябва да се инициализарат със стойнност 0. Накрая, паметта, заета от старият масив, трябва да се осовободи явно чрез прилагане на оператора delete. void IntArray::grow() { int *oldia = ia; int oldSize = size; size += size/2 + 1; ia = new int[ size ]; // copy elements of old array into new for ( int i = 0; i < oldSize; ++i ) ia[ i ] = oldia[ i ];
ia[ i ] = 0; delete oldia; }
нея, се освобождава автоматично, когато изпълнението на функцията приключи. Това не се отнася, обаче, за адресирания от oldia масив. Неговият период на активност е от динамичен тип и продължава да съществува и извън границите на локалния обхват. Ако паметта, отделена за масива, адресиран чрез oldia, не бъде освободена явно, като се използува оператора delete, тя остава присъединена към програмата.
Когато изтриваме масив, който е класов обект, на оператора delete трябва да е известен размера му. Това е необходимо за да бъде извикан подходящия класов деструктор. Например, даден е следния масив:
ЇЇЇЇЇЇЇЇЇЇЇЇ ЇЇЇЇЇЇЇЇЇЇЇЇ 138.
паметта, която е била отделена чрез оператора new. Прилагането на оператора delete към памет, която не е отделена от свободната памет вероятно ще се прояви в недефинираното поведение на програмата по време на изпълнение. Прилагането на оператора delete върху указател със стойност 0, обаче, не предизвиква никакви опасни последици - т.е. към указател, който не адресира обект. Следват няколко примера за безопасно и небезопастно прилагане на оператора delete:
{ int i;
char *str = "dwarves"; int *pi = &i; intArray *pia = 0; doduble *pd = new double; delete str; // dangerous delete pi; // dangerous delete pia; // safe delete pd; // safe }
времето на изпълние на програмата тя може да бъде изчерпана. (Разбира се, ако обектите, които не са необходими повече, не бъдат изтрити, ще се увеличи скоростта на изчерпване на свободната памет). По подразбиране, new връща 0, когато наличната свободна памет не е достатъчна за да удоовлетвори заявката. Програмистът не може спокойно да игнорира възможността, когато new връща 0. Нашата функция grow(), например, няма да работи ако new не е в състояние да отдели исканата памет. Да припомним, че нашият текст изглеждаше така:
for ( int i = 0; i < oldSize; ++i ) ia[ i ] = oldia[ i ];
когато ia има стойност 0. Най-простият метод за да бъде направено това, е да се добави оператор за проверка на стойността на ia, който да следва обръщението към new. Например,
if ( !ia ) { error("IntArray::grow(): free store exhausted"); }
и предназначена да съобщава за грешки като осигурява елегантен изход.
ЇЇЇЇЇЇЇЇЇЇЇЇ ЇЇЇЇЇЇЇЇЇЇЇЇ 139.
на grow(): #include #include "IntArray.h" IntArray ia[ 10 ]; main()
{ cout << "size: " << ia.getSize() << "\n"; for ( int i = 0; i < ia.getSize(); ++i ) ia[i] = i*2; // initialize ia.grow(); cout << "new size: " << ia.getSize() << "\n"; for ( i = 0; i < ia.getSize(); ++i ) cout << ia[i] << " "; }
следния резултат: size: 10 new size: 16 0 2 4 6 7 10 12 14 16 18 0 0 0 0 0 0
изчерпването на свободната памет. Тя е реализирана като рекурсивна функция, чието условие за спиране е връщането на стойност 0 от new: #include viod exhaustFreeStore( unsigned long chunk ) { static int gepth = 1; static int report = 0; ++depth; // keep track of invocations double *ptr = new double[ chunk ]; if ( ptr ) exhaustFreeStore( chunk ); // free store exhausted delete ptr; if ( !report++) cout << "Free Store Exhausted:" << "\tchunk: " << chunk << "\depth: " << depth << "\n"; }
които имат различен размер дава следния резултат: ЇЇЇЇЇЇЇЇЇЇЇЇ ЇЇЇЇЇЇЇЇЇЇЇЇ 140.
Free Store Exhaused: ckunk: 100000 depth: 22 Free Store Exhaused: ckunk: 10000 depth: 209 Free Store Exhaused: ckunk: 1000 depth: 2072 Една от С++ библиотеките предлага известна помощ, като поддържа информация за свободната памет. Манипулаторът, обработващ изключенията _new_handler се разглежда в Раздел 4.4 (стр. 170) по-нататък в тази глава. Програмистът също може да постави обект, разположен в свободната памет на определен адрес. Формата на такова извикване на оператора new има вида:
оператора new по този начин трябва включите заглавния файл new.h. По този начин програмистът може да преразпределя паметта, която в един по-нататъшен момент ще съдържа обекти, определени чрез тази форма на оператора new. Например,
#include const Chunk = 16; class Foo { public: int val; Foo() { val = 0; }}; // preallocate memory, but no Foo objects char *buf = new char[ sizeof( Foo ) * Chunk ]; main() { // construct Chunk Foo objects for buf Foo *pb = new (buf) Foo[ Chunk ]; // check that objects were plased in buf if ( (char*)pb == buf ) cout << "Operator new worked!: pb: "
}
получим следните резултати:
програма. То е свързано с изпращането на buf към void*. Това е необходимо, понеже когато към оператора за изход се изпраща операнд char* се отпечатва "null terminated string", т.е. низа, който е адресиран. Чрез изпращането на buf към void* операторът за изход знае, че трябва да отпечата адресната стойност на buf. Това се дължи на факта, че операторът за изход се презарежда така, че да използува два различни ЇЇЇЇЇЇЇЇЇЇЇЇ
ЇЇЇЇЇЇЇЇЇЇЇЇ 141.
функции се разглеждат в един от подразделите на тази глава. Въпреки, че този тип на оператора new се използува главно с типовете class, той може да се използува и за вградените типове данни. Например,
int *pi = new int; main() { int *pi2 = new (pi) int; } 4.2. Един пример за свързан списък В този раздел се реализира един елементарен клас - списък от цели числа за да бъде илюстрирана както работата с указатели, така и използуването на операторите new и delete. Като минимум IntList трябва да поддържа две стойности - цялата стойност на елемента на списъка и адреса на следващия елемент на списъка. Това може да се представи по следния начин: int val; ListItem *next; Един списък представлява последователност от елементи. Всеки елемент съдържа стойност и указател, може и null, към следващия елемент на списъка. Списъкът може да бъде и празен; т.е. да бъде списък без елементи: IntList i1; // the empty list Списъкът може да нараства чрез добавяне на елементи. Тези елементи могат да бъдат вмъквани в началото на списъка: i1.insert( someValue ); или добавяни към края му: i1.append( someValue ); Списъкът може да бъде намаляван чрез отстраняване на елементи (предполага се, че той не е празен): i1.remove( someValue ); Потребителят трябва да бъде в състояние да показва елементите на на списъка: i1.display(); Ето една първа програма, която бихме желали да напишем като използуваме класа IntList. ЇЇЇЇЇЇЇЇЇЇЇЇ
ЇЇЇЇЇЇЇЇЇЇЇЇ 142.
main()
{ IntList i1; i1.display();
i1.insert( i ); i1.display();
for ( i = 0; i i12.append( i );
i12.display(); }
получава следния резултат:
( 11 10 9 8 7 6 5 4 3 2 1 0 ) ( 0 1 2 3 4 5 6 7 8 9 10 11 )
дефинирането на класа IntList. Това е и първото място, където можем да сгрешим. Неправилен за проекта избор ще бъде да
декларираме както val, така и next като членове на IntList. Например,
{
public: // ...
private: int val;
IntLIst *next; };
произтичат от объркването между обекта списък и елемента на списъка. Например, при този проект не се допуска наличието на празен списък. Не съществува начин за разграничаване на списъка, съдържащ един елемент от празния списък. Въпросителните знаци, в сигнатурата на конструктора на IntList са предназначени да подчертаят този проблем. Няма подразбираща се стойност за инициализиране на val, чрез която да се отбелязва, че списъкът е празен. Другите проблеми възникват от това, че не е определен смисъла на insert() и remove() ЇЇЇЇЇЇЇЇЇЇЇЇ ЇЇЇЇЇЇЇЇЇЇЇЇ 143.
на списъка. В пректа на IntList трябва да бъде направено разграничаване между елементите на списъка и самия обект списък като такъв. Един от начините да бъде направено това е да бъде дефиниран както клас IntList, така и клас IntItem. Ето дефиницията на IntItem:
class intItem { friend class IntList; private: IntItem( int v=0 ) { vla = v; next = 0 ) IntItem *next; int val;
}; IntItem се нарича клас private (личен). Само на IntList е разрешено да създава и обработва IntItem обектите. Това е смисъла на декларацията friend. Раздел 5.5 (стр. 200) разглежда подробно тази декларация. Раздел 5.1 (стр. 181) обяснява разликите между декларациите private и public. IntList е реализиран по следния начин: class IntItem; class IntList { public:
IntList(int val) { list = new IntItem( val ); } IntList() { list = 0; } // ... private:
IntItem *list; };
конструктора? Защо, например, да не дефинираме просто
IntList може да бъде int len; // length of list който да съдържа броя на елементите на списъка. Разгледайте аргументите за и против тази декларация. Следващата стъпка се състои в реализирането на член-функции, които поддържат потребителските обработки на IntList обектите. insert() поставя даден нов IntItem в началото на списъка. Това се реализара така: ЇЇЇЇЇЇЇЇЇЇЇЇ
ЇЇЇЇЇЇЇЇЇЇЇЇ 144.
{ // add to the front of the list IntItem *pt = new IntItem( val ); pt->next = list; list = pt; return val; }
IntItem в клая на списъка. Една помощна функция, atEnd(), връща указател към последния елемент на списъка:
{ // return pointer to last item on list IntItem *prv, *pt; for ( prv=pt=list; pt; prv=pt; pt=pt->next ) ; // null statement return prv; }
списък. Реализацията изглежда по следния начин: IntList::append( int val ) { // add to the back of the list IntItem *pt = new IntItem( val ); if ( list == 0 ) list = pt; else
(atEnd())->next = pt; return val; }
поддържането на следния IntList член. IntItem *endList; Как това може да се отрази на реализацията на append()? Потребителите на списъчния клас трябва да бъдат в състояние да показват елементите на списъка. Това е направено посредством член-функцията display(). Елементите на списъка се показват в скоби, по 16 на ред. Това изглежда така: ЇЇЇЇЇЇЇЇЇЇЇЇ ЇЇЇЇЇЇЇЇЇЇЇЇ 145.
const int lineLength = 16; IntList::display() { // display val member of list if ( list == 0 ) { cout << "( empty )\n"; return 0; }
int cnt = 0; // number of items displayed IntItem *pt = list; while ( pt ) { if ( ++cnt % lineLength == 1 && cnt != 1 ) cout << "\n "; cout << pt->val << " "; pt = pt->next; }
return cnt; }
if ( ++cnt % lineLength == 1 && cnt != 1 ) служи да се избягне появата на дясна затваряща скоба на всеки ред от самосебе си. Пълната спецификация на заглавния файл IntList.h до този момент изглежда така:
{ friend class IntList; private: IntItem(int v=0) { val = v; next = 0; } IntItem *next; int val;
}; ЇЇЇЇЇЇЇЇЇЇЇЇ ЇЇЇЇЇЇЇЇЇЇЇЇ 146.
{ public: IntList(int val) { list = new IntItem( val );} IntList() { list = 0; ) display(); insert( int = 0 ); append( int = 0 ); private:
IntItem *atEnd(); IntItem *list; };
елементи от списъка или да изтрива целея списък. От проектанта на класа зависи дали опита за отстраняване на елемент от празен списък да се определя като грешка. Но и в двата случая на потребителя на класа е необходима функцията-предикат isEmpty(): class IntItem { /* ... */ ; class IntList { public: isEmpty() { return list == 0; } // ...
private: IntItem *list; );
Забележете, че функцията връща броя на отстранените елементи. IntList::remove() { // delete the entire list IntItem *tmp, *pt = list; int cnt = 0; while ( pt ) { tmp = pt; pt = pt->next; ++cnt;
delete tmp; }
return cnt; }
елементи, които съдържат определена стойност. Един особен случай при извършването на това, е случаят, когато трябва да бъде остстранен първия елемент на списъка. Тогава тръбва да бъде изменен и самият член на list. ЇЇЇЇЇЇЇЇЇЇЇЇ
ЇЇЇЇЇЇЇЇЇЇЇЇ 147.
{ // delete all enries with value val IntItem *prv, *tmp, *pt = list; int cnt = 0; // while the first item on list == val while ( pt & pt->val == val ) { tmp = pt->next; // save pointer to next delete pt; ++cnt;
pt = tmp; };
return cnt; // list empty prv = pt; pt = pt->next; while ( pt ) { // iterate through list if ( pt->val == val ) { tmp = prv->next = pt->next; delete pt; ++cnt;
pt = tmp; } else { prv = pt; pt = pt->next; } }; // end, while (pt) return cnt; }
броя на елементите на списъка. За празния списък, разбира се, трябва да бъде връщана стойност 0. IntList::length() { int cnt = 0; IntItem *pt = list; for ( ; pt; pt = pt->next, ++cnt ) ; // null statement return cnt; }
четири член-функции. (разширената спецификацията на заглавния файл IntList.h, беше оставена като упаражнение за читателя). ЇЇЇЇЇЇЇЇЇЇЇЇ ЇЇЇЇЇЇЇЇЇЇЇЇ 148.
Каталог: files -> tu files tu files -> Увод в компютърната графика tu files -> Xii. Защита и безопасност на ос tu files -> Електрически апарати tu files -> Средства за описание на синтаксиса tu files -> Stratofortress tu files -> Писане на скриптове за bash шел : версия 2 tu files -> 6Технологии на компютърната графика 1Модели на изображението tu files -> Z=f(x), където x- входни данни; z tu files -> Body name библиотека global Matrix imports (достъп по име) … var m[N, N] := … end decl., proc … resource f final code imports node, Matrix end name var x: node node; if x … Matrix m[3,4] :=: … end Изтегляне 4.54 Mb. Сподели с приятели:
|