TheLib.Ru » Программирование » Деревяго Сергей » C++ 3rd: комментарии » онлайн-чтение (стр. 3)

 

 




Стр.431: 14.6.3. Отображение исключений



В настоящее время стандарт не поддерживает отображение исключений в std::bad_exception описанным в данном разделе образом. Вот что об этом пишет д-р Страуструп:


The standard doesn't support the mapping of exceptions as I describe it in 14.6.3. It specifies mapping to std::bad_exception for exceptions thrown explicitly within an unexpected() function. This makes std::bad_exception an ordinary and rather pointless exception. The current wording does not agree with the intent of the proposer of the mechanism (Dmitry Lenkov of HP) and what he thought was voted in. I have raised the issue in the standards committee.


Стандарт не поддерживает отображение исключений в том виде, как это было мной описано в разделе 14.6.3. Он специфицирует отображение в std::bad_exception только для исключений, явно возбужденных в функции unexpected(). Это лишает std::bad_exception первоначального смысла, делая его обычным и сравнительно бессмысленным исключением. Текущая формулировка (стандарта) не совпадает с первоначально предложенной Дмитрием Ленковым из HP. Я возбудил соответствующее issue в комитете по стандартизации.



Ну и раз уж столько слов было сказано про формулировку из стандарта, думаю, что стоит ее привести:


15.5.2 Функция unexpected() [except.unexpected]



  1. Если функция со спецификацией исключений возбуждает исключение не принадлежащее ее спецификации, будет вызвана функция
    	void unexpected();

    сразу же после завершения раскрутки стека (stack unwinding).



  2. Функция unexpected() не может вернуть управление, но может (пере)возбудить исключение. Если она возбуждает новое исключение, которое разрешено нарушенной до этого спецификацией исключений, то поиск подходящего обработчика будет продолжен с точки вызова сгенерировавшей неожиданное исключение функции. Если же она возбудит недозволенное исключение, то: Если спецификация исключений не содержит класс std::bad_exception (18.6.2.1), то будет вызвана terminate(), иначе (пере)возбужденное исключение будет заменено на определяемый реализацией объект типа std::bad_exception и поиск соответствующего обработчика будет продолжен описанным выше способом.



  3. Таким образом, спецификация исключений гарантирует, что могут быть возбуждены только перечисленные исключения. Если спецификация исключений содержит класс std::bad_exception, то любое неописанное исключение может быть заменено на std::bad_exception внутри unexpected().






Стр.460: 15.3.2. Доступ к базовым классам



class XX : B { /* ... */ };  // B -- закрытый базовый класс

class YY : B { /* ... */ };  // B -- открытая базовая структура


На самом деле, в оригинале было так:

class XX : B { /* ... */ };  // B -- закрытая база

struct YY : B { /* ... */ };  // B -- открытая база

Т.е. вне зависимости от того, является ли база B классом или структурой, права доступа к унаследованным членам определяются типом наследника: по умолчанию, класс закрывает доступ к своим унаследованным базам, а структура -- открывает.


В принципе, в этом нет ничего неожиданного -- доступ по умолчанию к обычным, не унаследованным, членам задается теми же правилами.




Стр.461: 15.3.2.1. Множественное наследование и управление доступом



... доступ разрешен только в том случае, если он разрешен по каждому из возможных путей.


Тут, конечно, имеет место досадная опечатка, что, кстати сказать, сразу видно из приведенного примера. Т.е. читать следует так: ... если он разрешен по некоторому из возможных путей.




Стр.475: 15.5. Указатели на члены



Поэтому указатель на виртуальный член можно безопасно передавать из одного адресного пространства в другое...


Это утверждение, вообще говоря, неверно и я вам советую никогда так не поступать. Сейчас покажу почему.


Прежде всего, стоит отметить, что в C++ вы не сможете прямо вывести значение указателя на член:

struct S {

       int i;

       void f();

};



void g()

{

 cout<<&S::i;  // ошибка: operator<< не реализован для типа int S::*

 cout<<&S::f;  // ошибка: operator<< не реализован для типа void (S::*)()

}

Это довольно странно. Andrew Koenig пишет по этому поводу, что дело не в недосмотре разработчиков библиотеки ввода/вывода, а в том, что не существует переносимого способа для вывода чего-либо содержательного (кстати, я оказался первым, кто вообще об этом спросил, так что проблему определенно нельзя назвать злободневной). Мое же мнение состоит в том, что каждая из реализаций вполне способна найти способ для вывода более-менее содержательной информации, т.к. в данном случае даже неидеальное решение -- это гораздо лучше, чем вообще ничего.


