Распределитель ( allocator ) — важная часть стандартной библиотеки C++, отвечающая за динамическое выделение и освобождение памяти для контейнеров STL во время выполнения. По умолчанию используется универсальный распределитель, но допускается его пользовательское переопределение. Концепция была предложена Александром Страновским в 1994 году при разработке стандартной библиотеки шаблонов (STL) с целью разделить контейнеры от модели хранения данных, а затем, в стандартной версии C++, из-за требований к производительности, степень абстракции модели данных была снижена [1]. Страновский вместе с Бьянно Страуструпом и другими переработали интерфейс контейнеров для совместимости с распределителями, где ключевыми функциями являются определение типов указателей на память, предоставление интерфейсов выделения/освобождения памяти и механизм rebind [1]. В стандарте C++11 был введен областьный распределитель, а ограничения на состояние распределителей были ослаблены, что позволило поддерживать управление общими областями памяти [3–4]. Пользовательские распределители часто применяются для оптимизации производительности пулов памяти, управления специальными областями памяти и отладки ошибок памяти, требуя реализации базовых функций, таких как конструктор и деструктор [1–2][7]. Стратегии реализации распределителей включают пуловые распределители, хеш-карты, списки свободных блоков (FreeList), что повышает эффективность выделения памяти за счет сокращения системных вызовов и минимизации фрагментации памяти.

Введение
Продолжениередактор
В программировании на C++ аlocator (англ. allocator) является важной частью стандартной библиотеки C++. В библиотеке C++ определены различные структуры данных, объединённые общим названием «контейнеры» (например, связанные списки, множества и т.д.), и одним из их общих свойств является возможность изменения размера во время выполнения программы. Для реализации этого особенно важно динамическое выделение памяти, и именно аlocator используется для обработки запросов контейнеров на выделение и освобождение памяти. Другими словами, аlocator предназначен для скрытия низкоуровневых деталей управления памятью в контейнерах STL. По умолчанию стандартная библиотека C++ использует встроенный универсальный аlocator, однако в зависимости от конкретных потребностей программист может самостоятельно создать аlocator для его замены.

Аlocator был впервые разработан Александром Страновским как часть стандартной библиотеки шаблонов C++ (Standard Template Library, STL), с целью создания метода, который «сделает библиотеку более гибкой и независимой от базовой модели данных», позволяя программистам использовать пользовательские типы указателей и ссылок внутри библиотеки. Однако при включении стандартной библиотеки шаблонов в стандартный C++ комитет по стандартизации C++ осознал, что полная абстракция модели данных приведёт к неприемлемым потерям производительности. В качестве компромисса стандарт стал строже регулировать аlocator, и в связи с этим степень настраиваемости аlocator, описанного в современном стандарте, значительно ограничена по сравнению с первоначальными замыслами Страновского.

Хотя настройка аlocator имеет определённые ограничения, в многих случаях всё же требуется использование пользовательских аlocator, обычно для инкапсуляции способов доступа к различным типам памяти (например, к общей памяти и памяти, уже освободившейся), или для повышения производительности при использовании пулов памяти для выделения памяти. Кроме того, с точки зрения использования памяти и времени выполнения, в программах, где выполняется частое выделение небольших объёмов памяти, внедрение специально разработанного аlocator может принести значительную пользу.

Требования к использованиюредактор
Любая классическая C++-класс, удовлетворяющая потребностям использования динамического памяти, может использоваться в качестве динамического памяти. В частности, если класс (в данном случае — класс A) имеет способность выделять память для объектов определённого типа (здесь — типа T), он должен предоставлять следующие определения типов:

A::pointer — указатель
A::const_pointer — постоянный указатель
A::reference — ссылка
A::const_reference — постоянная ссылка
A::value_type — тип значения
A::size_type — тип размера памяти, представляющий максимальный размер одного объекта в модели выделения памяти, определённой классом A, как неотрицательное целое число
A::difference_type — тип разницы между указателями, представляет собой знаковое целое число и используется для обозначения разницы между двумя указателями внутри модели выделения памяти.

