Вот сколько ни вожусь с этими аллокаторами, всё одного понять не могу. Зачем они нужны в таком виде?
Реальной области памяти с их помощью не ввести (ссылочного типа не сделать), только разные приплясывания на тему основной памяти. Эффективного распределения в общем случае добиться весьма трудно, в частности rebind требует от аллокатора фактически произвольного распределения памяти при отсутствии данных экземпляра аллокатора или же тем более сложных приплясываний при наличии данных экземпляра (например идентификатора пула или что-то типа этого). Вообще, стандартные аллокаторы (в том числе и по мнению Страуструпа) не должны иметь данных экземпляра. Безумные пляски с аллокаторами можно встретить и в SGI-реализации STL:

>// Note that standard-conforming allocators use many language features
>// that are not yet widely implemented. In particular, they rely on
>// member templates, partial specialization, partial ordering of function
>// templates, the typename keyword, and the use of the template keyword
>// to refer to a template member of a dependent type.

Пример у Страуструпа с Pool_alloc работает на массивах, но вот работать этот аллокатор для списков не будет (без переделок) — он распределяет данные размера sizeof(T), а в списке нужно sizeof(T) + delta, где delta скорее всего 2*sizeof(list_node<T>*) (код условен). Таким образом мы сталкиваемся с двумя одновременными "хинтами" к аллокатору (понятно, что общий аллокатор пойдёт в любом случае, но он не эффективен в частностях).
Первый хинт исходит от пользователя. Например, пользователь может знать, что он напихает кучу элементов в список, что-то с ними поделает, а потом удалит все сразу. Очевидно, в данном случае эффективнее всего работа с пулами, где память распределяется просто как в стеке (путём движения указателя верха и аллокации страниц по мере необходимости, если заранее их число не известно), а потом удаление всего сразу.
Второй хинт исходит от контейнера. Список точно знает, что ему всегда нужно аллоцировать память одинаковыми кусками и это можно эффективно использовать. Другие контейнеры могут предлагать свои хинты. Таких хинтов не так уж и много (даже использование описаных двух резко увеличит эффективность), остаётся только выбрать нужный аллокатор, удовлетворяющий большинству [наиболее важных] хинтов. Как это сделать? Как оставить пользователю возможность всё-таки управлять аллокаторами, так как нужно ему? И не озадачивать пользователя сверх меры, когда это не нужно? Простое — просто, сложное возможно.

Дальнейшие мои размышления были прерваны сном и чтением Страуструпа и стандарта на ночь, дабы всё-таки въехать в глубинную мысль (ибо очень умные люди)... Так и не понял, наверное тормоз я какой-то, и начал думать дальше...
Пришёл примерно к следующим выводам. Во-первых, имеет смысл отделить спецификацию памяти (типы pointer, reference, методы construct, etc) от непосредственно аллокатора. Потому, что в одной памяти могут работать разные аллокаторы, но объекты при этом должны жить счастливо. Во-вторых, в контейнеры передавать некую фабрику аллокаторов, умеющую генерировать аллокаторы по хинтам. Эта фабрика может быть вообще синглетоном, может создаваться по мере необходимости или их может быть много на разные случаи жизни. Важно то, чтобы фабрика умела обрабатывать хинты кумулятивно. Например, пользователь выставляет "много аллокаций, разом удалить", список говорит "аллокации одинакового размера", фабрика выдаёт адекватный аллокатор.

Понятно, что это чистой воды теоретизирование, что фактически имплементация может отличаться, что может быть и на текущей модели аллокаторов можно такое сделать (поправив реализацую STL соответственно)... Но больше всего меня смущает :

Implementations of containers described in this International Standard 
are permitted to assume that their Allocator template parameter meets 
the following two additional requirements:
— All instances of a given allocator type are required to be interchangeable 
and always compare equal to each other.
— The typedef members pointer, const_pointer, size_type, 
and difference_type are required to be T*, T const*, size_t, and ptrdiff_t, 
respectively.