Поэтому для иллюстрации внутреннего представления указателей на члены я написал следующий пример:

#include <string.h>

#include <stdio.h>



struct S {

       int i1;

       int i2;



       void f1();

       void f2();



       virtual void vf1();

       virtual void vf2();

};



const int SZ=sizeof(&S::f1);



union {

      unsigned char c[SZ];

      int i[SZ/sizeof(int)];

      int S::* iptr;

      void (S::*fptr)();

} hack;



void printVal(int s)

{

 if (s%sizeof(int)) for (int i=0; i<s; i++) printf(" %02x", hack.c[i]);

 else for (int i=0; i<s/sizeof(int); i++)

          printf(" %0*x", sizeof(int)*2, hack.i[i]);



 printf("\n");

 memset(&hack, 0, sizeof(hack));

}



int main()

{

 printf("sizeof(int)=%d sizeof(void*)=%d\n", sizeof(int), sizeof(void*));



 hack.iptr=&S::i1;

 printf("sizeof(&S::i1 )=%2d value=", sizeof(&S::i1));

 printVal(sizeof(&S::i1));



 hack.iptr=&S::i2;

 printf("sizeof(&S::i2 )=%2d value=", sizeof(&S::i2));

 printVal(sizeof(&S::i2));



 hack.fptr=&S::f1;

 printf("sizeof(&S::f1 )=%2d value=", sizeof(&S::f1));

 printVal(sizeof(&S::f1));



 hack.fptr=&S::f2;

 printf("sizeof(&S::f2 )=%2d value=", sizeof(&S::f2));

 printVal(sizeof(&S::f2));



 hack.fptr=&S::vf1;

 printf("sizeof(&S::vf1)=%2d value=", sizeof(&S::vf1));

 printVal(sizeof(&S::vf1));



 hack.fptr=&S::vf2;

 printf("sizeof(&S::vf2)=%2d value=", sizeof(&S::vf2));

 printVal(sizeof(&S::vf2));

}



void S::f1() {}

void S::f2() {}



void S::vf1() {}

void S::vf2() {}

Существенными для понимания местами здесь являются объединение hack, используемое для преобразования значения указателей на члены в последовательность байт (или целых), и функция printVal(), печатающая данные значения.


Я запускал вышеприведенный пример на трех компиляторах, вот результаты:

sizeof(int)=4 sizeof(void*)=4

sizeof(&S::i1 )= 8 value= 00000005 00000000

sizeof(&S::i2 )= 8 value= 00000009 00000000

sizeof(&S::f1 )=12 value= 004012e4 00000000 00000000

sizeof(&S::f2 )=12 value= 004012ec 00000000 00000000

sizeof(&S::vf1)=12 value= 004012d0 00000000 00000000

sizeof(&S::vf2)=12 value= 004012d8 00000000 00000000



sizeof(int)=4 sizeof(void*)=4

sizeof(&S::i1 )= 4 value= 00000001

sizeof(&S::i2 )= 4 value= 00000005

sizeof(&S::f1 )= 8 value= ffff0000 004014e4

sizeof(&S::f2 )= 8 value= ffff0000 004014f4

sizeof(&S::vf1)= 8 value= 00020000 00000008

sizeof(&S::vf2)= 8 value= 00030000 00000008



sizeof(int)=4 sizeof(void*)=4

sizeof(&S::i1 )= 4 value= 00000004

sizeof(&S::i2 )= 4 value= 00000008

sizeof(&S::f1 )= 4 value= 00401140

sizeof(&S::f2 )= 4 value= 00401140

sizeof(&S::vf1)= 4 value= 00401150

sizeof(&S::vf2)= 4 value= 00401160

Прежде всего в глаза бросается то, что несмотря на одинаковый размер int и void*, каждая из реализаций постаралась отличиться в выборе представления указателей на члены, особенно первая. Что же мы можем сказать еще?


  1. Во всех трех реализациях указатель на член-данные является смещением -- не прямым адресом. Это вполне логично и из этого следует, что эти указатели можно безопасно передавать из одного адресного пространства в другое.


  2. Указатели на невиртуальные функции члены являются или просто указателем на функцию, или содержат такой указатель в качестве одного из фрагментов. Очевидно, что их передавать в другое адресное пространство нельзя. Впрочем, в этом также нет ничего неожиданного.


  3. А теперь самое интересное -- указатели на виртуальные функции-члены. Как вы можете видеть, только у одного из трех компиляторов они получились похожими на "передаваемые" -- у второго.


