STL stack allocate
添加时间:2013-6-16 点击量:
游戏编程精华精辟3供给了一份栈分派器源代码：
＃include <memory>
＃include <limits>
template <typename T>
class StackAlloc
{
public:
// Typedefs
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;
// Constructors
StackAlloc（） throw（）
:
mpStack（ NULL ），
mBytesAllocated（ 0 ），
mMaxBytes（ 0 ）
{
}
StackAlloc（ unsigned char pStack， size_t nMaxBytes ） throw（）
:
mpStack（ pStack ），
mBytesAllocated（ 0 ），
mMaxBytes（ nMaxBytes ）
{
}
StackAlloc（ const StackAlloc& sa ） throw（）
:
mpStack（ sa.mpStack ），
mBytesAllocated（ 0 ），
mMaxBytes（ sa.mMaxBytes ）
{
// Copying the stack resets mBytesAllocated to zero
}
＃if _MSC_VER >= 1400 // VC 7 cant handle template members
template <typename U>
StackAlloc（ const StackAlloc<U>& sa ） throw（）
:
mpStack（ sa.mpStack ），
mBytesAllocated（ 0 ），
mMaxBytes（ sa.mMaxBytes ）
{
// Copying the stack resets mBytesAllocated to zero
}
＃endif
StackAlloc& operator=（ const StackAlloc& sa ）
{
// Copying the stack resets mBytesAllocated to zero
mpStack = sa.mpStack;
mBytesAllocated = 0;
mMaxBytes = sa.mMaxBytes;
return this;
}
// Destructor
~StackAlloc（） throw（）
{
}
// Utility functions
pointer address（ reference r ） const
{
return &r;
}
const_pointer address（ const_reference c ） const
{
return &c;
}
size_type max_size（） const
{
return std::numeric_limits<size_t>::max（） / sizeof（T）;
}
// In-place construction
void construct（ pointer p， const_reference c ）
{
// placement new operator
new（ reinterpret_cast<void>（p） ） T（c）;
}
// In-place destruction
void destroy（ pointer p ）
{
// call destructor directly
（p）->~T（）;
}
// Rebind to allocators of other types
template <typename U>
struct rebind
{
typedef StackAlloc<U> other;
};
// Allocate raw memory
pointer allocate（ size_type n， const void = NULL ）
{
void pRaw = mpStack + mBytesAllocated;
mBytesAllocated += （ n sizeof（T） ）;
if（ mBytesAllocated+1 > mMaxBytes ）
throw std::bad_alloc（）;
return pointer（pRaw）;
}
// Free raw memory.
// Note that C++ standard defines this function as
// deallocate（ pointer p， size_type）. Because Visual C++ 6.0
// compiler doesnt support template rebind， Dinkumware uses
// void hack.
void deallocate（ void， size_type ）
{
// No need to free stack memory
}
// Non-standard Dinkumware hack for Visual C++ 6.0 compiler.
// VC 6 doesnt support template rebind.
char _Charalloc（ size_type n ）
{
return reinterpret_cast<char>（ allocate（ n， NULL ） ）;
}
// Required for global comparison functions
unsigned char GetStack（） const
{
return mpStack;
}
private:
unsigned char mpStack;
size_t mBytesAllocated;
size_t mMaxBytes;
}; // end of StackAlloc
// Comparison
template <typename T1>
bool operator==（ const StackAlloc<T1>& lhs， const StackAlloc<T1>& rhs） throw（）
{
return lhs.GetStack（） == rhs.GetStack（）;
}
template <typename T1>
bool operator!=（ const StackAlloc<T1>& lhs， const StackAlloc<T1>& rhs） throw（）
{
return lhs.GetStack（） != rhs.GetStack（）;
}
View Code
测试发明在VS2012下编译运行，栈分派器在开释内存时失足。
原因是当用户供给自定义的分派器时，VS会保存一个分派策略对象来经管计数神马的。
项目组VS源代码如下：
_Vector_alloc（const _Alty& _Al = _Alty（））
: _Alval（_Al）
{ // construct allocator _Al
_Alloc_proxy（）;
}
//-------------------------------------------------------------
void _Alloc_proxy（）
{ // construct proxy _Alval
typename _Alloc::template rebind<_Container_proxy>::other
_Alproxy（_Alval）;
this->_Myproxy = _Alproxy.allocate（1）;
_Alproxy.construct（this->_Myproxy， _Container_proxy（））;
this->_Myproxy->_Mycont = this;
}
View Code
vector的栈分派器是_Alval，也就是用户供给的栈分派器。
分派策略对象_Myproxy占用的内存也是经由过程_Alval申请的。仅仅是如许也许不会呈现神马题目，可是_Myproxy是经由过程调用template <typename U> StackAlloc（ const StackAlloc<U>& sa ）重绑定函数从_Alval获取了一个新的分派器对象_Alproxy。此时_Alval与_Alproxy其实是共用一段内存的，而彼此不知道对方的存在。导致_Myproxy应用的内存在vector插入元素时被覆盖。当vector开释内存或者迁徙内存时须要开释掉_Myproxy的内存时法度就溃散了。
实际上游戏编程精华精辟3供给的stack allocate在语义上就存在题目，mpstack不该该是值语义的，因为stack allocate实际上即没有真正向体系申请内存，也并没有真正的开释内存，而只是代为经管一段底本就存在的内存。是以，mpstack应当是引用语义的。
现将本人批改后的代码献上：
PS:只在VS2012下测试了vector与list容器。
1 template<typename T>
2 class stack_alloc
3 {
4 public:
5 typedef size_t size_type;
6 typedef ptrdiff_t difference_type;
7 typedef T pointer;
8 typedef const T const_pointer;
9 typedef T& reference;
10 typedef const T& const_reference;
11 typedef T value_type;
12
13 public:
14 stack_alloc（） throw（）
15 : m_begin（NULL）
16 ， m_cur（m_begin）
17 ， m_max_bytes（0）
18 {
19 }
20
21 stack_alloc（uchar pstack， size_t max_bytes） throw（）
22 : m_begin（pstack）
23 ， m_cur（m_begin）
24 ， m_max_bytes（max_bytes）
25 {
26 }
27
28 stack_alloc（const stack_alloc& sa） throw（）
29 : m_begin（sa.m_begin）
30 ， m_cur（sa.m_cur）
31 ， m_max_bytes（sa.m_max_bytes）
32 {
33 }
34
35 ＃if _MSC_VER >= 1400 // VC 7 cant handle template members
36 template <typename U>
37 stack_alloc（const stack_alloc<U>& sa） throw（）
38 : m_begin（sa.m_begin）
39 ， m_cur（sa.m_cur）
40 ， m_max_bytes（sa.m_max_bytes）
41 {
42 }
43 ＃endif
44
45 stack_alloc& operator=（ const stack_alloc& rhs ）
46 {
47 return this;
48 }
49
50 ~stack_alloc（） throw（）
51 {
52 }
53
54 public:
55 // Utility functions
56 pointer address（ reference r ） const
57 {
58 return &r;
59 }
60
61 const_pointer address（ const_reference c ） const
62 {
63 return &c;
64 }
65
66 size_type max_size（） const
67 {
68 return m_max_bytes/sizeof（T）;
69 }
70
71 // In-place construction
72 void construct（ pointer p， const_reference c ）
73 {
74 new（ reinterpret_cast<void>（p） ） T（c）;
75 }
76
77 // In-place destruction
78 void destroy（ pointer p ）
79 {
80 （p）->~T（）;
81 }
82
83 // Rebind to allocators of other types
84 template <typename U>
85 struct rebind
86 {
87 typedef stack_alloc<U> other;
88 };
89
90 // Allocate raw memory
91 pointer allocate（ size_type n， const void = NULL ）
92 {
93 void praw = m_cur;
94 m_cur += nsizeof（T）;
95 if（m_cur+1>m_begin+m_max_bytes）
96 {
97 throw std::bad_alloc（）;
98 }
99
100 return pointer（praw）;
101 }
102
103 void deallocate（ void p， size_type n）
104 {
105 }
106
107 // Non-standard Dinkumware hack for Visual C++ 6.0 compiler.
108 // VC 6 doesnt support template rebind.
109 char _charalloc（ size_type n ）
110 {
111 return reinterpret_cast<char>（ allocate（ n， NULL ） ）;
112 }
113
114 unsigned char get_stack（） const
115 {
116 return m_begin;
117 }
118
119 uchar& m_cur;
120 size_t m_max_bytes;
121 uchar m_begin;
122 };
123
124 template <typename T>
125 bool operator==（ const stack_alloc<T>& lhs， const stack_alloc<T>& rhs） throw（）
126 {
127 return lhs.get_stack（） == rhs.get_stack（）;
128 }
129
130 template <typename T>
131 bool operator!=（ const stack_alloc<T>& lhs， const stack_alloc<T>& rhs） throw（）
132 {
133 return lhs.get_stack（） != rhs.get_stack（）;
134 }
View Code
我们永远不要期待别人的拯救，只有自己才能升华自己。自己已准备好了多少容量，方能吸引对等的人与我们相遇，否则再美好的人出现、再动人的事情降临身边，我们也没有能量去理解与珍惜，终将擦肩而过。—— 姚谦《品味》
游戏编程精华精辟3供给了一份栈分派器源代码：
＃include <memory>
＃include <limits>
template <typename T>
class StackAlloc
{
public:
// Typedefs
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;
// Constructors
StackAlloc（） throw（）
:
mpStack（ NULL ），
mBytesAllocated（ 0 ），
mMaxBytes（ 0 ）
{
}
StackAlloc（ unsigned char pStack， size_t nMaxBytes ） throw（）
:
mpStack（ pStack ），
mBytesAllocated（ 0 ），
mMaxBytes（ nMaxBytes ）
{
}
StackAlloc（ const StackAlloc& sa ） throw（）
:
mpStack（ sa.mpStack ），
mBytesAllocated（ 0 ），
mMaxBytes（ sa.mMaxBytes ）
{
// Copying the stack resets mBytesAllocated to zero
}
＃if _MSC_VER >= 1400 // VC 7 cant handle template members
template <typename U>
StackAlloc（ const StackAlloc<U>& sa ） throw（）
:
mpStack（ sa.mpStack ），
mBytesAllocated（ 0 ），
mMaxBytes（ sa.mMaxBytes ）
{
// Copying the stack resets mBytesAllocated to zero
}
＃endif
StackAlloc& operator=（ const StackAlloc& sa ）
{
// Copying the stack resets mBytesAllocated to zero
mpStack = sa.mpStack;
mBytesAllocated = 0;
mMaxBytes = sa.mMaxBytes;
return this;
}
// Destructor
~StackAlloc（） throw（）
{
}
// Utility functions
pointer address（ reference r ） const
{
return &r;
}
const_pointer address（ const_reference c ） const
{
return &c;
}
size_type max_size（） const
{
return std::numeric_limits<size_t>::max（） / sizeof（T）;
}
// In-place construction
void construct（ pointer p， const_reference c ）
{
// placement new operator
new（ reinterpret_cast<void>（p） ） T（c）;
}
// In-place destruction
void destroy（ pointer p ）
{
// call destructor directly
（p）->~T（）;
}
// Rebind to allocators of other types
template <typename U>
struct rebind
{
typedef StackAlloc<U> other;
};
// Allocate raw memory
pointer allocate（ size_type n， const void = NULL ）
{
void pRaw = mpStack + mBytesAllocated;
mBytesAllocated += （ n sizeof（T） ）;
if（ mBytesAllocated+1 > mMaxBytes ）
throw std::bad_alloc（）;
return pointer（pRaw）;
}
// Free raw memory.
// Note that C++ standard defines this function as
// deallocate（ pointer p， size_type）. Because Visual C++ 6.0
// compiler doesnt support template rebind， Dinkumware uses
// void hack.
void deallocate（ void， size_type ）
{
// No need to free stack memory
}
// Non-standard Dinkumware hack for Visual C++ 6.0 compiler.
// VC 6 doesnt support template rebind.
char _Charalloc（ size_type n ）
{
return reinterpret_cast<char>（ allocate（ n， NULL ） ）;
}
// Required for global comparison functions
unsigned char GetStack（） const
{
return mpStack;
}
private:
unsigned char mpStack;
size_t mBytesAllocated;
size_t mMaxBytes;
}; // end of StackAlloc
// Comparison
template <typename T1>
bool operator==（ const StackAlloc<T1>& lhs， const StackAlloc<T1>& rhs） throw（）
{
return lhs.GetStack（） == rhs.GetStack（）;
}
template <typename T1>
bool operator!=（ const StackAlloc<T1>& lhs， const StackAlloc<T1>& rhs） throw（）
{
return lhs.GetStack（） != rhs.GetStack（）;
}
View Code
测试发明在VS2012下编译运行，栈分派器在开释内存时失足。
原因是当用户供给自定义的分派器时，VS会保存一个分派策略对象来经管计数神马的。
项目组VS源代码如下：
_Vector_alloc（const _Alty& _Al = _Alty（））
: _Alval（_Al）
{ // construct allocator _Al
_Alloc_proxy（）;
}
//-------------------------------------------------------------
void _Alloc_proxy（）
{ // construct proxy _Alval
typename _Alloc::template rebind<_Container_proxy>::other
_Alproxy（_Alval）;
this->_Myproxy = _Alproxy.allocate（1）;
_Alproxy.construct（this->_Myproxy， _Container_proxy（））;
this->_Myproxy->_Mycont = this;
}
View Code
vector的栈分派器是_Alval，也就是用户供给的栈分派器。
分派策略对象_Myproxy占用的内存也是经由过程_Alval申请的。仅仅是如许也许不会呈现神马题目，可是_Myproxy是经由过程调用template <typename U> StackAlloc（ const StackAlloc<U>& sa ）重绑定函数从_Alval获取了一个新的分派器对象_Alproxy。此时_Alval与_Alproxy其实是共用一段内存的，而彼此不知道对方的存在。导致_Myproxy应用的内存在vector插入元素时被覆盖。当vector开释内存或者迁徙内存时须要开释掉_Myproxy的内存时法度就溃散了。
实际上游戏编程精华精辟3供给的stack allocate在语义上就存在题目，mpstack不该该是值语义的，因为stack allocate实际上即没有真正向体系申请内存，也并没有真正的开释内存，而只是代为经管一段底本就存在的内存。是以，mpstack应当是引用语义的。
现将本人批改后的代码献上：
PS:只在VS2012下测试了vector与list容器。
1 template<typename T>
2 class stack_alloc
3 {
4 public:
5 typedef size_t size_type;
6 typedef ptrdiff_t difference_type;
7 typedef T pointer;
8 typedef const T const_pointer;
9 typedef T& reference;
10 typedef const T& const_reference;
11 typedef T value_type;
12
13 public:
14 stack_alloc（） throw（）
15 : m_begin（NULL）
16 ， m_cur（m_begin）
17 ， m_max_bytes（0）
18 {
19 }
20
21 stack_alloc（uchar pstack， size_t max_bytes） throw（）
22 : m_begin（pstack）
23 ， m_cur（m_begin）
24 ， m_max_bytes（max_bytes）
25 {
26 }
27
28 stack_alloc（const stack_alloc& sa） throw（）
29 : m_begin（sa.m_begin）
30 ， m_cur（sa.m_cur）
31 ， m_max_bytes（sa.m_max_bytes）
32 {
33 }
34
35 ＃if _MSC_VER >= 1400 // VC 7 cant handle template members
36 template <typename U>
37 stack_alloc（const stack_alloc<U>& sa） throw（）
38 : m_begin（sa.m_begin）
39 ， m_cur（sa.m_cur）
40 ， m_max_bytes（sa.m_max_bytes）
41 {
42 }
43 ＃endif
44
45 stack_alloc& operator=（ const stack_alloc& rhs ）
46 {
47 return this;
48 }
49
50 ~stack_alloc（） throw（）
51 {
52 }
53
54 public:
55 // Utility functions
56 pointer address（ reference r ） const
57 {
58 return &r;
59 }
60
61 const_pointer address（ const_reference c ） const
62 {
63 return &c;
64 }
65
66 size_type max_size（） const
67 {
68 return m_max_bytes/sizeof（T）;
69 }
70
71 // In-place construction
72 void construct（ pointer p， const_reference c ）
73 {
74 new（ reinterpret_cast<void>（p） ） T（c）;
75 }
76
77 // In-place destruction
78 void destroy（ pointer p ）
79 {
80 （p）->~T（）;
81 }
82
83 // Rebind to allocators of other types
84 template <typename U>
85 struct rebind
86 {
87 typedef stack_alloc<U> other;
88 };
89
90 // Allocate raw memory
91 pointer allocate（ size_type n， const void = NULL ）
92 {
93 void praw = m_cur;
94 m_cur += nsizeof（T）;
95 if（m_cur+1>m_begin+m_max_bytes）
96 {
97 throw std::bad_alloc（）;
98 }
99
100 return pointer（praw）;
101 }
102
103 void deallocate（ void p， size_type n）
104 {
105 }
106
107 // Non-standard Dinkumware hack for Visual C++ 6.0 compiler.
108 // VC 6 doesnt support template rebind.
109 char _charalloc（ size_type n ）
110 {
111 return reinterpret_cast<char>（ allocate（ n， NULL ） ）;
112 }
113
114 unsigned char get_stack（） const
115 {
116 return m_begin;
117 }
118
119 uchar& m_cur;
120 size_t m_max_bytes;
121 uchar m_begin;
122 };
123
124 template <typename T>
125 bool operator==（ const stack_alloc<T>& lhs， const stack_alloc<T>& rhs） throw（）
126 {
127 return lhs.get_stack（） == rhs.get_stack（）;
128 }
129
130 template <typename T>
131 bool operator!=（ const stack_alloc<T>& lhs， const stack_alloc<T>& rhs） throw（）
132 {
133 return lhs.get_stack（） != rhs.get_stack（）;
134 }
View Code
我们永远不要期待别人的拯救，只有自己才能升华自己。自己已准备好了多少容量，方能吸引对等的人与我们相遇，否则再美好的人出现、再动人的事情降临身边，我们也没有能量去理解与珍惜，终将擦肩而过。—— 姚谦《品味》