Фиг с ним со вторым требованием, пока мы все чаще всего живём в обычной памяти, кроме того ссылок-то и не сделать. А вот с первым-то что делать?

Вобщем такой вот странный и задумчивый постинг. Можно смело его выбросить

Здравствуйте orangy, Вы писали:

O>Вобщем такой вот странный и задумчивый постинг.

Это не странный, и не задумчивый постинг, ситуация в нем излагается верно. Алокаторы были хорошей идей, но, к сожалению, требования по производительности к контейнерам практически убили идею алокаторов. В своем текущем состоянии алокаторы почти ни на что не годны, если считаться со всеми трбования Стандарта.

Могу немного успокоить: реализация STL от Плоджера (поставляется с MS Visual C++) проверяет равенство алокаторов (для списков точно) при операциях над двумя списками (splice и merge), так что с ней на самом деле можно использовать алокаторы с состоянием. Я сам проверял, здорово работает. STLPort не проверяет равенство алокаторов, и с ним такие фокусы работать не будут.

Здравствуйте orangy, Вы писали:

O>Вот сколько ни вожусь с этими аллокаторами, всё одного понять не могу. Зачем они нужны в таком виде?

Типичные примеры использования: pool, улучшение reference locality, улучшение производительности распределения памяти и т.п.

O>Реальной области памяти с их помощью не ввести (ссылочного типа не сделать), только разные приплясывания на тему основной памяти.

Конечно, новый ссылочный тип ты сделать не сможешь. Насколько я помню, распределители (типа, перевод для allocator ) вводили для работы с far и near памятью, для которой предполагалась возможность указания far/near ссылок средствами компиляторов.

O>Эффективного распределения в общем случае добиться весьма трудно, в частности rebind требует от аллокатора фактически произвольного распределения памяти

Вовсе нет. В своем rebind ты можешь выбирать соответствующий other в зависимости от sizeof(U) переданного в rebind типа U. Если для какого-то размера ты не хочешь писать распределитель — пожалуйста: typedef std::allocator<U> other.

O>при отсутствии данных экземпляра аллокатора или же тем более сложных приплясываний при наличии данных экземпляра (например идентификатора пула или что-то типа этого). Вообще, стандартные аллокаторы (в том числе и по мнению Страуструпа) не должны иметь данных экземпляра.

Что есть, то есть, но об этом ниже.

O>Безумные пляски с аллокаторами можно встретить и в SGI-реализации STL: "Note that standard-conforming allocators use many language features that are not yet widely implemented <...>"

Это не беда самих распределителей, а проблема, специфичная для сторонней STL, предназначенной для большого количества компиляторов, в т.ч. старых. Компиляторы становятся все лучше, а для старых изобретаются все более изощренные техники обхода их недостатков

O>Пример у Страуструпа с Pool_alloc работает на массивах, но вот работать этот аллокатор для списков не будет (без переделок) — он распределяет данные размера sizeof(T), а в списке нужно sizeof(T) + delta, где delta скорее всего 2*sizeof(list_node<T>*) (код условен).

Не беда:

template<class T>
class Pool_alloc
{
public:
  template<class U>
  struct rebind
  {
    typedef Pool_alloc<U> other;
  };

  . . .
};

Список не будет работать непосредственно с Pool_alloc<T>, а получит Pool_alloc<T>::template rebind<list_node<T> >::other, т.е. Pool_alloc<list_node<T> >, в котором sizeof() будет уже правильным, т.е. sizeof(list_node<T>).

O>в данном случае эффективнее всего работа с пулами, где память распределяется просто как в стеке <...> Список точно знает, что ему всегда нужно аллоцировать память одинаковыми кусками и это можно эффективно использовать. <...> Как это сделать?

Единственное препятствие — невозможность распределителя иметь собственное состояние. Не беда, воспользуемся старыми добрыми приемами: пусть его состояние хранится глобально:

