double dji_index = inner_product( // умножаем пары (weight,value)
// и суммируем
dow_price.begin,dow_price.end,
dow_weight.begin,
0.0);
cout << "Значение DJI" << dji_index << '\n';
Обратите внимание на то, что алгоритм
inner_product
получает две последовательности. В то же время он получает только три аргумента: у второй последовательности задается только начало. Предполагается, что вторая последовательность содержит не меньше элементов,
чем первая. В противном случае мы получим сообщение об ошибке во время выполнения программы. В алгоритме
inner_product
вторая последовательность вполне может содержать больше элементов, чем первая; лишние элементы просто не будут использоваться.
Две последовательности не обязательно должны иметь одинаковый тип или содержать элементы одинаковых типов. Для того чтобы проиллюстрировать это утверждение, мы записали цены в объект класса
vector
, а веса — в объект класса
list
.
21.5.4. Обобщение алгоритма inner_product
Алгоритм
inner_product
можно обобщить так же, как и алгоритм
accumulate
. Однако в отличие от предыдущего обобщения алгоритму
inner_product
нужны еще два аргумента: первый — для связывания аккумулятора с новым значением, точно так же как в алгоритме
T inner_product(In first,In last,In2 first2,T init,
BinOp op,BinOp2 op2)
{
while(first!=last) {
init = op(init,op2(*first,*first2));
++first;
++first2;
}
return init;
}
В разделе 21.6.3 мы еще вернемся к примеру с индексом Доу–Джонса и используем обобщенную версию алгоритма
inner_product
как часть более элегантного решения задачи.
21.6. Ассоциативные контейнеры
После класса
vector
вторым по частоте использования, вероятно, является стандартный контейнер
map
, представляющий собой упорядоченную последовательность пар (ключ,значение) и позволяющий находить значение по ключу; например, элемент
my_phone_book["Nicholas"]
может быть телефонным номером Николаса. Единственным достойным конкурентом класса map по популярности является класс
unordered_map
(см. раздел 21.6.4), оптимизированный для ключей, представляющих собой строки. Структуры данных, аналогичные контейнерам
map
и
unordered_map
, известны под разными названиями, например ассоциативные массивы (associative arrays), хеш-таблицы (hash tables) и красно-черные деревья (red-black trees). Популярные и полезные понятия всегда имеют много названий. Мы будем называть их всех ассоциативными контейнерами (associative containers).
В стандартной библиотеке предусмотрены восемь ассоциативных контейнеров.
Эти контейнеры определены в заголовках
<map>
,
<set>
,
<unordered_map>
и
<unordered_set>
.
21.6.1. Ассоциативные массивы
Рассмотрим более простую задачу: создадим список номеров вхождений слов в текст. Для этого вполне естественно записать список слов вместе с количеством их вхождений в текст. Считывая новое слово, мы проверяем, не появлялось ли оно ранее; если нет, вставляем его в список и связываем с ним число 1. Для этого можно было бы использовать объект типа
list
или
vector
, но тогда мы должны были бы искать каждое считанное слово. Такое решение было бы слишком медленным. Класс
map
хранит свои ключи так, чтобы их было легко увидеть, если они там есть. В этом случае поиск становится
тривиальной задачей.
int main
{
map<string,int> words; // хранит пары (слово, частота)
string s;
while (cin>>s) ++words[s]; // контейнер words индексируется
// строками
typedef map<string,int>::const_iterator Iter;
for (Iter p = words.begin; p!=words.end; ++p)
cout << p–>first << ": " << p–>second << '\n';
}
Самой интересной частью этой программы является выражение
++words[s]
. Как видно уже в первой строке функции
main
, переменная
words
— это объект класса map, состоящий из пар (
string
,
int
); т.е. контейнер
words
отображает строки
string
в целые числа
int
. Иначе говоря, имея объект класса
string
, контейнер
words
дает нам доступ к соответствующему числу типа
int
. Итак, когда мы индексируем контейнер words объектом класса
string
(содержащим слово, считанное из потока ввода), элемент
words[s]
является ссылкой на число типа
int
, соответствующее строке
s
. Рассмотрим конкретный пример.
words["sultan"]
Если строки "
sultan
" еще не было, то она вставляется в контейнер
words
вместе со значением, заданным по умолчанию для типа
int
, т.е.
0
. Теперь контейнер
words
содержит элемент
("sultan", 0
). Следовательно, если строка "
sultan
" ранее не вводилась, то выражение
++words["sultan"]
свяжет со строкой "
sultan
" значение
1
. Точнее говоря, объект класса map выяснит, что строки "
sultan
" в нем нет, вставит пару
("sultan",0
), а затем оператор
++
увеличит это значение на единицу, в итоге оно станет равным
1
.
Проанализируем программу еще раз: выражение
++words[s]
получает слово из потока ввода и увеличивает его значение на единицу. При первом вводе каждое слово получает значение
1
. Теперь смысл цикла становится понятен.
while (cin>>s) ++words[s];
Он считывает каждое слово (отделенное пробелом) из потока ввода и вычисляет количество его вхождений в контейнер. Теперь нам достаточно просто вывести результат. По контейнеру
map
можно перемещаться так же, как по любому другому контейнеру из библиотеки STL. Элементы контейнера
map<string,int>
имеют тип
pair<string,int>
. Первый член объекта класса pair называется
first
, второй —
second
. Цикл вывода выглядит следующим образом:
typedef map<string,int>::const_iterator Iter;
for (Iter p = words.begin; p!=words.end; ++p)
cout << p–>first << ": " << p–>second << '\n';
Оператор
typedef
(см. разделы 20.5 и A.16) предназначен для обеспечения удобства работы и удобочитаемости программ. В качестве текста мы ввели в программу вступительный текст из первого издания книги The C++ Programming Language.
C++ is a general purpose programming language designed to make
programming more enjoyable for the serious programmer. Except
for minor details, C++ is a superset of the C programming language.
In addition to the facilities provided by C, C++ provides flexible and