Шрифт:
// вычисление индекса Доу-Джонса
vector<double> dow_price; // цена акции каждой компании
dow_price.push_back(81.86);
dow_price.push_back(34.69);
dow_price.push_back(54.45);
// ...
list<double> dow_weight; // вес каждой компании в индексе
dow_weight.push_back(5.8549);
dow_weight.push_back(2.4808);
dow_weight.push_back(3.8940);
// ...
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
нужны еще два аргумента: первый — для связывания аккумулятора с новым значением, точно так же как в алгоритме accumulate
, а второй — для связывания с парами значений.
template<class In,class In2,class T,class BinOp,class BinOp2 >
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
. Рассмотрим конкретный пример.