Эффективное использование STL, Мейерс Скотт

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

на обложку

Мейерс Скотт

Шрифт:

Контейнер

map

эмулируется на базе сортированного вектора практически так же, как и контейнер

set

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

DataCompare

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

… // Подготовительная фаза: много вставок,

// мало операций поиска

sort(vd.begin, vd.end, DataCompare); // Конец подготовительной фазы

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

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

// stable_sort - см. совет 31)

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

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

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

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

vector<Data>::iterator i = lower_bound(vd.begin, vd.end.s,

DataCompare); // Поиск с применением

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

//!(i->first<s)) описана

//в совете 45

pair<vector<Data>::iterator, vector<Data>::iterator> range =

equal_range(vd.begin, vd.end, s, DataCompare); // Поиск с применением

if (range.first != range.second)… // equal_range

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

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

sort(vd.begin, vd.end, DataCompare); //Начало новой фазы поиска…

Как видите, после написания

DataCompare

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

map

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

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

Допустим, у нас имеется класс

Widget

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

class Widget {

public:

Widget;

Widget(double weight);

Widget& operator=(double weight);

…

};

Предположим, мы хотим создать контейнер

map

, ассоциирующий

int

Widget

, и инициализировать созданное множество конкретными значениями. Все выглядит очень просто:

map<int, Widget> 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<K, V> m

команда

m[k]=v;

проверяет, присутствует ли ключ

в контейнере. Если ключ отсутствует, он добавляется вместе с ассоциированным значением

. Если ключ уже присутствует, ассоциированное с ним значение заменяется на

Для этого

operator[]

возвращает ссылку на объект значения, ассоциированного с ключом

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

operator[]

. Но при отсутствии ключа

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

operator[]

возвращает ссылку на созданный объект.

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

map<int, Widget> m;

m[1]=1.50;

Выражение

m[1]

представляет собой сокращенную запись для

m.operator[](1)