Bộ nhớ tùy chỉnh Allocator cho bản đồ STL

Question

Câu hỏi này là về việc xây dựng các phiên bản của trình phân bổ tùy chỉnh trong khi chèn vào một bản đồ :: std.

Đây là một cấp phát tùy chỉnh cho std::map<int,int> cùng với một chương trình nhỏ mà sử dụng nó:

#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; 
} 

Đây là kết quả của chương trình này:

 
-------Alloc--CONSTRUCTOR--------bffcdaa6      St4pairIKiiE 
Construct T Alloc from X Alloc--bffcda77 St13_Rb_tree_nodeISt4pairIKiiEE      St4pairIKiiE 
Copy Constructor ---------------bffcdad8 St13_Rb_tree_nodeISt4pairIKiiEE 
Destructor ---------------------bffcda77 St13_Rb_tree_nodeISt4pairIKiiEE 
Destructor ---------------------bffcdaa6      St4pairIKiiE 
======>Creating a new pool object. 
Construct T Alloc from X Alloc--bffcd9df      St4pairIKiiE St13_Rb_tree_nodeISt4pairIKiiEE 
+++++++ 0985d028 St4pairIKiiE. 
Destructor ---------------------bffcd9df      St4pairIKiiE 
Construct T Alloc from X Alloc--bffcd95f      St4pairIKiiE St13_Rb_tree_nodeISt4pairIKiiEE 
+++++++ 0985d048 St4pairIKiiE. 
Destructor ---------------------bffcd95f      St4pairIKiiE 
Construct T Alloc from X Alloc--bffcd95f      St4pairIKiiE St13_Rb_tree_nodeISt4pairIKiiEE 
+++++++ 0985d068 St4pairIKiiE. 
Destructor ---------------------bffcd95f      St4pairIKiiE 
======>End of map insertions. 
Construct T Alloc from X Alloc--bffcda23      St4pairIKiiE St13_Rb_tree_nodeISt4pairIKiiEE 
-+-+-+- 0985d068. 
Destructor ---------------------bffcda23      St4pairIKiiE 
Construct T Alloc from X Alloc--bffcda43      St4pairIKiiE St13_Rb_tree_nodeISt4pairIKiiEE 
-+-+-+- 0985d048. 
Destructor ---------------------bffcda43      St4pairIKiiE 
Construct T Alloc from X Alloc--bffcda43      St4pairIKiiE St13_Rb_tree_nodeISt4pairIKiiEE 
-+-+-+- 0985d028. 
Destructor ---------------------bffcda43      St4pairIKiiE 
Destructor ---------------------bffcdad8 St13_Rb_tree_nodeISt4pairIKiiEE 

cuối hai cột của chương trình đầu ra một cấp phát cho std::pair<const int, int> được xây dựng mỗi khi có một chèn vào bản đồ. Tại sao điều này lại cần thiết? Có cách nào để ngăn chặn điều này không?

Cảm ơn!

Chỉnh sửa: Mã này được thử nghiệm trên máy x86 với phiên bản g ++ 4.1.2. Nếu bạn muốn chạy nó trên máy 64 bit, bạn sẽ phải thay đổi ít nhất là dòng return malloc(24). Thay đổi thành return malloc(48) sẽ hoạt động.

Answer 1

Nó là như vậy bởi vì các cấp phát là std::pair<const int, int> nhưng thực hiện thực sự cần phải phân bổ một cấu trúc dữ liệu phức tạp hơn, trong đó đó là một thành viên. Trong khi tôi mong đợi bộ cấp phát thực sự cần thiết để được xây dựng và lưu trữ, nó không phải là bất hợp pháp cho nó được tái xây dựng mỗi lần. Đây là chi tiết triển khai mà bạn không thể thoát mà không thay đổi việc triển khai của mình. Loại cấp phát thực tế được tạo là St13_Rb_tree_nodeISt4pairIKiiEE (tên bị cắt xén).

Answer 2

Trong MyPool.h (singleton):

class MyPool 
{ 
... 
public: 
    static MyPool & GetInstance(void); 
private: 
    MyPool(void); 
} 

Trong MyPool.cpp:

MyPool & MyPool::GetInstance(void) 
{ 
    static MyPool retval; 
    return retval; 
} 

Trong 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") 

Bạn có thể sử dụng nó như sau:

std::map<keyT,valueT,std::less<keyT>,fooStdAllocator> your_map;