Есть некоторое количество типов (думаю, пара сотен), объекты которых (от десятков до тысяч) будут храниться в списках. Хочется это дело сделать грамотно на аллокаторах, а не просто выделять в куче память для каждого объекта.
В MFC CList<> есть такая штука, которая выделяет память блоками (по умолчанию по 10 штук) и новые элементы списка размещает в ней, т.е. выделение памяти происходит в 10 раз реже; все свободные блоки связываются в односвязный список-"стек", так что при удалении блока из основного списка он просто скидывается в конец односвязного списка свободных блоков, а при последующем добавлении берется оттуда. Все достаточно быстро, по идее сложность константная.
Хочу сделать похожий алгоритм для себя (без MFC).
Первый вопрос — есть ли готовые реализации?
Второй вопрос — а как принято их передавать? Просто передается тип аллокатора шаблонным параметром?