18.
Стандартная библиотека шаблонов построена на трех базовых и двух вспомогательных понятиях. К базовым понятиям относятся:
контейнеры - содержат коллекции (наборы) объектов (элементов контейнеров);
алгоритмы - предназначены для обработки элементов коллекций, представленных контейнерами;
итераторы - обеспечивают универсальный доступ к элементам контейнеров и перебор этих элементов.
Вспомогательными понятиями служат адаптеры и функторы.
STL контейнер — это параметризованный класс, представляемый шаблоном классов. Объект такого параметризованного класса пригоден для включения других объектов.
Для представления различных коллекций (структур данных) в STL определены контейнеры двух видов: последовательные и ассоциативные.
Последовательные контейнеры представляют собой упорядоченные коллекции, в которых каждый элемент занимает конкретную позицию, не зависящую от значения элемента. Позиция может зависеть от того, какой была коллекция в момент помещения в нее элемента и/или от явного указания места для размещаемого элемента.
Последовательные контейнеры:
deque - дек. Термин происходит от сокращения фразы double-ended queue — двусторонняя очередь. Дек создается как динамический массив, в который можно включать элементы и из которого можно брать элементы с обоих концов. Вставка в произвольную позицию дека — трудоемкая по числу операций и тем самым по времени исполнения процедура. Для применения дека в программу необходимо включить заголовок <deque>.
list - двусвязный список. Каждый элемент списка содержит некоторое значение (данные) и две ссылки (два указателя) - на предыдущий и на последующий элементы списка. Списки не допускают произвольного обращения (доступа) к элементам. Достоинство списка - быстрое выполнение вставки и удаления элемента, размещенного в любой позиции. Требуется только изменение ссылок. Для применения списка в программу необходимо включить заголовок <list>.
vector- вектор - «безопасный», автоматически расширяющийся массив, обеспечивающий произвольный доступ к находящимся в нем элементам. Доступ осуществляется как с помощью индексирования, так и с помощью специального метода at(). Для применения вектора в программу необходимо включить заголовок <vector>.
Вектор — это самый простой контейнер, относящийся к классу упорядоченных коллекций и реализованный в памяти в виде динамического массива, элементы которого хранятся в определенном порядке и занимают непрерывную область памяти с возможностью расширения с конца. В силу такой организации vector обеспечивает произвольный доступ к своим элементам. Итераторы вектора являются итераторами произвольного доступа (т. е. позволяют передвигаться по контейнеру в обоих направлениях на произвольное количество элементов), поэтому к вектору применимы все алгоритмы STL.
Операции вставки и удаления элементов в конце вектора происходят с высоким быстродействием, однако при их выполнении внутри вектора быстродействие существенно снижается, поскольку все элементы в последующих позициях приходится перемещать на новое место.
v[0] | v[1] |
|
|
|
|
|
| v[n] |
|
Рис.1. Структура контейнера vector |
При работе с контейнерами вместо указателей используются итераторы, выполняющие те же функции, но организованные в виде встроенных классов, что позволяет обеспечить корректную работу со всеми контейнерами. Для итераторов перегружены основные операции, имитирующие их поведение как обычных указателей. Одной из особенностей итераторов является соглашение, по которому, при указании интервала, итератор конца показывает не на последний элемент, а на элемент, лежащий после последнего, даже если физически таковой отсутствует. Такой интервал называется полуоткрытым и обозначается: [begin,end).
Чтобы использовать вектор в программе, необходимо подключить заголовочный файл:
#include <vector>
Описание класса vector, как и всей стандартной библиотеки, лежит в стандартной области имен std.
В программе же, при описании переменной типа vector, необходимо конкретизировать тип хранимых данных, например: vector<int> v.
Операции с векторами
Операции с векторами рассмотрим по группам, составив соответствующие таблицы: конструкторы, немодифицирующие операции, операции сравнения, операции присваивания, доступ к элементам вектора, итераторы вектора, вставка и удаление элементов.
Таблица 1. Конструкторы
|
Здесь Т — тип данных элементов вектора.
Таблица 2. Немодифицирующие операции
Операция | Назначение |
v.size () | Возвращает размер вектора |
v.empty() | Возвращает true, если вектор пуст |
v.max_size() | Возвращает максимальный размер вектора |
v.capacity() | Возвращает максимально доступный размер вектора без перераспределения памяти |
v. reserve() | Увеличивает емкость вектора, если текущая емкость меньше |
Таблица 3. Операции сравнения
|
Таблица 4. Операции присваивания
|
Таблица 5. Доступ к элементам вектора
|
С вектором можно обращаться как с массивом данных, однако имеются и дополнительные возможности. Так, метод at(), возвращая элемент контейнера, обеспечивает контроль выхода индекса за границы допустимого интервала, он порождает исключение при выходе за границу интервала, остальные методы в этой ситуации, как правило, приводят к ошибке времени выполнения. Методы front() и back() возвращают первый и последний элементы вектора.
Таблица 6. Итераторы вектора
|
Разработчиками STL приняты соглашения, согласно которым при указании диапазона начальный итератор показывает на первый элемент диапазона, а конечный — на элемент, следующий за последним элементом диапазона. В связи с этим достаточно оригинально решена проблема продвижения по контейнеру в обратном направлении: итератор начала показывает на последний элемент, а итератор конца — на фиктивный элемент, стоящий перед начальным. Их можно было бы назвать "начало конца вектора" и "конец начала вектора".
Таблица 7. Вставка и удаление элементов
|
Контейнер List
По своей внутренней структуре списки принципиально отличаются от векторов и деков. Каждый элемент списка, кроме данных, содержит ссылки на предыдущий и последующий элемент. Такая организация позволяет вставлять и удалять данные не только в начало и конец списка, но и в произвольное место в нем при одной и той же производительности
Списки не поддерживают итераторы произвольного доступа, в них не определены ни оператор индексирования [ ], ни метод at(). Для доступа к элементу списка необходимо перебрать все предшествующие элементы. В связи с этим списки не поддерживают работу с некоторыми алгоритмами. В частности, со списком не может быть реализован алгоритм сортировки, однако список имеет собственные методы сортировки.
Чтобы использовать список в программе, необходимо подключить заголовочный файл list.
Операции со списками рассмотрим по группам, составив соответствующие таблицы: конструкторы, немодифицирующие операции, модифицирующие операции, специальные операции (табл. 8 - 11).
Таблица 8. Конструкторы
|
Таблица 9. Немодифицирующие операции
Операция | Назначение |
lst.size() | Возвращает размер списка |
lst.empty() | Возвращает true, если список пуст |
lst.max_size() | Возвращает максимальный размер списка |
lst1 == lst2 | Проверяет равенство |
lst1!= lst2 | Проверяет неравенство |
lst1 < lst2 | Проверяет, что lst1 < lst2 |
lst1 > lst2 | Проверяет, что lst1 > lst2 |
lst1 <= lst2 | Проверяет, что lst1 <= lst2 |
lst1 >= lst2. | Проверяет, что lstl >= lst2 |
lst.front() | Возвращает первый элемент |
lst.backO | Возвращает последний элемент |
lst.begin() | Возвращает итератор первого элемента |
lst.end() | Возвращает итератор за последним элементом |
lst.rbeginO | Возвращает обратный итератор начала контейнера для перебора в обратном направлении |
lst.rend() | Возвращает обратный итератор конца контейнера для перебора в обратном направлении |
Таблица 10. Модифицирующие операции
Операция | Назначение |
lst1 = lst2 | Присваивает списку lst1 все элементы lst2 |
lst.assign(n,elem) | Присваивает n копий elem |
lst.assign(beg,end) | Присваивает контейнеру list элементы интервала [beg,end) |
lst1.swap(lst2) | Меняет местами содержимое lstl и lst2 |
swap(lstl,lst2) | То же в форме функции |
lst.insert(pos,elem) | Вставляет в позицию pos элемент, возвращает позицию следующего элемента |
lst.insert(pos,n,elem) | Вставляет в позицию pos n элементов elem |
lst.insert(pos,beg,end) | Вставляет элементы интервала [beg, end) с позиции pos |
lst.push_back(elem) | Вставляет элемент elem в конец списка |
lst.pop_back() | Удаляет последний элемент |
lst.push_front(elem) | Вставляет элемент elem в начало списка |
lst.pop_front() | Удаляет первый элемент |
lst.remove(val) | Удаляет все элементы со значением val |
lst.remove_if(op) | Удаляет все элементы, для которых op(elem) возвращает true |
lst.erase(pos) | Удаляет элемент в позиции pos и возвращает позицию следующего элемента |
lst.erase(beg,end) | Удаляет все элементы из интервала [beg, end) и возвращает позицию следующего элемента |
lst.resize(num) | Приводит контейнер к размеру num |
lst.resize(num,elem) | Приводит контейнер к размеру num, новые элементы создаются как копии elem |
lst.clear() | Удаляет содержимое списка |
Таблица 11. Специальные операции списка
Операция | Назначение |
lst.unique() | Удаляет дубликаты |
lst.unique(op) | Удаляет дубликаты, для которых ор возвращает true |
lst.splice(pos,lst1) | Перемещает все элементы lst1 в lst перед позицией итератора pos |
lst.splice(pos,lst1,pos1) | Перемещает все элементы lst1, начиная с позиции итератора pos1, в lst перед позицией итератора pos |
lst.splice(pos,lst1, beg1,end1) | Перемещает все элементы интервала [beg1,end1) списка lst1 в lst перед позицией итератора pos |
lst.sort() | Сортирует все элементы оператором < |
lst.sort(op) | Сортирует все элементы по критерию ор |
lst.merge(lst1) | Перемещает все элементы lst1 в lst с сохранением сортировки |
lst.merge(lstl,op) | Перемещает все элементы lstl в 1st с сохранением сортировки по критерию ор |
lst.reverse() | Переставляет все элементы в обратном порядке |
Итераторы
Итераторы стандартной библиотеки обеспечивают доступ к элементам контейнера. Все контейнеры предоставляют методы для присвоения начального и конечного значения итераторам. Итераторы контейнеров реализованы как вложенные классы, поэтому при действиях с контейнерами можно использовать и соответствующие итераторы. Например, при работе с контейнером-вектором
vector<int> L;
мы можем объявить в программе и соответствующий итератор
vector<int>::iterator il = L.begin();
Категории итераторов
Итераторы стандартной библиотеки делятся на категории. В библиотеке определено 5 категорий итераторов в порядке повышения «способностей»:
- входной (input) — чтение элементов контейнера в прямом направлении;
- выходной (output) — запись элементов контейнера в прямом направлении;
- прямой (forward) — чтение и запись элементов контейнера в прямом направлении;
- двунаправленный (bidirectional) — чтение и запись элементов контейнера в прямом и обратном направлениях;
- произвольного доступа (random access) — произвольный доступ для чтения и записи элементов контейнера.
На практике для любого контейнера гарантируется двунаправленный итератор.
Для всех контейнеров, кроме списка, обеспечивается итератор произвольного доступа, который реализует полную арифметику встроенных указателей.
Итераторы могут быть константными и неконстантными. Константные итераторы не используются для изменения элементов контейнера.
Итераторы могут быть действительными (когда итератору соответствует элемент контейнера) и недействительными (при отсутствии соответствия между итератором и элементами контейнера). Итератор может стать недействительным по трем причинам:
- итератор не был инициализирован;
- итератор равен end();
- контейнер, с которым связан итератор, изменил размеры или вовсе уничтожен.
Последнее часто является источником ошибок в программах, так как при удалении и вставке итераторы становятся недействительными.
Для всех категорий итераторов определены следующие операции (i и j — итераторы):
i++ — смещение вперед (возвращает старую позицию);
++i — смещение вперед (возвращает новую позицию);
i = j — присваивание итераторов;
i == j — сравнение итераторов;
i!= j — сравнение двух итераторов на неравенство;
*i — обращение к элементу;
i->member — обращение к компоненту элемента; эквивалентно операции (*i).member.
Остальные операции, определенные для разных категорий итераторов, представлены в табл.12.
Таблица 12. Операции с итераторами разных категорий
Категория итератора | Операции | Контейнеры |
Входной | х=*і — чтение элемента | все |
Выходной | *i = х — запись элемента | все |
Прямой | х=*і, *i =x | все |
Двунаправленный | х= *i, *i = x, --і, і-- | все |
Произвольного доступа | х =*і, *і = х, --і, і--, і+n, і-n, і+=n, і-=n, і < j, і > j, і <= j, і >= j | все, кроме list |
Итераторы вставки позволяют вставлять в существующий пустой контейнер новые элементы. Библиотека предоставляет три вида итераторов вставки:
back_insert_iterator — вставка в конец последовательности (конечный итератор вставки);
front_insert_iterator — вставка в начало последовательности (начальный итератор вставки);
insert_iterator — вставка перед заданным элементом (общий итератор вставки).
Итератор вставки в конец (конечный итератор) работает с любым последовательным контейнером. Итератор вставки в начало (начальный итератор) нельзя использовать с вектором, поскольку вектор не обеспечивает вставку элементов в начало — для него не определен метод push_front(). Третий вид итераторов подходит для любого контейнера.
Обращаться к итераторам вставки непосредственно не слишком удобно, поэтому в библиотеке реализованы функции-обертки в виде шаблонов. Так, «конечный» итератор для контейнера создается функцией back_inserter():
template <class Container»
back_insert_iterator<Container> back_inserter(Container& x);
Аналогичный вид имеет функция front_inserter():
template <class Container»
front_insert_iterator<Container> front_inserter(Container& x);
Потоковые итераторы — это итераторы в виде адаптеров, воспринимающих поток данных в качестве источника или приемника данных. Потоковый итератор ввода читает элементы из потока данных, а потоковый итератор вывода записывает данные в выходной поток.
Потоковый итератор вывода создается одним из двух конструкторов:
- ostream_iterator<T>(stream, delim) — создается итератор, связанный с выходным потоком streamt в котором выводимые значения разделяются строкой delim (тип const char *);
- ostream_iterator<T>(stream) — создается итератор, связанный с выходным потоком stream, в котором выводимые значения не разделяются.
Вывод в поток выполняется операцией присваивания, а «перемещение» — операцией ++, как и «перемещение» итераторов вставки. Можно использовать итератор вывода непосредственно, однако чаще выходной итератор применяется совместно с алгоритмами.
Потоковый итератор ввода позволяет алгоритмам читать исходные данные не из контейнера, а из входного потока. Для получения данных из потока необходимо иметь два итератора: итератор входного потока и итератор конца потока. Итераторы создаются двумя конструкторами:
- istream_iterator<T>(stream) — создается итератор, связанный с входным потоком stream;
- istream_iterator<T>() — создается итератор конца потока.
Если попытка чтения заканчивается неудачей (например, наступает ситуация end-of-file), потоковый итератор ввода превращается в «конечный» итератор.
Итераторы ввода можно определять отдельными переменными, а можно использовать анонимные непосредственно в качестве аргументов при вызове.
Дата добавления: 2015-09-28; просмотров: 23 | Нарушение авторских прав
| <== предыдущая лекция | | | следующая лекция ==> |
| 15. Понятие вины. Формы и виды виныСогласно психологической теории, вина определяется как психическое отношение лица к совершаемому общественно опасному действию или бездействию и его | | | Городской центр кино и досуга |