D::vfun(), i vot k chemu eto privelo:
dptr 0012FF6C D::vfun(): this=0012FF6C ptr1 0012FF6C b2ptr 0012FF70 D::vfun(): this=0012FF6C ptr2 0012FF70T.o. oba raza byla vyzvana
D::vfun(), no vozvrashchaemoe ej znachenie zavisit ot sposoba vyzova (ptr1!=ptr2), kak eto, sobstvenno govorya, i dolzhno byt'.
Delaetsya eto tochno tak zhe, kak uzhe bylo opisano v razdele 361 "12.2.6. Virtual'nye funkcii", tol'ko pomimo korrektirovki prinimaemogo znacheniya this neobhodimo dopolnitel'no proizvesti korrektirovku this vozvrashchaemogo. Ponyatno, chto virtual'nye funkcii s kovariantnym tipom vozvrata vstrechayutsya nastol'ko redko, chto realizaciya ih vyzova posredstvom rasshireniya vtbl vryad li mozhet byt' priznana adekvatnoj. Na praktike obychno sozdayutsya special'nye funkcii-zaglushki, ch'i adresa pomeshchayutsya v sootvetstvuyushchie elementy vtbl:
// psevdokod
// original'naya D::vfun, napisannaya programmistom
D* D::vfun(D *const this)
{
// ...
}
// sgenerirovannaya kompilyatorom funkciya-zaglushka dlya vyzova D::vfun() cherez
// ukazatel' na bazovyj klass B2
B2* D::vfun_stub(B2 *const this)
{
return D::vfun(this+delta_1)+delta_2;
}
gde vozvrashchaemyj funkciej ukazatel' korrektiruetsya posredstvom konstanty delta_2, voobshche govorya, ne ravnoj delta_1.
Podvodya itog, hochetsya otmetit', chto v obshchem sluchae vyzov virtual'noj funkcii stanovitsya vse men'she pohozh na "prosto kosvennyj vyzov funkcii". Nu, i raz uzh rech' zashla o virtual'nyh funkciyah s kovariantnym tipom vozvrata, stoit privesti sootvetstvuyushchuyu chast' standarta:
10.3. Virtual'nye funkcii [class.virtual]
D::f zameshchaet funkciyu B::f, tipy vozvrashchaemyh imi znachenij budut kovariantnymi, esli oni udovletvoryayut sleduyushchim usloviyam:
B::f identichen klassu v vozvrashchaemom znachenii D::f ili on yavlyaetsya odnoznachno opredelennym otkrytym pryamym ili kosvennym bazovym klassom vozvrashchaemogo D::f klassa i pri etom dostupen v D
D::f imeet te zhe ili men'shie cv-kvalifikatory, chto i klass v vozvrashchaemom znachenii B::f.
D::f otlichaetsya ot tipa vozvrashchaemogo znacheniya B::f, to tip klassa v vozvrashchaemom znachenii D::f dolzhen byt' zavershen v tochke opredeleniya D::f ili on dolzhen byt' tipom D. Kogda zameshchayushchaya funkciya budet vyzyvana (kak poslednyaya zamestivshaya funkciya), tip ee vozvrashchaemogo znacheniya budet (staticheski) preobrazovan v tip vozvrashchaemogo znacheniya zameshchaemoj funkcii (5.2.2). Naprimer:
class B {};
class D : private B { friend class Derived; };
struct Base {
virtual void vf1();
virtual void vf2();
virtual void vf3();
virtual B* vf4();
virtual B* vf5();
void f();
};
struct No_good : public Base {
D* vf4(); // oshibka: B (bazovyj klass D) nedostupen
};
class A;
struct Derived : public Base {
void vf1(); // virtual'naya i zameshchaet Base::vf1()
void vf2(int); // ne virtual'naya, skryvaet Base::vf2()
char vf3(); // oshibka: nepravil'nyj tip vozvrashchaemogo znacheniya
D* vf4(); // OK: vozvrashchaet ukazatel' na proizvodnyj klass
A* vf5(); // oshibka: vozvrashchaet ukazatel' na nezavershennyj klass
void f();
};
void g()
{
Derived d;
Base* bp=&d; // standartnoe preobrazovanie: Derived* v Base*
bp->vf1(); // vyzov Derived::vf1()
bp->vf2(); // vyzov Base::vf2()
bp->f(); // vyzov Base::f() (ne virtual'naya)
B* p=bp->vf4(); // vyzov Derived::pf() i preobrazovanie
// vozvrata v B*
Derived* dp=&d;
D* q=dp->vf4(); // vyzov Derived::pf(), preobrazovanie
// rezul'tata v B* ne osushchestvlyaetsya
dp->vf2(); // oshibka: otsutstvuet argument
}
3.9.3. CV-kvalifikatory [basic.type.qualifier]
| net cv-kvalifikatora | < | const |
| net cv-kvalifikatora | < | volatile |
| net cv-kvalifikatora | < | const volatile |
const |
< | const volatile |
volatile |
< | const volatile |
Vmeste s tem, ne stoit dumat', chto STL ne soderzhit snizhayushchih effektivnost' kompromissov. Ochevidno, chto special'no napisannyj dlya resheniya konkretnoj problemy kod budet rabotat' effektivnee, vopros v tom, naskol'ko effektivnee? Naprimer, esli nam nuzhno prosto sohranit' v pamyati zaranee neizvestnoe kolichestvo elementov, a zatem ih posledovatel'no ispol'zovat', to (odnosvyaznyj) spisok budet naibolee adekvatnoj strukturoj dannyh. Odnako STL ne soderzhit odnosvyaznyh spiskov, kak mnogo my na etom teryaem?
Rassmotrim sleduyushchij primer:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <list>
struct List { // odnosvyaznyj spisok
struct Data {
int val;
Data* next;
Data(int v, Data* n=0) : val(v), next(n) {}
};
Data *head, *tail;
List() { head=tail=0; }
~List()
{
for (Data *ptr=head, *n; ptr; ptr=n) { // udalyaem vse elementy
n=ptr->next;
delete ptr;
}
}
void push_back(int v) // dobavlyaem element
{
if (!head) head=tail=new Data(v);
else tail=tail->next=new Data(v);
}
};
long Count, Var;
void f1()
{
List lst;
for (int i=0; i<1000; i++)
lst.push_back(i);
for (List::Data* ptr=lst.head; ptr; ptr=ptr->next)
Var+=ptr->val;
}
void f2()
{
typedef std::list<int> list_type;
list_type lst;
for (int i=0; i<1000; i++)
lst.push_back(i);
for (list_type::const_iterator ci=lst.begin(), cend=lst.end(); ci!=cend; ++ci)
Var+=*ci;
}
int main(int argc, char** argv)
{
if (argc>1) Count=atol(argv[1]);
clock_t c1,c2;
{
c1=clock();
for (long i=0; i<Count; i++)
for (long j=0; j<1000; j++)
f1();
c2=clock();
printf("f1(): %ld ths calls per %.1f sec\n", Count, double(c2-c1)/CLK_TCK);
}
{
c1=clock();
for (long i=0; i<Count; i++)
for (long j=0; j<1000; j++)
f2();
c2=clock();
printf("f2(): %ld ths calls per %.1f sec\n", Count, double(c2-c1)/CLK_TCK);
}
}
V nem f1() ispol'zuet opredelennyj nami List: vstavlyaet 1000 elementov, a zatem prohodit po spisku.
T.k. STL ispol'zuet sobstvennyj raspredelitel' pamyati (vskore vy uvidite, chto delaet ona eto sovsem ne naprasno), to to zhe samoe sleduet poprobovat' i nam:
struct List { // odnosvyaznyj spisok
struct Data {
// ...
// dlya sobstvennogo raspredeleniya pamyati
static Data* free;
static void allocate();
void* operator new(size_t);
void operator delete(void*, size_t);
};
// ...
};
List::Data* List::Data::free;
void List::Data::allocate()
{
const int sz=100; // vydelyaem bloki po sz elementov
free=reinterpret_cast<Data*>(new char[sz*sizeof(Data)]);
// sceplyaem svobodnye elementy
for (int i=0; i<sz-1; i++)
free[i].next=free+i+1;
free[sz-1].next=0;
}
inline void* List::Data::operator new(size_t)
{
if (!free) allocate();
Data* ptr=free;
free=free->next;
return ptr;
}
inline void List::Data::operator delete(void* dl, size_t)
{ // dobavlyaem v nachalo spiska svobodnyh elementov
Data* ptr=static_cast<Data*>(dl);
ptr->next=free;
free=ptr;
}
Obratite vnimanie, chto v dannom primere nash raspredelitel' pamyati ne vozvrashchaet poluchennuyu pamyat' sisteme. No eto ne memory leak (utechka pamyati) -- eto memory pool, t.e. zaranee vydelennyj zapas pamyati dlya bystrogo posleduyushchego ispol'zovaniya. Na pervyj vzglyad, raznica mezhdu memory leak i memory pool mozhet pokazat'sya slishkom tonkoj, no ona est': delo v tom, chto v pervom sluchae potreblenie pamyati ne ogranicheno, vplot' do polnogo ee ischerpaniya, a vo vtorom ono nikogda ne prevysit real'no zatrebovannogo programmoj ob容ma plyus nekotoraya del'ta, ne prevoshodyashchaya razmer vydelyaemogo bloka.
I eshche, nash raspredelitel' soderzhit ochen' ser'eznuyu oshibku -- on nepravil'no obrabatyvaet udalenie nulya (NULL-ukazatelya). V nashem primere eto ne imeet znacheniya, no v real'nom kode vy obyazany eto uchest', t.e.:
inline void List::Data::operator delete(void* dl, size_t)
{
if (!dl) return; // ignoriruem NULL
// dobavlyaem v nachalo spiska svobodnyh elementov
Data* ptr=static_cast<Data*>(dl);
ptr->next=free;
free=ptr;
}
I, dlya chistoty eksperimenta, v zaklyuchenie poprobuem dvusvyaznyj spisok -- ego po pravu mozhno nazvat' vruchnuyu napisannoj al'ternativoj std::list<int>:
struct DList { // dvusvyaznyj spisok
struct Data {
int val;
Data *prev, *next;
Data(int v, Data* p=0, Data* n=0) : val(v), prev(p), next(n) {}
// dlya sobstvennogo raspredeleniya pamyati
static Data* free;
static void allocate();
void* operator new(size_t);
void operator delete(void*, size_t);
};
Data *head, *tail;
DList() { head=tail=0; }
~DList()
{
for (Data *ptr=head, *n; ptr; ptr=n) { // udalyaem vse elementy
n=ptr->next;
delete ptr;
}
}
void push_back(int v) // dobavlyaem element
{
if (!head) head=tail=new Data(v);
else tail=tail->next=new Data(v, tail);
}
};
Itak, vse gotovo, i mozhno pristupat' k testirovaniyu. Dannye tri testa ya poproboval na dvuh raznyh kompilyatorah, vot rezul'tat:
| odnosvyaznyj | odnosvyaznyj s sobstvennym raspredelitelem pamyati |
dvusvyaznyj s sobstvennym raspredelitelem pamyati |
||||
| f1() | f2() | f1() | f2() | f1() | f2() | |
| realizaciya 1 | 9.6 | 12.1 | 1.1 | 12.1 | 1.3 | 12.1 |
| realizaciya 2 | 20.2 | 2.5 | 1.8 | 2.5 | 1.9 | 2.5 |
I chto zhe my zdes' vidim?
vr inicializiruetsya konstruktorom Record(), a kazhdyj iz s1 elementov kontejnera vi inicializiruetsya int().
Inicializaciya 10 000 elementov konstruktorom po umolchaniyu ne mozhet ne vpechatlyat' -- tol'ko v ochen' redkom sluchae nuzhno imenno eto. Esli vy vydelyaete eti 10 000 elementov pro zapas, dlya posleduyushchej perezapisi, to stoit podumat' o sleduyushchej al'ternative:
vector<X> vx; // ob座avlyaem pustoj vektor
vx.reserve(10000); // rezerviruem mesto voizbezhanie "dorogih"
// pereraspredelenij v push_back()
// ...
vx.push_back(x_work); // dobavlyaem elementy po mere nadobnosti
O nej tem bolee stoit podumat', t.k. dazhe v otlichnoj realizacii STL 3.2 ot sgi konstruktor
vector<int> vi(s1);podrazumevaet yavnyj cikl zapolneniya nulyami:
for (int i=0; i<s1; i++)
vi.elements[i]=0;
i trebuetsya dostatochno intellektual'nyj optimizator dlya prevrashcheniya etogo cikla v vyzov memset():
memset(vi.elements, 0, sizeof(int)*s1);chto znachitel'no uluchshit proizvoditel'nost' (konechno ne programmy voobshche, a tol'ko dannogo otrezka koda). Matt Austern postavlen v izvestnost', i v budushchih versiyah sgi STL mozhno ozhidat' povysheniya proizvoditel'nosti dannogo konstruktora.
Ochen' zhal', chto dorogaya redakciya sochla vozmozhnym pomestit' v knigu takuyu glupost'. Dlya privedeniya kolichestva "dorogih" pereraspredelenij k priemlemomu urovnyu O(log(N)), v STL ispol'zuetsya uvelichenie ob容ma zarezervirovannoj pamyati v poltora-dva raza, a pri prostom dobavlenii nekotorogo kolichestva (10, naprimer) my, ochevidno, poluchim O(N), chto est' ploho. Takzhe otmechu, chto dlya umen'sheniya kolichestva pereraspredelenij stoit vospol'zovat'sya reserve(), osobenno, esli vy zaranee mozhete ocenit' predpolagaemuyu glubinu steka.
I delo ne tol'ko v opredelenii operacii "men'she", a eshche i v tom, chto char* ne stoit ispol'zovat' v kachestve elementov STL kontejnerov voobshche: kontejner budet soderzhat' znachenie ukazatelya -- ne soderzhimoe stroki, kak kto-to po naivnosti mog polagat'. Naprimer, sleduyushchaya funkciya soderzhit ser'eznuyu oshibku:
void f(set<char*>& cset)
{
for (;;) {
char word[100];
// schityvaem slovo v word ...
cset.insert(word); // oshibka: vstavlyaem odin i tot zhe ukazatel'
// na lokal'nuyu peremennuyu
}
}
Dlya polucheniya ozhidaemogo rezul'tata sleduet ispol'zovat' string:
void f(set<string>& cset)
{
for (;;) {
char word[100];
// schityvaem slovo v word ...
cset.insert(word); // OK: vstavlyaem string
}
}
Ispol'zovanie char* v STL kontejnerah privodit k chrezvychajno kovarnym oshibkam, t.k. inogda vse rabotaet pravil'no. Naprimer dokumentaciya k sgi STL shiroko ispol'zuet char* v svoih uchebnyh primerah:
struct ltstr
{
bool operator()(const char* s1, const char* s2) const
{
return strcmp(s1, s2) < 0;
}
};
int main()
{
const int N = 6;
const char* a[N] = {"isomer", "ephemeral", "prosaic",
"nugatory", "artichoke", "serif"};
set<const char*, ltstr> A(a, a + N);
// i t.d.
}
Dannyj primer vpolne korrekten, no stoit tol'ko vmesto staticheski razmeshchennyh strokovyh literalov ispol'zovat' lokal'no formiruemye C-stroki, kak nepriyatnosti ne zastavyat sebya zhdat'.
Otnosites' skepticheski k uchebnym primeram!
pair.
CHestno govorya, pri pervom znakomstve s shablonami ot vseh etih mnogoslovnyh ob座avlenij nachinaet ryabit' v glazah, i ne vsegda ponyatno, chto imenno udobno v takoj vot funkcii:
template <class T1,class T2>
pair<T1,T2> std::make_pair(const T1& t1, const T2& t2)
{
return pair<T1,T2>(t1,t2);
}
A udobno sleduyushchee: Esli nam nuzhen ekzemplyar klassa-shablona, to my obyazany predostavit' vse neobhodimye dlya instanciirovaniya klassa parametry, t.k. na osnovanii argumentov konstruktora oni ne vyvodyatsya. S funkciyami-shablonami dela obstoyat poluchshe:
char c=1; int i=2; // probuem sozdat' "paru" pair(c,i); // nepravil'no -- pair<char,int> ne vyvoditsya pair<char,int>(c,i); // pravil'no make_pair(c,i); // pravil'no
operator[]().
Voobshche govorya, sushchestvuet, t.k. ona ob座avlena v klasse, no, vvidu ee nekonstantnosti, primenena byt' ne mozhet -- pri popytke instanciirovaniya vy poluchite oshibku kompilyacii.
K schast'yu, eto ne tak: v dannom sluchae etot "dovol'no slozhnyj i redkij sintaksis" ne trebuetsya.
V samom dele, esli razresheno
f<int>(); // f -- funkciya-shablonto pochemu vdrug kompilyator ne mozhet pravil'no razobrat'sya s
obj.f<int>(); // f -- funkciya-shablon, chlen klassaMozhet, i razbiraetsya!
Istoricheski, neponimanie vozniklo iz-za togo, chto:
template byl izobreten komitetom po standartizacii, a ne d-rom Straustrupom;
template kak kvalifikator.
hash_map.
A vot eshche odin "lyap", i net emu opravdaniya! Delo v tom, chto v standarte ponyatiya "podderzhivaemyj hash_map" ne sushchestvuet. Eshche bol'she pikantnosti dannoj situacii pridaet tot fakt, chto v samoj STL, kotoraya yavlyaetsya osnovnoj chast'yu standartnoj biblioteki C++, hash_map est' (i est' uzhe davno). D-r Straustrup pishet po etomu povodu, chto hash_map prosto proglyadeli, a kogda hvatilis', to bylo uzhe pozdno -- nikakie sushchestvennye izmeneniya vnesti v standart bylo uzhe nel'zya. Nu chto zh, byvaet...
CHto zhe nam sovetuyut priznat' chitaemym i effektivnym (vprochem, k effektivnosti, teoreticheski, pretenzij dejstvitel'no net)?
list<int>::const_iterator p=find_if(c.begin(),c.end(),bind2nd(less<int>(),7));Osmelyus' predlozhit' drugoj variant:
list<int>::const_iterator p;
for (p=c.begin(); p!=c.end(); ++p)
if (*p<7) break;
Trudno li eto napisat'? Po-vidimomu, net. YAvlyaetsya li etot yavnyj cikl menee chitaemym? Po moemu mneniyu, on dazhe prevoshodit chitaemost' primera s ispol'zovaniem bind2nd(). A esli nuzhno napisat' uslovie vida *p>=5 && *p<100, chto, v principe, vstrechaetsya ne tak uzh i redko, to variant s ispol'zovaniem svyazyvatelej i find_if() proigryvaet odnoznachno. Stoit dobavit' i chisto psihologicheskij effekt: vyzov krasivoj funkcii chasto podsoznatel'no vosprinimaetsya atomarnoj operaciej i ne lishne podcherknut', chto za krasivym fasadom poroj skryvaetsya krajne neeffektivnyj posledovatel'nyj poisk.
V celom, ya agitiruyu protiv poteri zdravogo smysla pri ispol'zovanii predostavlennogo nam pestrogo nabora svistulek i kolokol'chikov. Uvy, sleduet priznat', chto dlya skol'-nibud' slozhnogo primeneniya oni ne prednaznacheny, da i na prostom primere pol'za prakticheski ne vidna.
Teper' nemnogo pro vyzovy funkcij-chlenov dlya elementov kontejnera s pomoshch'yu mehanizma mem_fun(). Dejstvitel'no, variant
for_each(lsp.begin(),lsp.end(),mem_fun(&Shape::draw)); // risuem vse figurypodkupaet svoim izyashchestvom. I dazhe bolee togo, predostavlyaemye
mem_fun() vozmozhnosti dejstvitel'no mogut byt' vostrebovany, naprimer, pri realizacii nekotorogo abstraktnogo shablona razrabotki (design pattern). No za krasivym fasadom skryvaetsya vyzov funkcii cherez ukazatel' na chlen -- operaciya otnyud' ne deshevaya i daleko ne vse kompilyatory umeyut vstraivat' vyzov funkcii cherez takoj ukazatel'. Budem riskovat'?
A chto, esli nam nuzhno povernut' vse figury na zadannyj ugol? bind2nd(), govorite? A esli na raznye ugly da prichem ne vse elementy kontejnera, i eti ugly rasschityvayutsya po slozhnomu algoritmu? Po-moemu, takoj variant v real'nyh programmah vstrechaetsya gorazdo chashche.
Vyhodit, chto i mehanizm mem_fun() ne ochen'-to prednaznachen dlya ser'eznogo ispol'zovaniya. Izuchit' ego, konechno, stoit, a vot ispol'zovat' ili net -- reshat' vam.
Vot eto da! T.e. esli ya popytayus' udalit' element iz spiska s pomoshch'yu takogo remove(), to vmesto udaleniya elementa ya poluchu prosto pereprisvaivanie (v srednem) poloviny ego elementov?!
Pojmite menya pravil'no, sredi privedennyh v etom razdele algoritmov budut i prakticheski poleznye, no derzhat' v standartnoj biblioteke ne tol'ko neeffektivnye, no dazhe ne sootvetstvuyushchie svoemu nazvaniyu algoritmy -- eto uzhe slishkom!
No v takom vide oni budut sovershenno neeffektivny v prilozhenii ko vstroennym tipam, ved' obshcheizvestno, chto dlya kopirovaniya bol'shih ob容mov informacii (esli bez nego dejstvitel'no nikak nel'zya obojtis') sleduet ispol'zovat' funkcii standartnoj biblioteki C memcpy() i memmove(). Vy nechasto ispol'zuete vektory vstroennyh tipov? Osmelyus' zametit', chto vektor ukazatelej vstrechaetsya ne tak uzh i redko i kak raz podhodit pod eto opredelenie. K schast'yu, u menya est' horoshaya novost': v kachestvennoj realizacii STL (naprimer ot sgi) vyzov operacii kopirovaniya dlya vector<int> kak raz i privedet k effektivnomu memmove().
Vybor podhodyashchego algoritma proizvoditsya na etape kompilyacii s pomoshch'yu special'no opredelennogo shablona __type_traits<> -- svojstva tipa. Kotoryj (po umolchaniyu) imeet bezopasnye nastrojki dlya slozhnyh tipov s netrivial'nymi konstruktorami/destruktorami i optimizirovannye specializacii dlya POD tipov, kotorye mozhno kopirovat' prostym peremeshcheniem blokov pamyati.
V C++ vy chasto budete vstrechat' abbreviaturu POD (Plain Old Data). CHto zhe ona oboznachaet? POD tip -- eto tip, ob容kty kotorogo mozhno bezopasno peremeshchat' v pamyati (s pomoshch'yu memmove(), naprimer). Dannomu usloviyu ochevidno udovletvoryayut vstroennye tipy (v tom chisle i ukazateli) i klassy bez opredelyaemoj pol'zovatelem operacii prisvaivaniya i destruktora.
Pochemu ya ob etom govoryu? Potomu chto, naprimer, ochevidnoe opredelenie klassa Date yavlyaetsya POD tipom:
class Date {
int day, mon, year;
// ili dazhe
long val; // yyyymmdd
public:
// ...
};
Poetomu stoit razreshit' optimizaciyu predostaviv sootvetstvuyushchuyu specializaciyu __type_traits<>:
template<> struct __type_traits<Date> {
// ...
};
Tol'ko imejte vvidu: __type_traits<> -- ne chast' standartnoj biblioteki, raznye realizacii mogut ispol'zovat' razlichnye imena ili dazhe ne proizvodit' optimizaciyu voobshche. Izuchite to, chto est' u vas.
* vozvrashchaet znachenie *(current-1)...
Da, po smyslu imenno tak:
24.4.1.3.3 operator* [lib.reverse.iter.op.star]
reference operator*() const;
Iterator tmp = current; return *--tmp;
I don't think anyone would use a reverse iterator if an iterator was an alternative, but then you never know what people might know. When you actually need to go through a sequence in reverse order a reverse iterator is often quite efficient compared to alternatives. Finally, there may not be any overhead because where the iterator is a vector the temporary isn't hard to optimize into a register use. One should measure before worrying too much about overhead.YA ne dumayu, chto by kto-to ispol'zoval obratnyj iterator tam, gde mozhno ispol'zovat' obychnyj, no my nikogda ne mozhem znat', chto dumayut drugie lyudi. Kogda vam dejstvitel'no nuzhno projti posledovatel'nost' v obratnom poryadke, obratnyj iterator yavlyaetsya vpolne priemlemoj al'ternativoj. V principe, inogda mozhno voobshche izbezhat' nakladnyh rashodov, naprimer v sluchae obratnogo prohoda po vektoru, kogda vremennaya peremennaya-iterator bez truda razmeshchaetsya v registre. V lyubom sluchae, ne stoit chrezmerno bespokoit'sya o proizvoditel'nosti ne provedya real'nyh izmerenij.
Vmeste s tem, obratnyj iterator vse-taki neset v sebe nenuzhnye nakladnye rashody, i dlya obratnogo prohoda po posledovatel'nosti luchshe ispol'zovat' obychnyj iterator s yavnym (pre)dekrementom.
I raz uzh rech' zashla o real'nyh izmereniyah, davajte ih proizvedem.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <list>
long Count, Var;
typedef std::list<int> list_type;
list_type lst;
void f1()
{
for (list_type::reverse_iterator ri=lst.rbegin(), rend=lst.rend(); ri!=rend;
++ri)
Var+=*ri;
}
void f2()
{
list_type::iterator i=lst.end(), beg=lst.begin();
if (i!=beg) {
do {
--i;
Var+=*i;
} while (i!=beg);
}
}
int main(int argc, char** argv)
{
if (argc>1) Count=atol(argv[1]);
for (int i=0; i<10000; i++)
lst.push_back(i);
clock_t c1, c2;
{
c1=clock();
for (long i=0; i<Count; i++)
for (long j=0; j<1000; j++)
f1();
c2=clock();
printf("f1(): %ld ths calls per %.1f sec\n", Count, double(c2-c1)/CLK_TCK);
}
{
c1=clock();
for (long i=0; i<Count; i++)
for (long j=0; j<1000; j++)
f2();
c2=clock();
printf("f2(): %ld ths calls per %.1f sec\n", Count, double(c2-c1)/CLK_TCK);
}
}
V dannom primere spisok iz 10 000 elementov prohoditsya neskol'ko tysyach raz (zadaetsya parametrom) s ispol'zovaniem obratnogo (v f1()) i obychnogo (v f2()) iteratorov. Pri ispol'zovanii kachestvennogo optimizatora raznicy vremeni vypolneniya zamecheno ne bylo, a dlya "obychnyh" realizacij ona sostavila ot 45% do 2.4 raza.
I eshche odna problema: privodit li postinkrement iteratora k sushchestvennym nakladnym rashodam po sravneniyu s preinkrementom? Davajte vnesem sootvetstvuyushchie izmeneniya:
void f1()
{
for (list_type::iterator i=lst.begin(), end=lst.end(); i!=end; ++i)
Var+=*i;
}
void f2()
{
for (list_type::iterator i=lst.begin(), end=lst.end(); i!=end; i++)
Var+=*i;
}
I opyat' vse tot zhe rezul'tat: raznicy mozhet ne byt', a tam, gde ona proyavlyalas', ee velichina nahodilas' v predelah 5 - 30 procentov.
V celom, ne stoit ispol'zovat' potencial'no bolee dorogie obratnye iteratory i postinkrementy, esli vy ne ubedilis' v intellektual'nosti ispol'zuemogo optimizatora.
Vpolne rezonnym budet vopros: chto zhe zdes' imelos' vvidu? Nedostatok kakih svojstv meshaet ssylkam C++ byt' "sovershennymi"? D-r. Straustrup otvetil sleduyushchee:
Something that would allow a copy constructor to be defined using a user-defined reference object.CHto-to, chto pozvolilo by opredelit' konstruktor kopirovaniya s ispol'zovaniem predostavlennogo pol'zovatelem ssylochnogo tipa.
template<class T>
T* Pool_alloc<T>::allocate(size_type n, void* =0)
{
if (n==1) return static_cast<T*>(mem_alloc());
// ...
}
Kak vsegda, samoe interesnoe skryvaetsya za mnogotochiem. Kak zhe nam realizovat' chast' allocate<>() dlya n!=1? Prostym vyzovom v cikle mem_alloc()? Uvy, v dannom sluchae ochevidnoe reshenie ne podhodit sovershenno. Pochemu? Davajte rassmotrim povedenie Pool_alloc<char>. Glyadya na konstruktor original'nogo Pool:
Pool::Pool(unsigned int sz)
: esize(sz<sizeof(Link*) ? sizeof(Link*) : sz)
{
// ...
}
mozhno zametit', chto dlya sz==sizeof(char) dlya kazhdogo char my budem vydelyat' sizeof(Link*) bajt pamyati. Dlya "obychnoj" realizacii eto oznachaet chetyrehkratnyj pererashod pamyati! T.o. vydelenie pamyati dlya massivov ob容ktov tipa X, gde sizeof(X)<sizeof(Link*) stanovitsya netrivial'noj zadachej, ravno kak i posleduyushchee ih osvobozhdenie v deallocate<>(), fakticheski, pridetsya principial'no izmenit' algoritm raboty allokatora.
template<class T, class A> T* temporary_dup(vector<T,A>& v)
{
T* p=get_temporary_buffer<T>(v.size()).first;
if (p==0) return 0;
copy(v.begin(),v.end(),raw_storage_iterator<T*,T>(p));
return p;
}
Voobshche govorya, privedennaya funkciya napisana nekorrektno, t.k. ne proveryaetsya vtoroj element vozvrashchaemoj get_temporary_buffer<>() pary. T.k. get_temporary_buffer<>() mozhet vernut' men'she pamyati, chem my zaprosili, to neobhodima drugaya proverka:
template<class T, class A> T* temporary_dup(vector<T,A>& v)
{
pair<T*,ptrdiff_t> p(get_temporary_buffer<T>(v.size()));
if (p.second<v.size()) {
if (p.first) return_temporary_buffer(p.first);
return 0;
}
copy(v.begin(),v.end(),raw_storage_iterator<T*,T>(p));
return p.first;
}
assign(s,n,x) pri pomoshchi assign(s[i],x) prisvaivaet n kopij x stroke s.compare() ispol'zuet dlya sravneniya simvolov lt() i eq().
K schast'yu, dlya obychnyh simvolov char_traits<char> eto ne tak, v tom smysle, chto ne proishodit vyzov v cikle lt(), eq(), assign(s[i],x), a ispol'zuyutsya special'no dlya etogo prednaznachennye memcmp() i memset(), chto, vprochem, ne vliyaet na konechnyj rezul'tat. T.e. ispol'zuya strcmp() my nichego ne vyigryvaem, dazhe bolee togo, v special'no provedennyh mnoj izmereniyah proizvoditel'nosti, sravneniya string okazalis' na 30% bystree, chem prinyatoe v C sravnenie char* s pomoshch'yu strcmp(). CHto i ne udivitel'no: dlya string razmery sravnivaemyh massivov char izvestny zaranee.
basic_string hranit dlinu stroki, ne polagayas' na zavershayushchij simvol (nol').
Vmeste s tem, horosho optimizirovannye realizacii hranyat stroku vmeste s zavershayushchim nulem, daby maksimal'no uskorit' funkciyu basic_string::c_str(). Ne sekret, chto bol'shinstvo ispol'zuemyh funkcij (tradicionno) prinimayut stroku v vide [const] char* vmesto ekvivalentnogo po smyslu [const] string&, ishodya iz togo prostogo fakta, chto my ne mozhem uskorit' "bezopasnuyu" realizaciyu, no mozhem skryt' effektivnuyu za bezopasnym interfejsom.
K slovu skazat', moj lichnyj opyt svidetel'stvuet o tom, chto sluhi ob opasnosti manipulirovaniya prostymi char* v stile C okazyvayutsya sil'no preuvelichennymi. Da, vy dolzhny sledit' za vsemi melochami, no, naprimer, ni u kogo ne voznikaet protesta po povodu togo, chto esli v formule kornej kvadratnogo uravneniya my vmesto '-' napishem '+', to rezul'tat budet neveren.
Rezyumiruya dannyj abzac, hochu skazat', chto string ispol'zovat' mozhno i nuzhno, no esli logika raboty vashej programmy intensivno ispol'zuet manipulyacii so strokami, stoit podumat' o razrabotke sobstvennyh sredstv, osnovannyh na funkciyah tipa memcpy(), a v "uzkih" mestah bez etogo prosto ne obojtis'.
YA by poprosil vas ser'ezno otnestis' k dannomu sovetu (t.e. k proverke imeyushchejsya realizacii). Naprimer, sgi STL 3.2 vsegda kopiruet simvoly stroki, ne polagayas' na osnovannuyu na podschete ssylok versiyu. Avtory biblioteki ob座asnyayut eto tem, chto ispol'zuyushchie model' podscheta ssylok stroki ne podhodyat dlya mnogopotochnyh prilozhenij.
Imi utverzhdaetsya, chto ispol'zuyushchie dannuyu realizaciyu strok mnogopotochnye prilozheniya avarijno zavershayut svoyu rabotu odin raz v neskol'ko mesyacev i imenno iz-za strok. V principe, model' podscheta ssylok dejstvitel'no ploho podhodit dlya mnogopotochnyh prilozhenij, t.k. ee ispol'zovanie privodit k sushchestvennym nakladnym rashodam (bolee podrobno ob etom mozhno pochitat' u Herb Sutter Reference Counting - Part III), no vot sobstvenno avarijnoe zavershenie raboty mozhet byt' vyzvano tol'ko oshibkami v realizacii -- chudes ne byvaet.
Kak by to ni bylo, no fakt ostaetsya faktom: sushchestvuyut otlichno optimizirovannye realizacii standartnoj biblioteki, kotorye, po tem ili inym prichinam, otkazalis' ot ispol'zovaniya osnovannyh na podschete ssylok strok.
Rezyumiruya dannyj material hochu otmetit', chto ya vsegda, gde eto vozmozhno, starayus' izbegat' kopirovaniya strok, naprimer putem peredachi const string&.
(cerr.operator<<("x=")).operator<<(x);
Konechno zhe na samom dele vse ne tak: v novyh potokah vvoda-vyvoda operator vyvoda stroki bol'she ne yavlyaetsya funkciej-chlenom, sledovatel'no ono budet interpretirovano tak:
operator<<(cerr,"x=").operator<<(x);Tovarishchi programmisty! Eshche raz povtoryu: nikogda ne kopirujte blokami staryj tekst, a esli eto vse-taki neobhodimo, -- obyazatel'no proveryajte kazhduyu zagogulinu!
Vot grazhdanin Straustrup zabyl proverit', i, v rezul'tate, novyj reliz ego monografii soderzhit ochevidnuyu oshibku.
Vynuzhden vas ogorchit': opredelennye standartom potoki C++ zayavlennym svojstvom ne obladayut. Oni vsegda rabotayut medlennee C, a v nekotoryh realizaciyah -- medlenno do smeshnogo (pravda, ob容ktivnosti radi stoit otmetit', chto mne popadalis' i sovershenno otvratitel'no realizovannye FILE* potoki C, v rezul'tate chego C++ kod vyryvalsya vpered; no eto prosto nedorazumenie, esli ne skazat' krepche!). Rassmotrim sleduyushchuyu programmu:
#include <stdio.h>
#include <time.h>
#include <io.h> // dlya open()
#include <fcntl.h>
#include <iostream>
#include <fstream>
using namespace std;
void workc(char*);
void workcpp(char*);
void work3(char*);
int main(int argc, char **argv)
{
if (argc==3)
switch (*argv[2]-'0') {
case 1: {
workc(argv[1]);
break;
}
case 2: {
workcpp(argv[1]);
break;
}
case 3: {
work3(argv[1]);
break;
}
}
}
void workc(char* fn)
{
FILE* fil=fopen(fn, "rb");
if (!fil) return;
time_t t1; time(&t1);
long count=0;
while (getc(fil)!=EOF)
count++;
time_t t2; time(&t2);
fclose(fil);
cout<<count<<" bytes per "<<t2-t1<<" sec.\n" ;
}
void workcpp(char* fn)
{
ifstream fil(fn, ios_base::in|ios_base::binary);
if (!fil) return;
time_t t1; time(&t1);
long count=0;
while (fil.get()!=EOF)
count++;
time_t t2; time(&t2);
cout<<count<<" bytes per "<<t2-t1<<" sec.\n" ;
}
class File {
int fd; // deskriptor fajla
unsigned char buf[BUFSIZ]; // bufer standartnogo razmera
unsigned char* gptr; // sleduyushchij chitaemyj simvol
unsigned char* bend; // konec dannyh
int uflow();
public:
File(char* fn) : gptr(0), bend(0) { fd=open(fn, O_RDONLY|O_BINARY); }
~File() { if (Ok()) close(fd); }
int Ok() { return fd!=-1; }
int gchar() { return (gptr<bend) ? *gptr++ : uflow(); }
};
int File::uflow()
{
if (!Ok()) return EOF;
int rd=read(fd, buf, BUFSIZ);
if (rd<=0) { // oshibka ili EOF
close(fd);
fd=-1;
return EOF;
}
gptr=buf;
bend=buf+rd;
return *gptr++;
}
void work3(char* fn)
{
File fil(fn);
if (!fil.Ok()) return;
time_t t1; time(&t1);
long count=0;
while (fil.gchar()!=EOF)
count++;
time_t t2; time(&t2);
cout<<count<<" bytes per "<<t2-t1<<" sec.\n" ;
}
Ee nuzhno zapuskat' s dvu