Итак, указатели на виртуальные функции-члены можно безопасно передавать в другое адресное пространство чрезвычайно редко. И это правильно! Дело в том, что в определение C++ закралась ошибка: указатели на обычные и виртуальные члены должны быть разными типами. Только в этом случае можно обеспечить оптимальность реализации.


Указатели на функции-члены во втором компиляторе реализованы неоптимально, т.к. иногда они содержат указатель на "обычную" функцию (ffff0000 004014e4), а иногда -- индекс виртуальной функции (00020000 00000008). В результате чего, вместо того, чтобы сразу произвести косвенный вызов функции, компилятор проверяет старшую часть первого int, и если там стоит -1 (ffff), то он имеет дело с обычной функцией членом, иначе -- с виртуальной. Подобного рода проверки при каждом вызове функции-члена через указатель вызывают ненужные накладные расходы.


Внимательный читатель должен спросить: "Хорошо, пусть они всегда содержат обычный указатель на функцию, но как тогда быть с указателями на виртуальные функции? Ведь мы не можем использовать один конкретный адрес, так как виртуальные функции принято замещать в производных классах." Правильно, дорогой читатель! Но выход есть, и он очевиден: в этом случае компилятор автоматически генерирует промежуточную функцию-заглушку.


Например, следующий код:

struct S {

       virtual void vf() { /* 1 */ }

               void f () { /* 2 */ }

};



void g(void (S::*fptr)(), S* sptr)

{

 (sptr->*fptr)();

}



int main()

{

 S s;

 g(S::vf, &s);

 g(S::f , &s);

}

превращается в псевдокод:
void S_vf(S *const this) { /* 1 */ }

void S_f (S *const this) { /* 2 */ }



void S_vf_stub(S *const this)

{

 // виртуальный вызов функции S::vf()

 (this->vptr[index_of_vf])(this);

}



void g(void (*fptr)(S *const), S* sptr)

{

 fptr(sptr);

}



int main()

{

 S s;

 g(S_vf_stub, &s);  // обратите внимание: не S_vf !!!

 g(S_f      , &s);

}

А если бы в C++ присутствовал отдельный тип "указатель на виртуальную функцию-член", он был бы представлен простым индексом виртуальной функции, т.е. фактически простым size_t, и генерации функций-заглушек (со всеми вытекающими потерями производительности) было бы можно избежать. Более того, его, как и указатель на данные-член, всегда можно было бы передавать в другое адресное пространство.




Стр.477: 15.6. Свободная память



// полагаем, что p указывает на s байтов памяти, выделенной Employee::operator new()


Данное предположение не вполне корректно: p также может являться нулевым указателем, и в этом случае определяемый пользователем operator delete() должен корретно себя вести, т.е. ничего не делать.


Запомните: определяя operator delete(), вы обязаны правильно обрабатывать удаление нулевого указателя! Т.о. код должен выглядеть следующим образом:

void Employee::operator delete(void* p, size_t s)

{

 if (!p) return;  // игнорируем нулевой указатель



 // полагаем, что p указывает на s байтов памяти, выделенной

 // Employee::operator new() и освобождаем эту память

 // для дальнейшего использования

}

Интересно отметить, что стандартом специально оговорено, что аргумент p функции
template <class T> void std::allocator::deallocate(pointer p, size_type n);

не может быть нулевым. Без этого замечания использование функции Pool::free в разделе 19.4.2. "Распределители памяти, определяемые пользователем" было бы некорректным.




Стр.478: 15.6. Свободная память



В принципе, освобождение памяти осуществляется тогда внутри деструктора (который знает размер).


Именно так. Т.е. если вы объявили деструктор некоторого класса

A::~A()

{

 // тело деструктора

}

то компилятором (чаще всего) будет сгенерирован следующий код
// псевдокод

A::~A(A *const this, bool flag)

{

 if (this) {

    // тело деструктора

    if (flag) delete(this, sizeof(A));

 }

}

Ввиду чего функция
void f(Employee* ptr)

{

 delete ptr;

}

превратится в
// псевдокод

void f(Employee* ptr)

{

 Employee::~Employee(ptr, true);

}

