частности, мы хотели бы иметь код, решающий универсальные задачи программирования, и не переписывать программы каждый раз, когда изменяется способ хранения данных или их интерпретация. В частности, хотелось бы выполнялись следующие условия.
• Поиск значения в объекте класса vector не должен отличаться от поиска значения в массиве.
• Поиск объекта класса string без учета регистра не должен отличаться от поиска объекта класса string с учетом нижнего и верхнего регистров.
• Графическое изображение экспериментальных данных с точными значениями не должно отличаться от графического изображения экспериментальных данных с округленными значениями.
• Копирование файла не должно отличаться от копирования вектора.
Учитывая сказанное, мы хотим писать код, удовлетворяющий следующим условиям:
• его легко читать;
• легко модифицировать;
• он имеет систематический характер;
• он короткий;
• быстро работает.
Для того чтобы минимизировать объем работы программиста, мы должны решить следующие задачи.
• Единообразный доступ к данным:
• независимость от способа хранения данных;
• независимость от типа данных.
• Доступ к данным, безопасный с точки зрения типа:
• легкое перемещение по данным;
• компактное хранение данных.
• Скорость работы:
• поиск данных;
• добавление данных;
• удаление данных.
• Стандартные версии большинства широко распространенных алгоритмов таких как copy, find, search, sort, sum, ...
Библиотека STL обеспечивает не только эти возможности. Мы изучим эту библиотеку не только потому, что она представляет собой очень полезный набор инструментов, но и потому, что является примером максимальной гибкости и эффективности. Библиотека STL была разработана Алексом Степановым (Alex Stepanov) для того, чтобы создать базу для универсальных, правильных и эффективных алгоритмов, работающих с разнообразными структурами данных. Ее целью были простота, универсальность и элегантность математики.
Если бы в нашем распоряжении не было библиотеки с ясно выраженными идеями и принципами, то каждый программист должен был бы разрабатывать каждую программу, используя лишь основные языковые конструкции и придерживаясь идей, которые в данный момент кажутся хорошими. Для этого пришлось бы выполнить много лишней работы. Более того, в результате часто получается беспринципная путаница; часто такие программы не может понять никто, кроме их авторов, и очень сомнительно, что эти программы можно использовать в другом контексте.
Итак, рассмотрев мотивы и цели, перейдем к описанию основных определений из библиотеки STL, а затем изучим примеры их применения для более простого создания более совершенного кода для обработки данных.
20.3. Последовательности и итераторы
Основным понятием в библиотеке STL является последовательность. С точки зрения авторов этой библиотеки, любая коллекция данных представляет собой последовательность. Последовательность имеет начало и конец. Мы можем перемещаться по последовательности от начала к концу, при необходимости считывая или записывая значение элементов. Начало и конец последовательности идентифицируются парой итераторов. Итератор (iterator) — это объект, идентифицирующий элемент последовательности.
Последовательность можно представить следующим образом:
Здесь begin и end — итераторы; они идентифицируют начало и конец последовательности. Последовательность в библиотеке STL часто называют “полуоткрытой” (“half-open”); иначе говоря, элемент, идентифицированный итератором begin, является частью последовательности, а итератор end ссылается на ячейку, следующую за концом последовательности. Обычно такие последовательности (диапазоны) обозначаются следующим образом: [begin:end]. Стрелки, направленные от одного элемента к другому, означают, что если у нас есть итератор на один элемент, то мы можем получить итератор на следующий.
• Что такое итератор? Это довольно абстрактное понятие.
• Итератор указывает (ссылается) на элемент последовательности (или на ячейку, следующую за последним элементом).
• Два итератора можно сравнивать с помощью операторов == и !=.
• Значение элемента, на который установлен итератор, можно получить с помощью унарного оператора * (“разыменование”).
• Итератор на следующий элемент можно получить, используя оператор ++.
Допустим, что p и q — итераторы, установленные на элементы одной и той же последовательности.
Очевидно, что идея итератора связана с идеей указателя (см. раздел 17.4). Фактически указатель на элемент массива является итератором. Однако многие итераторы являются не просто указателями; например, мы могли бы определить итератор с проверкой выхода за пределы допустимого диапазона, который генерирует исключение при попытке сослаться за пределы последовательности [begin:end] или разыменовать итератор end. Оказывается, что итератор обеспечивает огромную гибкость и универсальность именно как абстрактное понятие, а не как конкретный тип. В этой и следующей главах при приведем еще несколько примеров.
ПОПРОБУЙТЕ
Напишите функцию void copy(int* f1, int* e1, int* f2), копирующую элементы массива чисел типа int, определенного последовательностью [f1:e1] в другую последовательность [f2:f2+(e1–f1)]. Используйте только упомянутые выше итераторы (а не индексирование).
Итераторы используются в качестве средства связи между нашим кодом (алгоритмами) и нашими данными. Автор кода знает о существовании итераторов (но не знает, как именно они обращаются к данным), а поставщик данных предоставляет итераторы, не раскрывая всем пользователям детали механизма хранения данных. В результате получаем достаточно независимые друг от друга алгоритмы и контейнеры. Процитируем Алекса Степанова: “Алгоритмы и контейнеры библиотеки STL потому так хорошо работают друг с другом, что ничего не знают друг о друге”. Вместо этого и алгоритмы, и контейнеры знают о последовательностях, определенных парами итераторов.
Иначе говоря, автор кода больше не обязан ничего знать о разнообразных способах хранения данных и обеспечения доступа к ним; достаточно просто знать об итераторах. И наоборот, если поставщик данных больше не обязан писать код для обслуживания огромного количества разнообразных пользователей, ему достаточно реализовать итератор для данных. На базовом уровне итератор определен только операторами *, ++, == и !=. Это обеспечивает его простоту и быстродействие.
Библиотека STL содержит около десяти контейнеров и 60 алгоритмов, связанных с итераторами (см. главу 21). Кроме того, многие организации и отдельные лица создают контейнеры и алгоритмы в стиле библиотеки STL. Вероятно, библиотека STL в настоящее время является наиболее широко известным и широко используемым примером обобщенного программирования (см. раздел 19.3.2). Если вы знаете основы и несколько примеров, то сможете использовать и все остальное.
20.3.1. Вернемся к примерам
Посмотрим, как можно решить задачу “найти максимальный элемент” с помощью последовательности STL.
template<class Iterator>
Iterator high(Iterator first, Iterator last)
