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



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 элементов, а затем проходит по списку.




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