template<class T, int Id>
class Alloc
{
  // здесь мы вполне можем скомбинировать Id и T для получения
  // идентификатора данных, хранящихся глобально, и при необходимости
  // получать данные по сгенерированному идентификатору
};

Этот подход позволяет достаточно гибко управлять процессом распределения памяти:

std::list<T, Alloc<T, 1> > l1;
std::list<T, Alloc<T, 1> > l2;
std::list<T, Alloc<T, 2> > l3;
std::list<T, Alloc<T, 2> > l4;

В данном примере предполагается, что первые два списка будут выделять память из одного (глобального) пула, а вторые — из другого.

O>больше всего меня смущает :
O>

O>Implementations of containers described in this International Standard 
O>are permitted to assume that their Allocator template parameter meets 
O>the following two additional requirements:
O>— All instances of a given allocator type are required to be interchangeable 
O>and always compare equal to each other.

Главная проблема заключается в отсутствии достаточного опыта работы с распределителями, имеющими состояние. Никто в точности не представляет их семантику. Если распределители не эквивалентны, то std::list<T>::splice потребует O(n) вычислений, в то время как сейчас O(1) (если std::list<T>::size — O(N)). Иными словами, потребуется копировать содержимое вместо банального изменения пары указателей, как это делают сейчас большинство реализаций. Не вполне ясно, какой выбор следует предпочесть. Кроме того, до сих пор нет согласия, что делать с состояниями распределителей при операциях присваивания и обмена содержимого (swap) контейнеров: одни выступают за копирование/обмен распределителей, другие считают, что распределители копироваться/обмениваться не должны. И т.д. Поэтому было решено не накладывать ограничений на реализации, а подождать пока не будет накоплен достаточный опыт. Стандарт поощряет реализации экспериментировать с распределителями, имеющими состояние. Ходили слухи, что Metrowerks собирались делать что-то в таком духе.

http://www.dinkumware.com/manuals/reader.aspx?lib=cpl&amp;h=lib_cont.html

According to the C++ Standard a container class defined by STL can assume that:

All objects of class Alloc compare equal.
Type Alloc::const_pointer is the same as const Ty *.
Type Alloc::const_reference is the same as const Ty&.
Type Alloc::pointer is the same as Ty *.
Type Alloc::reference is the same as Ty&.
In this implementation, however, containers do not make such simplifying assumptions. Thus, they work properly with allocator objects that are more ambitious:

All objects of class Alloc need not compare equal. (You can maintain multiple pools of storage.)
Type Alloc::const_pointer need not be the same as const Ty *. (A const pointer can be a class.)
Type Alloc::pointer need not be the same as Ty *. (A pointer can be a class.)

Здравствуйте dupamid, Вы писали:

D>Могу немного успокоить: реализация STL от Плоджера (поставляется с MS Visual C++) проверяет равенство алокаторов (для списков точно) при операциях над двумя списками (splice и merge), так что с ней на самом деле можно использовать алокаторы с состоянием. Я сам проверял, здорово работает. STLPort не проверяет равенство алокаторов, и с ним такие фокусы работать не будут.

Не успокоил, к сожалению. Перед тем, как писать этот постинг, я исследовал доступные реализации STL (SGI, Dinkumware, STLPort) на эту тему. Проблемы есть везде и нигде они не решены полностью. Наиболее проработана в этом смысле SGI — правда там свои аллокаторы (которые сейчас и изучаю) + адаптеры к стандарту.
STL от Dinkumware (Плоджеровская) может работать с аллокаторами с состояниями. Но какой ценой? Посмотрим поближе (сильно покоцано):

class _List_nod                                    // base class for _List_ptr to hold allocator _Alnod
class _List_ptr    : public _List_nod<_Ty, _Alloc> // base class for _List_val to hold allocator _Alptr
class _List_val    : public _List_ptr<_Ty, _Alloc>    // base class for list to hold allocator _Alval

