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

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

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++. Такой код предназначен как спецификация эквивалентности одной конструкции другой, не обязательно как способ, которым конструкция должна быть реализована (хотя в некоторых случаях данный код, однозначно, является оптимальной реализацией).

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

Чтобы избежать избыточных определений 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);

}

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

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, называемого значимым типом ( value type ) итератора. Для каждого типа итератора X, для которого определено равенство, имеется соответствующий знаковый целочисленный тип, называемый типом расстояния ( distanсe type ) итератора.

Так как итераторы - обобщение указателей, их семантика - обобщение семантики указателей в C++. Это гарантирует, что каждая шаблонная функция, которая использует итераторы, работает с обычными указателями. Есть пять категорий итераторов в зависимости от операций, определённых для них: ввода ( input iterators ), вывода ( output iterators ), последовательные ( forward iterators ), двунаправленные ( bidirectional iterators ) и произвольного доступа ( random access iterators .) Последовательные итераторы удовлетворяют всем требованиям итераторов ввода и вывода и могут использоваться всякий раз, когда определяется тот или другой вид. Двунаправленные итераторы удовлетворяют всем требованиям последовательных итераторов и могут использоваться всякий раз, когда определяется последовательный итератор. Итераторы произвольного доступа удовлетворяют всем требованиям двунаправленных итераторов и могут использоваться всякий раз, когда определяется двунаправленный итератор. Имеется дополнительный атрибут, который могли быть иметь последовательные, двунаправленные и произвольного доступа итераторы, то есть они могут быть модифицируемые ( mutable ) или постоянные ( constant ) в зависимости от того, ведёт ли себя результат operator* как ссылка или как ссылка на константу. Постоянные итераторы не удовлетворяют требованиям итераторов вывода.

Таблица 1. Отношения среди категорий итераторов

Точно также, как обычный указатель на массив гарантирует, что имеется значение указателя, указывающего за последний элемент массива, так и для любого типа итератора имеется значение итератора, который указывает за последний элемент соответствующего контейнера. Эти значения называются законечными ( past-the-end ) значениями. Значения итератора, для которых operator* определён, называются разыменовываемыми ( dereferenceable ). Библиотека никогда не допускает, что законечные значения являются разыменовываемыми. Итераторы могут также иметь исключительные ( singular ) значения, которые не связаны ни с каким контейнером. Например, после объявления неинициализированного указателя x (например, int* x;), всегда должно предполагаться, что x имеет исключительное значение указателя. Результаты большинства выражений не определены для исключительных значений. Единственное исключение - присваивание неисключительного значения итератору, который имеет исключительное значение. В этом случае исключительное значение перезаписывается таким же образом, как любое другое значение. Разыменовываемые и законечные значения всегда являются неисключительными.