Послесловие
Если бы у нас было N видов контейнеров, содержащих данные, и M операций, которые мы хотели бы над ними выполнить, то мы могли бы легко написать N*M фрагментов кода. Если бы данные имели K разных типов, то нам пришлось бы написать N*M*K фрагментов кода. Библиотека STL решает эту проблему, разрешая задавать тип элемента в виде параметра (устраняя множитель K) и отделяя доступ к данным от алгоритмов. Используя итераторы для доступа к данным в любом контейнере и в любом алгоритме, мы можем ограничиться N+M алгоритмами. Это огромное облегчение. Например, если бы у нас было 12 контейнеров и 60 алгоритмов, то прямолинейный подход потребовал бы создания 720 функций, в то время как стратегия, принятая в библиотеке STL, требует только 60 функций и 12 определений итераторов: тем самым мы экономим 90% работы. Кроме того, в библиотеке STL приняты соглашения, касающиеся определения алгоритмов, упрощающие создание корректного кода и облегчающие его композицию с другими кодами, что также экономит много времени.
Глава 21
Алгоритмы и ассоциативные массивы
“Теоретически практика проста”.
Тригве Рийнскауг (Trygve Reenskaug)
В этой главе мы завершаем описание идей, лежащих в основе библиотеки STL, и наш обзор ее возможностей. Здесь мы сосредоточим свое внимание на алгоритмах. Наша главная цель — ознакомить читателей с десятками весьма полезных алгоритмов, которые сэкономят им дни, если не месяцы, работы. Описание каждого алгоритма сопровождается примерами его использования и указанием технологий программирования, которые обеспечивают его работу. Вторая цель, которую мы преследуем, — научить читателей писать свои собственные элегантные и эффективные алгоритмы в тех случаях, когда ни стандартная, ни другие доступные библиотеки не могут удовлетворить их потребности. Кроме того, мы рассмотрим еще три контейнера:
map
,
set
и
unordered_map
.
21.1. Алгоритмы стандартной библиотеки
Стандартная библиотека содержит около шестидесяти алгоритмов. Все они иногда чем-то полезны; мы сосредоточим внимание на часто используемых алгоритмах, которые используются многими, а также на тех, которые иногда оказываются очень полезными для решения какой-то задачи.
По умолчанию проверка равенства выполняется с помощью оператора
==
, а упорядочивание — на основе оператора
<
(меньше). Алгоритмы из стандартной библиотеки определены в заголовке
<algorithm>
. Более подробную информацию читатели найдут в приложении Б.5 и в источниках, перечисленных в разделе 20.7. Эти алгоритмы работают с одной или двумя последовательностями. Входная последовательность определяется парой итераторов; результирующая последовательность — итератором, установленным на ее первый элемент. Как правило, алгоритм параметризуется одной или несколькими операциями, которые можно определить либо с помощью объектов-функций, либо собственно функций. Алгоритмы обычно сообщают о сбоях, возвращая итератор, установленный на конец входной последовательности. Например, алгоритм
find(b,e,v)
вернет элемент
e
, если не найдет значение
v
.
21.2. Простейший алгоритм: find()
Вероятно, простейшим из полезных алгоритмов является алгоритм
find()
. Он находит элемент последовательности с заданным значением.
template<class In, class T>
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<int>& v,int x)
{
vector<int>::iterator p = find(v.begin(),v.end(),x);
if (p!=v.end()) {
// мы нашли x в v
}
else {
// в v нет элемента, равного x
}
// ...
}
В этом примере, как в большинстве случаев, последовательность содержит все элементы контейнера (в данном случае вектора). Мы сравниваем возвращенный итератор с концом последовательности, чтобы узнать, найден ли искомый элемент.
Теперь мы знаем, как используется алгоритм
find()
, а также группу аналогичных алгоритмов, основанных на тех же соглашениях. Однако, прежде чем переходить к другим алгоритмам, внимательнее посмотрим на определение алгоритма
find()
.
template<class In, class T>
In find(In first,In last,const T& val)
// находит первый элемент в последовательности [first,last],
// равный val
