Рассмотрим графическую иллюстрацию поиска в (неупорядоченном) векторе, сбалансированном бинарном дереве и хеш-таблице.
• Поиск в неупорядоченном контейнере
vector
.
• Поиск в контейнере
map
(сбалансированном бинарном дереве).
• Поиск в контейнере
unordered_map
(хеш-таблица).
Контейнер
unordered_map
из библиотеки STL реализован с помощью хештаблицы, контейнер
map
— на основе сбалансированного бинарного дерева, а контейнер
vector
— в виде массива. Полезность библиотеки STL частично объясняется тем, что она позволила объединить в одно целое разные способы хранения данных и доступа к ним, с одной стороны, и алгоритмы, с другой.
Эмпирическое правило гласит следующее.
• Используйте контейнер
vector
, если у вас нет веских оснований не делать этого.
• Используйте контейнер
map
, если вам необходимо выполнить поиск по значению (и если тип ключа позволяет эффективно выполнять операцию “меньше”).
• Используйте контейнер
unordered_map
, если вам необходимо часто выполнять поиск в большом ассоциативном массиве и вам не нужен упорядоченный обход (и если тип вашего ключа допускает эффективное использование хеш-функций).
Мы не будем подробно описывать контейнер
unordered_map
. Его можно использовать с ключом типа
string
или
int
точно так же, как контейнер map, за исключением того, что при обходе элементов они не будут упорядочены. Например, мы могли бы переписать фрагмент кода для вычисления индекса- Доу–Джонса из раздела 21.6.3 следующим образом:
unordered_map<string,double> dow_price;
typedef unordered_map<string,double>::const_iterator Dow_iterator;
for (Dow_iterator p = dow_price.begin(); p!=dow_price.end(); ++p) {
const string& symbol = p–>first; // the "ticker" symbol
cout << symbol << '\t'
<< p–>second << '\t'
<< dow_name[symbol] << '\n';
}
Теперь поиск в контейнере
dow
можно выполнять быстрее. Однако это ускорение может оказаться незаметным, поскольку в этот индекс включены только тридцать компаний. Если бы мы учли цены акций всех компаний, котирующихся на нью-йоркской фондовой бирже, то сразу почувствовали бы разницу в производительности работы программы. Отметим пока лишь логическое отличие: данные на каждой итерации выводятся не в алфавитном порядке.
Неупорядоченные ассоциативные массивы в стандарте языка С++ являются новшеством и еще не стали полноправным его элементом, поскольку они описаны в техническом отчете Комиссии по стандартизации языка С++ (Technical Report), а не в тексте самого стандарта. Тем не менее они широко распространены, а там, где их нет, часто можно обнаружить их аналоги, например, что-нибудь вроде класса
hash_map
.
ПОПРОБУЙТЕ
Напишите небольшую программу, используя директиву
#include<unordered_map>
. Если она не работает, значит, класс
unordered_map
не был включен в вашу реализацию языка C++. Если вам действительно нужен контейнер
unordered_map
, можете загрузить одну из его доступных реализаций из сети веб (см., например, сайт www.boost.org).
21.6.5. Множества
Контейнер
set
можно интерпретировать как ассоциативный массив, в котором значения не важны, или как ассоциативный массив без значений. Контейнер
set
можно изобразить следующим образом:
Например, контейнер
set
, в котором перечислены фрукты (см. раздел 21.6.2), можно представить следующим образом:
Чем полезны контейнеры
set
? Оказывается, существует много проблем, при решении которых следует помнить, видели ли мы уже какое-то значение или нет. Один из примеров — перечисление имеющихся фруктов (независимо от цены); второй пример — составление словарей. Немного другой способ использования этого контейнера — множество “записей”, элементы которого являются объектами, потенциально содержащими много информации, в которых роль ключа играет один из их членов. Рассмотрим пример.
struct Fruit {
string name;
int count;
double unit_price;
Date last_sale_date;
// ...
};
struct Fruit_order
{
bool operator()(const Fruit& a, const Fruit& b) const
{
return a.name<b.name;
}
};
set<Fruit, Fruit_order> inventory; // использует функции класса
// Fruit_Order для сравнения
// объектов класса Fruit
Здесь мы снова видим, что объект-функция значительно расширяет спектр задач, которые удобно решать с помощью компонентов библиотеки STL.
Поскольку контейнер
set
не имеет значений, он не поддерживает операцию индексирования (
operator[]()
). Следовательно, вместо нее мы должны использовать “операции над списками”, такие как
insert()
и
erase()
. К сожалению, контейнеры
map
и
set
не поддерживают функцию
push_back()
по очевидной причине: место вставки нового элемента определяет контейнер
set
, а не программист.