и т.к. класс Employee имеет виртуальный деструктор, это в конечном итоге приведет к вызову соответствующего метода.




Стр.479: 15.6.1. Выделение памяти под массив



На этом пункте стоит остановиться поподробнее, так как с оператором new[] связаны не вполне очевидные вещи. Не мудрствуя лукаво, привожу перевод раздела 10.3 "Array Allocation" из книги "The Design and Evolution of C++" одного известного автора:


Определенный для класса X оператор X::operator new() используется исключительно для размещения одиночных объектов класса X (включая объекты производных от X классов, не имеющих собственного распределителя памяти). Следовательно

X* p = new X[10];

не вызывает X::operator new(), т.к. X[10] является массивом, а не объектом класса X.


Это вызывало много жалоб, т.к. я не разрешил пользователям контролировать размещение массивов типа X. Однако я был непреклонен, т.к. массив элементов типа X -- это не объект типа X, и, следовательно, распределитель памяти для X не может быть использован. Если бы он использовался и для распределения массивов, то автор X::operator new() должен был бы иметь дело как с распределением памяти под объект, так и под массив, что сильно усложнило бы более распространенный случай. А если распределение памяти под массив не очень критично, то стоит ли вообще о нем беспокоиться? Тем более, что возможность управления размещением одномерных массивов, таких как X[d] не является достаточной: что, если мы захотим разместить массив X[d][d2]?


Однако, отсутствие механизма, позволяющего контролировать размещение массивов вызывало определенные сложности в реальных программах, и, в конце концов, комитет по стандартизации предложил решение данной проблемы. Наиболее критичным было то, что не было возможности запретить пользователям размещать массивы в свободной памяти, и даже способа контролировать подобное размещение. В системах, основанных на логически разных схемах управления размещением объектов это вызывало серьезные проблемы, т.к. пользователи наивно размещали большие динамические массивы в обычной памяти. Я недооценил значение данного факта.


Принятое решение заключается в простом предоставлении пары функций, специально для размещения/освобождения массивов:

class X {

      // ...

      void* operator new(size_t sz);    // распределение объектов

      void operator delete(void* p);



      void* operator new[](size_t sz);  // распределение массивов

      void operator delete[](void* p);

};

Распределитель памяти для массивов используется для массивов любой размерности. Как и в случае других распределителей, работа operator new[] состоит в предоставлении запрошенного количества байт; ему не нужно самому беспокоиться о размере используемой памяти. В частности, он не должен знать о размерности массива или количестве его элементов. Laura Yaker из Mentor Graphics была первой, кто предложил операторы для размещения и освобождения массивов.




Стр.480: 15.6.2. "Виртуальные конструкторы"



... допускаются некоторые ослабления по отношению к типу возвращаемого значения.


Следует отметить, что эти "некоторые ослабления" не являются простой формальностью. Рассмотрим следующий пример:

#include <stdio.h>



struct B1 {

       int b1;  // непустая

       virtual ~B1() { }

};



struct B2 {

       int b2;  // непустая



       virtual B2* vfun()

       {

        printf("B2::vfun()\n");  // этого мы не должны увидеть

        return this;

       }

};



struct D : B1, B2 {  // множественное наследование от непустых классов

       virtual D* vfun()

       {

        printf("D::vfun(): this=%p\n", this);

        return this;

       }

};



int main()

{

 D d;



 D* dptr=&d;

 printf("dptr\t%p\n", dptr);



 void* ptr1=dptr->vfun();

 printf("ptr1\t%p\n", ptr1);



 B2* b2ptr=&d;

 printf("b2ptr\t%p\n", b2ptr);



 void* ptr2=b2ptr->vfun();

 printf("ptr2\t%p\n", ptr2);

}

Обратите внимание: в данном примере я воспользовался "некоторыми ослаблениями" для типа возвращаемого значения D::vfun(), и вот к чему это привело:
dptr    0012FF6C

D::vfun(): this=0012FF6C

ptr1    0012FF6C

b2ptr   0012FF70

D::vfun(): this=0012FF6C

ptr2    0012FF70

Т.о. оба раза была вызвана D::vfun(), но возвращаемое ей значение зависит от способа вызова (ptr1!=ptr2), как это, собственно говоря, и должно быть.


