Руководство по стандартной библиотеке шаблонов (STL) - [2]

main(int argc, char** argv) {
 if (argc!= 2) throw("usage: remove_if_divides integer\n ");
 remove_copy_if(istream_iterator‹int›(cin), istream_iterator‹int›(), ostream_iterator‹int›(cout, "\n"),  not1(bind2nd(modulus‹int›(), atoi(argv[1]))));
}

Вся работа выполняется алгоритмом remove_copy_if, который читает целые числа одно за другим, пока итератор ввода не становится равным end-of-stream (конец-потока) итератору, который создаётся конструктором без параметров. (Вообще все алгоритмы работают способом "отсюда досюда", используя два итератора, которые показывают начало и конец ввода.) Потом remove_copy_if записывает целые числа, которые выдерживают проверку, в выходной поток через итератор вывода, который связан с cout. В качестве предиката remove_copy_if использует функциональный объект, созданный из функционального объекта modulus‹int›, который берёт i и j и возвращает i % j как бинарный предикат, и превращает в унарный предикат, используя bind2nd, чтобы связать второй параметр с параметром командной строки atoi(argv[1]). Потом отрицание этого унарного предиката получается с помощью адаптера функции not1.

Несколько более реалистичный пример - фильтрующая программа, которая берёт файл и беспорядочно перетасовывает его строки.

main(int argc, char**) {
 if (argc!= 1) throw("usage: shuffle\n");
 vector‹string› v;
 copy(istream_iterator‹string›(cin), istream_iterator‹string›(), inserter(v, v.end()));
 random_shuffle(v.begin(), v.end());
 copy(v.begin(), v.end(), ostream_iterator‹string›(cout));
}

В этом примере copy перемещает строки из стандартного ввода в вектор, но так как вектор предварительно не размещён в памяти, используется итератор вставки, чтобы вставить в вектор строки одну за другой. (Эта методика позволяет всем функциям копирования работать в обычном режиме замены также, как в режиме вставки.) Потом random_shuffle перетасовывает вектор, а другой вызов copy копирует его в поток cout.

Требования

Для гарантии совместной работы различные компоненты библиотеки должны удовлетворять некоторым основным требованиям. Требования должны быть общими, насколько это возможно, так что вместо высказывания "класс X должен определить функцию-член operator++() ", мы говорим "для любого объекта x класса X определён ++x ". (Не определено, является ли оператор членом или глобальной функцией.) Требования установлены в терминах чётких выражений, которые определяют допустимые условия типов, удовлетворяющих требованиям. Для каждого набора требований имеется таблица, которая определяет начальный набор допустимых выражений и их семантику. Любой обобщённый алгоритм, который использует требования, должен быть написан в терминах допустимых выражений для своих формальных параметров.

Если требуется, чтобы была операция линейного времени сложности, это значит - не хуже, чем линейного времени, и операция постоянного времени удовлетворяет требованию.

В некоторых случаях мы представили семантические требования, использующие код C++. Такой код предназначен как спецификация эквивалентности одной конструкции другой, не обязательно как способ, которым конструкция должна быть реализована (хотя в некоторых случаях данный код, однозначно, является оптимальной реализацией).

Основные компоненты

Этот раздел содержит некоторые основные шаблонные функции и классы, которые используются в остальной части библиотеки.

Операторы (Operators)

Чтобы избежать избыточных определений operator!= из operator== и operator›, ‹=, ›= из operator‹, библиотека обеспечивает следующее:

template ‹class Tl, class T2›
inline bool operator!=(const T1& x, const T2& y) {
 return !(x == y);
}

template ‹class Tl, class T2›
inline bool operator›(const T1& x, const T2& y) {
 return y ‹ x;
}

template ‹class Tl, class T2›
inline bool operator‹=(const T1& x, const T2& y) {
 return !(y ‹ x);
}

template ‹class Tl, class T2›
inline bool operator›=(const T1& x, const T2& y) {
 return !(x ‹ y);
}

Пара (Pair)

Библиотека включает шаблоны для разнородных пар значений.

template ‹class T1, class T2›
struct pair {
 T1 first;
 T2 second;
 pair() {}
 pair(const T1& x, const T2& y): first(x), second(y) {}
};

template ‹class T1, class T2›
inline bool operator==(const pair‹Tl,T2›& x, const pair‹Tl,T2›& y) {
 return x.first == y.first && x.second == y.second;
}

template ‹class T1, class T2›
inline bool operator‹(const pair‹Tl,T2›& x, const pair‹Tl,T2›& y) {
 return x.first ‹ y.first || (!(y.first ‹ x.first) && x.second ‹ y.second);
}

Библиотека обеспечивает соответствующую шаблонную функцию make_pair, чтобы упростить конструкцию пар. Вместо выражения, например:

return pair‹int, double›(5, 3.1415926); // явные типы,

можно написать

return make_pair(5, 3.1415926); // типы выводятся.

template ‹class Tl, class T2›
inline pair‹Tl,T2› make_pair(const T1& x, const T2& y) {
 return pair‹Tl,T2›(x, y);
}

Итераторы

Итераторы - это обобщение указателей, которые позволяют программисту работать с различными структурами данных (контейнерами) единообразным способом. Чтобы создать шаблонные алгоритмы, которые правильно и эффективно работают с различными типами структур данных, нам нужно формализовать не только интерфейсы, но также семантику и предположения сложности итераторов. Итераторы - это объекты, которые имеют operator*, возвращающий значение некоторого класса или встроенного типа T, называемого