В каждом из них хранится по одному аллокатору, полученному через rebind. Причём реально используется для распределения памяти _Alnod, _Alptr — только для конструирования и разрушения указателей на элементы, _Alval и того меньше — для сравнения аллокаторов в операциях типа splice. Таким образом на список заводится как минимум три аллокатора. Далее, несмотря на "пальцатое" использование allocator::pointer там, где это просто, в сложных местах наблюдаются забавные конструкции (упрощено):

_Nodeptr _Buynode(_Nodeptr _Next, _Nodeptr _Prev, const _Ty& _Val)
{    // allocate a node and set links
  _Nodeptr _Pnode = this->_Alnod.allocate(1, (void *)0);
  new ((void *)_Pnode) _Node(_Next, _Prev, _Val);
  return (_Pnode);
}

Т.е. пыжились, пыжились, кричали о том, что надо конструировать объекты через аллокатор (хотя дефолтный и делает то же самое) — так и бросили это гнилое занятие.

Нет в жизни счастья

ЗЫ: желающим предложить счастье в .Net прошу не беспокоиться

Здравствуйте orangy, Вы писали:

O>Не успокоил, к сожалению. Перед тем, как писать этот постинг, я исследовал доступные реализации STL (SGI, Dinkumware, STLPort) на эту тему. Проблемы есть везде и нигде они не решены полностью. Наиболее проработана в этом смысле SGI — правда там свои аллокаторы (которые сейчас и изучаю) + адаптеры к стандарту.
O>STL от Dinkumware (Плоджеровская) может работать с аллокаторами с состояниями. Но какой ценой? Посмотрим поближе (сильно покоцано):
O>

O>class _List_nod                                    // base class for _List_ptr to hold allocator _Alnod
O>class _List_ptr    : public _List_nod<_Ty, _Alloc> // base class for _List_val to hold allocator _Alptr
O>class _List_val    : public _List_ptr<_Ty, _Alloc>    // base class for list to hold allocator _Alval
O>

O>В каждом из них хранится по одному аллокатору, полученному через rebind. Причём реально используется для распределения памяти _Alnod, _Alptr — только для конструирования и разрушения указателей на элементы, _Alval и того меньше — для сравнения аллокаторов в операциях типа splice. Таким образом на список заводится как минимум три аллокатора.

На счет эффективности не проверял, но работать работает — это соверешнно точно! Насчет трех алокаторов, я сдеалал просто, каждый алокатор хранил только указатель на настоящий "мой" алокатор, так что он весил всего sizeof(void*). Равенство алокаторов проверяется через равенство соответствующих указателей на настоящии алокаторы.

O> Далее, несмотря на "пальцатое" использование allocator::pointer там, где это просто, в сложных местах наблюдаются забавные конструкции (упрощено):
O>

O>_Nodeptr _Buynode(_Nodeptr _Next, _Nodeptr _Prev, const _Ty& _Val)
O>{    // allocate a node and set links
O>  _Nodeptr _Pnode = this->_Alnod.allocate(1, (void *)0);
O>  new ((void *)_Pnode) _Node(_Next, _Prev, _Val);
O>  return (_Pnode);
O>}
O>

O>Т.е. пыжились, пыжились, кричали о том, что надо конструировать объекты через аллокатор (хотя дефолтный и делает то же самое) — так и бросили это гнилое занятие.

Память выделяется через алокатор, а конструируется через placment new, что не нравиться? Все равно пользовательский вариант должен давать то же результат.

Здравствуйте Павел Кузнецов, Вы писали:

ПК>Типичные примеры использования: pool, улучшение reference locality, улучшение производительности распределения памяти и т.п.
Да вот, пытаюсь именно для этого и прикрутить всё это дело. Скриплю мозгами

O>>Реальной области памяти с их помощью не ввести (ссылочного типа не сделать), только разные приплясывания на тему основной памяти.

