Программирование — страница 40 из 57

Алгоритмы и ассоциативные массивы

“Теоретически практика проста”.

Тригве Рийнскауг (Trygve Reenskaug)

В этой главе мы завершаем описание идей, лежащих в основе библиотеки STL, и наш обзор ее возможностей. Здесь мы сосредоточим свое внимание на алгоритмах. Наша главная цель — ознакомить читателей с десятками весьма полезных алгоритмов, которые сэкономят им дни, если не месяцы, работы. Описание каждого алгоритма сопровождается примерами его использования и указанием технологий программирования, которые обеспечивают его работу. Вторая цель, которую мы преследуем, — научить читателей писать свои собственные элегантные и эффективные алгоритмы в тех случаях, когда ни стандартная, ни другие доступные библиотеки не могут удовлетворить их потребности. Кроме того, мы рассмотрим еще три контейнера: map, set и unordered_map.

21.1. Алгоритмы стандартной библиотеки

Стандартная библиотека содержит около шестидесяти алгоритмов. Все они иногда чем-то полезны; мы сосредоточим внимание на часто используемых алгоритмах, которые используются многими, а также на тех, которые иногда оказываются очень полезными для решения какой-то задачи.

 По умолчанию проверка равенства выполняется с помощью оператора ==, а упорядочивание — на основе оператора < (меньше). Алгоритмы из стандартной библиотеки определены в заголовке . Более подробную информацию читатели найдут в приложении Б.5 и в источниках, перечисленных в разделе 20.7. Эти алгоритмы работают с одной или двумя последовательностями. Входная последовательность определяется парой итераторов; результирующая последовательность — итератором, установленным на ее первый элемент. Как правило, алгоритм параметризуется одной или несколькими операциями, которые можно определить либо с помощью объектов-функций, либо собственно функций. Алгоритмы обычно сообщают о сбоях, возвращая итератор, установленный на конец входной последовательности. Например, алгоритм find(b,e,v) вернет элемент e, если не найдет значение v.

21.2. Простейший алгоритм: find()

Вероятно, простейшим из полезных алгоритмов является алгоритм find(). Он находит элемент последовательности с заданным значением.

template
In find(In first, In last, const T& val)
// находит первый элемент в последовательности [first,last], равный val
{
  while (first!=last && *first != val) ++first;
  return first;
}

Посмотрим на определение алгоритма find(). Естественно, вы можете использовать алгоритм find(), не зная, как именно он реализован, — фактически мы его уже применяли (например, в разделе 20.6.2). Однако определение алгоритма find() иллюстрирует много полезных проектных идей, поэтому оно достойно изучения.

 Прежде всего, алгоритм find() применяется к последовательности, определенной парой итераторов. Мы ищем значение val в полуоткрытой последовательности [first:last]. Результат, возвращаемый функцией find(), является итератором. Он указывает либо на первый элемент последовательности, равный значению val, либо на элемент last. Возвращение итератора на элемент, следующий за последним элементом последовательности, — самый распространенный способ, с помощью которого алгоритмы библиотеки STL сообщают о том, что элемент не найден. Итак, мы можем использовать алгоритм find() следующим образом:

void f(vector& v,int x)
{
  vector::iterator p = find(v.begin(),v.end(),x);
  if (p!=v.end()) {
    // мы нашли x в v
  }
  else {
    // в v нет элемента, равного x
  }
  // ...
}

В этом примере, как в большинстве случаев, последовательность содержит все элементы контейнера (в данном случае вектора). Мы сравниваем возвращенный итератор с концом последовательности, чтобы узнать, найден ли искомый элемент.

Теперь мы знаем, как используется алгоритм find(), а также группу аналогичных алгоритмов, основанных на тех же соглашениях. Однако, прежде чем переходить к другим алгоритмам, внимательнее посмотрим на определение алгоритма find().

template
In find(In first,In last,const T& val)
 // находит первый элемент в последовательности [first,last],
 // равный val
{
  while (first!=last && *first != val) ++first;
  return first;
}

Вы полагаете, что этот цикл вполне тривиален? Мы так не думаем. На самом деле это минимальное, эффективное и непосредственное представление фундаментального алгоритма. Однако, пока мы не рассмотрим несколько примеров, это далеко не очевидно. Сравним несколько версий алгоритма.

template
In find(In first,In last,const T& val)
 // находит первый элемент в последовательности [first,last],
 // равный val
 for (In p = first; p!=last; ++p)
   if (*p == val) return p;
 return last;
}

Эти два определения логически эквивалентны, и хороший компилятор сгенерирует для них обоих одинаковый код. Однако на практике многие компиляторы не настолько хороши, чтобы устранить излишнюю переменную (p) и перестроить код так, чтобы все проверки выполнялись в одном месте. Зачем это нужно? Частично потому, что стиль первой (рекомендуемой) версии алгоритма find() стал очень популярным, и мы должны понимать его, чтобы читать чужие программы, а частично потому, что для небольших функций, работающих с большими объемами данных, большее значение имеет эффективность.

ПОПРОБУЙТЕ

