Требования к фактическим параметрам шаблона
Лабораторная работа № 8
Использование контейнеров string и vector библиотеки STL при работе со строковыми данными и численными массивами
Теоретическое описание.
Стандартная библиотека шаблонов (STL) (англ. Standard Template Library) — набор согласованных обобщённых алгоритмов, контейнеров, средств доступа к их содержимому и различных вспомогательных функций в C++.
Стандартная библиотека шаблонов до включения в стандарт C++ была сторонней разработкой, в начале — фирмы HP, а затем SGI. Стандарт языка не называет её «STL», так как эта библиотека стала неотъемлемой частью языка, однако многие люди до сих пор используют это название, чтобы отличать её от остальной части стандартной библиотеки (потоки ввода/вывода (iostream), подраздел Си и др.). Проект под названием STLPort, основанный на SGI STL, осуществляет постоянное обновление STL, iostream и строковых классов. Некоторые другие проекты также занимаются разработкой частных применений стандартной библиотеки для различных конструкторских задач. Каждый производитель компиляторов C++ обязательно поставляет какую-либо реализацию этой библиотеки, так как она является очень важной частью стандарта и широко используется. Архитектура STL была разработана Александром Степановым и Менгом Ли.
В библиотеке выделяют пять основных компонентов:
Контейнер (англ. container) —хранение набора объектов в памяти.Контейнеры библиотекиSTLможно разделить на четыре категории: последовательные, ассоциативные, контейнеры-адаптеры и псевдоконтейнеры. Подробное описание указанных категорий см. в приложении А. В контейнерах для хранения элементов используется семантика передачи объектов по значению. Другими словами, при добавлении контейнер получает копию элемента. Если создание копии нежелательно, то используют контейнер указателей на элементы. Присвоение элементов реализуется с помощью оператора присваивания, а их разрушение происходит с использованием деструктора.
|
|
|
Итератор (англ. iterator) —обеспечение средств доступа к содержимому контейнера.В библиотекеSTL для доступа к элементам в качестве посредника используется обобщённая абстракция, именуемая итератором. Каждый контейнер поддерживает «свой» вид итератора, который представляет собой «модернизированный» интеллектуальный указатель, «знающий» как получить доступ к элементам конкретного контейнера. Стандарт C++ определяет пять категорий итераторов: входные, выходные, однонаправленные, двунаправленные, произвольного доступа Подробное описание указанных категорий итераторов см. в приложении Б.
Алгоритм (англ. algorithm) —определение вычислительной процедуры.Как правило для работыалгоритм получает на вход пару итераторов - интервал. Если алгоритм осуществлял поиск элемента, то будет возвращен либо итератор, указывающий на соответствующий элемент, либо конец интервала.
|
|
|
Адаптер (англ. adaptor) —адаптация компонентов для обеспечения различного интерфейса.
Функциональный объект (англ. functor) —сокрытие функции в объекте для использования другимикомпонентами.
Такое разделение позволяет уменьшить количество компонентов. Например, вместо написания отдельной функции поиска элемента для каждого типа контейнера обеспечивается единственная версия, которая работает с каждым из них, пока соблюдаются основные требования.
Контейнеры
Контейнеры библиотеки STL можно разделить на четыре категории: последовательные, ассоциативные, контейнеры-адаптеры и псевдоконтейнеры.
Последовательные контейнеры
| vector | C-подобный динамический массив произвольного доступа с автоматическим изменением размера при добавлении/удалении элемента. Может быть битовым. |
| list | Двусвязный список, элементы которого хранятся в произвольных кусках памяти, в отличие от контейнера vector, где элементы хранятся в непрерывной области памяти. |
| deque | Контейнер похож на vector, но с возможностью быстрой вставки и удаления элементов на обоих концах. Реализован в виде двусвязанного списка линейных массивов. В отличие от vector, дек не гарантирует расположение всех своих элементов в непрерывном участке памяти, что делает невозможным безопасное использование арифметики указателей для доступа к элементам контейнера. |
| string | Специальный контейнер для работы со строками. Отличие от vector<char> сосредоточены в функциях для манипулирования строками и в политике работы с памятью |
|
|
|
Ассоциативные контейнеры
| set | Упорядоченное множество уникальных элементов. При вставке/удалении элементов множества итераторы, указывающие на элементы этого множества, не становятся недействительными. Обеспечивает стандартные операции над множествами типа объединения, пересечения, вычитания. Тип элементов множества должен реализовывать оператор сравнения operator< или требуется предоставить функцию-компаратор. Реализован на основе самобалансирующего дерева двоичного поиска. |
| multise | То же что и set, но позволяет хранить повторяющиеся элементы. |
| map | Упорядоченный ассоциативный массив пар элементов, состоящих из ключей и соответствующих им значений. Ключи должны быть уникальны. Порядок следования элементов определяется ключами. При этом тип ключа должен реализовывать оператор сравнения operator<, либо требуется предоставить функцию-компаратор. |
| multimap | То же что и map, но позволяет хранить несколько одинаковых ключей. |
|
|
|
Контейнеры –адаптеры
| stack | Стек — контейнер, в котором добавление и удаление элементов осуществляется с одного конца. |
| queue | Очередь — контейнер, с одного конца которого можно добавлять элементы, а с другого — вынимать. |
| priority_queue | Очередь с приоритетом, организованная так, что самый большой элемент всегда стоит на первом месте. |
Псевдоконтейнеры
| bitset | Служит для хранения битовых масок. Похож на vector<bool> фиксированного размера. Размер фиксируется тогда, когда объявляется объект bitset. Итераторов в bitset нет. Оптимизирован по размеру памяти. |
| basic_string | Контейнер, предназначенный для хранения и обработки строк. Хранит в памяти элементы подряд единым блоком, что позволяет организовать быстрый доступ ко всей последовательности. Элементы должны быть POD - простой структурой данных (в современных языках программирования высокого уровня тип данных, имеющий жёстко определённое расположение полей в памяти, не требующий ограничения доступа и автоматического управления. Переменные такого типа можно копировать простыми процедурами копирования участков памяти наподобие memcpy.) Определена конкатенация с помощью +. |
| valarray | Шаблон служит для хранения числовых массивов и оптимизирован для достижения повышенной вычислительной производительности. В некоторой степени похож на vector, но в нём отсутствует большинство стандартных для контейнеров операций. Определены операции над двумя valarray и над valarray и скаляром (поэлементные). Эти операции возможно эффективно реализовать как на векторных процессорах, так и на скалярных процессорах с блоками SIMD. |
В контейнерах для хранения элементов используется семантика передачи объектов по значению. Другими словами, при добавлении контейнер получает копию элемента. Если создание копии нежелательно, то используют контейнер указателей на элементы. Присвоение элементов реализуется с помощью оператора присваивания, а их разрушение происходит с использованием деструктора. В таблице приведены основные требования к элементам в контейнерах:
| Метод | Описание | Примечание |
| Конструктор копии | Создает новый элемент, идентичный старому | Используется при каждой вставке элемента в контейнер |
| Оператор присваивания | Заменяет содержимое элемента копией исходного элемента | Используется при каждой модификации элемента |
| Деструктор | Разрушает элемент | Используется при каждом удалении элемента |
| Конструктор по умолчанию | Создает элемент без аргументов | Применяется только для определенных операций |
| operator== | Сравнивает два элемента | Используется при выполнении operator== для двух контейнеров |
| operator | Определяет, меньше ли один элемент другого | Используется при выполнении operator< для двух контейнеров |
Все «полноценные» стандартные контейнеры удовлетворяют определенному набору требований (или соглашений). В приведенной ниже таблице полагается, что С — класс контейнера, содержащий объекты типа Т.
| Выражение | Возвращаемый тип | Сложность | Примечание |
| C::value type | T | Время компиляции | |
| C::reference | T | Время компиляции | |
| C::const reference | Время компиляции | ||
| C::pointer | Тип указателя, указывающего на C::reference | Время компиляции | Указатель на Т |
| C::iterator | Тип итератора, указывающего на C::reference | Время компиляции | Итератор любого типа, кроме итератора вывода |
| C::const_iterator | Тип итератора, указывающего на C::const_reference | Время компиляции | Итератор любого типа, кроме итератора вывода |
| C::size_type | Беззнаковый целочисленный тип | Время компиляции | |
| C obj; | Постоянная | После: obj.size() == 0 | |
| C obj1; obj1 = obj2; | Линейная | После: obj1 == obj2 | |
| C obj; (&obj)->~C(); | Результат не используется | Линейная | После: a.size() == 0. |
| obj.begin() | Постоянная | ||
| obj.end() | Постоянная | ||
| obj1 == obj2 | Обратимый в bool | Линейная | |
| obj1 != obj2 | Обратимый в bool | Линейная | |
| obj.size() | size_type | Зависит от типа | Не рекомендуется применять для проверки, пуст ли контейнер |
| obj.empty() | Обратимый в bool | Постоянная | |
| obj1 < obj2 | Обратимый в bool | Линейная | |
| obj1 > obj2 | Обратимый в bool | Линейная | |
| obj1 <= obj2 | Обратимый в bool | Линейная | |
| obj1 >= obj2 | Обратимый в bool | Линейная | |
| obj.swap(obj2) | void | Постоянная |
Итераторы
В библиотеке STL для доступа к элементам в качестве посредника используется обобщённая абстракция, именуемая итератором. Каждый контейнер поддерживает «свой» вид итератора, который представляет собой «модернизированный» интеллектуальный указатель, «знающий» как получить доступ к элементам конкретного контейнера. Стандарт C++ определяет пять категорий итераторов, описанных в следующей таблице:
| Категория | Поддерживаемые операции | Примечание |
| Входные | operator++, operator*, operator->, конструктор копии, operator=, operator==, operator!= | Обеспечивают доступ для чтения в одном направлении. Позволяют выполнить присваивание или копирование с помощью оператора присваивания и конструктора копии |
| Выходные | operator++, operator*, конструктор копии | Обеспечивают доступ для записи в одном направлении. Их нельзя сравнивать на равенство. |
| Однонаправленные | operator++, operator*, operator->, конструктор копии, конструктор по умолчанию, operator=, operator==, operator!= | Обеспечивают доступ для чтения и записи в одном направлении. Позволяют выполнить присваивание или копирование с помощью оператора присваивания и конструктора копии. Их можно сравнивать на равенство. |
| Двунаправленные | operator++, operator--, operator*, operator>, конструктор копии, конструктор по умолчанию, operator=, operator==, operator!= | Поддерживают все функции, описанные для однонаправленных итераторов (см. выше). Кроме того, они позволяют переходить к предыдущему элементу. |
| Произвольного доступа | operator++, operator--, operator*, operator>, конструктор копии, конструктор по умолчанию, operator=, operator==, operator!=, operator+, operator-, operator+=, operator-=, operator<, operator>, operator<=, operator>=, operator[] | Эквивалентны обычным указателям: поддерживают арифметику указателей, синтаксис индексации массивов и все формы сравнения. |
| Входные | operator++, operator*, operator->, конструктор копии, operator=, operator==, operator!= | Обеспечивают доступ для чтения в одном направлении. Позволяют выполнить присваивание или копирование с помощью оператора присваивания и конструктора копии |
Использование шаблонов призвано, облегчить процесс написания полноценных программ, где под понятием "написание" подразумевается не только процедура первоначального написания кода программы, но и последующий за этим долгий процесс отладки, модификации и сопровождения, созданного вами программного продукта. Чем же шаблоны могут упростить процесс написания программ?
Ранее мы дублировали и размножали части программ, используя простое, но эффективное средство - текстовый редактор. Сегодня С++ предлагает нам более совершенный способ дублирования, и имя ему - "шаблоны".
Наиболее распространенным поводом для дублирования фрагментов программ является необходимость реализовать некий новый объем кода, аналогичный уже написанному, но изменив типы данных (например, целые на целые длинные). Чаще всего для подобной операции с помощью программы-редактора повторяли текст программы еще раз и меняли типы данных. Программируя на С++, вы могли бы воспользоваться средствами переопределения (перегрузки) и дать обеим функциям одно и тоже имя. Переопределение делает текст программы более наглядным, но не избавляет нас от необходимости повторять один и тот же алгоритм в нескольких местах.
Механизм шаблонов предлагает совершенное решение, позволяющее отделить общий алгоритм от его реализации применительно к конкретным типам данных. Вы можете составить текст подпрограммы сейчас, а используемые типы уточнять позднее. Это возможно, так как используемый тип данных является в этом случае параметром. Шаблоны сочетают в себе преимущества однократной подготовки фрагментов программы (аналогично макрокомандам) и контроль типов, присущий переопределяемым функциям.
В языке С++ имеются два типа шаблонов - шаблоны функций и шаблоны классов.
Шаблоны функций
Объявление шаблона функции начинается с заголовка, состоящего из ключевого слова template, за которым следует список параметров шаблона.
| 1 2 3 4 5 6 7 8 9 | // Описание шаблона функции template <class X> X min (X a, X b) { return a<b ? a : b; } |
Ключевое слово class в описании шаблона означает тип, идентификатор в списке параметров шаблона X означает имя любого типа.
В описании заголовка функции этот же идентификатор означает тип возвращаемого функцией значения и типы параметров функции.
| 1 2 3 4 5 6 7 | ... // Использование шаблона функции int m = min (1, 2); ... |
Экземпляр шаблона функции порождается (генерируется) компилятором
| 1 2 3 4 5 | int min (int a, int b) { return a<b ? a : b; } |
В списке параметров шаблона слово class может также относится к обычному типу данных. Таким образом, список параметров шаблона <class T> просто означает, что Т представляет собой тип, который будет задан позднее. Так как Т является параметром, обозначающим тип, шаблоны иногда называют параметризованными типами.
Приведем описание шаблона функции
| 1 2 3 4 5 6 7 8 9 | template <class T> T toPower (T base, int exponent) { T result = base; if (exponent==0) return (T)1; if (exponent<0) return (T)0; while (--exponent) result *= base; return result; } |
Переменная result имеет тип Т, так что, когда передаваемое в программу значение есть 1 или 0, то оно сначала приводится к типу Т, чтобы соответствовать объявлению шаблона функции.
Типовой аргумент шаблона функции определяется согласно типам данных, используемых в вызове этой функции:
| 1 2 3 4 5 | int i = toPower (10, 3); long l = toPower (1000L, 4); double d = toPower (1e5, 5); |
В первом примере Т становится типом int, во втором - long. Наконец, в третьем примере Т становится типом double. Следующий пример приведет к ошибке компиляции, так как в нем принимающая переменная и возвращаемое значение имеют разные типы:
int i = toPower (1000L, 4);
Требования к фактическим параметрам шаблона
Шаблон функции toPower() может быть использован почти для любого типа данных. Предостережение "почти" проистекает из характера операций, выполняемых над параметром base и переменной result в теле функции toPower(). Какой бы тип мы ни использовали в функции toPower(), эти операции для нее должны быть определены. В противном случае компилятор не будет знать, что ему делать. Вот список действий, выполняемых в функции toPower() с переменными base и result:
1. T result = base;
2. return (T)1;
3. return (T)0;
4. result *= base;
5. return result;
Все эти действия определены для встроенных типов. Однако если вы создадите функцию toPower() для какого-либо классового типа, то в этом случае такой класс должен будет включать общедоступные принадлежащие функции, которые обеспечивают следующие возможности:
- действие 1 инициализирует объект типа Т таким образом, что класс Т должен содержать конструктор копирования,
- действия 2 и 3 преобразуют значения типа int в объект типа Т, поэтому класс Т должен содержать конструктор с параметром типа int, поскольку именно таким способом в классах реализуется преобразование к классовым типам,
- действие 4 использует операцию *= над типом Т, поэтому класс должен содержать собственную функ-цию-operator *=().
- действие 5 предполагает, что в типе T предусмотрена возможность построения безопасной копии возвращаемого объекта (см. конструктор копирования).
Схема такого класса выглядит следующим образом:
| 1 2 3 4 5 6 7 | class T { public: T (const T &base); // конструктор копирования T (int i); //приведение int к Т operator *= (T base); // ... прочие методы } |
Используя классы в шаблонах функций, убедитесь в том, что вы знаете, какие действия с ними выполняются в шаблоне функции, и определены ли для класса эти действия. Если вы не снабдили класс необходимыми функциями, возникнут различные невразумительные сообщения об ошибках.
Дата добавления: 2021-01-21; просмотров: 103; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!