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

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

Как видите, все реализуется достаточно прямолинейно. Основные затруднения связаны с выбором алгоритма поиска (binary_search, lower_bound и т. д.), но в этом вам поможет совет 45.

При переходе от map/multimap к контейнеру vector ситуация становится более интересной, поскольку vector должен содержать объекты pair, входящие в map/ multimap. Но при объявлении объекта типа map(или его multimap-аналога) элементы, хранящиеся в контейнере, в действительности относятся к типу pair К, V>. Чтобы эмулировать map или multimap на базе vector, признак константности необходимо устранить, поскольку в процессе сортировки элементы вектора перемещаются посредством присваивания, а это означает, что оба компонента пары должны допускать присваивание. Следовательно, при эмуляции mapна базе vector данные, хранящиеся в векторе, должны относиться к типу pair, а не pair.

Содержимое map/multimap хранится в отсортированном виде, но при сортировке учитывается только ключевая составляющая элемента (первый компонент пары), поэтому при сортировке vector должно происходить то же самое. Нам придется написать собственную функцию сравнения для пар, поскольку оператор < типа pair сравнивает обе составляющие пары.

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

typedef pair 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. Перед нами практически буквальное переложение комментариев, приведенных ранее, если не считать присутствия функции keyLess, предназначенной для согласования функций operator(). Каждая функция просто сравнивает два ключа, поэтому, чтобы не программировать одни и те же действия дважды, мы производим проверку в keyLess, а функция operator() возвращает полученный результат. Конечно, этот прием упрощает сопровождение DataCompare, однако у него есть один недостаток: наличие функций operator() с разными типами параметров исключает адаптацию объектов функций (см. совет 40). С этим ничего не поделаешь.

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

vector vd;// Альтернатива для map

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

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

// (при эмуляции 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 [] возвращает ссылку на созданный объект.