Уверены ли вы, что эти два определения являются логически эквивалентными? Почему? Попробуйте привести аргументы в пользу их эквивалентности. Затем примените оба алгоритма к одному и тому же набору данных. Знаменитый специалист по компьютерным наукам Дон Кнут ((Don Knuth) однажды сказал: “Я только доказал, что алгоритм является правильным, но я его не проверял”. Даже математические доказательства содержат ошибки. Для того чтобы убедиться в своей правоте, нужно иметь как доказательства, так и результаты тестирования. 

21.2.1. Примеры использования обобщенных алгоритмов

 Алгоритм find() является обобщенным. Это значит, что его можно применять к разным типам данных. Фактически его обобщенная природа носит двойственный характер.

• Алгоритм find() можно применять к любой последовательности в стиле библиотеки STL.

• Алгоритм find() можно применять к любому типу элементов.

Рассмотрим несколько примеров (если они покажутся вам сложными, посмотрите на диаграммы из раздела 20.4).

void f(vector& v,int x) // работает с целочисленными векторами
{
  vector::iterator p = find(v.begin(),v.end(),x);
  if (p!=v.end()) { /* мы нашли x */ }
    // ...
}

 Здесь операции над итераторами, использованные в алгоритме find(), являются операциями над итераторами типа vector::iterator; т.е. оператор ++ (в выражении ++first) просто перемещает указатель на следующую ячейку памяти (где хранится следующий элемент вектора), а операция * (в выражении *first) разыменовывает этот указатель. Сравнение итераторов (в выражении first!=last) сводится к сравнению указателей, а сравнение значений (в выражении *first!=val) — к обычному сравнению целых чисел.

Попробуем применить алгоритм к объекту класса list.

void f(list& v,string x) // работает со списком строк
{
  list::iterator p = find(v.begin(),v.end(),x);
  if (p!=v.end()) { /* мы нашли x */ }
    // ...
}

 Здесь операции над итераторами, использованные в алгоритме find(), являются операциями над итераторами класса list::iterator. Эти операторы имеют соответствующий смысл, так что логика их работы совпадает с логикой работы операторов из предыдущего примера (для класса vector). В то же время они реализованы совершенно по-разному; иначе говоря, оператор ++ (в выражении ++first) просто следует за указателем, установленным на следующий узел списка, а оператор * (в выражении *first) находит значение в узле Link. Сравнение итераторов (в выражении first!=last) сводится к сравнению указателей типа Link*, а сравнение значений (в выражении *first!=val) означает сравнение строк с помощью оператора != из класса string.

Итак, алгоритм find() чрезвычайно гибкий: если мы будем соблюдать простые правила работы с итераторами, то сможем использовать алгоритм find() для поиска элементов в любой последовательности любого контейнера. Например, с помощью алгоритма find() мы можем искать символ в объекте класса Document, определенного в разделе 20.6.

void f(Document& v,char x) // работает с объектами класса Document
{
  Text_iterator p = find(v.begin(),v.end(),x);
  if (p!=v.end()) { /* мы нашли x */ }
    // ...
}

Эта гибкость является отличительной чертой алгоритмов из библиотеки STL и делает их более полезными, чем многие люди могут себе представить.

21.3. Универсальный алгоритм поиска: find_if()

Нам редко приходится искать какое-то конкретное значение. Чаще нас интересует значение, удовлетворяющее определенным критериям. Мы смогли бы выполнять намного более полезную операцию find, если бы могли определять свои собственные критерии поиска. Например, мы могли бы найти число, превышающее 42. Мы могли бы также сравнивать строки, не учитывая регистр (верхний или нижний).

Кроме того, мы могли найти первое нечетное число. А может, мы захотели бы найти запись с адресом "17 Cherry Tree Lane".

Стандартный алгоритм поиска в соответствии с критерием, заданным пользователем, называется find_if().

template
In find_if(In first,In last,Pred pred)
{
  while (first!=last && !pred(*first)) ++first;
  return first;
}

Очевидно (если сравнить исходные коды), что он похож на алгоритм find(), за исключением того, что в нем используется условие !pred(*first), а не *first!=val; иначе говоря, алгоритм останавливает поиск, как только предикат pred() окажется истинным, а не когда будет обнаружен элемент с заданным значением.

 Предикат (predicate) — это функция, возвращающая значение true или false. Очевидно, что алгоритм find_if() требует предиката, принимающего один аргумент, чтобы выражение pred(*first) было корректным. Мы можем без труда написать предикат, проверяющий какое-то свойство значения, например “содержит ли строка букву x”, “превышает ли число значение 42” или “является ли число нечетным?” Например, мы можем найти первое нечетное число в целочисленном векторе.

bool odd(int x) { return x%2; } // % — деление по модулю

void f(vector& v)
{
  vector::iterator p = find_if(v.begin(), v.end(), odd);
  if (p!=v.end()) { /* мы нашли нечетное число */ }
    // ...
}

При данном вызове алгоритм find_if() применит функцию odd() к каждому элементу, пока не найдет первое нечетное число. Аналогично, мы можем найти первый элемент списка, значение которого превышает 42.

bool larger_than_42(double x) { return x>42; }

void f(list& v)
{
  list::iterator p = find_if(v.begin(), v.end(),
  larger_than_42);
  if (p!=v.end()) { /* мы нашли значение, превышающее 42 */ }
    // ...
}

Однако последний пример не вполне удовлетворительный. А что, если мы после этого захотим найти элемент, который больше 41? Нам придется написать новую функцию. Хотите найти элемент, который больше 19? Пишите еще одну функцию. Должен быть более удобный способ!

Если мы хотим сравнивать элемент с произвольным значением v, то должны как-то сделать это значение неявным аргументом предиката алгоритма find_if(). Мы могли бы попробовать (выбрав в качестве удобного имени идентификатор v_val).

double v_val; // значение, с которым предикат larger_than_v()
              // сравнивает свой аргумент
bool larger_than_v(double x) { return x>v_val; }

void f(list& v,int x)
{
  v_val = 31; // устанавливаем переменную v_val равной 31,
              // для следующего вызова предиката larger_than_v
  list::iterator p = find_if(v.begin(),v.end(),
                                     larger_than_v);
  if (p!=v.end()) { /* мы нашли значение, превышающее 31 */ }
    v_val = x; // устанавливаем переменную v_val равной x
               // для следующего вызова предиката larger_than_v
  list::iterator q = find_if(v.begin(), v.end(),
                                     larger_than_v);
  if (q!=v.end()) { /* мы нашли значение, превышающее x*/ }
    // ...
}

 Какая гадость! Мы убеждены, что люди, написавшие такую программу, в конце концов получат по заслугам, но мы заранее сочувствуем пользователям и любому человеку, который столкнется с этим кодом. Повторим: должен быть более удобный способ!

ПОПРОБУЙТЕ

Почему такое использование переменной v вызывает у нас такое отвращение? Назовите по крайней мере три способа, которые приведут к непонятным ошибкам. Назовите три приложения, в которых такие программы особенно недопустимы. 

21.4. Объекты-функции

Итак, мы хотим передавать предикат алгоритму find_if() и чтобы этот предикат сравнивал элементы со значением, которое мы зададим как его аргумент. В частности, мы хотим написать примерно такой код:

void f(list& v, int x)
{
  list::iterator p = find_if(v.begin(), v.end(),
  Larger_than(31));
  if (p!=v.end()) { /* мы нашли число, превышающее 31 */ }
    list::iterator q = find_if(v.begin(), v.end(),
  Larger_than(x));
  if (q!=v.end()) { /* мы нашли число, превышающее x */ }
    // ...
}

Очевидно, что функция Larger_than должна удовлетворять двум условиям.

• Ее можно вызывать как предикат, например pred(*first).

• Она может хранить значение, например 31 или x, передаваемое при вызове.

 Для того чтобы выполнить эти условия, нам нужен объект-функция, т.е. объект, который ведет себя как функция. Нам нужен объект, поскольку именно объекты могут хранить данные, например значение для сравнения. Рассмотрим пример.

class Larger_than {
  int v;
public:
  Larger_than(int vv) : v(vv) { } // хранит аргумент
  bool operator()(int x) const { return x>v; } // сравнение
};

Следует отметить, что это определение представляет собой именно то, что мы требовали от предиката. Теперь осталось понять, как это работает. Написав выражение Larger_than(31), мы (очевидно) создаем объект класса Larger_than, хранящий число 31 в члене v. Рассмотрим пример.

find_if(v.begin(),v.end(),Larger_than(31))

Здесь мы передаем объект Larger_than(31) алгоритму find_if() как параметр с именем pred. Для каждого элемента v алгоритм find_if() осуществляет вызов

pred(*first)

Это активизирует оператор вызова функции, т.е. функцию-член operator(), для объекта-функции с аргументом *first. В результате происходит сравнение значения элемента, т.е. *first, с числом 31.

Мы видим, что вызов функции можно рассматривать как результат работы оператора (), аналогично любому другому оператору. Оператор () называют также оператором вызова функции (function call operator) или прикладным оператором (application operator). Итак, оператор () в выражении pred(*first) эквивалентен оператору Larger_than::operator(), точно так же, как оператор [] в выражении v[i] эквивалентен оператору vector::operator[].

21.4.1. Абстрактная точка зрения на функции-объекты

 Таким образом, мы имеем механизм, позволяющий функции хранить данные, которые ей нужны. Очевидно, что функции-объекты образуют универсальный, мощный и удобный механизм. Рассмотрим понятие объекта-функции подробнее.

class F {  // абстрактный пример объекта-функции
      S s; // состояние
public:
  F(const S& ss):s(ss) { /* устанавливает начальное значение */ }
  T operator() (const S& ss) const
  {
    // делает что-то с аргументом ss
    // возвращает значение типа T (часто T — это void,
    // bool или S)
  }
  const S& state() const { return s; } // демонстрирует
  // состояние
  void reset(const S& ss) { s = ss; }  // восстанавливает
  // состояние
};

Объект класса F хранит данные в своем члене s. По мере необходимости объект-функция может иметь много данных-членов. Иногда вместо фразы “что-то хранит данные” говорят “нечто пребывает в состоянии”. Когда мы создаем объект класса F, мы можем инициализировать это состояние. При необходимости мы можем прочитать это состояние. В классе F для считывания состояния предусмотрена операция state(), а для записи состояния — операция reset(). Однако при разработке объекта-функции мы свободны в выборе способа доступа к его состоянию.

Разумеется, мы можем прямо или косвенно вызывать объект-функцию, используя обычную систему обозначений. При вызове объект-функция F получает один аргумент, но мы можем определять объекты-функции, получающие столько параметров, сколько потребуется.

 Использование объектов-функций является основным способом параметризации в библиотеке STL. Мы используем объекты-функции для того, чтобы указать алгоритму поиска, что именно мы ищем (см. раздел 21.3), для определения критериев сортировки (раздел 21.4.2), для указания арифметических операций в численных алгоритмах (раздел 21.5), для того, чтобы указать, какие объекты мы считаем равными (раздел 21.8), а также для многого другого. Использование объектов-функций — основной источник гибкости и универсальности алгоритмов.

 Объекты-функции, как правило, очень эффективны. В частности, передача по значению небольшого объекта-функции в качестве аргумента шаблонной функции обеспечивает оптимальную производительность. Причина проста, но удивительна для людей, хорошо знающих механизм передачи функций в качестве аргументов: обычно передача функции в виде объекта приводит к созданию значительно более маленького и быстродействующего кода, чем при передаче функции как таковой! Это утверждение оказывается истинным, только если объект мал (например, если он содержит одно-два слова данных или вообще не хранит данные) или передается по ссылке, а также если оператор вызова функции невелик (например, простое сравнение с помощью оператора <) и определен как подставляемая функция (например, если его определение содержится в теле класса). Большинство примеров в этой главе — и в книге в целом — соответствует этому правилу. Основная причина высокой производительности небольших и простых объектов-функций состоит в том, что они предоставляют компилятору объем информации о типе, достаточный для того, чтобы сгенерировать оптимальный код. Даже устаревшие компиляторы с несложными оптимизаторами могут генерировать простую машинную инструкцию “больше” для сравнения в классе Larger_than, вместо вызова функции. Вызов функции обычно выполняется в 10–50 раз дольше, чем простая операция сравнения. Кроме того, код для вызова функции больше, чем код простого сравнения.

21.4.2. Предикаты на членах класса

Как мы уже видели, стандартные алгоритмы хорошо работают с последовательностями элементов базовых типов, таких как int и double. Однако в некоторых предметных областях более широко используются контейнеры объектов пользовательских классов. Рассмотрим пример, играющий главную роль во многих областях, — сортировка записей по нескольким критериям.

struct Record {
  string name;   // стандартная строка
  char addr[24]; // старый стиль для согласованности
                 // с базами данных
  // ...
};

vector vr;

Иногда мы хотим сортировать вектор vr по имени, а иногда — по адресам. Если мы не стремимся одновременно к элегантности и эффективности, наши методы ограничены практической целесообразностью. Мы можем написать следующий код:

// ...
sort(vr.begin(),vr.end(),Cmp_by_name()); // сортировка по имени
// ...
sort(vr.begin(),vr.end(),Cmp_by_addr()); // сортировка по адресу
// ...

Cmp_by_name — это объект-функция, сравнивающий два объекта класса Record по членам name. Для того чтобы дать пользователю возможность задавать критерий сравнения, в стандартном алгоритме sort предусмотрен необязательный третий аргумент, указывающий критерий сортировки. Функция Cmp_by_name() создает объект Cmp_by_name для алгоритма sort(), чтобы использовать его для сравнения объектов класса Record. Это выглядит отлично, в том смысле, что нам не приходится об этом беспокоиться самим. Все, что мы должны сделать, — определить классы Cmp_by_name и Cmp_by_addr.

// разные сравнения объектов класса Record:
struct Cmp_by_name {
  bool operator()(const Record& a,const Record& b) const
    { return a.name < b.name; }
};

struct Cmp_by_addr {
  bool operator()(const Record& a, const Record& b) const
    { return strncmp(a.addr,b.addr,24) < 0; }  // !!!
};

Класс Cmp_by_name совершенно очевиден. Оператор вызова функции operator()() просто сравнивает строки name, используя оператор < из стандартного класса string. Однако сравнение в классе Cmp_by_addr выглядит ужасно. Это объясняется тем, что мы выбрали неудачное представление адреса — в виде массива, состоящего из 24 символов (и не завершающегося нулем). Мы сделали этот выбор частично для того, чтобы показать, как объект-функцию можно использовать для сокрытия некрасивого и уязвимого для ошибок кода, а частично для того, чтобы продемонстрировать, что библиотека STL может решать даже ужасные, но важные с практической точки зрения задачи. Функция сравнения использует стандартную функцию strncmp(), которая сравнивает массивы символов фиксированной длины и возвращает отрицательное число, если вторая строка лексикографически больше, чем первая. Как только вам потребуется выполнить такое устаревшее сравнение, вспомните об этой функции (см., например, раздел Б.10.3).

21.5. Численные алгоритмы

Большинство стандартных алгоритмов из библиотеки STL связаны с обработкой данных: они их копируют, сортируют, выполняют поиск среди них и т.д. В то же время некоторые из них предназначены для вычислений. Они могут оказаться полезными как для решения конкретных задач, так и для демонстрации общих принципов реализации численных алгоритмов в библиотеке STL. Существуют всего четыре таких алгоритма.

Эти алгоритмы определены в заголовке . Мы опишем первые два из них, а остальные при необходимости читатели могут изучить самостоятельно.

21.5.1. Алгоритм accumulate()

Простейшим и наиболее полезным численным алгоритмом является алгоритм accumulate(). В простейшем варианте он суммирует значения, принадлежащие последовательности.

template T accumulate(In first, In last, T init)
{
  while (first!=last) {
    init = init + *first;
    ++first;
  }
  return init;
}

Получив начальное значение init, он просто добавляет к нему каждое значение из последовательности [first:last] и возвращает сумму. Переменную init, в которой накапливается сумма, часто называют аккумулятором (accumulator). Рассмотрим пример.

int a[] = { 1, 2, 3, 4, 5 };
cout << accumulate(a, a+sizeof(a)/sizeof(int), 0);

Этот фрагмент кода выводит на экран число 15, т.е. 0+1+2+3+4+5 (0 является начальным значением). Очевидно, что алгоритм accumulate() можно использовать для всех видов последовательностей.

void f(vector& vd,int* p,int n)
{
  double sum = accumulate(vd.begin(),vd.end(),0.0);
  int sum2 = accumulate(p,p+n,0);
}

Тип результата (суммы) совпадает с типом переменной, которую алгоритм accumulate() использует в качестве аккумулятора. Это обеспечивает высокую степень гибкости которая может играть важную роль. Рассмотрим пример.

void f(int* p,int n)
{
  int s1 = accumulate(p, p+n, 0);        // суммируем целые числа в int
  long sl = accumulate(p, p+n, long(0)); // суммируем целые числа
                                         // в long
 double s2 = accumulate(p, p+n, 0.0);    // суммируем целые числа
                                         // в double
}

На некоторых компьютерах переменная типа long состоит из гораздо большего количества цифр, чем переменная типа int. Переменная типа double может представить большие (и меньшие) числа, чем переменная типа int, но, возможно, с меньшей точностью. В главе 24 мы еще вернемся к вопросу о диапазоне и точности в вычислениях.

 Использование переменной init в качестве аккумулятора представляет собой весьма распространенную идиому, позволяющую задать тип аккумулятора.

void f(vector& vd,int* p,int n)
{
  double s1 = 0;
  s1 = accumulate(vd.begin(),vd.end(),s1);
  int s2 = accumulate(vd.begin(), vd.end(),s2); // Ой
  float s3 = 0;
  accumulate(vd.begin(), vd.end(), s3);         // Ой
}

 Не забудьте инициализировать аккумулятор и присвоить результат работы алгоритма accumulate() какой-нибудь переменной. В данном примере в качестве инициализатора использовалась переменная s2, которая сама еще не получила начальное значение до вызова алгоритма; результат такого вызова будет непредсказуем. Мы передали переменную s3 алгоритму accumulate() (по значению; см. раздел 8.5.3), но результат ничему не присвоили; такая компиляция представляет собой простую трату времени.

21.5.2. Обобщение алгоритма accumulate()

Итак, основной алгоритм accumulate() с тремя аргументами выполняет суммирование. Однако существует много других полезных операций, например умножение и вычитание, которые можно выполнять над последовательностями, поэтому в библиотеке STL предусмотрена версия алгоритма accumulate() с четырьмя аргументами, позволяющая задавать используемую операцию.

template
T accumulate(In first, In last, T init, BinOp op)
{
  while (first!=last) {
    init = op(init, *first);
    ++first;
  }
  return init;
}

Здесь можно использовать любую бинарную операцию, получающую два аргумента, тип которых совпадает с типом аккумулятора. Рассмотрим пример.

array a = { 1.1, 2.2, 3.3, 4.4 };   // см. раздел 20.9
cout << accumulate(a.begin(),a.end(), 1.0, multiplies());

Этот фрагмент кода выводит на печать число 35.1384, т.е. 1.0*1.1*2.2*3.3*4.4 (1.0 — начальное значение). Бинарный оператор multiplies(), передаваемый как аргумент, представляет собой стандартный объект-функцию, выполняющий умножение; объект-функция multiplies перемножает числа типа double, объект-функция multiplies перемножает числа типа int и т.д. Существуют и другие бинарные объекты-функции: plus (сложение), minus (вычитание), divides и modulus (вычисление остатка от деления). Все они определены в заголовке (раздел Б.6.2).

 Обратите внимание на то, что для умножения чисел с плавающей точкой естественным начальным значением является число 1.0. Как и в примере с алгоритмом sort() (см. раздел 21.4.2), нас часто интересуют данные, хранящиеся в объектах классов, а не обычные данные встроенных типов. Например, мы могли бы вычислить общую стоимость товаров, зная стоимость их единицы и общее количество.

struct Record {
  double unit_price;
  int units;   // количество проданных единиц
  // ...
};

Мы можем поручить какому-то оператору в определении алгоритма accumulate извлекать данные units из соответствующего элемента класса Record и умножать на значение аккумулятора.

double price(double v,const Record& r)
{
  return v + r.unit_price * r.units; // вычисляет цену
                                     // и накапливает итог
}

void f(const vector& vr)
{
  double total = accumulate(vr.begin(),vr.end(),0.0,price);
  // ...
}

Мы поленились и использовали для вычисления цены функцию, а не объект-функцию, просто, чтобы показать, что так тоже можно делать. И все же мы рекомендуем использовать объекты функции в следующих ситуациях.

• Если между вызовами необходимо сохранять данные.

• Если они настолько короткие, что их можно объявлять подставляемыми (по крайней мере, для некоторых примитивных операций).

В данном случае мы могли бы использовать объект-функцию, руководствуясь вторым пунктом этого списка.

ПОПРОБУЙТЕ

Определите класс vector, проинициализируйте его четырьмя записями по своему выбору и вычислите общую стоимость, используя приведенные выше функции.

21.5.3. Алгоритм inner_product

Возьмите два вектора, перемножьте их элементы попарно и сложите эти произведения. Результат этих вычислений называется скалярным произведением (inner product) двух векторов и является наиболее широко используемой операцией во многих областях (например, в физике и линейной алгебре; раздел 24.6).

Если вы словам предпочитаете программу, то прочитайте версию этого алгоритма из библиотеки STL.

template
T inner_product(In first, In last, In2 first2, T init)
  // примечание: вычисляет скалярное произведение двух векторов
{
  while(first!=last) {
    init = init + (*first) * (*first2); // перемножаем
    // элементы
    ++first;
    ++first2;
  }
  return init;
}

Эта версия алгоритма обобщает понятие скалярного произведения для любого вида последовательностей с любым типом элементов. Рассмотрим в качестве примера биржевой индекс. Он вычисляется путем присваивания компаниям неких весов. Например, индекс Доу–Джонса Alcoa на момент написания книги составлял 2,4808. Для того чтобы определить текущее значение индекса, умножаем цену акции каждой компании на ее вес и складываем полученные результаты. Очевидно, что такой индекс представляет собой скалярное произведение цен и весов. Рассмотрим пример.

// вычисление индекса Доу-Джонса
vector dow_price;        // цена акции каждой компании
dow_price.push_back(81.86);
dow_price.push_back(34.69);
dow_price.push_back(54.45);
// ...

list 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
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).

