Программирование

20. Выполните эксперимент, посвященный сравнению временных затрат при работе с классами vector и list. Способ измерения длительности работы программы изложен в разделе 26.6.1. Сгенерируйте N случайных целых чисел в диапазоне [0:N]. Вставьте каждое сгенерированное число в вектор vector (после каждой вставки увеличивающийся на один элемент). Храните объект класса vector в упорядоченном виде; иначе говоря, значение должно быть вставлено так, чтобы все предыдущие значения были меньше или равны ему, а все последующие значения должны быть больше него. Выполните тот же эксперимент, используя класс list для хранения целых чисел. При каких значениях 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. Алгоритмы стандартной библиотеки

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

  По умолчанию проверка равенства выполняется с помощью оператора ==, а упорядочивание — на основе оператора < (меньше). Алгоритмы из стандартной библиотеки определены в заголовке . Более подробную информацию читатели найдут в приложении Б.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() иллюстрирует много полезных проектных идей, поэтому оно достойно изучения.