РУКОВОДСТВО ПО СТАНДАРТНОЙ БИБЛИОТЕКЕ ШАБЛОНОВ (STL)
Шрифт:
Распределители
Одна из общих проблем в мобильности - это способность инкапсулировать информацию относительно модели памяти. Эта информация включает типы указателей, тип их разности, тип размера объектов в этой модели памяти, также как её примитивы выделения и освобождения памяти.
STL принимается за эту проблему, обеспечивая стандартный набор требований для распределителей (allocators), являющихся объектами, которые инкапсулируют эту информацию. Все контейнеры в STL параметризованы в терминах распределителей. Это значительно упрощает задачу взаимодействия с многочисленными моделями памяти.
Требования распределителей (Allocator requirements)
В
Все операции c распределителями, как ожидается, сводятся к постоянному времени.
Таблица 7. Требования распределителей
| выражение | возвращаемый тип | утверждение/примечание состояние до/после |
|---|---|---|
| X::value_type | Т | – |
| X::reference | леводопустимое значение T (lvalue of T) | – |
| X::const_reference | const lvalue of T | – |
| X::pointer | указатель на тип T | результатом operator* для значений X::pointer является reference. |
| X::const_pointer | указатель на тип const T | результат operator* для значений X::const_pointer ― const_reference; это - тот же самый тип указателя, как X::pointer, в частности, sizeof(X::const_pointer)==sizeof(X::pointer). |
| X:: size_type | беззнаковый целочисленный тип | тип, который может представлять размер самого большого объекта в модели памяти. |
| X::difference_type | знаковый целочисленный тип | тип, который может представлять разность между двумя любыми указателями в модели памяти. |
| X a; | – | примечание: предполагается деструктор. |
| a.address(r) | указатель | *(a.address(r))==r. |
| a.const_address(s) | const_pointer | *(a.address(s))==s. |
| a.allocate(n) | X::pointer | память распределяется для n объектов типа T, но объекты не создаются. allocate может вызывать соответствующее исключение. |
| a.deallocate(p) | результат не используется | все объекты в области, указываемой p, должны быть уничтожены до этого запроса. |
| construct(p, a) | void | после: *p==a. |
| destroy(p) | void | значение, указываемое p, уничтожается. |
| a.init_page_size | X::size_type | возвращённое значение - оптимальное значение для начального размера буфера данного типа. Предполагается, что если k возвращено функцией init_page_size, t - время конструирования для T, и u - время, которое требуется для выполнения allocate(k), тогда k*t будет намного больше, чем u. |
| a.max_size | X::size_type | наибольшее положительное значение X::difference_type |
pointer относится к категории модифицируемых итераторов произвольного доступа, ссылающихся на T. const_pointer относится к категории постоянных итераторов произвольного доступа, ссылающихся на T. Имеется определённое преобразование из pointer в const_pointer.
Для любого шаблона распределителя Alloc имеется определение для типа void. У Alloc‹void› определены только конструктор, деструктор и Alloc‹void›::pointer. Преобразования определены из любого Alloc‹T›::pointer в Alloc‹void›::pointer и обратно, так что для любого p будет p == Alloc‹T›::pointer(Alloc‹void›::pointer(p)).
Распределитель по умолчанию (The default allocator)
Предполагается, что в дополнение к 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) | постоянная |