В стандартной библиотеке предусмотрены восемь ассоциативных контейнеров.

Эти контейнеры определены в заголовках , , и .

21.6.1. Ассоциативные массивы

Рассмотрим более простую задачу: создадим список номеров вхождений слов в текст. Для этого вполне естественно записать список слов вместе с количеством их вхождений в текст. Считывая новое слово, мы проверяем, не появлялось ли оно ранее; если нет, вставляем его в список и связываем с ним число 1. Для этого можно было бы использовать объект типа list или vector, но тогда мы должны были бы искать каждое считанное слово. Такое решение было бы слишком медленным. Класс map хранит свои ключи так, чтобы их было легко увидеть, если они там есть. В этом случае поиск становится тривиальной задачей.

int main()
{
  map words;     // хранит пары (слово, частота)
  string s;
  while (cin>>s) ++words[s]; // контейнер words индексируется
                             // строками
  typedef map::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 имеют тип pair. Первый член объекта класса pair называется first, второй — second. Цикл вывода выглядит следующим образом:

typedef map::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

efficient facilities for defining new types.

Результат работы программы приведен ниже.

C: 1
C++: 3
C,: 1
Except: 1
In: 1
a: 2
addition: 1
and: 1
by: 1
defining: 1
designed: 1
details,: 1
efficient: 1
enjoyable: 1
facilities: 2
flexible: 1
for: 3
general: 1
is: 2
language: 1
language.: 1
make: 1
minor: 1
more: 1
new: 1
of: 1
programmer.: 1
programming: 3
provided: 1
provides: 1
purpose: 1
serious: 1
superset: 1
the: 3
to: 2
types.: 1

Если не хотите проводить различие между верхним и нижним регистрами букв или учитывать знаки пунктуации, то можно решить и эту задачу: см. упр. 13.

21.6.2. Обзор ассоциативных массивов

Так что же такое контейнер map? Существует много способов реализации ассоциативных массивов, но в библиотеке STL они реализованы на основе сбалансированных бинарных деревьев; точнее говоря, они представляют собой красно-черные деревья. Мы не будем вдаваться в детали, но поскольку вам известны эти технические термины, вы можете найти их объяснение в литературе или в веб.

Дерево состоит из узлов (так же как список состоит из узлов; см. раздел 20.4). В объекте класса Node хранятся ключ, соответствующее ему число и указатели на два последующих узла.

Вот как может выглядеть объект класса map в памяти компьютера, если мы вставили в него пары (Kiwi,100), (Quince,0), (Plum,8), (Apple,7), (Grape,2345) и (Orange,99).

Поскольку ключ хранится в члене класса Node с именем first, основное правило организации бинарного дерева поиска имеет следующий вид:

left–>firstfirst

Иначе говоря, для каждого узла выполняются два условия.

• Ключ его левого подузла меньше ключа узла.

• Ключ узла меньше, чем ключ правого подузла.

 Можете убедиться, что эти условия выполняются для каждого узла дерева. Это позволяет нам выполнять поиск вниз по дереву, начиная с корня. Забавно, что в литературе по компьютерным наукам деревья растут вниз. Корневым узлом является узел, содержащий пару (Orange, 99). Мы просто перемещаемся по дереву вниз, пока не найдем подходящее место. Дерево называется сбалансированным (balanced), если (как в приведенном выше примере) каждое его поддерево содержит примерно такое же количество узлов, как и одинаково удаленные от корня поддеревья. В сбалансированном дереве среднее количество узлов, которые мы должны пройти, пока не достигнем заданного узла, минимально.

В узле могут храниться дополнительные данные, которые контейнер может использовать для поддержки баланса. Дерево считается сбалансированным, если каждый узел имеет примерно одинаковое количество наследников как слева, так и справа. Если дерево, состоящее из N узлов, сбалансировано, то для обнаружения узла необходимо просмотреть не больше log₂N узлов. Это намного лучше, чем N/2 узлов в среднем, которые мы должны были бы просмотреть, если бы ключи хранились в списке, а поиск выполнялся с начала (в худшем случае линейного поиска нам пришлось бы просмотреть N узлов). (См. также раздел 21.6.4.)

Для примера покажем, как выглядит несбалансированное дерево.

Это дерево по-прежнему удовлетворяет критерию, требующему, чтобы ключ каждого узла был больше ключа левого подузла и меньше ключа правого.

left–>firstfirst

И все же это дерево является несбалансированным, поэтому нам придется совершить три перехода, чтобы найти узлы Apple и Kiwi, вместо двух, как в сбалансированном дереве. Для деревьев, содержащих много узлов, эта разница может оказаться существенной, поэтому для реализации контейнеров map используются сбалансированные деревья.

Разбираться в принципах организации деревьев, используемых для реализации контейнера map, необязательно. Достаточно предположить, что профессионалы знают хотя бы принципы их работы. Все, что нам нужно, — это интерфейс класса map из стандартной библиотеки. Ниже приведена его несколько упрощенная версия.

template> class map
{
  // ...
  typedef pair value_type; // контейнер map хранит
                                      // пары (Key,Value)
  typedef sometype1 iterator;         // указатель на узел дерева
  typedef sometype2 const_iterator;

  iterator begin();      // указывает на первый элемент
  iterator end();        // указывает на следующий за последним
                         // элемент
  Value& operator[](const Key& k); // индексирование
                                   // по переменной k
  iterator find(const Key& k);     // поиск по ключу k
  void erase(iterator p);          // удаление элемента, на который
                                   // указывает итератор p
  pair insert(const value_type&);
  // вставляет пару (key,value)
  // ...
};

Настоящий вариант контейнера определен в заголовке . Можно представить себе итератор в виде указателя Node*, но при реализации итератора нельзя полагаться на какой-то конкретный тип.

Сходство интерфейсов классов vector и list (см. разделы 20.5 и B.4) очевидно. Основное отличие заключается в том, что при перемещении по контейнеру элементами теперь являются пары типа pair. Этот тип является очень полезным в библиотеке STL.

template struct pair {
  typedef T1 first_type;
  typedef T2 second_type;
  T1 first;
  T2 second;

  pair():first(T1()),second(T2()) { }
  pair(const T1& x,const T2& y):first(x),second(y) { }
  template
    pair(const pair& p):first(p.first), second(p.second) { }
};

template
 pair make_pair(T1 x, T2 y)
{
  return pair(x,y);
}

Мы скопировали полное определение класса pair и его полезную вспомогательную функцию make_pair() из стандарта.

 При перемещении по контейнеру map элементы перебираются в порядке, определенном ключом. Например, если мы перемещаемся по контейнеру, описанному в примере, то получим следующий порядок обхода:

(Apple,7) (Grape,2345) (Kiwi,100) (Orange,99) (Plum,8) (Quince,0)

Порядок вставки узлов значения не имеет.

Операция insert() имеет странное возвращаемое значение, которое в простых программах, как правило, мы игнорируем. Это пара, состоящая из итератора, установленного на пару (ключ, значение), и переменной типа bool, принимающей значение true, если данная пара (ключ, значение) была вставлена с помощью вызова функции insert(). Если ключ уже был в контейнере, то вставка игнорируется и значение типа bool принимает значение false.

 Мы можем определить порядок обхода ассоциативного массива с помощью третьего аргумента (предикат Cmp в объявлении класса map). Рассмотрим пример.

map m;

Предикат No_case определяет сравнение символов без учета регистра (см. раздел 21.8). По умолчанию порядок обхода определяется предикатом less, т.е. отношением “меньше”. 

21.6.3. Еще один пример ассоциативного массива

Для того чтобы оценить полезность контейнера map, вернемся к примеру с индексом Доу–Джонс из раздела 21.5.3. Описанный там код работает правильно, только если все веса записаны в объекте класса vector в тех же позициях, что и соответствующие имена. Это требование носит неявный характер и легко может стать источником малопонятных ошибок. Существует много способов решения этой проблемы, но наиболее привлекательным является хранение всех весов вместе с их тикером, например (“AA”,2.4808). Тикер — это аббревиатура названия компании. Аналогично тикер компании можно хранить вместе с ценой ее акции, например (“AA”,34.69). В заключение для людей, редко сталкивающихся с фондовым рынком США, мы можем записывать тикер вместе с названием компании, например (“AA”,“Alcoa Inc.”); иначе говоря, можем хранить три аассоциативных массива соответствующих значений.

Сначала создадим ассоциативный контейнер, содержащий пары (символ,цена).

map dow_price;
  // Индекс Доу - Джонса (символ, цена);
  // текущие котировки см. на веб-сайте www.djindexes.com
dow_price["MMM"] = 81.86;
dow_price ["AA"] = 34.69;
dow_price ["MO"] = 54.45;
// ...

Ассоциативный массив, содержащий пары (символ, вес), объявляется так:

map dow_weight; // Индекс Доу-Джонса (символ, вес)
dow_weight.insert(make_pair("MMM", 5.8549));
dow_weight.insert(make_pair("AA",2.4808));
dow_weight.insert(make_pair("MO",3.8940));
// ...

Мы использовали функции insert() и make_pair() для того, чтобы показать, что элементами контейнера map действительно являются объекты класса pair. Этот пример также иллюстрирует значение обозначений; мы считаем, что индексирование понятнее и — что менее важно — легче записывается.

Ассоциативный контейнер, содержащий пары (символ, название).

map dow_name; // Доу-Джонс (символ, название)
dow_name["MMM"] = "3M Co.";
dow_name["AA"] = "Alcoa Inc.";
dow_name["MO"] = "Altria Group Inc.";
// ...

С помощью этих ассоциативных контейнеров можно легко извлечь любую информацию. Рассмотрим пример.

double alcoa_price = dow_price ["AAA"]; // считываем значения из
                                        // ассоциативного массива
double boeing_price = dow_price ["BA"];
if (dow_price.find("INTC") != dow_price.end()) // находим элемент
                                               // ассоциативного
                                               // массива
cout << "Intel is in the Dow\n";

Перемещаться по ассоциативному массиву легко. Мы просто должны помнить, что ключ называется first, а значение — second.

typedef map::const_iterator Dow_iterator;

// записывает цену акции для каждой компании, входящей в индекс
// Доу - Джонса
for (Dow_iterator p = dow_price.begin(); p!=dow_price.end(); ++p) {
  const string& symbol = p–>first; // тикер
    cout << symbol << '\t'
<< p–>second << '\t'
<< dow_name[symbol] << '\n';
}

Мы можем даже выполнить некоторые вычисления, непосредственно используя ассоциативный контейнер. В частности, можем вычислить индекс, как в разделе 21.5.3. Мы должны извлечь цены акций и веса из соответствующих ассоциативных массивов и перемножить их. Можно без труда написать функцию, выполняющую эти вычисления с любыми двумя ассоциативными массивами map.

double weighted_value(
  const pair& a,
  const pair& b
)  // извлекает значения и перемножает
  {
    return a.second * b.second;
  }

Теперь просто подставим эту функцию в обобщенную версию алгоритма

inner_product() и получим значение индекса.
double dji_index =
  inner_product(dow_price.begin(), dow_price.end(),
  // все компании
                dow_weight.begin(), // их веса
                0.0,                // начальное значение
                plus(),     // сложение (обычное)
                weighted_value);    // извлекает значение и веса,
                                    // а затем перемножает их

 Почему целесообразно хранить такие данные в ассоциативных массивах, а не в векторах? Мы использовали класс map, чтобы связь между разными значениями стала явной. Это одна из причин. Кроме того, контейнер map хранит элементы в порядке, определенном их ключами. Например, при обходе контейнера dow мы выводили символы в алфавитном порядке; если бы мы использовали класс vector, то были бы вынуждены сортировать его. Чаще всего класс map используют просто потому, что хотят искать значения по их ключам. Для крупных последовательностей поиск элементов с помощью алгоритма find() намного медленнее, чем поиск в упорядоченной структуре, такой как контейнер map.

ПОПРОБУЙТЕ

Приведите этот пример в рабочее состояние. Затем добавьте несколько компаний по своему выбору и задайте их веса. 

21.6.4. Алгоритм unordered_map()

 Для того чтобы найти элемент в контейнере vector, алгоритм find() должен проверить все элементы, начиная с первого и заканчивая искомым или последним элементом вектора. Средняя сложность этого поиска пропорциональна длине вектора (N); в таком случае говорят, что алгоритм имеет сложность O(N).

 Для того чтобы найти элемент в контейнере map, оператор индексирования должен проверить все элементы, начиная с корня дерева и заканчивая искомым значением или листом дерева. Средняя сложность этого поиска пропорциональна глубине дерева. Максимальная глубина сбалансированного бинарного дерева, содержащего N элементов, равна log₂N, а сложность поиска в нем имеет порядок O(log₂N), т.е. пропорциональна величине log₂N. Это намного лучше, чем O(N).

Реальная сложность поиска зависит от того, насколько быстро нам удастся найти искомые значения и какие затраты будут связаны с выполнением операции сравнения и итераций. Обычно следование за указателями (при поиске в контейнере map) несколько сложнее, чем инкрементация указателя (при поиске в контейнере vector с помощью алгоритма find()).

 Для некоторых типов, особенно для целых чисел и символьных строк, можно достичь еще более высоких результатов поиска, чем при поиске по дереву контейнера map. Не вдаваясь в подробности, укажем, что идея заключается в том, что по ключу мы можем вычислить индекс в контейнере vector. Этот индекс называется значением хеш-функции (hash value), а контейнер, в котором используется этот метод, — хеш-таблицей (hash table). Количество возможных ключей намного больше, чем количество ячеек в хеш-таблице. Например, хеш-функция часто используется для того, чтобы отобразить миллиарды возможных строк в индекс вектора, состоящего из тысячи элементов. Такая задача может оказаться сложной, но ее можно решить. Это особенно полезно при реализации больших контейнеров map. Основное преимущество хеш-таблицы заключается в том, что средняя сложность поиска в ней является (почти) постоянной и не зависит от количества ее элементов, т.е. имеет порядок O(1). Очевидно, что это большое преимущество для крупных ассоциативных массивов, например, содержащих 500 тысяч веб-адресов. Более подробную информацию о хеш-поиске читатели могут найти в документации о контейнере unordered_map (доступной в сети веб) или в любом учебнике по структурам данных (ищите в оглавлении хеш-таблицы и хеширование).

Рассмотрим графическую иллюстрацию поиска в (неупорядоченном) векторе, сбалансированном бинарном дереве и хеш-таблице.

• Поиск в неупорядоченном контейнере vector.

• Поиск в контейнере map (сбалансированном бинарном дереве).

• Поиск в контейнере unordered_map (хеш-таблица).

Контейнер unordered_map из библиотеки STL реализован с помощью хештаблицы, контейнер map — на основе сбалансированного бинарного дерева, а контейнер vector — в виде массива. Полезность библиотеки STL частично объясняется тем, что она позволила объединить в одно целое разные способы хранения данных и доступа к ним, с одной стороны, и алгоритмы, с другой.

 Эмпирическое правило гласит следующее.

• Используйте контейнер vector, если у вас нет веских оснований не делать этого.

• Используйте контейнер map, если вам необходимо выполнить поиск по значению (и если тип ключа позволяет эффективно выполнять операцию “меньше”).

• Используйте контейнер unordered_map, если вам необходимо часто выполнять поиск в большом ассоциативном массиве и вам не нужен упорядоченный обход (и если тип вашего ключа допускает эффективное использование хеш-функций).

Мы не будем подробно описывать контейнер unordered_map. Его можно использовать с ключом типа string или int точно так же, как контейнер map, за исключением того, что при обходе элементов они не будут упорядочены. Например, мы могли бы переписать фрагмент кода для вычисления индекса- Доу–Джонса из раздела 21.6.3 следующим образом:

unordered_map dow_price;

typedef unordered_map::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 не был включен в вашу реализацию языка 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
 }
};