Делается это точно так же, как уже было описано в разделе 361 "12.2.6. Виртуальные функции", только помимо корректировки принимаемого значения this необходимо дополнительно произвести корректировку this возвращаемого. Понятно, что виртуальные функции с ковариантным типом возврата встречаются настолько редко, что реализация их вызова посредством расширения vtbl вряд ли может быть признана адекватной. На практике обычно создаются специальные функции-заглушки, чьи адреса помещаются в соответствующие элементы vtbl:

// псевдокод



// оригинальная D::vfun, написанная программистом

D* D::vfun(D *const this)

{

 // ...

}



// сгенерированная компилятором функция-заглушка для вызова D::vfun() через

// указатель на базовый класс B2

B2* D::vfun_stub(B2 *const this)

{

 return D::vfun(this+delta_1)+delta_2;

}

где возвращаемый функцией указатель корректируется посредством константы delta_2, вообще говоря, не равной delta_1.


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


10.3. Виртуальные функции [class.virtual]



  1. Тип возвращаемого значения замещающей функции может быть или идентичен типу замещаемой функции или быть ковариантным (covariant). Если функция D::f замещает функцию B::f, типы возвращаемых ими значений будут ковариантными, если они удовлетворяют следующим условиям:


    • они оба являются указателями или ссылками на класс (многоуровневые указатели или ссылки на многоуровневые указатели запрещены)


    • класс в возвращаемом значении B::f идентичен классу в возвращаемом значении D::f или он является однозначно определенным открытым прямым или косвенным базовым классом возвращаемого D::f класса и при этом доступен в D


    • как указатели так и ссылки имеют идентичные cv-квалификаторы и, при этом, класс возвращаемого значения D::f имеет те же или меньшие cv-квалификаторы, что и класс в возвращаемом значении B::f.


    Если тип возвращаемого значения D::f отличается от типа возвращаемого значения B::f, то тип класса в возвращаемом значении D::f должен быть завершен в точке определения D::f или он должен быть типом D. Когда замещающая функция будет вызывана (как последняя заместившая функция), тип ее возвращаемого значения будет (статически) преобразован в тип возвращаемого значения замещаемой функции (5.2.2). Например:
    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();  // ошибка: B (базовый класс D) недоступен
    
};
    

    
class A;
    
struct Derived : public Base {
    
 void vf1();     // виртуальная и замещает Base::vf1()
    
 void vf2(int);  // не виртуальная, скрывает Base::vf2()
    
 char vf3();     // ошибка: неправильный тип возвращаемого значения
    
 D*   vf4();     // OK: возвращает указатель на производный класс
    
 A*   vf5();     // ошибка: возвращает указатель на незавершенный класс
    
 void f();
    
};
    

    
void g()
    
{
    
 Derived d;
    
 Base* bp=&d;      // стандартное преобразование: Derived* в Base*
    
 bp->vf1();        // вызов  Derived::vf1()
    
 bp->vf2();        // вызов  Base::vf2()
    
 bp->f();          // вызов  Base::f()  (не виртуальная)
    
 B* p=bp->vf4();   // вызов  Derived::pf() и преобразование
    
                   // возврата в B*
    
 Derived* dp=&d;
    
 D* q=dp->vf4();   // вызов  Derived::pf(), преобразование
    
                   // результата в B* не осуществляется
    
 dp->vf2();        // ошибка: отсутствует аргумент
    
}



А что означает загадочная фраза "меньшие cv-квалификаторы"?


3.9.3. CV-квалификаторы [basic.type.qualifier]



  1. Множество cv-квалификаторов является частично упорядоченным:




























    нет cv-квалификатора < const
    нет cv-квалификатора < volatile
    нет cv-квалификатора < const volatile
    const < const volatile
    volatile < const volatile







Стр.498: 16.2.3. STL-контейнеры



Она явилась результатом целенаправленного поиска бескомпромиссно эффективных общих алгоритмов.


Вместе с тем, не стоит думать, что STL не содержит снижающих эффективность компромиссов. Очевидно, что специально написанный для решения конкретной проблемы код будет работать эффективнее, вопрос в том, насколько эффективнее? Например, если нам нужно просто сохранить в памяти заранее неизвестное количество элементов, а затем их последовательно использовать, то (односвязный) список будет наиболее адекватной структурой данных. Однако STL не содержит односвязных списков, как много мы на этом теряем?


Рассмотрим следующий пример:

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#include <list>



struct List {  // односвязный список

       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) {  // удаляем все элементы

            n=ptr->next;

            delete ptr;

        }

       }



       void push_back(int v)  // добавляем элемент

       {

        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);

 }

}