ПК>Конечно, новый ссылочный тип ты сделать не сможешь. Насколько я помню, распределители (типа, перевод для allocator ) вводили для работы с far и near памятью, для которой предполагалась возможность указания far/near ссылок средствами компиляторов.

Дыкть разве модель памяти — то же самое, что и модель распределения?

O>>Эффективного распределения в общем случае добиться весьма трудно, в частности rebind требует от аллокатора фактически произвольного распределения памяти

ПК>Вовсе нет. В своем rebind ты можешь выбирать соответствующий other в зависимости от sizeof(U) переданного в rebind типа U. Если для какого-то размера ты не хочешь писать распределитель — пожалуйста: typedef std::allocator<U> other.
Каким образом я могу выбирать? Специализацией для типа?

O>>Пример у Страуструпа с Pool_alloc работает на массивах, но вот работать этот аллокатор для списков не будет (без переделок) — он распределяет данные размера sizeof(T), а в списке нужно sizeof(T) + delta, где delta скорее всего 2*sizeof(list_node<T>*) (код условен).

ПК>Не беда:
ПК>[код поскипан]

ПК>Список не будет работать непосредственно с Pool_alloc<T>, а получит Pool_alloc<T>::template rebind<list_node<T> >::other, т.е. Pool_alloc<list_node<T> >, в котором sizeof() будет уже правильным, т.е. sizeof(list_node<T>).
Всё правильно, за одним маленьким исключением. Пользователь подобные пулы сконфигурять не может. Точнее, может, но с большими заморочками.
Схема такая:
— в список передаётся распределитель для типа Т
— список, пользуясь rebind получает тип распределеителя для своих узлов
— список создаёт новый распределитель для узлов (а то и больше, см. также другой мой пост в этой теме)
— новый распределитель создаётся как копия полученного, причём используется, очевидно, шаблонный конструктор:
[code]
template<class _Other>
allocator(const allocator<_Other>&)
{ // construct from a related allocator (do nothing)
}
[/ccode]
Таким образом, создаётся куча распределителей, данные копируются туда-сюда и чтобы донести нужную информацию до конкретного распределителя, который будет выделять память нужно долго и высоко прыгать

O>>в данном случае эффективнее всего работа с пулами, где память распределяется просто как в стеке <...> Список точно знает, что ему всегда нужно аллоцировать память одинаковыми кусками и это можно эффективно использовать. <...> Как это сделать?

ПК><...> пусть его состояние хранится глобально:

ПК>

ПК>template<class T, int Id>
ПК>class Alloc
ПК>{
ПК>  // здесь мы вполне можем скомбинировать Id и T для получения
ПК>  // идентификатора данных, хранящихся глобально, и при необходимости
ПК>  // получать данные по сгенерированному идентификатору
ПК>};

А это собственно то же самое, что я и говорил о фабриках аллокаторов, только выражено по другому. Наличие Id означает присутствие в системе (не важно как конкретно оно выглядит) некоего диспетчера, менеджера, фабрики, синглетона, который глобален и может по некоторым данных выдать конкретный объект, который и выполнит функции распределения памяти. Таким образом распределитель — всего лишь адаптер к чему-то более сложному.

ПК>Этот подход позволяет достаточно гибко управлять процессом распределения памяти:
Ессно Поэтому я и думаю о том, как бы это обобщить и привести к общему знаменателю.

[пример поскипан]

O>>больше всего меня смущает <...>:

ПК>Если распределители не эквивалентны, то std::list<T>::splice потребует O(n) вычислений, в то время как сейчас O(1)

Всё это так, пока мы не разделим распределитель и память. splice между разной памятью — O(n), splice внутри одной памяти с любыми распределителями — O(1)

<.. слухи поскипаны ..>

Здравствуйте dupamid, Вы писали:

O>>Не успокоил, к сожалению. <...>
O>><...> Таким образом на список заводится как минимум три аллокатора.

D><...> Насчет трех алокаторов, я сдеалал просто, каждый алокатор хранил только указатель на настоящий "мой" алокатор, так что он весил всего sizeof(void*).
Таким образом, у тебя хранится три одинаковых указателя Это конечно мелочь, но ...