set 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::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 Out copy(In first, In last, Out res)
{
  while (first!=last) {
    *res = *first;    // копирует элемент
    ++res;
    ++first;
  }
  return res;
}

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

void f(vector& vd, list& li)
  // копирует элементы списка чисел типа int в вектор чисел типа
  // double
{
  if (vd.size() < li.size()) error("целевой контейнер слишком мал");
  copy(li.begin(), li.end(), vd.begin());
  // ...
}

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

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

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

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

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

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

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

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

ostream_iterator oo(cout); // связываем поток *oo с потоком
                                   // cout для записи
*oo = "Hello, ";                   // т.е. cout << "Hello, "
++oo;                              // "готов к выводу следующего
                                   // элемента"
*oo = "World!\n";                  // т.е. cout << "World!\n"

В стандартной библиотеке есть тип ostream_iterator, предназначенный для работы с потоком вывода; ostream_iterator — это итератор, который можно использовать для записи значений типа T.

В стандартной библиотеке есть также тип istream_iterator для чтения значений типа T.

istream_iterator ii(cin);  // чтение *ii — это чтение строки
                                   // из cin

string s1 = *ii;                   // т.е. cin>>s1
++ii;                              // "готов к вводу следующего
                                   // элемента"
string s2 = *ii; // т.е. cin>>s2