В нем f1() использует определенный нами List: вставляет 1000 элементов, а затем проходит по списку.


Т.к. STL использует собственный распределитель памяти (вскоре вы увидите, что делает она это совсем не напрасно), то то же самое следует попробовать и нам:

struct List {  // односвязный список

       struct Data {



              // ...



              // для собственного распределения памяти

              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;  // выделяем блоки по sz элементов

 free=reinterpret_cast<Data*>(new char[sz*sizeof(Data)]);



 // сцепляем свободные элементы

 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)

{  // добавляем в начало списка свободных элементов

 Data* ptr=static_cast<Data*>(dl);

 ptr->next=free;

 free=ptr;

}

Обратите внимание, что в данном примере наш распределитель памяти не возвращает полученную память системе. Но это не memory leak (утечка памяти) -- это memory pool, т.е. заранее выделенный запас памяти для быстрого последующего использования. На первый взгляд, разница между memory leak и memory pool может показаться слишком тонкой, но она есть: дело в том, что в первом случае потребление памяти не ограничено, вплоть до полного ее исчерпания, а во втором оно никогда не превысит реально затребованного программой объема плюс некоторая дельта, не превосходящая размер выделяемого блока.


И еще, наш распределитель содержит очень серьезную ошибку -- он неправильно обрабатывает удаление нуля (NULL-указателя). В нашем примере это не имеет значения, но в реальном коде вы обязаны это учесть, т.е.:

inline void List::Data::operator delete(void* dl, size_t)

{

 if (!dl) return;  // игнорируем NULL



 // добавляем в начало списка свободных элементов

 Data* ptr=static_cast<Data*>(dl);

 ptr->next=free;

 free=ptr;

}

И, для чистоты эксперимента, в заключение попробуем двусвязный список -- его по праву можно назвать вручную написанной альтернативой std::list<int>:
struct DList {  // двусвязный список

       struct Data {

              int val;

              Data *prev, *next;



              Data(int v, Data* p=0, Data* n=0) : val(v), prev(p), next(n) {}



              // для собственного распределения памяти

              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) {  // удаляем все элементы

            n=ptr->next;

            delete ptr;

        }

       }



       void push_back(int v)  // добавляем элемент

       {

        if (!head) head=tail=new Data(v);

        else tail=tail->next=new Data(v, tail);

       }

};

Итак, все готово, и можно приступать к тестированию. Данные три теста я попробовал на двух разных компиляторах, вот результат:



































  односвязный односвязный с собственным
распределителем памяти		 двусвязный с собственным
распределителем памяти
f1() f2() f1() f2() f1() f2()
реализация 1 9.6 12.1 1.1 12.1 1.3 12.1
реализация 2 20.2 2.5 1.8 2.5 1.9 2.5


И что же мы здесь видим?



  • добавление собственного распределителя памяти существенно ускоряет программу (в нашем примере, от 9 до 11 раз). Также замечу, что это приводит и к существенной экономии памяти (как правило, для борьбы с внутренней фрагментацией стандартные распределители памяти выделяют отрезки памяти, кратные некоторому числу, например 16 байт; плюс память теряется на структурах, поддерживающих список выделенных блоков. Т.е. желательно выделять память большими блоками и как можно реже.


  • в зависимости от качества компилятора/реализации STL, использование STL может быть как почти приемлемым (замедление 30% для двусвязного и 40% для односвязного списков), так и неприемлемым совершенно (замедление от 9 до 11 раз!)


  • двусвязный список является вполне приемлемой альтернативой односвязному (замедление 5 - 20%)


Итак, наши измерения показывают, что бескомпромиссная эффективность STL является мифом. Даже более того, если вы используете недостаточно хороший оптимизатор, то использование STL вызовет существенные накладные расходы.




Стр.505: 16.3.4. Конструкторы



То есть каждый из 10 000 элементов vr инициализируется конструктором Record(), а каждый из s1 элементов контейнера vi инициализируется int().


Инициализация 10 000 элементов конструктором по умолчанию не может не впечатлять -- только в очень редком случае нужно именно это. Если вы выделяете эти 10 000 элементов про запас, для последующей перезаписи, то стоит подумать о следующей альтернативе:

vector<X> vx;          // объявляем пустой вектор

vx.reserve(10000);     // резервируем место воизбежание "дорогих"

                       // перераспределений в push_back()

// ...

vx.push_back(x_work);  // добавляем элементы по мере надобности