Программирование. Принципы и практика использования C++ Исправленное издание - Бьёрн Страуструп

class="p1">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, а не программист.

Вместо этого следует использовать функцию insert().

inventory.insert(Fruit("quince",5));

inventory.insert(Fruit("apple", 200, 0.37));

Одно из преимуществ контейнера set над контейнером map заключается в том, что мы можем непосредственно использовать значение, полученное от итератора. Поскольку в контейнере set нет пар (ключ, значение), как в контейнере map (см. раздел 21.6.3), оператор разыменования возвращает значение элемента.

typedef set<Fruit>::const_iterator SI;

for (SI p = inventory.begin(),p!=inventory.end(); ++p)

  cout << *p << 'n';

Разумеется, этот фрагмент работает, только если вы определили оператор << для класса Fruit.

21.7. Копирование

В разделе 21.2 мы назвали функцию find() “простейшим полезным алгоритмом”. Естественно, эту точку зрения можно аргументировать. Многие простые алгоритмы являются полезными, даже тривиальными. Зачем писать новую программу, если можно использовать код, который кто-то уже написал и отладил? С точки зрения простоты и полезности алгоритм copy() даст алгоритму find() фору. В библиотеке STL есть три варианта алгоритма copy().

21.7.1. Алгоритм copy()

Основная версия алгоритма copy() определена следующим образом:

template<class In, class Out> Out copy(In first, In last, Out res)

{

  while (first!=last) {

    *res = *first;    // копирует элемент

    ++res;

    ++first;

  }

  return res;

}

Получив пару итераторов, алгоритм copy() копирует последовательность в другую последовательность, заданную итератором на ее первый элемент. Рассмотрим пример.

void f(vector<double>& vd, list<int>& li)

  // копирует элементы списка чисел типа int в вектор чисел типа

  // double

{

  if (vd.size() < li.size()) error("целевой контейнер слишком мал");

  copy(li.begin(), li.end(), vd.begin());

  // ...

}

Обратите внимание на то, что тип входной последовательности может отличаться от типа результирующей последовательности. Это обстоятельство повышает универсальность алгоритмов из библиотеки STL: они работают со всеми видами последовательностей, не делая лишних предположений об их реализации. Мы не забыли проверить, достаточно ли места в результирующей последовательности для записи вводимых элементов. Такая проверка входит в обязанности программиста. Алгоритмы из библиотеки STL программировались для достижения максимальной универсальности и оптимальной производительности; по умолчанию они не проверяют диапазоны и не выполняют других тестов, защищающих пользователей. Каждый раз, когда это требуется, пользователь должен сам выполнить такую проверку. 

21.7.2. Итераторы потоков

 

 Вы часто будете слышать выражения “копировать в поток вывода” или “копировать из потока ввода”. Это удобный и полезный способ описания некоторых видов ввода-вывода. Для выполнения этой операции действительно использует алгоритм copy().

Напомним свойства последовательностей.

• Последовательность имеет начало и конец.

• Переход на следующий элемент последовательности осуществляется с помощью оператора ++.

• Значение элемента последовательности можно найти с помощью оператора *.

Потоки ввода и вывода можно легко описать точно так же. Рассмотрим пример.

ostream_iterator<string> oo(cout); // связываем поток *oo с потоком

                                   // cout для записи

*oo = "Hello, ";                   // т.е. cout << "Hello, "

++oo;                              // "готов к выводу следующего

                                   // элемента"

*oo = "World!n";                  // т.е. cout