РУКОВОДСТВО ПО СТАНДАРТНОЙ БИБЛИОТЕКЕ ШАБЛОНОВ (STL)
Шрифт:
Введение
Стандартная Библиотека Шаблонов предоставляет набор хорошо сконструированных и согласованно работающих вместе обобщённых компонентов C++. Особая забота была проявлена для обеспечения того, чтобы все шаблонные алгоритмы работали не только со структурами данных в библиотеке, но также и с встроенными структурами данных C++. Например, все алгоритмы работают с обычными указателями. Ортогональный проект библиотеки позволяет программистам использовать библиотечные структуры данных со своими собственными алгоритмами, а библиотечные алгоритмы - со своими собственными структурами данных. Хорошо определённые семантические требования и требования сложности гарантируют, что компонент пользователя будет работать с библиотекой и что
Другое важное соображение - эффективность. C++ успешен, потому что он объединяет выразительную мощность с эффективностью. Много усилий было потрачено, чтобы проверить, что каждый шаблонный компонент в библиотеке имеет обобщённую реализацию, которая имеет эффективность выполнения с разницей в пределах нескольких процентов от эффективности соответствующей программы ручной кодировки.
Третьим соображением в проекте была разработка библиотечной структуры, которая, будучи естественной и лёгкой для понимания, основана на прочной теоретической основе.
Структура библиотеки
Библиотека содержит пять основных видов компонентов:
– алгоритм (algorithm): определяет вычислительную процедуру.
– контейнер (container): управляет набором объектов в памяти.
– итератор (iterator): обеспечивает для алгоритма средство доступа к содержимому контейнера.
– функциональный объект (function object): инкапсулирует функцию в объекте для использования другими компонентами.
– адаптер (adaptor): адаптирует компонент для обеспечения различного интерфейса.
Такое разделение позволяет нам уменьшить количество компонентов. Например, вместо написания функции поиска элемента для каждого вида контейнера мы обеспечиваем единственную версию, которая работает с каждым из них, пока удовлетворяется основной набор требований.
Следующее описание разъясняет структуру библиотеки. Если программные компоненты сведены в таблицу как трёхмерный массив, где одно измерение представляет различные типы данных (например, int, double), второе измерение представляет различные контейнеры (например, вектор, связный список, файл), а третье измерение представляет различные алгоритмы с контейнерами (например, поиск, сортировка, перемещение по кругу), если i, j и k - размеры измерений, тогда должно быть разработано i* j *k различных версий кода. При использовании шаблонных функций, которые берут параметрами типы данных, нам нужно только j * k версий. Далее, если заставим наши алгоритмы работать с различными контейнерами, то нам нужно просто j+k версий. Это значительно упрощает разработку программ, а также позволяет очень гибким способом использовать компоненты в библиотеке вместе с определяемыми пользователем компонентами. Пользователь может легко определить специализированный контейнерный класс и использовать для него библиотечную функцию сортировки. Для сортировки пользователь может выбрать какую-то другую функцию сравнения либо через обычный указатель на сравнивающую функцию, либо через функциональный объект (объект, для которого определён operator), который сравнивает. Если пользователю необходимо выполнить передвижение через контейнер в обратном направлении, то используется адаптер reverse_iterator.
Библиотека расширяет основные средства C++ последовательным способом, так что программисту на C/C++ легко начать пользоваться библиотекой. Например, библиотека содержит шаблонную функцию merge (слияние). Когда пользователю нужно два массива a и b объединить в с, то это может быть выполнено так:
Когда пользователь хочет объединить вектор и список (оба - шаблонные
где begin и end - функции-члены контейнеров, которые возвращают правильные типы итераторов или указателе-подобных объектов, позволяющие merge выполнить задание, а raw_storage_iterator - адаптер, который позволяет алгоритмам помещать результаты непосредственно в неинициализированную память, вызывая соответствующий конструктор копирования.
Во многих случаях полезно перемещаться через потоки ввода-вывода таким же образом, как через обычные структуры данных. Например, если мы хотим объединить две структуры данных и затем сохранить их в файле, было бы хорошо избежать создания вспомогательной структуры данных для хранения результата, а поместить результат непосредственно в соответствующий файл. Библиотека обеспечивает и istream_iterator, и ostream_iterator шаблонные классы, чтобы многие из библиотечных алгоритмов могли работать с потоками ввода-вывода, которые представляют однородные блоки данных. Далее приводится программа, которая читает файл, состоящий из целых чисел, из стандартного ввода, удаляя все числа, делящиеся на параметр команды, и записывает результат в стандартный вывод:
Вся работа выполняется алгоритмом remove_copy_if, который читает целые числа одно за другим, пока итератор ввода не становится равным end-of-stream (конец-потока) итератору, который создаётся конструктором без параметров. (Вообще все алгоритмы работают способом "отсюда досюда", используя два итератора, которые показывают начало и конец ввода.) Потом remove_copy_if записывает целые числа, которые выдерживают проверку, в выходной поток через итератор вывода, который связан с cout. В качестве предиката remove_copy_if использует функциональный объект, созданный из функционального объекта modulus‹int›, который берёт i и j и возвращает i % j как бинарный предикат, и превращает в унарный предикат, используя bind2nd, чтобы связать второй параметр с параметром командной строки atoi(argv[1]). Потом отрицание этого унарного предиката получается с помощью адаптера функции not1.
Несколько более реалистичный пример - фильтрующая программа, которая берёт файл и беспорядочно перетасовывает его строки.
В этом примере copy перемещает строки из стандартного ввода в вектор, но так как вектор предварительно не размещён в памяти, используется итератор вставки, чтобы вставить в вектор строки одну за другой. (Эта методика позволяет всем функциям копирования работать в обычном режиме замены также, как в режиме вставки.) Потом random_shuffle перетасовывает вектор, а другой вызов copy копирует его в поток cout.
Требования