Используя итераторы ostream_iterator и istream_iterator, можно вводить и выводить данные с помощью алгоритма copy(). Например, словарь, сделанный наспех, можно сформировать следующим образом:

int main()
{
  string from, to;
  cin >> from >> to;         // вводим имена исходного
                             // и целевого файлов

  ifstream is(from.c_str()); // открываем поток ввода
  ofstream os(to.c_str());   // открываем поток вывода

  istream_iterator ii(is); // создаем итератор ввода
                                   // из потока
  istream_iterator eos;    // сигнальная метка ввода
  ostream_iterator oo(os,"\n"); // создаем итератор
                                        // вывода в поток
  vector b(ii,eos);             // b — вектор, который
                                        // инициализируется
                                        // данными из потока ввода
  sort(b.begin(),b.end());              // сортировка буфера
  copy(b.begin(),b.end(),oo);           // буфер копирования для вывода
}

Итератор eos — это сигнальная метка, означающая “конец ввода.” Когда поток istream достигает конца ввода (который часто называется eof), его итератор istream_iterator становится равным итератору istream_iterator, который задается по умолчанию и называется eos.

 Обратите внимание на то, что мы инициализируем объект класса vector парой итераторов. Пара итераторов (a,b), инициализирующая контейнер, означает следующее: “Считать последовательность [a:b] в контейнер”. Естественно, для этого мы использовали пару итераторов (ii,eos) — начало и конец ввода. Это позволяет нам не использовать явно оператор >> и функцию push_back(). Мы настоятельно не рекомендуем использовать альтернативный вариант.

