Александр Степанов - РУКОВОДСТВО ПО СТАНДАРТНОЙ БИБЛИОТЕКЕ ШАБЛОНОВ (STL)
ИТЕРАТОРЫ ПОТОКОВ
Чтобы шаблоны алгоритмов могли работать непосредственно с потоками ввода-вывода, предусмотрены соответствующие шаблонные классы, подобные итераторам. Например,
partial_sum_copy(istream_iterator‹double›(cin), istream_iterator‹double›(), ostream_iterator‹double›(cout, "n"));
читает файл, содержащий числа с плавающей запятой, из cin и печатает частичные суммы в cout.
Итератор входного потока (Istream Iterator)
istream_iterator‹T› читает (используя operator››) последовательные элементы из входного потока, для которого он был создан. После своего создания итератор каждый раз при использовании ++ читает и сохраняет значение T. Если достигнут конец потока (operator void* () в потоке возвращает false), итератор становится равным значению end-of-stream (конец-потока). Конструктор без параметров istream_iterator() всегда создаёт итераторный объект конца потокового ввода, являющийся единственым законным итератором, который следует использовать для конечного условия. Результат operator* для конца потока не определён, а для любого другого значения итератора возвращается const T&.
Невозможно записывать что-либо с использованием входных итераторов. Основная особенность входных итераторов - тот факт, что операторы ++ не сохраняют равенства, то есть i==j не гарантирует вообще, что ++i==++j. Каждый раз, когда ++ используется, читается новое значение. Практическое следствие этого факта - то, что входные итераторы могут использоваться только для однопроходных алгоритмов, что действительно имеет здравый смысл, так как многопроходным алгоритмам всегда более соответствует использование структур данных в оперативной памяти.
Два итератора конец-потока всегда равны. Итератор конец-потока не равен не-конец-потока итератору. Два не-конец-потока итератора равны, когда они созданы из того же самого потока.
template ‹class T, class Distance = ptrdiff_t›
class istream_iterator: public input_iterator‹T, Distance› {
friend bool operator==(const istream_iterator‹T, Distance›& x, const istream_iterator‹T, Distance›& y);
public:
istream_iterator();
istream_iterator(istream& s);
istream_iterator(const istream_iterator‹T, Distance›& x);
~istream_iterator();
const T& operator*() const;
istream_iterator‹T, Distance›& operator++();
istream_iterator‹T, Distance› operator++(int);
};
template ‹class T, class Distance›
bool operator==(const istream_iterator‹T, Distance›& x, const istream_iterator‹T, Distance›& y);
Итератор выходного потока (Ostream Iterator)
istream_iterator‹T› записывает (используя operator‹‹) последовательные элементы в выходной поток, из которого он был создан. Если он был создан с параметром конструктора char*, эта строка, называемая строкой разделителя (delimiter string), записывается в поток после того, как записывается каждое T. Невозможно с помощью выходного итератора получить значение. Его единственное использование - выходной итератор в ситуациях, подобных нижеследующему:
while (first != last) *result++ = *first++;
ostream_iterator определён как:
template ‹class T›
class ostream_iterator: public output_iterator {
public:
ostream_iterator(ostream& s);
ostream_iterator(ostream& s, const char* delimiter);
ostream_iterator(const ostream_iterator‹T›& x);
~ostream_iterator();
ostream_iterator‹T›& operator=(const T& value);
ostream_iterator‹T›& operator*();
ostream_iterator‹T›& operator++();
ostream_iterator‹T›& operator++(int);
};
АЛГОРИТМЫ
Все алгоритмы отделены от деталей реализации структур данных и используют в качестве параметров типы итераторов. Поэтому они могут работать с определяемыми пользователем структурами данных, когда эти структуры данных имеют типы итераторов, удовлетворяющие предположениям в алгоритмах.
Для некоторых алгоритмов предусмотрены и оперативные и копирующие версии. Решение, включать ли копирующую версию, было обычно основано на рассмотрении сложности. Когда стоимость выполнения операции доминирует над стоимостью копии, копирующая версия не включена. Например, sort_copy не включена, так как стоимость сортировки намного значительнее, и пользователи могли бы также делать copy перед sort. Когда такая версия предусмотрена для какого-то алгоритма algorithm, он называется algorithm _copy . Алгоритмы, которые берут предикаты, оканчиваются суффиксом _if (который следует за суффиксом _copy).
Класс Predicate используется всякий раз, когда алгоритм ожидает функциональный объект, при применении которого к результату разыменования соответствующего итератора возвращается значение, обратимое в bool. Другими словами, если алгоритм берёт Predicate pred как свой параметр и first как свой параметр итератора, он должен работать правильно в конструкции if (pred(*first)) {…}. Предполагается, что функциональный объект pred не применяет какую-либо непостоянную функцию для разыменованного итератора.
Класс BinaryPredicate используется всякий раз, когда алгоритм ожидает функциональный объект, который при его применении к результату разыменования двух соответствующих итераторов или к разыменованию итератора и типа T, когда T - часть сигнатуры, возвращает значение, обратимое в bool. Другими словами, если алгоритм берёт BinaryPredicate binary_pred как свой параметр и first1 и first2 как свои параметры итераторов, он должен работать правильно в конструкции if (binary_pred(*first, *first2)) {…}. BinaryPredicate всегда берёт тип первого итератора как свой первый параметр, то есть в тех случаях, когда T value - часть сигнатуры, он должен работать правильно в контексте if (binary_pred (*first, value)) {…}. Ожидается, что binary_pred не будет применять какую-либо непостоянную функцию для разыменованных итераторов.
В описании алгоритмов операторы + и - используются для некоторых категорий итераторов, для которых они не должны быть определены. В этих случаях семантика a+n такая же, как семантика {X tmp = a; advance(tmp, n); return tmp;}, а семантика a-b такая же, как семантика {Distance n; distance(a, b, n); return n;}.
Не меняющие последовательность операции (Non-mutating sequence operations)
Операции с каждым элементом (For each)
template <class InputIterator, class Function>
Function for_each(InputIterator first, InputIterator last, Function f);
for_each применяет f к результату разыменования каждого итератора в диапазоне [first, last) и возвращает f. Принято, что f не применяет какую-то непостоянную функцию к разыменованному итератору. f применяется точно last-first раз. Если f возвращает результат, результат игнорируется.
Найти (Find)
template ‹class InputIterator, class T›
InputIterator find(InputIterator first, InputIterator last, const T& value);
template ‹class InputIterator, class Predicate›
InputIterator find_if(InputIterator first, InputIterator last, Predicate pred);
find возвращает первый итератор i в диапазоне [first, last), для которого соблюдаются следующие соответствующие условия: *i==value, pred(*i)==true. Если такой итератор не найден, возвращается last. Соответствующий предикат применяется точно find(first, last, value) - first раз.
Найти рядом (Аdjacent find)
template ‹class ForwardIterator›
ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last);
template ‹class ForwardIterator, class BinaryPredicate›
ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate binary_pred);
adjacent_find возвращает первый итератор i такой, что i и i+1 находятся в диапазоне [first, last) и для которого соблюдаются следующие соответствующие условия: *i==*(i+1), binary_pred(*i, *(i+1))==true. Если такой итератор i не найден, возвращается last. Соответствующий предикат применяется, самое большее, max((last - first) - 1, 0) раз.
Подсчет (Count)
template ‹class InputIterator, class T, class Size›
void count(InputIterator first, InputIterator last, const T& value, Size& n);
template ‹class InputIterator, class Predicate, class Size›
void count_if(InputIterator first, InputIterator last, Predicate pred, Size& n);
count добавляет к n число итераторов i в диапазоне [first, last), для которых соблюдаются следующие соответствующие условия: *i==value, pred(*i)==true. Соответствующий предикат применяется точно last-first раз.
count должен сохранять результат в параметре ссылки вместо того, чтобы возвращать его, потому что тип размера не может быть выведен из встроенных типов итераторов, как, например, int*.
Отличие (Mismatch)
template ‹class InputIterator1, class InputIterator2›
pair‹InputIterator1, InputIterator2› mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);
template ‹class InputIterator1, class InputIterator2, class BinaryPredicate›
pair‹InputIterator1, InputIterator2› mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate binary_pred);
mismatch возвращает пару итераторов i и j таких, что j==first2 + (i - first1) и i является первым итератором в диапазоне [first1, last1), для которого следующие соответствующие условия выполнены: !(*i==*(first2 + (i - first1))), binary_pred (*i, *(first2 + (i - first1)))==false. Если такой итератор i не найден, пара last1 и first2 + (last1 - first1) возвращается. Соответствующий предикат применяется, самое большее, last1 - first1 раз.
