Александр Степанов - РУКОВОДСТВО ПО СТАНДАРТНОЙ БИБЛИОТЕКЕ ШАБЛОНОВ (STL) Страница 12

ИТЕРАТОРЫ ПОТОКОВ

Чтобы шаблоны алгоритмов могли работать непосредственно с потоками ввода-вывода, предусмотрены соответствующие шаблонные классы, подобные итераторам. Например,

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 раз.