vector b(max_size); // не пытайтесь угадать объем входных
                            // данных
copy(ii,eos,b.begin());

Люди, пытающиеся угадать максимальный размер ввода, обычно недооценивают его, переполняют буфер и создают серьезные проблемы как для себя, так и для пользователей. Переполнение буфера может также создать опасность для сохранности данных.

ПОПРОБУЙТЕ

Приведите программу в рабочее состояние и протестируйте ее на небольшом файле, скажем, содержащем несколько сотен слов. Затем испытайте “настоятельно не рекомендованную версию”, в которой объем входных данных угадывается, и посмотрите, что произойдет при переполнении буфера ввода b. Обратите внимание на то, что наихудшим сценарием является тот, в котором вы не замечаете ничего плохого и передаете программу пользователям.

В нашей маленькой программе мы считываем слова, а затем упорядочиваем их. Пока все, что мы делаем, кажется очевидным, но почему мы записываем слова в “неправильные” ячейки, так что потом вынуждены их сортировать? Кроме того, что еще хуже, оказывается, что мы записываем слова и выводим их на печать столько раз, сколько они появляются в потоке ввода.

Последнюю проблему можно решить, используя алгоритм unique_copy() вместо алгоритма copy(). Функция unique_copy() просто не копирует повторяющиеся идентичные значения. Например, при вызове обычной функции copy() программы введет строку