O>>Т.е. пыжились, пыжились, кричали о том, что надо конструировать объекты через аллокатор (хотя дефолтный и делает то же самое) — так и бросили это гнилое занятие.

D>Память выделяется через алокатор, а конструируется через placment new, что не нравиться? Все равно пользовательский вариант должен давать то же результат.
Правильно вызывать _Alnode.construct — мало ли какие телодвижения аллокатор считает нужным выполнить до и/или после конструирования. Может он ссылки считает или в ЦРУ докладывает
Например как в другом месте того же списка:

this->_Alptr.construct(&_Next(_Pnode), _Pnode);

Здравствуйте orangy, Вы писали:

O>Правильно вызывать _Alnode.construct — мало ли какие телодвижения аллокатор считает нужным выполнить до и/или после конструирования. Может он ссылки считает или в ЦРУ докладывает
O>Например как в другом месте того же списка:
O>

this->>_Alptr.construct(&_Next(_Pnode), _Pnode);
O>

Проблема очень проста и обойти ее нельзя метод construct конструирует с помощью контсруктора копирования, если же надо вызвать другой конструктор, то иначе как через placment-new поступить не получиться. Это проблема часто встречается, к сожалению.

Вопрос действитльно ли нужно делать дополнительные действия до и/или после конструирования, гипотетически это недостаток, но на практике, по-моему, не большая проблема.

Здравствуйте dupamid, Вы писали:

O>>Например как в другом месте того же списка:
O>>

this->>>_Alptr.construct(&_Next(_Pnode), _Pnode);
O>>

D>Проблема очень проста и обойти ее нельзя метод construct конструирует с помощью контсруктора копирования, если же надо вызвать другой конструктор, то иначе как через placment-new поступить не получиться. Это проблема часто встречается, к сожалению.
Хмм... А так?