Таким образом можно объявить объекты и ссылки на эти объекты в универсальном виде. Цель предоставления allocator этих типов указателей или ссылок заключается в том, чтобы скрыть физические детали реализации указателей или ссылок; поскольку в эпоху 16-битного программирования дальние указатели (far pointer) сильно отличались от обычных указателей, allocator может определять структуры для представления таких указателей или ссылок, и пользователи контейнеров не должны знать, как они реализованы.

Хотя по стандарту допускается предположение, что A::pointer и A::const_pointer класса allocator A являются простыми типами, эквивалентными T* и T const* соответственно при реализации библиотеки, в целом рекомендуется поддерживать универсальные динамические памяти.

Кроме того, если существует динамический памяти A для определённого типа объектов T, то класс A должен содержать четыре членских функции: функцию выделения памяти, функцию освобождения памяти, функцию максимального количества и функцию получения адреса:

A::pointer A::allocate(size_type n, A<void>::const_pointer hint = 0). Функция выделения памяти предназначена для выделения памяти. Параметр вызова n указывает на количество объектов, которое необходимо выделить, а параметр hint (который должен быть указателем на объект, уже выделенный классом A) является необязательным и может использоваться для указания адреса памяти, где будет находиться новый массив при выделении, что позволяет повысить локальность ссылок, однако в реальном процессе выделения программа может автоматически игнорировать этот параметр в зависимости от ситуации. При вызове функции она возвращает указатель на первый элемент нового массива, размер которого достаточно велик, чтобы вместить n элементов класса T. Здесь важно отметить, что при вызове функции память выделена только для этого массива, а сами объекты ещё не созданы.

void A::deallocate(A::pointer p, A::size_type n). Функция освобождения памяти. Здесь p — указатель на объект, который необходимо освободить (параметр передаётся в качестве аргумента функции A::allocate), а n — количество объектов. При вызове этой функции освобождаются n элементов, начиная с p, но объекты не разрушаются. Согласно стандарту C++, перед вызовом функции deallocate объекты в адресном пространстве должны быть разрушены.

A::max_size(), функция максимального количества. Возвращает максимальное количество элементов, которое может успешно выделить однократный вызов функции A::allocate. Результат соответствует значению A::size_type(-1) / sizeof(T).

A::pointer A::address(reference x). Функция получения адреса.При вызове возвращается указатель на x. Кроме того, поскольку процесс создания/разрушения объекта происходит отдельно от процесса выделения/освобождения памяти, динамический память также требует членских функций A::construct (конструктор) и A::destroy (деструктор), которые должны выполнять создание и разрушение объекта соответственно. Эти функции должны быть эквивалентны следующим:

template <typename T>
void A::construct(A::pointer p, A::const_reference t) { new ((void*) p) T(t); }}
template <typename T>
void A::destroy(A::pointer p) { ((T*)p)->~T(); }}
В приведённом коде используется синтаксис placement new и напрямую вызывается деструктор. Детерминатор должен быть копируемым, например, детерминатор для объектов класса T может быть создан из детерминатора для класса U. Если детерминатор выделил блок памяти, то этот блок можно освободить только детерминатором, эквивалентным данному детерминатору. Кроме того, детерминатор должен предоставлять член-класс шаблонный template <typename U> struct A::rebind { typedef A<U> other;};С помощью параметризации шаблонов (C++) можно получать разные динамические память для различных типов данных. Например, если задан динамический память IntAllocator для целого типа (int), то можно вызвать IntAllocator::rebind<long>::other, чтобы получить соответствующий динамический память для длинного целого типа (long). Фактически, stl::list<int> фактически выделяет node<int>, содержащий указатели на двунаправленную связную список, а не сам тип int — именно поэтому и был введен оператор rebind. Операторы сравнения, связанные с динамическими памятью, возвращают истину только тогда, когда память, выделенная одним динамическим памятью, может быть освобождена другим динамическим памятью. Результат оператора != противоположен этому.