Скорее всего, они появятся в следующей версии стандарта C++. См. http: www.sgi.com/tech/stl.

rs.push back( one ):

rs.push back( two ):

rs.push back( three );

rs.push back( four ):

rs.push back( five ):

Ring<str1ng>::iterator it = rs.beginO:

++it: ++it:

it.insert( six ):

it = rs.beginO:

Двукратный перебор элементов кольца: for(int i = 0: i < rs.sizeO * 2: i++) cout *it++ endl: } III:-

Как видите, основной код сосредоточен в классе итератора. Итератор Ring должен уметь возвращаться к началу контейнера, поэтому в нем хранится ссылка на список своего родительского объекта Ring. По этой ссылке итератор узнает, добрался ли он до конца контейнера и как вернуться к началу.

Интерфейс Ring весьма ограничен. В частности, в нем отсутствует функция end(), поскольку при достижении конца происходит переход к началу. А это означает, что Ring не может использоваться с многочисленными алгоритмами STL, для которых необходим конечный итератор (добавление этой возможности оказывается делом нетривиальным). А если это ограничение вас огорчает, вспомните стек, очередь и приоритетную очередь - эти контейнеры вообще не используют итераторов!

Расширения STL

Хотя контейнеры STL обладают практически всеми функциональными возможностями, которые вам могут понадобиться, их набор все же нельзя считать абсолютно универсальным. Например, в стандартных реализациях множеств и отображений используются деревья. Такие реализации работают достаточно быстро, но в какой-то конкретной ситуации может потребоваться еще более высокая скорость. Участники комитета по стандартизации С++ сощлись на том, что в стандартный язык С++ следует включить поддержку хещированных реализаций set и тар, но времени на проработку этих компонентов уже не оставалось, и они так и остались нестандартизованными *.

К счастью, существует целый ряд свободно распространяемых альтернативных рещений. Одно из преимуществ STL состоит в том, что эта библиотека устанавливает базовую модель для создания STL-подобных классов, и тот, кто уже знаком с STL, сможет легко разобраться в других рещениях, основанных на этой модели.

Реализация библиотеки STL от Silicon Graphics, которая называется SGI, принадлежит к числу самых мощных альтернативных реализаций. При желании ею можно заменить реализацию STL ващего компилятора. Кроме того, SGI содержит ряд дополнительных контейнеров, включая хешированное множество (hash set), хещированное мультимножество (hash multiset), хешированное отображение

(hash map), хешированное мультиотображение (hash multimap), односвязный список (slist) и горе (разновидность класса string, оптимизированная для работы с очень большими строками и для быстрых операций конкатенации и выделения подстрок).

Давайте сравним относительное быстродействие реализации тар на базе дерева и хешированной реализации hash map из библиотеки SGI. Для простоты ограничимся отображением int/int:

: C07:MapVsHashMap.cpp

Заголовочный файл hash He входит в стандартную

реализацию STL для С++. Это расширение,

доступное только в SGI STL

(включается в поставку dmc).

{-Ьог}{-msc){-g++}{-mwcc}

linclude <hash map>

linclude <iostream>

linclude <map>

linclude <ctime>

using namespace std;

int main(){ hash map<int. int> hm; map<int. int> m; clock t ticks = clockO; for(int i = 0; i < 100; i++) for(int j = 0; j < 1000; j++) m.insert(make pair(j,j)); cout map insertions: clockO - ticks endl; ticks = clockO; for(int i = 0; i < 100; i++) for(int j = 0; j < 1000; j++) hm.insert(make pai r(j.j)); cout hash map insertions;

clockO - ticks endl; ticks - clockO; for(int i = 0; i < 100; i++) for(int j = 0; j < 1000; j++) m[j];

cout map::operatorC] lookups:

clockO - ticks endl; ticks = clockO; for(int i = 0: i < 100: i++)

for(int j - 0: j < 1000: j++) hm[j];

cout hash map::operator[] lookups:

clockO - ticks endl: ticks = clockO; for(int i = 0: i < 100: i++)

for(int j = 0; j < 1000; j++) m.find(j): cout map::find() lookups:

clockO - ticks endl: ticks = clockO: for(int i = 0: i < 100; i++)

for(int j = 0: j < 1000: j++) hm.find(j): cout hash map::find() lookups:

clockO - ticks endl; } /:-

Другие контейнеры

в стандартную библиотеку входят два контейнера, которые не являются контейнерами STL : bitset и valarray. Иначе говоря, эти контейнеры не удовлетворяют всем требованиям контейнеров STL. Контейнер bitset, описанный ранее в этой главе, пакует биты в целые числа и не поддерживает прямой адресации элементов. Шаблон valarray представляет собой аналог контейнера vector, оптимизированный для эффективных математических вычислений. Ни один из этих контейнеров не поддерживает итераторов. Хотя valarray может специализироваться для нечисловых типов, этот шаблон содержит математические функции, ориентированные на работу с числовыми данными: sin, cos, tan и т. д.

Определим вспомогательный шаблон для вывода элементов valarray:

: C07:PnntValarray.h #ifndef PRINTVALARRAY H #define PRINTVALARRAY H linclude <valarray> linclude <iostream> linclude <cstddef>

tempiate<class T>

void print(const char* Ibl. const valarray<T>& a) { std::cout Ibl : : for(size t i = 0: i < a.sizeO: ++i)

std::cout a[i] : std::cout std::endl:

lendif PRINTVALARRAY H /:-

Большинство функций и операторов valarray ориентировано на работу не с отдельными элементами, а с массивом valarray в целом, как показывает следующий пример:

: C07:Valarrayl.cpp {-Ьог} Базовые возможности valarray linclude PrintValarray.h using namespace std:

double redouble x) { return 2.0 * x - 1.0: }

int mainO { double nC] = {1.0. 2.0. 3.0. 4.0}: valarray<double> v(n. sizeof n / sizeof n[0]); print( v . V):

valarray<double> shCv.shiftd)): print( shift 1 , sh):

Как уже отмечалось, специализация vector<bool> тоже в определенной степени не является контейнером STL.

Согласно результатам хронометража, hash map во всех операциях превосходит тар по скорости примерно в 4 раза (причем, как и ожидалось, функция find() при поиске в обоих типах отображений работает чуть быстрее оператора [ ]). Если про-файлер показывает, что операции с отображением являются узким местом вашего приложения, подумайте о переходе на hash map.