РУКОВОДСТВО ПО СТАНДАРТНОЙ БИБЛИОТЕКЕ ШАБЛОНОВ (STL)
Шрифт:
Предполагается, что в дополнение к allocator поставщики библиотеки обеспечивают распределители для всех моделей памяти.
Контейнеры
Контейнеры - это объекты, которые содержат другие объекты. Они управляют размещением в памяти и свобождением этих объектов через конструкторы, деструкторы, операции вставки и удаления.
В следующей таблице мы полагаем, что X - контейнерный класс, содержащий объекты типа T, a и b - значения X, u - идентификатор, r - значение X&.
Таблица 8. Требования контейнеров
| выражение | возвращаемый тип | семантика исполнения | утверждение/примечание состояние до/после | сложность |
|---|---|---|---|---|
| X::value_type | Т | – | – | время компиляции |
| X::reference | – | – | – | время компиляции |
| X::const_reference | – | – | – | время
|
| X::pointer | тип указателя, указывающий на X::reference | – | указатель на T в модели памяти, используемой контейнером | время компиляции |
| X::iterator | тип итератора, указывающий на X::reference | – | итератор любой категории, кроме итератора вывода. | время компиляции |
| X::const_iterator | тип итератора, указывающий на X::const_reference | – | постоянный итератор любой категории, кроме итератора вывода. | время компиляции |
| X::difference_type | знаковый целочисленный тип | – | идентичен типу расстояния X::iterator и X::const_iterator | время компиляции |
| X::size_type | беззнаковый целочисленный тип | – | size_type может представлять любое неотрицательное значение difference_type | время компиляции |
| X u; | – | – | после: u.size==0. | постоянная |
| X | – | – | X.size==0. | постоянная |
| X(a) | – | – | a==X(a). | линейная |
| X u(a); X u==a; | – | X u; u = a; | после: u==a. | линейная |
| (&a)-›~X | результат не используется | – | после: a.size==0. примечание: деструктор применяется к каждому элементу a, и вся память возвращается. | линейная |
| a.begin | iterator; const_iterator для постоянного a | – | – | постоянная |
| a.end | iterator; const_iterator для постоянного a | – | – | постоянная |
| a==b | обратимый в bool | a.size==b.size && equal(a.begin, a.end, b.begin) | == - это отношение эквивалентности. примечание: equal определяется в разделе алгоритмов. | линейная |
| a!= b | обратимый в bool | !(a==b) | – | линейная |
| r = a | X& | if(&r!=&a){ (&r)-›X::~X; new(&r)X(a); return r;} | после: r==a. | линейнaя |
| a.size | size_type | size_type n = 0; distance(a.begin, a.end, n); return n; | – | постоянная |
| a.max_size | size_type | – | size самого большого возможного контейнера. | постоянная |
| a.empty | обратимый в bool | a.size==0 | – | постоянная |
| a ‹ b | обратимый в bool | lexicographical_compare(a.begin, a.end, b.begin, b.end) | до: ‹ определён для значений T. ‹ - отношение полного упорядочения. lexicographical_compare определяется в разделе алгоритмов. | линейная |
| a › b | обратимый в bool | b ‹ a | – | линейнaя |
| a ‹= b | обратимый в bool | !(a › b) | – | линейная |
| a ›= b | обратимый в bool | !(a ‹ b) | – | линейная |
| a.swap(b) | void | swap(a, b) | – | постоянная |
Функция-член size возвращает число элементов в контейнере. Её семантика определяется правилами конструкторов, вставок и удалений.
begin возвращает итератор, ссылающийся на первый элемент в контейнере. end возвращает итератор, который является законечным.
Если тип итератора контейнера принадлежит к категории двунаправленных итераторов или итераторов произвольного доступа, то контейнер называется reversible (обратимым) и удовлетворяет следующим дополнительным требованиям:
Таблица 9. Требования обратимых контейнеров (в дополнение к контейнерам)
| выражение | возвращаемый тип | семантика исполнения | сложность |
|---|---|---|---|
| X::reverse_iterator | – | reverse_iterator‹iterator, value_type, reference, difference_type› для итератора произвольного доступа. reverse_bidirectional_iterator‹iterator, value_type, reference, difference_type› для двунаправленного итератора | время компиляции |
| X::const_reverse_iterator | – | reverse_iterator‹const_iterator, value_type, const_reference, difference_type› для итератора произвольного доступа. reverse_bidirectional_iterator‹const_iterator, value_type, const_reference, difference_type› для двунаправленного итератора. | время компиляции |
| a.rbegin | reverse_iterator; const_reverse_iterator для постоянного a | reverse_iterator(end) | постоянная |
| a.rend | reverse_iterator; const_reverse_iterator для постоянного a | reverse_iterator(begin) | постоянная |
Последовательности (Sequences)
Последовательность - это вид контейнера, который организует конечное множество объектов одного и того же типа в строгом линейном порядке. Библиотека обеспечивает три основных вида последовательных контейнеров: vector (вектор), list (список) и deque (двусторонняя очередь). Она также предоставляет контейнерные адаптеры, которые облегчают создание абстрактных типов данных, таких как стеки или очереди, из основных видов последовательностей (или из других видов последовательностей, которые пользователь может сам определить).
В следующих двух таблицах X - последовательный класс, a - значение X, i и j удовлетворяют требованиям итераторов ввода, [i, j) - допустимый диапазон, n - значение X::size_type, p - допустимый итератор для a, q - разыменовываемый итератор для a, [q1, q2) - допустимый диапазон в a, t - значение X::value_type.
Сложности выражений зависят от последовательностей.
Таблица 10. Требования последовательностей (в дополнение к контейнерам)
| выражение | возвращаемый тип | утверждение/примечание состояние до/после |
|---|---|---|
| X(n, t) X a(n, t); | – | после: size==n. создаёт последовательность с n копиями t. |
| X(i, j) X a(i, j); | – | после: size==расстоянию между i и j. создаёт последовательность, равную диапазону [i, j). |
| a.insert(p, t) | iterator | вставляет копию t перед p. возвращаемое значение указывает на вставленную копию. |
| a.insert(p, n, t) | результат не используется | вставляет n копий t перед p. |
| a.insert(p, i, j) | результат не используется | вставляет копии элементов из диапазона [i, j) перед p. |
| a.erase(q) | результат не используется | удаляет элемент, указываемый q. |
| a.erase(ql, q2) | результат не используется | удаляет элементы в диапазоне [ql, q2). |
vector (вектор), list (список) и deque (двусторонняя очередь) выдвигают программисту различные предложения сложности и должны использоваться соответственно. vectоr - тип последовательности, которая используется по умолчанию. list нужно использовать, когда имеются частые вставки и удаления из середины последовательности, deque - структура данных для выбора, когда большинство вставок и удалений происходит в начале или в конце последовательности.
Типы iterator и const_iterator для последовательностей должны быть, по крайней мере, из категории последовательных итераторов.
Таблица 11. Необязательные операции последовательностей
| выражение | возвращаемый тип | семантика исполнения | контейнер |
|---|---|---|---|
| a.front | reference; const_reference для постоянного a | *a.begin | vector, list, deque |
| a.back | reference; const_reference для постоянного a | *a.(--end) | vector, list, deque |
| a.push_front(t) | void | a.insert(a.begin, t) | list, deque |
| a.push_back(t) | void | a.insert(a.end, t) | vector, list, deque |
| a.pop_front | void | a.erase(a.begin) | list, deque |
| a.pop_back | void | a.erase(--a.end) | vector, list, deque |
| a[n] | reference; const_reference для постоянного a | *(a.begin + n) | vector, deque |
Все операции в расположенной выше таблице обеспечиваются только для контейнеров, для которых они занимают постоянное время.
Вектор (Vector)
vector - вид последовательности, которая поддерживает итераторы произвольного доступа. Кроме того, он поддерживает операции вставки и удаления в конце с постоянным (амортизированным) временем; вставка и удаление в середине занимают линейное время. Управление памятью обрабатывается автоматически, хотя для улучшения эффективности можно давать подсказки.