bool operator()(const T& x, const T& y) const {return x&& y;}
};
template ‹class T›
struct logical_or: binary_function‹T, T, bool› {
bool operator()(const T& x, const T& y) const {return x || y;}
};
template ‹class T›
struct logical_not: unary_function‹T, bool› {
bool operator()(const T& x) const {return!x;}
};
Распределители
Одна из общих проблем в мобильности - это способность инкапсулировать информацию относительно модели памяти. Эта информация включает типы указателей, тип их разности, тип размера объектов в этой модели памяти, также как её примитивы выделения и освобождения памяти.
STL принимается за эту проблему, обеспечивая стандартный набор требований для распределителей (allocators), являющихся объектами, которые инкапсулируют эту информацию. Все контейнеры в STL параметризованы в терминах распределителей. Это значительно упрощает задачу взаимодействия с многочисленными моделями памяти.
Требования распределителей (Allocator requirements)
В следующей таблице мы предполагаем, что X - класс распределителей для объектов типа T, a - значение X, n имеет тип X::size_type, p имеет тип X::pointer, r имеет тип X::reference и s имеет тип X::const_reference.
Все операции 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_typepointer относится к категории модифицируемых итераторов произвольного доступа, ссылающихся на 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)
template ‹class T›
class allocator {
public:
typedef T* pointer;
typedef const T* const_pointer;
typedef T& reference;
typedef const T& const_reference;
typedef T value_type;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
allocator();
~allocator();
pointer address(reference x);
const_pointer const_address(const_reference x);
pointer allocate(size_type n);
void deallocate(pointer p);
size_type init_page_size();
size_type max_size();
};
class allocator‹void› {
public:
typedef void* pointer;
allocator();
~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) - постоянная