C++ 3d.Комментарии



STL-контейнеры - часть 2


Т.к. 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;




Содержание  Назад  Вперед