Скотт Мейерс - Эффективное использование STL
typedef pair<string,int> Data; // Тип, хранимый в "map" в данном примере
class DataCompare{// Класс для функций сравнения public:
bool operator()(constData& Ihs, //Функция сравнения
constData& rhs) const //для сортировки
{
return keyLess(Ihs.first,rhs.first); //Определение keyLess
}//приведено ниже
bool operator()(const Data& Ihs.// Функция сравнения
const Data::first_type& k) const // для поиска (форма 1)
{
return keyLess(lhs.first,rhs.first);
bool operator()(const Data::first_type& k.// Функция сравнения
const Data& rhs) const;// для поиска (форма 2)
{
return keyLess(k.rhs.first);
}
private:// "Настоящая" функция
bool keyLess(const Data::first_type& kl.// сравнения
const Data::first_type& k2) const
{
return kl < k2;
}
}
В данном примере предполагается, что сортированный вектор эмулирует map<string,int>. Перед нами практически буквальное переложение комментариев, приведенных ранее, если не считать присутствия функции keyLess, предназначенной для согласования функций operator(). Каждая функция просто сравнивает два ключа, поэтому, чтобы не программировать одни и те же действия дважды, мы производим проверку в keyLess, а функция operator() возвращает полученный результат. Конечно, этот прием упрощает сопровождение DataCompare, однако у него есть один недостаток: наличие функций operator() с разными типами параметров исключает адаптацию объектов функций (см. совет 40). С этим ничего не поделаешь.
Контейнер 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 = 1ower_bound(vd.begin(),vd.end().s, DataCompareO): 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. DataCompareO): 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; проверяет, присутствует и ключ к в контейнере. Если ключ отсутствует, он добавляется вместе с ассоциированным значением v. Если ключ уже присутствует, ассоциированное с ним значение заменяется на v.
Для этого operator [] возвращает ссылку на объект значения, ассоциированного с ключом к, после чего v присваивается объекту, к которому относится эта ссылка. При обновлении значения, ассоциированного с существующим ключом, никаких затруднений не возникает — в контейнере уже имеется объект, ссылка на который возвращается функцией operator[]. Но при отсутствии ключа к готового объекта, на который можно было бы вернуть ссылку, не существует. В этом случае объект создается конструктором по умолчанию, после чего operator [] возвращает ссылку на созданный объект.
Вернемся к началу исходного примера:
map<int,Widget> 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<int,Widget> intWidgetMap: // Вспомогательное определение типа
pair<intWidgetMap::iterator.bool> result =//'Создание нового
m.insert(intWidgetMap::value_type(1,Widget())); // элемента с ключом 1
// и ассоциированным объектом, созданным
// конструктором по умолчанию; комментарии
// по поводу value_type // приведены далее
result.first->second = 1.50;// Присваивание значения
// созданному объекту
Теперь понятно, почему такой подход ухудшает быстродействие программы. Сначала мы конструируем объект Widget, а затем немедленно присваиваем ему новое значение. Конечно, правильнее было бы сразу сконструировать Widget с нужными данными вместо того, чтобы конструировать Widget по умолчанию и затем выполнять присваивание. Следовательно, вызов operator[] было бы правильнее заменить прямолинейным вызовом insert:
m.insert(intWidgetMap::value_type(1,1.50));
С функциональной точки зрения эта конструкция эквивалентна фрагменту, приведенному выше, но она позволяет сэкономить три вызова функций: создание временного объекта Widget конструктором по умолчанию, уничтожение этого временного объекта и оператор присваивания Widget. Чем дороже обходятся эти вызовы, тем большую экономию обеспечивает применение map:: insert вместо map::operator[].
В приведенном выше фрагменте используется определение типа value_type, предоставляемое всеми стандартными контейнерами. Помните, что для map и multimap (а также для нестандартных контейнеров hash_map и hash_multimap — совет 25) тип элемента всегда представляет собой некую разновидность pair.
Я уже упоминал о том, что operator[] упрощает операции «обновления с возможным созданием». Теперь мы знаем, что при создании insert работает эффективнее, чем operator[]. При обновлении, то есть при наличии эквивалентного ключа (см. совет 19) в контейнере map, ситуация полностью меняется. Чтобы понять, почему это происходит, рассмотрим потенциальные варианты обновления:
m[k] = v; // Значение, ассоциируемое
// с ключом к.заменяется на v при помощи оператора []
m.insert(intWidgetMap::value_type(k,v)).first->second = v; // Значение, ассоциируемое
// с ключом к, заменяется на v при помощи insert
Вероятно, один внешний вид этих команд заставит вас выбрать operator[], но в данном случае речь идет об эффективности, поэтому фактор наглядности не учитывается.
При вызове insert передается аргумент типа inWidgetMap::value_type (то есть pair<int,Widget>), потому при вызове insert необходимо сконструировать и уничтожить объект данного типа. Следовательно, при вызове insert будут вызваны конструктор и деструктор pair, что в свою очередь приведет к вызову конструктора и деструктора Widget, поскольку pair<in,Widget> содержит объект Widget. При вызове operator[] объект pair не используется, что позволяет избежать затрат на конструирование и уничтожение pair и Widget.
Следовательно, при вставке элемента в map по соображениям эффективности желательно использовать insert вместо operator[], а при обновлении существующих элементов предпочтение отдается operator[], что объясняется как эффективностью, так и эстетическими соображениями.
Конечно, нам хотелось бы видеть в STL функцию, которая бы автоматически выбирала оптимальное решение в синтаксически привлекательном виде. Интерфейс вызова мог бы выглядеть следующим образом:
