РУКОВОДСТВО ПО СТАНДАРТНОЙ БИБЛИОТЕКЕ ШАБЛОНОВ (STL)

Александр Степанов

Менг Ли

РУКОВОДСТВО ПО СТАНДАРТНОЙ БИБЛИОТЕКЕ ШАБЛОНОВ (STL)

Введение

Стандартная Библиотека Шаблонов предоставляет набор хорошо сконструированных и согласованно работающих вместе обобщённых компонентов C++. Особая забота была проявлена для обеспечения того, чтобы все шаблонные алгоритмы работали не только со структурами данных в библиотеке, но также и с встроенными структурами данных C++. Например, все алгоритмы работают с обычными указателями. Ортогональный проект библиотеки позволяет программистам использовать библиотечные структуры данных со своими собственными алгоритмами, а библиотечные алгоритмы - со своими собственными структурами данных. Хорошо определённые семантические требования и требования сложности гарантируют, что компонент пользователя будет работать с библиотекой и что он будет работать эффективно. Эта гибкость обеспечивает широкую применимость библиотеки.

Другое важное соображение - эффективность. C++ успешен, потому что он объединяет выразительную мощность с эффективностью. Много усилий было потрачено, чтобы проверить, что каждый шаблонный компонент в библиотеке имеет обобщённую реализацию, которая имеет эффективность выполнения с разницей в пределах нескольких процентов от эффективности соответствующей программы ручной кодировки.

Третьим соображением в проекте была разработка библиотечной структуры, которая, будучи естественной и лёгкой для понимания, основана на прочной теоретической основе.

Структура библиотеки

Библиотека содержит пять основных видов компонентов:

- алгоритм (algorithm): определяет вычислительную процедуру.

- контейнер (container): управляет набором объектов в памяти.

- итератор (iterator): обеспечивает для алгоритма средство доступа к содержимому контейнера.

- функциональный объект (function object): инкапсулирует функцию в объекте для использования другими компонентами.

- адаптер (adaptor): адаптирует компонент для обеспечения различного интерфейса.

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

Следующее описание разъясняет структуру библиотеки. Если программные компоненты сведены в таблицу как трёхмерный массив, где одно измерение представляет различные типы данных (например, int, double), второе измерение представляет различные контейнеры (например, вектор, связный список, файл), а третье измерение представляет различные алгоритмы с контейнерами (например, поиск, сортировка, перемещение по кругу), если i, j и k - размеры измерений, тогда должно быть разработано i* j *k различных версий кода. При использовании шаблонных функций, которые берут параметрами типы данных, нам нужно только j * k версий. Далее, если заставим наши алгоритмы работать с различными контейнерами, то нам нужно просто j+k версий. Это значительно упрощает разработку программ, а также позволяет очень гибким способом использовать компоненты в библиотеке вместе с определяемыми пользователем компонентами. Пользователь может легко определить специализированный контейнерный класс и использовать для него библиотечную функцию сортировки. Для сортировки пользователь может выбрать какую-то другую функцию сравнения либо через обычный указатель на сравнивающую функцию, либо через функциональный объект (объект, для которого определён operator()), который сравнивает. Если пользователю необходимо выполнить передвижение через контейнер в обратном направлении, то используется адаптер reverse_iterator.

Библиотека расширяет основные средства C++ последовательным способом, так что программисту на C/C++ легко начать пользоваться библиотекой. Например, библиотека содержит шаблонную функцию merge (слияние). Когда пользователю нужно два массива a и b объединить в с, то это может быть выполнено так:

int a[1000];

int b[2000];

int c[3000];

…

merge(a, a+1000, b, b+2000, c);

Когда пользователь хочет объединить вектор и список (оба - шаблонные классы в библиотеке) и поместить результат в заново распределённую неинициализированную память, то это может быть выполнено так:

vector‹Employee› a;

list‹Employee› b;

…

Employee* с = allocate(a.size() + b.size(), (Employee*)0);

merge(a.begin(), a.end(), b.begin(), b.end(), raw_storage_iterator‹Employee*, Employee›(c));

где begin() и end() - функции-члены контейнеров, которые возвращают правильные типы итераторов или указателе-подобных объектов, позволяющие merge выполнить задание, а raw_storage_iterator - адаптер, который позволяет алгоритмам помещать результаты непосредственно в неинициализированную память, вызывая соответствующий конструктор копирования.

Во многих случаях полезно перемещаться через потоки ввода-вывода таким же образом, как через обычные структуры данных. Например, если мы хотим объединить две структуры данных и затем сохранить их в файле, было бы хорошо избежать создания вспомогательной структуры данных для хранения результата, а поместить результат непосредственно в соответствующий файл. Библиотека обеспечивает и istream_iterator, и ostream_iterator шаблонные классы, чтобы многие из библиотечных алгоритмов могли работать с потоками ввода-вывода, которые представляют однородные блоки данных. Далее приводится программа, которая читает файл, состоящий из целых чисел, из стандартного ввода, удаляя все числа, делящиеся на параметр команды, и записывает результат в стандартный вывод:

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

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