the man bit the dog

и выведет на экран слова

bit

dog

man

the

the

Если же используем алгоритм unique_copy(), то программа выведет следующие слова:

bit

dog

man

the

 Откуда взялись переходы на новую строку? Вывод с разделителями настолько распространен, что конструктор класса ostream_iterator позволяет вам (при необходимости) указывать строку, которая может быть выведена после каждого значения.

ostream_iterator oo(os,"\n"); // создает итератор для
                                      // потока вывода

Очевидно, что переход на новую строку — это распространенный выбор для вывода, позволяющий людям легче разбираться в результатах, но, возможно, вы предпочли бы использовать пробелы? Мы могли бы написать следующий код:

ostream_iterator oo(os," ");  // создает итератор для потока
                                      // вывода

В этом случае результаты вывода выглядели бы так:

bit dog man the

21.7.3. Использование класса set для поддержания порядка

Существует еще более простой способ получить такой вывод: использовать контейнер set, а не vector.

int main()
{
  string from, to;
  cin >> from >> to;          // имена исходного и целевого файлов

  ifstream is(from.c_str());  // создаем поток ввода
  ofstream os(to.c_str());    // создаем поток вывода

  istream_iterator ii(is);     // создаем итератор ввода
                                       // из потока
  istream_iterator eos;        // сигнальная метка для ввода
  ostream_iterator oo(os," "); // создаем итератор
                                       // вывода в поток
  set b(ii,eos);      // b — вектор, который инициализируется
                              // данными из потока ввода
  copy(b.begin(),b.end(),oo); // копируем буфер в поток вывода
}

 Когда мы вставляем значение в контейнер set, дубликаты игнорируются. Более того, элементы контейнера set хранятся в требуемом порядке. Если в вашем распоряжении есть правильные инструменты, то большинство задач можно решить без труда.

21.7.4. Алгоритм copy_if()

Алгоритм copy() выполняет копирование без каких-либо условий. Алгоритм unique_copy() отбрасывает повторяющиеся соседние элементы, имеющие одинаковые значения. Третий алгоритм копирует только элементы, для которых заданный предикат является истинным.

template
Out copy_if(In first,In last,Out res,Pred p)
  // копирует элементы, удовлетворяющие предикату
{
  while (first!=last) {
    if (p(*first)) *res++ = *first;
    ++first;
  }
  return res;
}

Используя наш объект-функцию Larger_than из раздела 21.4, можем найти все элементы последовательности, которые больше шести.

void f(const vector& v)
  // копируем все элементы, которые больше шести
{
  vector v2(v.size());
  copy_if(v.begin(),v.end(),v2.begin(),Larger_than(6));
  // ...
}

 Из-за моей ошибки этот алгоритм выпал из стандарта 1998 ISO Standard. В настоящее время эта ошибка исправлена, но до сих пор встречаются реализации языка С++, в которых нет алгоритма copy_if. В таком случае просто воспользуйтесь определением, данным в этом разделе.

21.8. Сортировка и поиск

 Часто мы хотим упорядочить данные. Мы можем добиться этого, используя структуры, поддерживающие порядок, такие как map и set, или выполняя сортировку. Наиболее распространенной и полезной операцией сортировки в библиотеке STL является функция sort(), которую мы уже несколько раз использовали. По умолчанию функция sort() в качестве критерия сортировки использует оператор <, но мы можем задавать свои собственные критерии.

template void sort(Ran first, Ran last);
template void sort(Ran first,Ran last,Cmp cmp);

В качестве примера сортировки, основанной на критерии, определенном пользователем, покажем, как упорядочить строки без учета регистра.