_Alptr.construct(_Pnode,_Node(_Next, _Prev, _Val);

D>Вопрос действитльно ли нужно делать дополнительные действия до и/или после конструирования, гипотетически это недостаток, но на практике, по-моему, не большая проблема.
ИМХО это важно. Хотя, конечно, зависит от задачи.

Здравствуйте orangy, Вы писали:


D>>Проблема очень проста и обойти ее нельзя метод construct конструирует с помощью контсруктора копирования, если же надо вызвать другой конструктор, то иначе как через placment-new поступить не получиться. Это проблема часто встречается, к сожалению.
O>Хмм... А так?
O>

O>_Alptr.construct(_Pnode,_Node(_Next, _Prev, _Val);
O>

При таком коде конструктор копирования для твоего объекта будет вызываться дважды, что может быть очень накладно, я бы предпочел placment-new, хотя это зависит от задачи. Более того, а если _Val нет, что тогда делать, у класса, который засовывается в контейнер, не обязан быть контсруткор по умолчанию.

Здравствуйте dupamid, Вы писали:

O>>Хмм... А так?
O>>

O>>_Alptr.construct(_Pnode,_Node(_Next, _Prev, _Val);
O>>

D>При таком коде конструктор копирования для твоего объекта будет вызываться дважды, что может быть очень накладно, я бы предпочел placment-new, хотя это зависит от задачи. Более того, а если _Val нет, что тогда делать, у класса, который засовывается в контейнер, не обязан быть контсруткор по умолчанию.
Да, я понимаю, что копирования будет два, ну а что делать при такой архитектуре аллокаторов?
И еще,

_Nodeptr _Buynode()
{    // allocate a head node and set links
    _Nodeptr _Pnode = this->_Alnod.allocate(1, (void *)0);
    this->_Alptr.construct(&_Next(_Pnode), _Pnode);
    this->_Alptr.construct(&_Prev(_Pnode), _Pnode);
}

Для головы память выделяется не только под два pointer next и prev, но и под объект, хотя он и не конструируется. Так что накладностей там много, а толку чуть...

Здравствуйте orangy, Вы писали:

O>Да, я понимаю, что копирования будет два, ну а что делать при такой архитектуре аллокаторов?

Архитектура алокаторов мне и самому не нравиться

Что же касается накладных расходов, то даже если у алокатора нет данных экземпляра, то он будет занимать все равно не нулевое место в классе, так как для членов (в отличии от базовых классов) нельзя урезать размер до нуля. Так что при размере алокатора с указатель, есть сильное подозрение, что при использовании стандартных алокаторов размер list будет таким же. К сожалению, под рукой нет компилятора и не могу проверить.

Здравствуйте dupamid, Вы писали:

D>>>Проблема очень проста и обойти ее нельзя метод construct конструирует с помощью контсруктора копирования, если же надо вызвать другой конструктор, то иначе как через placment-new поступить не получиться.
Кстати, если construct сделать темплейтным методом

template<class _Ty>
    class allocator
{
...
 template<class _Tother>
 void construct(pointer _Ptr, const _Tother& _Val)
 {    // construct object of type _Ty at _Ptr with value _Val
   new (_Ptr) _Ty(_Val);
 }
};

То всегда можно создавать прокси-классы для решения проблем многих аргументов.
Например:

struct _Node_proxy
{    // list node proxy
   pointer next,prev;
   const value_type *val;
   _Node_proxy(pointer next, pointer prev, const value_type &val) : next(next), prev(prev), val(&val) {}
}

struct _Node
{    // list node
  ...
  _Node(const _Node_proxy &p) : next(p.next), prev(p.prev), val(*p.val) {}
};

...
_Alloc.construct(Pnode, _Node_proxy(next,prev,val));
...

Ы?

Здравствуйте dupamid, Вы писали:

O>>Да, я понимаю, что копирования будет два, ну а что делать при такой архитектуре аллокаторов?
D>Архитектура алокаторов мне и самому не нравиться
Думать надо, что с этим делать. Жить-то хочется, и жить красиво и удобно

D><...> даже если у алокатора нет данных экземпляра, то он будет занимать все равно не нулевое место в классе, так как для членов (в отличии от базовых классов) нельзя урезать размер до нуля.
Да-да, ты совершенно прав, этот топик я хотел поднять следующим, в отдельной ветке (шоб не мешать в кучу).

Здравствуйте orangy, Вы писали:

O>разве модель памяти — то же самое, что и модель распределения?

Нет, но контейнер интересует как раз нечто, что умеет выделять/освобождать память; откуда это нечто ее берет контейнеру не интересно, за исключением того, какие в ней положены ссылки и указатели.

ПК>>В своем rebind ты можешь выбирать соответствующий other в зависимости от sizeof(U) переданного в rebind типа U. Если для какого-то размера ты не хочешь писать распределитель — пожалуйста: typedef std::allocator<U> other.
O>Каким образом я могу выбирать? Специализацией для типа?

Для выражения `sizeof(U) <= threshold'. Например, так (без частичной специализации, чтобы работало на VC++):

template<class T> class Alloc;

// sizeof(T) <= alloc_threshold
template<bool is_small /* true */>
struct AllocTraits
{
  template<class U>
  struct Rebind
  {
    typedef Alloc<U> Other;
  };
};

// sizeof(T) > alloc_threshold
template<>
struct AllocTraits<false>
{
  template<class U>
  struct Rebind
  {
    typedef std::allocator<U> Other;
  };
};

const unsigned alloc_threshold = 128; // whatever

template<class T>
class Alloc
{
public:
  template<class U>
  struct rebind
  {
    typedef typename AllocTraits<sizeof(U) <= alloc_threshold>::
      template Rebind<U>::Other other;
  };

  . . .
};

ПК>>Список не будет работать непосредственно с Pool_alloc<T>, а получит <...> Pool_alloc<list_node<T> >
O>Всё правильно, за одним маленьким исключением. Пользователь подобные пулы сконфигурять не может. Точнее, может, но с большими заморочками. <...>
O>Таким образом, создаётся куча распределителей, данные копируются туда-сюда и чтобы донести нужную информацию до конкретного распределителя, который будет выделять память нужно долго и высоко прыгать

Ну, не слишком. Достаточно, что в конечный распределитель попадет идентификатор пула (статический, если распределитель не имеет состояния). А как ты предлагаешь делать это по-другому? Стандартизировать какой-либо частный подход типа фабрик распределителей (звучит-то как) или подобного предлагать не надо, т.к. в интерфейсе это ничего не меняет, а является реализацией.

O>>>в данном случае эффективнее всего работа с пулами, где память распределяется просто как в стеке <...> Список точно знает, что ему всегда нужно аллоцировать память одинаковыми кусками и это можно эффективно использовать. <...> Как это сделать?

ПК>><...> пусть его состояние хранится глобально:<...>

O>А это собственно то же самое, что я и говорил о фабриках <...>. Наличие Id означает присутствие в системе <...> некоего диспетчера <...>, который глобален и может по некоторым данных выдать конкретный объект, который и выполнит функции распределения памяти. Таким образом распределитель — всего лишь адаптер к чему-то более сложному.

Я бы сказал "интерфейс". Так, имхо, и должно быть: как мы уже договорились, распределитель не представляет собой саму память, а только способ работы с ней. Разве что, по мере накопления опыта, можно будет сформулировать семантику в случае, когда распределители имеют состояние. "А в остальном, прекрасная маркиза..."

O>Всё это так, пока мы не разделим распределитель и память. splice между разной памятью — O(n), splice внутри одной памяти с любыми распределителями — O(1)

Так и в настоящий момент никто не неволит связывать распределитель и память. Делай, как тебе нравится.

Здравствуйте dupamid, Вы писали:

D>Что же касается накладных расходов, то даже если у алокатора нет данных экземпляра, то он будет занимать все равно не нулевое место в классе, так как для членов (в отличии от базовых классов) нельзя урезать размер до нуля.

Это означает, что решить эту проблему можно, закрыто унаследовав контейнер от распределителя. STLport решает это более сложным способом, но во время написания того кода оптимизация пустых баз еще не была внесена в черновик стандарта.

Здравствуйте orangy, Вы писали:

O>Кстати, если construct сделать темплейтным методом
O>То всегда можно создавать прокси-классы для решения проблем многих аргументов.

Предложение мне нравиться, но писать все равно придеться достаточно много и каждый раз. Хотя это, частично, является выходом из положения, точнее форточкой, через которую, при необходимости, можно вылезти.

Здравствуйте Павел Кузнецов, Вы писали:

D>>Что же касается накладных расходов, то даже если у алокатора нет данных экземпляра, то он будет занимать все равно не нулевое место в классе, так как для членов (в отличии от базовых классов) нельзя урезать размер до нуля.

ПК>Это означает, что решить эту проблему можно, закрыто унаследовав контейнер от распределителя. STLport решает это более сложным способом, но во время написания того кода оптимизация пустых баз еще не была внесена в черновик стандарта.

А как ее решает STLPort?

Наследоваться не всегда хороший подход. Например, при этом потребуется метод swap у алокатора, чтобы поддержать swap у контейнера.

Здравствуйте dupamid, Вы писали:

O>>Кстати, если construct сделать темплейтным методом
O>>То всегда можно создавать прокси-классы для решения проблем многих аргументов.

D>Предложение мне нравиться, но писать все равно придеться достаточно много и каждый раз. Хотя это, частично, является выходом из положения, точнее форточкой, через которую, при необходимости, можно вылезти.

Интересно, что, в свое время, предлагалось сделать аналогичное для метода push_back контейнеров, так, чтобы push_back мог бы не копировать созданный вовне объект, а конструировать его на месте по переданному шаблонному аргументу.