Пользовательский распределитель памяти для карты STL
Этот вопрос касается построения экземпляров пользовательского распределителя во время вставки в std::map.
Вот пользовательский распределитель для std::map<int,int> вместе с небольшой программой, которая его использует:
#include <stddef.h>
#include <stdio.h>
#include <map>
#include <typeinfo>
class MyPool {
public:
void * GetNext() {
return malloc(24);
}
void Free(void *ptr) {
free(ptr);
}
};
template<typename T>
class MyPoolAlloc {
public:
static MyPool *pMyPool;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef T* pointer;
typedef const T* const_pointer;
typedef T& reference;
typedef const T& const_reference;
typedef T value_type;
template<typename X>
struct rebind
{ typedef MyPoolAlloc<X> other; };
MyPoolAlloc() throw() {
printf("-------Alloc--CONSTRUCTOR--------%08x %32s\n", this, typeid(T).name());
}
MyPoolAlloc(const MyPoolAlloc&) throw() {
printf(" Copy Constructor ---------------%08x %32s\n", this, typeid(T).name());
}
template<typename X>
MyPoolAlloc(const MyPoolAlloc<X>&) throw() {
printf(" Construct T Alloc from X Alloc--%08x %32s %32s\n", this, typeid(T).name(), typeid(X).name());
}
~MyPoolAlloc() throw() {
printf(" Destructor ---------------------%08x %32s\n", this, typeid(T).name());
};
pointer address(reference __x) const { return &__x; }
const_pointer address(const_reference __x) const { return &__x; }
pointer allocate(size_type __n, const void * hint = 0) {
if (__n != 1)
perror("MyPoolAlloc::allocate: __n is not 1.\n");
if (NULL == pMyPool) {
pMyPool = new MyPool();
printf("======>Creating a new pool object.\n");
}
return reinterpret_cast<T*>(pMyPool->GetNext());
}
//__p is not permitted to be a null pointer
void deallocate(pointer __p, size_type __n) {
pMyPool->Free(reinterpret_cast<void *>(__p));
}
size_type max_size() const throw() {
return size_t(-1) / sizeof(T);
}
void construct(pointer __p, const T& __val) {
printf("+++++++ %08x %s.\n", __p, typeid(T).name());
::new(__p) T(__val);
}
void destroy(pointer __p) {
printf("-+-+-+- %08x.\n", __p);
__p->~T();
}
};
template<typename T>
inline bool operator==(const MyPoolAlloc<T>&, const MyPoolAlloc<T>&) {
return true;
}
template<typename T>
inline bool operator!=(const MyPoolAlloc<T>&, const MyPoolAlloc<T>&) {
return false;
}
template<typename T>
MyPool* MyPoolAlloc<T>::pMyPool = NULL;
int main(int argc, char *argv[]) {
std::map<int, int, std::less<int>, MyPoolAlloc<std::pair<const int,int> > > m;
//random insertions in the map
m.insert(std::pair<int,int>(1,2));
m[5] = 7;
m[8] = 11;
printf("======>End of map insertions.\n");
return 0;
}
Вот результат этой программы:
------- Alloc - КОНСТРУКТОР --------bffcdaa6 St4pairIKiiE Создание T Alloc из X Alloc- bffcda77 St13_Rb_tree_nodeISt4pairIKiiEE St4pairIKiiE Конструктор копирования ---------------bffcdad8 St13_Rb_tree_nodeISt4pairIKiiEE Разрушитель ---------------------bffcda77 St13_Rb_tree_nodeISt4pairIKiiEE Разрушитель ---------------------bffcdaa6 St4pairIKiiE ======> Создание нового объекта пула. Построить T Alloc из X Alloc-bffcd9df St4pairIKiiE St13_Rb_tree_nodeISt4pairIKiiEE +++++++ 0985d028 St4pairIKiiE. Деструктор ---------------------bffcd9df St4pairIKiiE Создание T Alloc из X Alloc-bffcd95f St4pairIKiiE St13_Rb_tree_nodeISt4pairIKiiEE +++++++ 0985d048 St4pairIKiiE. Деструктор ---------------------bffcd95f St4pairIKiiE Создайте T Alloc из X Alloc-bffcd95f St4pairIKiiE St13_Rb_tree_nodeISt4pairIKiiEE +++++++ 0985d068 St4pairIKiiE. Деструктор ---------------------bffcd95f St4pairIKiiE ======> Конец вставки карты. Создайте T Alloc из X Alloc-bffcda23 St4pairIKiiE St13_Rb_tree_nodeISt4pairIKiiEE -+-+-+- 0985d068. Деструктор ---------------------bffcda23 St4pairIKiiE Создайте T Alloc из X Alloc-bffcda43 St4pairIKiiE St13_Rb_tree_nodeISt4pairIKiiEE -+-+-+- 0985d048. Деструктор ---------------------bffcda43 St4pairIKiiE Создайте T Alloc из X Alloc-bffcda43 St4pairIKiiE St13_Rb_tree_nodeISt4pairIKiiEE -+-+-+- 0985d028. Деструктор ---------------------bffcda43 St4pairIKiiE Деструктор ---------------------bffcdad8 St13_Rb_tree_nodeISt4pairIKiiEE
Последние два столбца выходных данных показывают, что распределитель для std::pair<const int, int> создается каждый раз, когда есть вставка в карту. Почему это необходимо? Есть ли способ подавить это?
Спасибо!
Изменить: Этот код проверен на компьютере x86 с g++ версии 4.1.2. Если вы хотите запустить его на 64-битной машине, вам придется изменить хотя бы строку return malloc(24), Изменение на return malloc(48) должно сработать.
3 ответа
В MyPool.h (синглтон):
class MyPool
{
...
public:
static MyPool & GetInstance( void );
private:
MyPool(void);
}
В MyPool.cpp:
MyPool & MyPool::GetInstance( void )
{
static MyPool retval;
return retval;
}
В fooStdAllocator.h:
#pragma once
#include "MyPool.h"
#pragma push_macro( "new" )
#undef new
#include <new>
template <class T1> class fooStdAllocator;
// Description:
// Specialize for void
template <> class fooStdAllocator<void>
{
public:
typedef void * pointer;
typedef const void* const_pointer;
typedef void value_type;
template <class U1> struct rebind { typedef fooStdAllocator<U1> other; };
};
template <class T1> class fooStdAllocator
{
public:
// Description:
// Typedefs
typedef T1 value_type;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef T1* pointer;
typedef const T1* const_pointer;
typedef T1& reference;
typedef const T1& const_reference;
// Description:
// The rebind member allows a container to construct an allocator for some arbitrary type out of
// the allocator type provided as a template parameter.
template <class U1> struct rebind { typedef fooStdAllocator<U1> other; };
// Description:
// Constructors
fooStdAllocator( void ) : pool(MyPool::GetInstance()) {};
fooStdAllocator( const fooStdAllocator& other ) : pool(MyPool::GetInstance()) {};
template <class U1> fooStdAllocator(const fooStdAllocator<U1>&) : pool(MyPool::GetInstance()) {};
// Description:
// Destructor
~fooStdAllocator( void ) {};
// Description:
// Returns the address of r as a pointer type. This function and the following function are used
// to convert references to pointers.
pointer address(reference r) const { return &r; };
const_pointer address(const_reference r) const { return &r; };
// Description:
// Allocate storage for n values of T1.
pointer allocate( size_type n, fooStdAllocator<void>::const_pointer hint = 0 )
{
// I would never do it that way:
//pointer return_value = reinterpret_cast<pointer>( pool.GetNext() );
// I would prefer to use the got size to allocate:
pointer return_value = reinterpret_cast<pointer>( pool.GetNext(n) );
if ( return_value == 0 )
throw std::bad_alloc();
return return_value;
};
// Description:
// Deallocate storage obtained by a call to allocate.
void deallocate(pointer p, size_type n)
{
pool.Free(p);
};
// Description:
// Return the largest possible storage available through a call to allocate.
size_type max_size() const
{
size_type return_value = 0xFFFFFFFF;
return_value /= sizeof(T1);
return return_value;
};
// Description:
// Construct an object of type T1 at the location of ptr
void construct(pointer ptr)
{
::new (reinterpret_cast<void*>(ptr)) T1;
};
// Description:
// Construct an object of type T1 at the location of ptr, using the value of U1 in the call to the
// constructor for T1.
template <class U1> void construct(pointer ptr, const U1& val)
{
::new (reinterpret_cast<void*>(ptr)) T1(val);
};
// Description:
// Construct an object of type T1 at the location of ptr, using the value of T1 in the call to the
// constructor for T1.
void construct(pointer ptr, const T1& val)
{
::new (reinterpret_cast<void*>(ptr)) T1(val);
};
// Description:
// Call the destructor on the value pointed to by p
void destroy(pointer p)
{
p->T1::~T1();
};
private:
MyPool &pool;
};
// Return true if allocators b and a can be safely interchanged. "Safely interchanged" means that b could be
// used to deallocate storage obtained through a and vice versa.
template <class T1, class T2> bool operator == ( const fooStdAllocator<T1>& a, const fooStdAllocator<T2>& b)
{
return true;
};
// Return false if allocators b and a can be safely interchanged. "Safely interchanged" means that b could be
// used to deallocate storage obtained through a and vice versa.
template <class T1, class T2> bool operator != ( const fooStdAllocator<T1>& a, const fooStdAllocator<T2>& b)
{
return false;
};
#pragma pop_macro( "new" )
Вы можете использовать его следующим образом:
std::map<keyT,valueT,std::less<keyT>,fooStdAllocator> your_map;
Это так, потому что распределитель для std::pair<const int, int> но реализация на самом деле должна выделить более сложную структуру данных, членом которой она является. Хотя я и ожидал, что фактический распределитель должен быть создан и кэширован, это не является незаконным, так как он каждый раз перестраивается. Это деталь реализации, которую вы не можете избежать, не изменив свою реализацию. Фактический тип распределителя, который создается St13_Rb_tree_nodeISt4pairIKiiEE (искаженное имя).
У меня был недавний проект, который заставил меня изучить специальные распределители памяти для контейнеров C++. Именно тогда я наткнулся на эту статью. Этого было достаточно, чтобы скопировать набор кода, требующий минимальных изменений для работы.
Я собираюсь слегка изменить пример кода Naszta, который был разработан Prasoon Tiwari. Первым изменением было превращение MyPool в шаблонный класс. Извините, что мой пример будет включать изменение имени. Вот шаблон:
#pragma once
#include <cstdint>
//class MyPool
template <class T1>
class FooPool
{
public:
typedef T1 value_type;
typedef T1* pointer;
typedef const T1* const_pointer;
typedef T1& reference;
typedef const T1& const_reference;
static FooPool& GetInstance()
{
static FooPool myPool;
return myPool;
}
pointer GetNext( size_t szItemCount )
{
pointer pObjects = nullptr;
if ( szItemCount > 0 )
{
size_t blockSize = szItemCount * sizeof( T1 );
uint8_t* pBytes = new uint8_t[blockSize];
memset( pBytes, 0, blockSize );
pObjects = reinterpret_cast<pointer>(pBytes);
}
return pObjects;
}
bool Free( pointer pObjects )
{
uint8_t* pBytes = reinterpret_cast<uint8_t*>(pObjects);
delete[] pBytes;
return true;
}
private:
// hide constructor to enforce singleton usage
FooPool() = default;
// this constructor will show the type of objects in this pool
//FooPool()
//{
// OutputDebugStringA( "FooPool object type: ");
// OutputDebugStringA( typeid(T1).name() );
// OutputDebugStringA( " aka " );
// OutputDebugStringA( typeid(T1).raw_name() );
// OutputDebugStringA( "\n" );
//}
};
Существенным изменением здесь является то, что FooPool знает тип создаваемых объектов. Это воспринимается как предоставление ему большей гибкости в том, как он может распределять память. Ваш компилятор покажет вам несколько других настроек, которые нужно будет сделать в конструкторах FooStdAllocator.
Теперь это объявлено в FooStdAllocator как:
template <class T1>
class FooStdAllocator
{
private:
FooPool<T1>& m_FooPool;
...
}
Последнее изменение связано с вызовом FooStdAllocator для выполнения выделения. Это было изменено на:
pointer allocate( size_type n, FooStdAllocator<void>::const_pointer hint = nullptr )
{
//pointer return_value = reinterpret_cast<pointer>(pool.GetNext( n * sizeof( T1 ) ));
// FooPool is now templated so it now knows the size of T1
pointer return_value = m_FooPool.GetNext( n );
if ( return_value == nullptr )
{
throw std::bad_alloc();
}
return return_value;
}
Это включает в себя исправление xan в отношении размера распределения.