Эффективное использование STL полностью

// (при эмуляции multiset можно // воспользоваться алгоритмом // stable_sort - см. совет 31)

string s;// Объект с искомым значением

// Начало фазы поиска

if (binary_search(vd.begin(),vd.end(),s,DataCompare()))... // Поиск

// с применением binary_search

vector::iterator i = 1ower_bound(vd.begin(),vd.end().s, DataCompareO): if (i!=vd.end() && !(i->first

//Поиск с применением

//lower_bound: конструкция

//!(i->first

//в совете 45

pair::iterator.

vector::iterator> range = equal_range(vd.begin() .vd.end() ,s. DataCompareO): if (range, first !- range, second)...

//Поиск с применением

//equal_range

//Конец фазы поиска,

//начало фазы реорганизации

//Начало новой фазы поиска...

sort(vd.begin(),vd.end(),DataCompare());

Как видите, после написания DataCompare все более или менее становится на свои места. Показанное решение часто быстрее работает и расходует меньше памяти, чем аналогичная архитектура с настоящим контейнером map — при условии, что операции со структурой данных в вашей программе делятся на фазы, описанные на с. 99. Если подобное деление на фазы не соблюдается, использование сортированного вектора вместо стандартных ассоциативных контейнеров почти всегда оборачивается напрасной тратой времени.

Допустим, у нас имеется класс Widget с конструктором по умолчанию, а также конструктором и оператором присваивания с операндом типа double:

class Widget {

public:

Widget();

Widget(double weight);

Widget& operator=(double weight);

};

Предположим, мы хотим создать контейнер map, ассоциирующий int с Widget, и инициализировать созданное множество конкретными значениями. Все выглядит очень просто:

map m;

m[1]=1.50;

m[2]=3.67;

m[3]=10.5;

m[4]=45.8;

m[5]=0.0003;

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

Функция operator[] контейнеров map никак не связана с функциями operator[] контейнеров vector, deque и string, а также со встроенным оператором [ ], работающим с массивами. Функция map::operator[] упрощает операции «обновления с возможным созданием». Иначе говоря, при наличии объявления map m команда m[k]=v; проверяет, присутствует и ключ к в контейнере. Если ключ отсутствует, он добавляется вместе с ассоциированным значением v. Если ключ уже присутствует, ассоциированное с ним значение заменяется на v.

Для этого operator [] возвращает ссылку на объект значения, ассоциированного с ключом к, после чего v присваивается объекту, к которому относится эта ссылка. При обновлении значения, ассоциированного с существующим ключом, никаких затруднений не возникает — в контейнере уже имеется объект, ссылка на который возвращается функцией operator[]. Но при отсутствии ключа к готового объекта, на который можно было бы вернуть ссылку, не существует. В этом случае объект создается конструктором по умолчанию, после чего operator [] возвращает ссылку на созданный объект.

Вернемся к началу исходного примера:

map m;

m[1]=1.50;

Выражение m[1] представляет собой сокращенную запись для m.operator[](1), поэтому во второй строке присутствует вызов map:: operator[]. Функция должна вернуть ссылку на ассоциированный объект Widget. В данном примере m еще не содержит ни одного элемента, поэтому элемент с ключом 1 не существует. Конструктор по умолчанию создает объект Widget, ассоциируемый с ключом 1, и возвращает ссылку на этот объект. Наконец, созданному объекту Widget присваивается значение 1.50.

Иначе говоря, команда

m[1]=1.50:

функционально эквивалентна следующему фрагменту:

typedef map intWidgetMap: // Вспомогательное определение типа

pair result =//'Создание нового