Programovßnφ je tvrd² chlebφΦek a dokonalΘ zvlßdnutφ vÜech mo₧nostφ i zßludnostφ, kterΘ souΦasnΘ programovacφ prost°edky sk²tajφ, je nutnou podmφnkou ·sp∞chu. Sond do jejich taj∙, kterΘ Chip tak°ka pravideln∞ p°inßÜφ, nenφ, soud∞ dle Φtenß°sk²ch ohlas∙, nikdy dost, a proto pokraΦujeme i dnes û nahlΘdneme do dalÜφ z oÜidn²ch hlubin jazyka C++, do sprßvy pam∞ti.
Podφvßme-li se pozorn∞ji na deklarace kontejner∙ ve standardnφ ÜablonovΘ knihovn∞ jazyka C++, zjistφme, ₧e vedle typu uklßdanΘ hodnoty majφ dalÜφ parametr ù alokßtor, anglicky oznaΦovan² allocator. Co to je?
Standard jazyka C++ °φkß, ₧e alokßtory jsou objekty, kterΘ zapouzd°ujφ informace o alokaΦnφm modelu. P°elo₧eno do srozumiteln∞jÜφ mluvy to znamenß, ₧e obsahujφ funkce, kterΘ um∞jφ p°id∞lovat a uvol≥ovat pam∞¥, dßle obsahujφ informace o typech ukazatel∙ apod.
Kontejnery a alokßtory
Podφvejme se nejprve na deklaraci jednoho z nejb∞₧n∞jÜφch kontejner∙, seznamu. V hlaviΦkovΘm souboru list najdeme nßsledujφcφ °ßdky:
namespace std {
template<class T, class Allocator = allocator<T> >
class list;
// ...
}
Prvnφ parametr vyjad°uje typ hodnot, kterΘ chceme do kontejneru uklßdat, druh²m parametrem je typ alokßtoru. Implicitnφ hodnotou druhΘho parametru je standardnφ alokßtor std::allocator<T>, o kterΘm si krßtce povφme v zßv∞ru tohoto Φlßnku. Pokud tedy nemßme na alokaci pam∞ti pro dan² kontejner n∞jakΘ zvlßÜtnφ po₧adavky, m∙₧eme tento parametr vynechat a deklarovat nap°. seznam cel²ch Φφsel takto:
#include <list>
std::list<int> L;
PodobnΘ je to i u ostatnφch kontejner∙.
Po₧adavky na alokßtor
Pokud bychom cht∞li z jak²chkoli d∙vod∙ zm∞nit zp∙sob alokace pam∞ti v n∞kterΘ z instancφ standardnφch kontejner∙, m∙₧eme pou₧φt vlastnφ alokßtor. P°itom za alokßtor se pova₧uje jakßkoli t°φda, kterΘ mß p°edepsanΘ rozhranφ, tj. kterß implementuje jistΘ datovΘ typy a metody. Nenφ nutnΘ û obvykle ani vhodnΘ û odvozovat nov² alokßtor jako potomka standardnφho alokßtoru. V po₧adavcφch kladen²ch na alokßtor se sice nikde explicitn∞ ne°φkß, ₧e to musφ b²t Üablona, nicmΘn∞ obvykle se alokßtory jako Üablony definujφ, a proto si ho tak budeme ukazovat i zde.
V nßsledujφcφ deklaraci je T datov² typ hodnoty, pro kterou bude alokßtor vyhrazovat pam∞¥. Potom platφ, ₧e alokßtor musφ definovat nßsledujφcφ ve°ejn∞ p°φstupnΘ datovΘ typy:
template<class T>
class alokator {
public:
typedef T* pointer;
typedef const T* const_pointer;
typedef T& reference;
typedef const T& const_reference;
typedef T value_type;
typedef ui_t size_type;
typedef si_t difference_type;
template <class U> struct rebind {
typedef alokator<U> other;
};
// ...
};
Prvnφ dv∞ deklarace p°edstavujφ "univerzßlnφ" pojmenovßnφ pro ukazatel na T, resp. ukazatel na konstantu typu T; druhΘ dv∞ deklarace p°edstavujφ podobn∞ "univerzßlnφ" pojmenovßnφ pro referenci na hodnotu typu T, resp. pro referenci na konstantu typu T. V pßtΘ deklaraci se zavßdφ oznaΦenφ alokator<T>::value_type pro samotn² typ T.
Deklarace typu size_type pojmenovßvß datov² typ pro vyjßd°enφ velikosti. Identifikßtor ui_t zde zastupuje vhodn² celoΦφseln² typ bez znamΘnka, obvykle size_t. Deklarace typu difference_type zavßdφ pojmenovßnφ pro typ vyjad°ujφcφ rozdφl dvou ukazatel∙. Identifikßtor si_t zde zastupuje celoΦφseln² typ se znamΘnkem, typicky int (skryt² za ptrdiff_t nebo jin²m vhodn²m typedef ze standardnφ knihovny).
Poslednφ deklarace, rebind, je vlastn∞ Üablona pro typedef, kterß oznaΦuje alokßtor pro jin² datov² typ U. Alokßtor m∙₧e vyu₧φt za jist²ch okolnostφ slu₧eb jinΘho alokßtoru (b²t "vßzßn" na jin² alokßtor) a alokator<T>::rebind<U >::other pak p°edstavuje univerzßlnφ oznaΦenφ typu tohoto vßzanΘho alokßtoru. Poznamenejme, ₧e typ U m∙₧e b²t i toto₧n² s T.
Vedle toho musφ b²t pro alokßtory definovßny operßtory == a !=. Obvykle se deklarujφ jako globßlnφ funkce.
V²znam konstruktoru a kopφrovacφho konstruktoru je jasn²; vedle nich je tu vno°enß Üablona konstruktoru, kter² vytvo°φ instanci alokator<T> pro typ T na zßklad∞ instance alokßtoru alokator<U> pro jin² typ U. (Poznamenejme, ₧e deklaraci kopφrovacφho konstruktoru nelze vynechat, nebo¥ p°ekladaΦ C++ nepou₧ije vno°enou Üablonu jednoparametrickΘho konstruktoru k vytvo°enφ kopφrovacφho konstruktoru.)
Destruktor sice nenφ uvßd∞n v seznamu po₧adavk∙ kladen²ch na alokßtor, nicmΘn∞ jeho existence "se p°edpoklßdß".
Funkce address() vracejφ adresu zadanΘho objektu, p°edstavujφ tedy alternativu k operßtoru &. LiÜφ se pouze typem parametru ù prvnφ je urΦena pro zjiÜ¥ovßnφ adres nekonstantnφch objekt∙ typu T, druhß pro zjiÜ¥ovßnφ adres nekonstantnφch objekt∙.
Jßdrem implementace alokßtoru jsou metody allocate(), kterΘ se starajφ o vlastnφ alokaci pam∞ti. Jejich prvnφ parametr n udßvß poΦet objekt∙ typu T, kterΘ chceme alokovat. Metoda allocate() se tedy pokusφ vyhradit pole (souvisl² ·sek pam∞ti) o velikosti n*sizeof(T) bajt∙. Druh² parametr, hint, m∙₧e obsahovat adresu, odkud by m∞la pam∞¥ alokovanß touto metodou zaΦφt; metoda allocate() ovÜem m∙₧e tuto nßpov∞du ignorovat (a ve standardnφm alokßtoru ji opravdu ignoruje).
Poznamenejme, ₧e tato metoda alokuje "hrubou" pam∞¥, to znamenß, ₧e nevolß konstruktory pro objekty typu T, kterΘ do nφ budou ulo₧eny.
V deklaraci t∞chto metod nenφ specifikovßn ₧ßdn² typ v²jimek. To znamenß, ₧e se z nφ mohou rozÜφ°it v²jimky libovolnΘho typu. Standardnφ alokßtor v p°φpad∞ ne·sp∞chu vyvolß v²jimku typu bad_alloc, podobn∞ jako standardnφ operßtor new.
Metoda deallocate(n, p) uvolnφ pam∞¥, na kterou ukazuje p. Musφ to b²t pam∞¥ vyhrazenß metodou allocate() volanou s parametrem n. Pokud tato pam∞¥ obsahovala objekty, oΦekßvß se, ₧e pro n∞ ji₧ byly zavolßny destruktory. (To znamenß, ₧e podobn∞ jako metoda allocate()pracuje i deallocate() s hrubou pam∞tφ.)
Metoda max_size() vrßtφ nejv∞tÜφ hodnotu, kterou lze funkci allocate()p°edat jako po₧adavek. Jin²mi slovy, vrßtφ N, pro kterΘ lze jeÜt∞ ·sp∞Ün∞ zavolat allocate(N, 0).
Metoda construct(p, val) zavolß konstruktor typu T s parametrem val a vytvo°φ tak instanci typu T na adrese p.
Metoda destroy(p) zavolß destruktor na instanci typu T na adrese p.
vrßtφ true, tj. urΦφ, ₧e dva alokßtory jsou si rovny, prßv∞ kdy₧ pam∞¥ alokovanß jednφm z nich m∙₧e b²t uvoln∞na druh²m; v opaΦnΘm p°φpad∞ vrßtφ false. Operßtor != je negacφ operßtoru ==, tj. vrßtφ true, kdy₧ pam∞¥ alokovanß jednφm z jeho operand∙ nem∙₧e b²t uvoln∞na druh²m.
Jak vidφte, p°edepsanΘ rozhranφ alokßtoru je pom∞rn∞ slo₧itΘ; asi nejv∞tÜφ problΘmy mohou p∙sobit vno°enΘ Üablony, kterΘ zatφm jeÜt∞ °ada p°ekladaΦ∙ nepodporuje. To znamenß, ₧e ne₧ se pustφme do vlastnφ implementace alokßtoru, podφvßme se, jak je v knihovn∞ naÜeho p°ekladaΦe implementovßn standardnφ alokßtor, a podle n∞j navrhneme svou vlastnφ verzi.
Poznßmka
V dneÜnφch p°ekladaΦφch se i vestav∞nΘ datovΘ typy, jako je int nebo char, chovajφ (nebo spφÜe m∞ly by se chovat) podobn∞ jako objektovΘ typy û m∙₧eme pro n∞ volat "konstruktor" nap°. zßpisem int() a destruktor nap°. zßpisem i.~int(), kde i je prom∞nnß typu int. To umo₧≥uje pou₧φvat vestav∞nΘ typy jako parametry Üablon na mφst∞, kde se obvykle pou₧φvajφ objektovΘ typy s konstruktorem a destruktorem. V p°φpad∞ alokßtor∙ to umo₧≥uje volat konstruktor typu T v metod∞ construct() i v p°φpad∞, ₧e jde o n∞kter² z vestav∞n²ch typ∙.
P°φklad vlastnφho alokßtoru
Uka₧me si p°φklad. Definujeme jednoduch² alokßtor, kter² nßm umo₧nφ p°id∞lovat pam∞¥ pro dvoustrannou frontu z p°edem p°ipravenΘho pole û arΘny. Toto pole definujeme jako globßlnφ, abychom k n∞mu m∞li p°φstup a mohli snadno kontrolovat, co se s pam∞tφ kontejneru d∞je:
char arena[N];
Deklarace alokßtoru bude vychßzet z p°edepsanΘho rozhranφ, do n∞ho₧ p°idßme soukromou slo₧ku index. Ta bude slou₧it k orientaci v poli arena:
template<class T> class alok {
int index;
public:
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef T* pointer;
typedef const T* const_pointer;
typedef T& reference;
typedef const T& const_reference;
typedef T value_type;
template<class U> struct rebind {
typedef alok<U> other;
};
alok() throw():index(0){};
template<class U>
alok(const alok<U>& A) throw():index(A.Index()){};
alok(const alok<T>& A) throw():index(A.index){};
template<class U>
alok& operator=(const alok<U>&) throw() {}
~alok() throw(){};
pointer address(reference x) const
{return &x;};
const_pointer address(const_reference) const
{return &x;};
pointer allocate(size_type n, void* = 0);
void deallocate(pointer p, size_type n)
{};
size_type max_size() const
{return (10000-index>0?10000-index:0)/sizeof(T);}
void construct(pointer p, const T& val)
{*p = T(val);};
void destroy(pointer p)
{p->~T();}
int Index(){return index;}
};
Konstruktory majφ jedin² ·kol, a to inicializovat hodnotu slo₧ky index. Kopφrovacφ konstruktor a konstruktor, kter² vytvo°φ alokßtor pro typ T na zßklad∞ alokßtoru pro jin² typ U, musejφ okopφrovat hodnotu slo₧ky index. Metody address() prost∞ vracejφ adresu svΘho parametru.
Metoda allocate() se starß o alokaci. Proto₧e nßm jde o ukßzku, pou₧ijeme nejjednoduÜÜφ mysliteln² algoritmus û prost∞ budeme p°id∞lovat pam∞¥, dokud v poli arena n∞jakß bude, a kdy₧ nßm dojde, vyvolßme v²jimku:
template<class T>
alok<T>::pointer alok<T>::allocate(size_type n, void*)
{
void *p = &arena[index];
index+= n*sizeof(T);
if (n > N) throw std::bad_alloc();
return (pointer)p;
}
Metoda deallocate() se starß o uvoln∞nφ pam∞ti; v naÜem p°φpad∞ mß prßzdnΘ t∞lo, nebo¥ ji nepot°ebujeme û o uvol≥ovßnφ pam∞ti se vzhledem k pou₧itΘmu algoritmu alokace nemusφme starat. Jejφ definici ovÜem vynechat nem∙₧eme.
Metoda construct() mß za ·kol zkonstruovat v alokovanΘ pam∞ti na adrese p objekt typu T s poΦßteΦnφ hodnotou val. K tomu pou₧ije p°φkaz
*p = T(val);
Metoda destroy() ho zruÜφ, zavolß toti₧ jeho destruktor p°φkazem
p->~T();
Oba p°φkazy budou sprßvnΘ i v p°φpad∞, ₧e T bude n∞kter² ze standardnφch typ∙ û o tom jsme ji₧ hovo°ili.
Metoda max_size() vypoΦφtß, kolik instancφ typu T lze jeÜt∞ alokovat, a vypoΦtenou hodnotu vrßtφ.
Poznamenejme, ₧e takto napsan² alokßtor nenφ p°φliÜ kvalitnφ û mimo jinΘ proto, ₧e pokud by v programu vedle sebe existovalo n∞kolik instancφ, braly by pot°ebnou pam∞¥ z tΘho₧ pole, ani₧ by jakkoli koordinovaly svou Φinnost. (Nßm ovÜem nejde o p°φklad alokaΦnφho algoritmu, ale o p°φklad samotnΘho alokßtoru, a proto se s touto implementacφ spokojφme.)
Do rozhranφ alokßtoru m∙₧eme p°idat svΘ vlastnφ metody. Zde jsme p°idali funkci Index(), kterß vracφ hodnotu datovΘ slo₧ky index. Pot°ebujeme ji v Üablon∞ konstruktoru, kter² vytvo°φ alokßtor pro typ T z alokßtoru pro jin² typ U. Instance tΘ₧e Üablony s r∙zn²mi parametry, alok<T> a alok<U>, jsou dva r∙znΘ typy, a proto jeden z nich nem∙₧e pou₧φt soukromΘ slo₧ky druhΘho.
Alokßtor pro MSVC 6
P°edchozφ p°φklad lze p°elo₧it nap°. v C++Builderu 4 nebo 5. Nelze ho ovÜem pou₧φt v Microsoft Visual C++ 6, nebo¥ tento p°ekladaΦ jeÜt∞ nepodporuje vno°enΘ Üablony. Podφvejme se tedy, jak je t°eba deklarovat alokßtor pro tento p°ekladaΦ.
Proto₧e MSVC 6 nepodporuje vno°enΘ Üablony, chybφ v jeho implementaci standardnφ knihovny v alokßtoru struktura rebind a Üablona konstruktoru, kter² vytvo°φ alokßtor pro typ T z alokßtoru pro jin² typ. Chybφ tu i kopφrovacφ konstruktor.
Alokßtor pro jin² typ, other<U>, se z alokßtoru pro T volß pom∞rn∞ Φasto, a proto musφ b²t n∞Φφm nahrazen; v MSVC slou₧φ jako nßhrada funkce char* _Charalloc(size_type). Tato funkce musφ takΘ obsahovat alokaΦnφ algoritmus (stejn² jako allocate() nebo jin² û zßle₧φ na naÜich pot°ebßch).
Rozhranφ alokßtoru pro MSVC 6 bude vypadat takto:
template<class T>
class alok {
int index;
public:
// ... deklarace typ∙ stejnΘ jako p°edtφm
alok(); // jedin² konstruktor
// metody address() stejnΘ
pointer allocate(size_type n, const void *);
char *_Charalloc(size_type n);
// metody deallocate(), construct(), destroy()
// a max_size() podobnΘ
};
Pou₧itφ alokßtoru
Na zßv∞r si ukß₧eme pou₧itφ naÜeho alokßtoru. Chceme nap°. najφt chybu v prßci s dvoustrannou frontou. Nejprve tedy vyplnφme vÜechny prvky pole arena vhodn²m znakem, nap°. '0', abychom mohli sledovat jejich zm∞ny:
int i;
for(i = 0; i < N; i++) arena[i] = '0';
Pak deklarujeme dvoustrannou frontu znak∙, tedy instanci t°φdy deque, a vyplnφme ji velk²mi pφsmeny abecedy:
deque<char, alok<char> > D;
for(i = 'A'; i < 'Z'; i++)
D.push_front(char(i));
V²pisem obsahu pole arena (nebo jeho prohlφdkou ve vhodnΘm ladicφm nßstroji) m∙₧eme zjistit, jak se alokujφ prvky dvoustrannΘ fronty. (Detaily zßvisφ na implementaci; nap°. v borlandsk²ch p°ekladaΦφch se v naÜem p°φkladu pou₧ije jako prvnφ p°ibli₧n∞ p∞tist² prvek pole arena, v MSVC to bude p°ibli₧n∞ dvoutisφcφ prvek.)
Doplnφme-li t∞la vÜech t°φ konstruktor∙ o v²pis identifikace pou₧itΘho konstruktoru a typu T, nap°.
alok() throw()
:index(0)
{
cout << "1 " << typeid(T).name()<<endl;
};
kde jednotlivΘ konstruktory budou "oznaΦeny" Φφsly 1, 2 a 3, zjistφme po spuÜt∞nφ, ₧e nap°. v C++Builderu se p°i konstrukci dvoustrannΘ fronty znak∙ vytvo°φ jeden alokßtor pro typ char pomocφ konstruktoru bez parametr∙ a jeden pomocφ kopφrovacφho konstruktoru. P°i uklßdßnφ znak∙ do fronty se bude novß pam∞¥ p°id∞lovat pomocφ alokßtor∙ vytvo°en²ch pomocφ kopφrovacφho konstruktoru. ╚as od Φasu se ovÜem vytvo°φ i alokßtor pro typ char*, vytvo°en² pomocφ vno°enΘ Üablony konstruktoru.
Standardnφ alokßtor
Ve standardnφ knihovn∞ jazyka C++ najdeme implicitnφ implementaci alokßtoru, kterou oznaΦujeme jako standardnφ alokßtor. Jeho Üablona, std::allocator<>, je v hlaviΦkovΘm souboru <memory>; k alokaci pam∞ti vyu₧φvß operßtor new a k jejφmu uvol≥ovßnφ operßtor delete.
èablona standardnφho alokßtoru je vyhrazena pro typ void (tj. v hlaviΦkovΘm souboru memory je definovßna zvlßÜtnφ implementace std::allocator<void>).
Mφsto zßv∞ru...
Pou₧φvßnφ vlastnφch alokßtor∙ nepat°φ k nejb∞₧n∞jÜφm programßtorsk²m obrat∙m; jsou ale situace, kdy je to tΘm∞° nezbytnΘ, a jist∞ neuÜkodφ v∞d∞t o nich n∞co p°edem. èt∞stφ p°eje p°ipraven²m...
