РУКОВОДСТВО ПО СТАНДАРТНОЙ БИБЛИОТЕКЕ ШАБЛОНОВ (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.

Требования

Комментарии:
Популярные книги

Черный Маг Императора 13

Герда Александр
13. Черный маг императора
Фантастика:
попаданцы
аниме
сказочная фантастика
фэнтези
5.00
рейтинг книги
Черный Маг Императора 13

Последняя Арена 4

Греков Сергей
4. Последняя Арена
Фантастика:
рпг
постапокалипсис
5.00
рейтинг книги
Последняя Арена 4

Маяк надежды

Кас Маркус
5. Артефактор
Фантастика:
городское фэнтези
попаданцы
аниме
5.00
рейтинг книги
Маяк надежды

Великий перелом

Ланцов Михаил Алексеевич
2. Фрунзе
Фантастика:
попаданцы
альтернативная история
5.00
рейтинг книги
Великий перелом

Сопротивляйся мне

Вечная Ольга
3. Порочная власть
Любовные романы:
современные любовные романы
эро литература
6.00
рейтинг книги
Сопротивляйся мне

Инквизитор Тьмы 2

Шмаков Алексей Семенович
2. Инквизитор Тьмы
Фантастика:
попаданцы
альтернативная история
аниме
5.00
рейтинг книги
Инквизитор Тьмы 2

Мастер Разума V

Кронос Александр
5. Мастер Разума
Фантастика:
городское фэнтези
попаданцы
5.00
рейтинг книги
Мастер Разума V

Бандит 2

Щепетнов Евгений Владимирович
2. Петр Синельников
Фантастика:
боевая фантастика
5.73
рейтинг книги
Бандит 2

Истребители. Трилогия

Поселягин Владимир Геннадьевич
Фантастика:
альтернативная история
7.30
рейтинг книги
Истребители. Трилогия

Гардемарин Ее Величества. Инкарнация

Уленгов Юрий
1. Гардемарин ее величества
Фантастика:
городское фэнтези
попаданцы
альтернативная история
аниме
фантастика: прочее
5.00
рейтинг книги
Гардемарин Ее Величества. Инкарнация

Падение Твердыни

Распопов Дмитрий Викторович
6. Венецианский купец
Фантастика:
попаданцы
альтернативная история
5.33
рейтинг книги
Падение Твердыни

"Дальние горизонты. Дух". Компиляция. Книги 1-25

Усманов Хайдарали
Собрание сочинений
Фантастика:
фэнтези
боевая фантастика
попаданцы
5.00
рейтинг книги
Дальние горизонты. Дух. Компиляция. Книги 1-25

Ох уж этот Мин Джин Хо 2

Кронос Александр
2. Мин Джин Хо
Фантастика:
попаданцы
5.00
рейтинг книги
Ох уж этот Мин Джин Хо 2

Энфис 6

Кронос Александр
6. Эрра
Фантастика:
героическая фантастика
рпг
аниме
5.00
рейтинг книги
Энфис 6