bool operatorO(const Data::first type& k, Функция сравнения

const Data& rhs) const для поиска (форма 2)

return keyLess(к.rhs.first):

private: Настоящая функция

bool keyLess(const Data::first type& kl, сравнения

const Data:;first type& k2) const

return kl < k2;

В данном примере предполагается, что сортированный вектор эмулирует map<string, int>. Перед нами практически буквальное переложение комментариев, приведенных ранее, если не считать присутствия функции keyLess, предназначенной для согласования функций operatorO. Каждая функция просто сравнивает два ключа, поэтому, чтобы не программировать одни и те же действия дважды, мы производим проверку в keyLess, а функция operatorO возвращает ползенный результат. Конечно, этот прием упрощает сопровождение DataCompare, однако у него есть один недостаток: наличие функций operatorO с разными типами параметров исключает адаптацию объектов функций (см. совет 40). С этим ничего не поделаешь.

Контейнер тар эмулируется на базе сортированного вектора практически так же, как и контейнер set. Единственное принципиальное отличие заключается в том, что в качестве функций сравнения используются объекты DataCompare:

vector<Widget> vd: Альтернатива для map<string,int>

Подготовительная фаза: много вставок, мало операций поиска

объекта pair, но поиск выполняется только по значению ключа. С другой стороны, функция сравнения, используемая при поиске, должна ползать два разнотипных объекта - объект с типом ключа (искомое значение) и pair (одна из пар, хранящихся в векторе). Но это еще не все: мы не знаем, что передается в первом аргументе - ключ или pair, поэтому в действительности для поиска необходимы две функции: одна получает ключ, а другая - объект pair. В следующем примере объединено все сказанное ранее:

typedef pair<string,int> Data; Тип, хранимый в тар в данном примере

class DataCompare{ Класс для функций сравнения public:

bool operatorO(const Data& Ihs, Функция сравнения

const Data& rhs) const для сортировки

return keyLess(lhs.first.rhs.first); Определение keyLess

} приведено ниже

bool operatorO(const Data& Ihs, Функция сравнения

const Data:;first type& k) const для поиска (форма 1)

return keyLess(1hs.fi rst,rhs.fi rst):

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

map<int.Widget> m:

m[l]=1.50; m[2]=3.67:

sortCvd.beginO.vd.endO.DataCompareO); Конец подготовительной фазы

(при эмуляции multiset можно

воспользоваться алгоритмом

stable sort - см. совет 31) string s: Объект с искомым значением

Начало фазы поиска if (binary search(vd.begin().vd.end().s,DataCompare()))... Поиск

с применением binary search

vector<Data>::iterator i = 1ower bound(vd.begi n().vd.end О.s,

DataCompareO): Поиск с применением

if (i!=vd.end() && !(i->first<s))... lower bound: конструкция

!(i->first<s)) описана в совете 45

pa i r<vector<Data>::i terator.

vector<Data>::iterator> range = equal range(vd.begin() .vd.endO ,s.

DataCompareO): Поиск с применением

if (range, first != range, second)... equal range

Конец фазы поиска, начало фазы реорганизации sort(vd.begin(),vd.end(),DataCompareO): Начало новой фазы поиска...

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

Совет 24. Тщательно выбирайте между nnap::operator[] и тар::insert

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

class Widget { public: WidgetO:

Widget(double weight):

Widgets operator=(double weight):

т[3]=10.5: т[4]=45.8; т[5]=0.0003;

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

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

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

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

map<int.Widget> m; m[l]=1.50:

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

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

т[1]=1.50:

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

typedef map<1nt.Widget> intWidgetMap: Вспомогательное определение типа

pair<intWidgetMap;:iterator.bool> result = Создание нового

m.insertCintWidgetMap::value type(l.Widget())); элемента с ключом 1

и ассоциированным объектом, созданным конструктором по умолчанию: комментарии по поводу value type приведены далее

result.first->second = 1.50; Присваивание значения

созданному объекту