Стандартная библиотека шаблонов (классов) - STL

STL - Standart Template Library. Стандартная библиотека шаблонов. Эта библиотека представляет большой набор данных структур и алгоритмов. Кстати она разработана, что очень приятно Александром Степановым и Менг Ли работающих в Hewlett-Packard Lab, им помогал Д.Л. Муссер из Ренсселэровского политехнического института.

STL - это не просто расширение, недавно он был принят комитетом по стантартизации ANSI/ISO в качестве составляющей стандартной библиотеки C++. STL поддерживает как компилятор Borland, для которого его реализовала Rogue Wave Software так и Microsoft. У STL есть несколько версий.

Главное отличие STL это то, что она отделяет структуры данных от алгоритмов, которые с ними работают. Кроме того код у неё очень компактен.

Можно смело сказать, что основу STL составляют шаблоны. Именно они позволяют значительно сократить количество кода для программирования алгоритмов.

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

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

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

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

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

5 адаптер (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.

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

Если тип итератора контейнера принадлежит к категории двунаправленных итераторов или итераторов произвольного доступа, то контейнер называется reversible (обратимым).

Последовательность - это вид контейнера, который организует конечное множество объектов одного и того же типа в строгом линейном порядке. Библиотека обеспечивает три основных вида последовательных контейнеров:

1 vector (вектор) - тип последовательности, которая используется по умолчанию,

2 list (список) - нужно использовать, когда имеются частые вставки и удаления из середины последовательности,

3 deque (двусторонняя очередь) - структура данных для выбора, когда большинство вставок и удалений происходит в начале или в конце последовательности.

Последовательность также предоставляет контейнерные адаптеры, которые облегчают создание абстрактных типов данных, таких как стеки или очереди, из основных видов последовательностей (или из других видов последовательностей, которые пользователь может сам определить).