должны быть уничтожены все его узлы (с освобождением занимаемой ими памяти). А поскольку контейнер теперь содержит узлы, ранее входившие в
L2
, распределитель памяти
L1
должен освободить память, ранее выделенную распределителем
L2
. Становится ясно, почему Стандарт разрешает программистам STL допускать эквивалентность однотипных распределителей. Это сделано для того, чтобы память, выделенная одним объектом-распределителем (таким как
L2
), могла безопасно освобождаться другим объектом-распределителем (таким как L1). Отсутствие подобного допущения привое бы к значительному усложнению реализации врезки и к снижению ее эффективности (кстати, операции врезки влияют
и на другие компоненты STL, один из примеров приведен в совете 4).
Все это, конечно, хорошо, но чем больше размышляешь на эту тему, тем лучше понимаешь, какие жесткие ограничения накладывает предположение об эквивалентности однотипных распределителей. Из него следует, что переносимые объекты распределителей — то есть распределители памяти, правильно работающие в разных реализациях STL, — не могут обладать состоянием. Другими совами, это означает, что переносимые распределители не могут содержать нестатических переменных (по крайней мере таких, которые бы влияли на их работу). В частности, отсюда следует, что вы не сможете создать два распределителя
SpecialAllocator<int>
, выделяющих память из разных куч (heap). Такие распределители не были бы эквивалентными, и в некоторых реализациях STL попытки использования обоих распределителей привели бы к порче структур данных во время выполнения программы.
Обратите внимание: эта проблема возникает на стадии выполнения. Распределители, обладающие состоянием, компилируются вполне нормально — просто они не работают так, как предполагалось. За эквивалентностью всех однотипных распределителей вы должны следить сами. Не рассчитывайте на то, что компилятор предупредит о нарушении этого ограничения.
Справедливости ради стоит отметить, что сразу же за положением об эквивалентности однотипных распределителей памяти в Стандарт включен следующий текст: «…Авторам реализаций рекомендуется создавать библиотеки, которые… поддерживают неэквивалентные распределители. В таких реализациях… семантика контейнеров и алгоритмов для неэквивалентных экземпляров распределителей определяется самой реализацией».
Трогательное проявление заботы, однако пользователю STL, рассматривающему возможность создания нестандартного распределителя с состоянием, это не дает практически ничего. Этим положением можно воспользоваться только в том случае, если вы уверены в том, что используемая реализация STL поддерживает неэквивалентные распределители, готовы потратить время на углубленное изучение документации, чтобы узнать, подходит ли вам «определяемое самой реализацией» поведение неэквивалентных распределителей, и вас не беспокоят проблемы с переносом кода в реализации STL, в которых эта возможность может отсутствовать. Короче говоря, это положение (для особо любознательных — абзац 5 раздела 20.1.5) лишь выражает некие благие намерения по поводу будущего распределителей. До тех пор пока эти благие намерения не воплотятся в жизнь, программисты, желающие обеспечить переносимость своих программ, должны ограничиваться распределителями без состояния.
Выше уже говорилось о том, что распределители обладают определенным сходством с оператором
new
— они тоже занимаются выделением физической памяти, но имеют другой интерфейс. Чтобы убедиться в этом, достаточно рассмотреть объявления стандартных форм
В обоих случаях передается параметр, определяющий объем выделяемой памяти, но в случае с оператором
new
указывается конкретный объем в байтах, а в случае с
allocator<T>::allocate
указывается количество объектов
T
, размещаемых в памяти. Например, на платформе, где
sizeof (int)==4
, при выделении памяти для одного числа
int
оператору
new
передается число 4, а
allocator<int>::allocate
— число 1.
Для оператора
new
параметр относится к типу
size_t
, а для функции
allocate
— к типу
allocator<T>::size_type
, В обоих случаях это целочисленная величина без знака, причем
allocator<T>::size_type
обычно является простым определением типа для
size_t
. В этом несоответствии нет ничего страшного, однако разные правила передачи параметров оператору
new
и
allocator<T>::allocate
усложняют использование готовых пользовательских версий new в разработке нестандартных распределителей.
Оператор new отличается от
allocator<T>::allocate
и типом возвращаемого значения. Оператор
new
возвращает
void*
, традиционный способ представления указателя на неинициализированную память в C++. Функция
allocator<T>::allocate
возвращает
T*
(через определение типа
pointer
), что не только нетрадиционно, но и отдает мошенничеством. Указатель, возвращаемый
allocator<T>::allocate
, не может указывать на объект
T
, поскольку этот объект еще не был сконструирован! STL косвенно предполагает, что сторона, вызывающая
allocator<T>::allocate
, сконструирует в полученной памяти один или несколько объектов
T
(вероятно, посредством
allocator<T>::construct
,
uninitialized_fill
или
raw_storage_iterator
), хотя в случае
vector::reseve
или
string::reseve
этого может никогда не произойти (совет 13). Различия в типах возвращаемых значений оператора
new
и
allocator<T>::allocate
означают изменение концептуальной модели неинициализированной памяти, что также затрудняет применение опыта реализации оператора
new
к разработке нестандартных распределителей.
Мы подошли к последней странности распределителей памяти в STL: большинство стандартных контейнеров никогда не вызывает распределителей, с которыми они ассоциируются. Два примера:
list<int> L; // То же, что и list<int, allocator<int».
// Контейнер никогда не вызывает
// allocator<int> для выделения памяти!
set<Widget.SAW> s;// SAW представляет собой определение типа
// для SpeciаlAllосаtor<Widget>, однако
// ни один экземпляр SAW не будет
// выделять память!
Данная странность присуща
list
и стандартным ассоциативным контейнерам (
set
,
multiset
,
map
и
multimap
). Это объясняется тем, что перечисленные контейнеры являются узловыми, то есть основаны на структурах данных, в которых каждый новый элемент размещается в динамически выделяемом отдельном узле. В контейнере
list
узлы соответствуют узлам списка. В стандартных ассоциативных контейнерах узлы часто соответствуют узлам дерева, поскольку стандартные ассоциативные контейнеры обычно реализуются в виде сбалансированных бинарных деревьев.
Давайте подумаем, как может выглядеть типичная реализация
list<T>
. Список состоит из узлов, каждый из которых содержит объект
T
и два указателя (на следующий и предыдущий узлы списка).
template<typename T>, // Возможная реализация
typename Allocator=allocator<T> // списка
class list {
private:
Allocator alloc;// Распределитель памяти для объектов типа T