list<int> для хранения целых чисел. При каких значениях
N класс list обеспечивает более высокое быстродействие, чем класс vector? Попробуйте объяснить результаты эксперимента. Впервые этот эксперимент был предложен Джоном Бентли (John Bentley).
Послесловие
Если бы у нас было 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
{
while (first!=last && *first != val) ++first;
return first;
}
Вы полагаете, что этот цикл вполне тривиален? Мы так не думаем. На самом деле это минимальное, эффективное и непосредственное представление фундаментального алгоритма. Однако, пока мы не рассмотрим несколько примеров, это далеко не очевидно. Сравним несколько версий алгоритма.
template<class In, class T>
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() стал очень популярным, и мы должны понимать его, чтобы читать чужие программы, а частично потому, что для небольших функций, работающих с большими объемами данных, большее значение имеет эффективность.
ПОПРОБУЙТЕ
Уверены ли вы, что эти два