struct No_case { // lowercase(x) < lowercase(y)
  bool operator()(const string& x, const string& y) const
  {
    for (int i = 0; i
      if (i == y.length()) return false;      // y
      char xx = tolower(x[i]);
      char yy = tolower(y[i]);
      if (xx
      if (yy
    }
    if (x.length()==y.length()) return false; // x==y
    return true;   // x
  }
};

void sort_and_print(vector& vc)
{
  sort(vc.begin(),vc.end(),No_case());
  for (vector::const_iterator p = vc.begin();
    p!=vc.end(); ++p)
  cout << *p << '\n';
}

 Как только последовательность отсортирована, нам больше не обязательно перебирать все элементы с самого начала контейнера с помощью функции find(); вместо этого можно использовать бинарный поиск, учитывающий порядок следования элементов. По существу, бинарный поиск сводится к следующему.

Предположим, что мы ищем значение x; посмотрим на средний элемент.

• Если значение этого элемента равно x, мы нашли его!

• Если значение этого элемента меньше x, то любой элемент со значением х находится справа, поэтому мы просматриваем правую половину (применяя бинарный поиск к правой половине).

• Если значение этого элемента больше x, то любой элемент со значением х находится слева, поэтому мы просматриваем левую половину (применяя бинарный поиск к левой половине).

• Если мы достигли последнего элемента (перемещаясь влево или вправо) и не нашли значение x, то в контейнере нет такого элемента.

 Для длинных последовательностей бинарный поиск выполняется намного быстрее, чем алгоритм find() (представляющий собой линейный поиск). Алгоритмы бинарного поиска в стандартной библиотеке называются binary_search() и equal_range(). Что мы понимаем под словом “длинные”? Это зависит от обстоятельств, но десяти элементов обычно уже достаточно, чтобы продемонстрировать преимущество алгоритма binary_search() над алгоритмом find(). На последовательности, состоящей из тысячи элементов, алгоритм binary_search() работает примерно в 200 раз быстрее, чем алгоритм find(), потому что он имеет сложность O(log₂N) (см. раздел 21.6.4).

Алгоритм binary_search имеет два варианта.

template
bool binary_search(Ran first,Ran last,const T& val);

template
bool binary_search(Ran first,Ran last,const T& val,Cmp cmp);

 Эти алгоритмы требуют, чтобы их входные последовательности были упорядочены. Если это условие не выполняется, то могут возникнуть такие интересные вещи, как бесконечные циклы. Алгоритм binary_search() просто сообщает, содержит ли контейнер заданное значение.

void f(vector& vs)  // vs упорядочено
{
  if (binary_search(vs.begin(),vs.end(),"starfruit")) {
    // в контейнере есть строка "starfruit"
  }
  // ...
}

 Итак, алгоритм binary_search() — идеальное средство, если нас интересует, есть заданное значение в контейнере или нет. Если нам нужно найти этот элемент, мы можем использовать функции lower_bound(), upper_bound() или equal_range() (разделы 23.4 и Б.5.4). Как правило, это необходимо, когда элементы контейнера представляют собой объекты, содержащие больше информации, чем просто ключ, когда в контейнере содержатся несколько элементов с одинаковыми ключами или когда нас интересует, какой именно элемент удовлетворяет критерию поиска.

Задание

После выполнения каждой операции выведите содержание вектора на экран.

1. Определите структуру struct Item { string name; int iid; double value; /* ... */ };, создайте контейнер vector vi и заполните его десятью строками из файла.

2. Отсортируйте контейнер vi по полю name.

3. Отсортируйте контейнер vi по полю iid.

4. Отсортируйте контейнер vi по полю value; выведите его содержание на печать в порядке убывания значений (т.е. самое большое значение должно быть выведено первым).

5. Вставьте в контейнер элементы Item("horse shoe",99,12.34) и Item("Canon S400",9988,499.95).

6. Удалите два элемента Item из контейнера vi, задав поля name.

7. Удалите два элемента Item из контейнера vi, задав поля iid.

8. Повторите упражнение с контейнером типа list, а не vector.

Теперь поработайте с контейнером map.

1. Определите контейнер map с именем msi.

2. Вставьте в него десять пар (имя, значение), например msi["lecture"]=21.

3. Выведите пары (имя, значение) в поток cout в удобном для вас виде.

4. Удалите пары (имя, значение) из контейнера msi.

5. Напишите функцию, считывающую пары из потока cin и помещающую их в контейнер msi.

6. Прочитайте десять пар из потока ввода и поместите их в контейнер msi.

7. Запишите элементы контейнера msi в поток cout.

8. Выведите сумму (целых) значений из контейнера msi.

9. Определите контейнер map с именем mis.

10. Введите значения из контейнера msi в контейнер mis; иначе говоря, если в контейнере msi есть элемент ("lecture",21), то контейнер mis также должен содержать элемент (21,"lecture").

11. Выведите элементы контейнера mis в поток cout.

Несколько заданий, касающихся контейнера vector.

1. Прочитайте несколько чисел с плавающей точкой (не меньше 16 значений) из файла в контейнер vector с именем vd.

2. Выведите элементы контейнера vd в поток cout.

3. Создайте вектор vi типа vector с таким же количеством элементов, как в контейнере vd; скопируйте элементы из контейнера vd в контейнер vi.

4. Выведите в поток cout пары (vd[i], vi[i]) по одной в строке.

5. Выведите на экран сумму элементов контейнера vd.

6. Выведите на экран разность между суммой элементов контейнеров vd и vi.

7. Существует стандартный алгоритм reverse, получающий в качестве аргументов последовательность (пару итераторов); поменяйте порядок следования элементов vd на противоположный и выведите их в поток cout.

8. Вычислите среднее значение элементов в контейнере vd и выведите его на экран.

9. Создайте новый контейнер vector с именем vd2 и скопируйте в него элементы контейнера vd, которые меньше среднего значения.

10. Отсортируйте контейнер vd и выведите его элементы на экран.

Контрольные вопросы

1. Приведите примеры полезных алгоритмов из библиотеки STL?

2. Что делает алгоритм find()? Приведите по крайней мере пять примеров.

3. Что делает алгоритм count_if()?

4. Что алгоритм sort(b,e) использует в качестве критерия поиска?

5. Как алгоритмы из библиотеки STL получают контейнеры в качестве аргумента ввода?

6. Как алгоритмы из библиотеки STL получают контейнеры в качестве аргумента вывода?

7. Как алгоритмы из библиотеки STL обозначают ситуации “не найден” или “сбой”?

8. Что такое функция-объект?

9. Чем функция-объект отличается от функции?

10. Что такое предикат?

11. Что делает алгоритм accumulate()?

12. Что делает алгоритм inner_product()?

13. Что такое ассоциативный контейнер? Приведите не менее трех примеров.

14. Является ли класс list ассоциативным контейнером? Почему нет?

15. Сформулируйте принцип организации бинарного дерева.

16. Что такое (примерно) сбалансированное дерево?

17. Сколько места занимает элемент в контейнере map?

18. Сколько места занимает элемент в контейнере vector?

19. Зачем нужен контейнер unordered_map, если есть (упорядоченный) контейнер map?

20. Чем контейнер set отличается от контейнера map?

21. Чем контейнер multimap отличается от контейнера map?

22. Зачем нужен алгоритм copy(), если мы вполне могли бы написать простой цикл?

23. Что такое бинарный поиск?

Термины

Упражнения

1. Перечитайте главу и выполните все упражнения из врезок ПОПРОБУЙТЕ, если вы еще не сделали этого.

2. Найдите надежный источник документации по библиотеке STL и перечислите все стандартные алгоритмы.

3. Самостоятельно реализуйте алгоритм count(). Протестируйте его.

4. Самостоятельно реализуйте алгоритм count_if(). Протестируйте его.

5. Что нам следовало бы сделать, если бы мы не могли вернуть итератор end(), означающий, что элемент не найден? Заново спроектируйте и реализуйте алгоритмы find() и count(), чтобы они получали итераторы, установленные на первый и последний элементы. Сравните результаты со стандартными версиями.

6. В примере класса Fruit из раздела 21.6.5 мы копировали структуры Fruit в контейнер set. Что делать, если мы не хотим копировать эти структуры? Мы могли бы вместо этого использовать контейнер set. Однако в этом случае мы были бы вынуждены определить оператор сравнения для этого контейнера. Выполните это упражнение еще раз, используя контейнер set, Fruit_comparison>. Обсудите разницу между этими реализациями.

7. Напишите функцию бинарного поиска для класса vector (без использования стандартного алгоритма). Выберите любой интерфейс, какой захотите. Протестируйте его. Насколько вы уверены, что ваша функция бинарного поиска работает правильно? Напишите функцию бинарного поиска для контейнера list. Протестируйте ее. Насколько похожи эти две функции бинарного поиска? Как вы думаете, были бы они настолько похожи, если бы вам не было ничего известно о библиотеке STL?

8. Вернитесь к примеру, связанному с подсчетом частоты слов из раздела 21.6.1, и модифицируйте его, чтобы слова выводились в порядке следования частот, а не в лексикографическом порядке. Например, на экран должна выводиться строка 3: C++, а не C++: 3.

9. Определите класс Order (заказ), члены которого содержат имя клиента, его адрес, дату рождения и контейнер vector. Класс Purchase должен содержать поля name, unit_price и count, характеризующие товар. Определите механизм считывания из файла и записи в файл объектов класса Order. Определите механизм для вывода на экран объектов класса Order. Создайте файл, содержащий по крайней мере десять объектов класса Order, считайте его в контейнер vector, отсортируйте по имени (клиента) и запишите обратно в файл. Создайте другой файл, содержащий по крайней мере десять объектов класса Order, примерно треть из которых хранится в первом файле, считайте их в контейнер list, отсортируйте по адресам (клиента) и запишите обратно в файл. Объедините два файла в третий файл, используя функцию std::merge().

10. Вычислите общее количество заказов в двух файлах из предыдущего упражнения. Значение отдельного объекта класса Purchase (разумеется) равно unitprice*count.

11. Разработайте графический пользовательский интерфейс для ввода заказов из файла.

12. Разработайте графический пользовательский интерфейс для запроса файла заказов; например, “Найти все заказы от Joe,” “определить общую стоимость заказов в файле Hardware” или “перечислить все заказы из файла Clothing.” Подсказка: сначала разработайте обычный интерфейс и лишь потом на его основе начинайте разрабатывать графический.

13. Напишите программу, “очищающую” текстовый файл для использования в программе, обрабатывающей запросы на поиск слов; иначе говоря, замените знаки пунктуации пробелами, переведите слова в нижний регистр, замените выражения don’t словами do not (и т.д.) и замените существительные во множественном числе на существительные в единственном числе (например, слово ships станет ship). Не перестарайтесь. Например, определить множественное число в принципе трудно, поэтому просто удалите букву s, если обнаружите как слово ship, так и слово ships. Примените эту программу к реальному текстовому файлу, содержащему не менее 5 000 слов (например, к научной статье).

14. Напишите программу (используя результат предыдущего упражнения), отвечающую на следующие вопросы и выполняющую следующие задания: “Сколько раз слово ship встречается в файле?” “Какое слово встречается чаще всего?” “Какое слово в файле самое длинное?” “Какое слово в файле самое короткое?” “Перечислите все слова на букву s” и “Перечислите все слова, состоящие из четырех букв”.

15. Разработайте графический пользовательский интерфейс из предыдущего упражнения.

Послесловие

 Библиотека STL является частью стандартной библиотеки ISO C++, содержащей контейнеры и алгоритмы. Она предоставляет обобщенные, гибкие и полезные базовые инструменты. Эта библиотека позволяет сэкономить массу усилий: изобретать колесо заново может быть забавным, но вряд ли продуктивным занятием. Если у вас нет весомых причин избегать библиотеки STL, то используйте ее контейнеры и основные алгоритмы. Что еще важнее, библиотека STL — это пример обобщенного программирования, демонстрирующий, как способы устранения конкретных проблем и набор конкретных решений могут вырасти в мощную и универсальную коллекцию полезных инструментов. Если вам необходимо манипулировать данными — а большинство программистов именно этим и занимаются, — библиотека STL продемонстрирует пример, идею и подход к решению задачи.

Часть IV