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

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

Содержание раздела