では前の項目の実装アイデアを試してみたですね。
しかしここまでヒープアロケーターの実装しかしていないので、ヒープだけでなく STL コンテナ側に対応したスタックアロケーターもついでに作って見ましょう。
実際割り当てられる領域はスタックじゃないのですが、便宜上スタックアロケーターとします。
スタックアロケーターではメモリーの解放は自動なので、デストラクターはあまり考えなくても良いです。
抱負として全力で取り組みたいのは、コンストラクターと、メモリープールの設計です。
ではサンプルコードを見てみましょう。
main.cpp.
1 #include <cstddef>
2 #include <memory>
3 #include <cassert>
4 #include <cstdlib>
5 #include <iostream>
6 #include <list>
7 #include <vector>
8 #include <map>
9 #include <set>
10 #include <sys/types.h>
11 #include <unistd.h>
12 #include <sys/stat.h>
13 #include <sys/mman.h>
14
15 #define MAX_OBJECTS 1024
16 #define MAX_ALLOCS 4
17
18 template<std::size_t N>
19 class allocator
20 {
21 public:
22 typedef std::size_t size_type;
23 typedef std::map<size_type,std::vector<void*>> free_list_t;
24 typedef std::map<void*,size_type> size_list_t;
25
26 explicit inline allocator()
27 :
28 M_block_size_(sizeof(std::byte[N])),
29 M_max_objects_(MAX_OBJECTS),
30 M_pool_index_(0)
31 {
32 std::cout << "M_block_size_: " << M_block_size_ << '\n';
33 Mp_pool_ = new (&Mp_Mem_) std::byte[sizeof(std::byte[N])*MAX_OBJECTS];
34 }
35
36 inline ~allocator(){
37 }
38
39 inline void* allocate(size_type n) {
40
41 if(auto& vec = M_free_list_[n]; !vec.empty()){
42 void* reuse_address = vec.back();
43 vec.pop_back();
44 std::cout << "reuse free address: " << reuse_address << '\n';
45 return reuse_address;
46 } else if(M_pool_index_ + n < MAX_OBJECTS){
47 void* pblock = static_cast<void*>(Mp_pool_ + M_block_size_ * M_pool_index_);
48 M_size_list_[pblock] = n;
49 M_pool_index_ += n;
50 std::cout << "size / block size / pool size = " << n << "/" << M_block_size_
51 << "/" << M_pool_index_ << '\n';
52 return reinterpret_cast<void*>(::new (pblock) std::byte[n*M_block_size_]);
53 } else {
54 assert(false);
55 }
56 return nullptr;
57 }
58
59 inline void deallocate(void* memory,size_type)
60 {
61 size_type index = M_size_list_[memory];
62 std::cout << "deallocate: " << memory << " with size " << index << '\n';
63 M_free_list_[index].push_back(memory);
64 }
65
66 inline size_t get_block_size() const {
67 return M_block_size_;
68 }
69
70 private:
71 const size_t M_block_size_;
72 const unsigned M_max_objects_;
73 free_list_t M_free_list_;
74 size_list_t M_size_list_;
75 std::byte* Mp_pool_;
76 unsigned M_pool_index_; //新規割当時にインクリメント、下がることはない
77 std::byte Mp_Mem_[sizeof(std::byte[N])*MAX_OBJECTS];
78 };
79
80 /* スタックメモリーのブロックを割り当てるクラステンプレート */
81
82 template<typename T>
83 class block_allocator
84 {
85 public:
86 typedef T value_type;
87 typedef value_type* pointer;
88 typedef const value_type* const_pointer;
89 typedef value_type& reference;
90 typedef const value_type& const_reference;
91 typedef std::size_t size_type;
92 typedef std::ptrdiff_t difference_type;
93
94 template<typename U>
95 struct rebind
96 {
97 typedef block_allocator<U> other;
98 };
99
100 inline block_allocator() noexcept
101 {}
102 inline ~block_allocator() {}
103
104 inline explicit block_allocator(const block_allocator&) noexcept {}
105
106 template<typename U>
107 inline constexpr block_allocator(const block_allocator<U>&) noexcept
108 {}
109
110 inline pointer allocate(size_type n, typename std::allocator<T>::const_pointer = 0)
111 {
112 size_t s = sizeof(T);
113 std::printf("request size: %lu\n",s);
114
115 if(s <= 8)
116 return reinterpret_cast<T*>(S_alloc8_.allocate(n));
117 else if(s <= 16)
118 return reinterpret_cast<T*>(S_alloc16_.allocate(n));
119 else if(s <= 32)
120 return reinterpret_cast<T*>(S_alloc32_.allocate(n));
121 else
122 return reinterpret_cast<T*>(S_alloc256_.allocate(n));
123 }
124
125 inline void deallocate(T* p, size_type n) noexcept
126 {
127 size_t s = sizeof(T);
128 if(s <= 8)
129 S_alloc8_.deallocate(reinterpret_cast<void*>(p),n);
130 else if(s <= 16)
131 S_alloc16_.deallocate(reinterpret_cast<void*>(p),n);
132 else if(s <= 32)
133 S_alloc32_.deallocate(reinterpret_cast<void*>(p),n);
134 else
135 S_alloc256_.deallocate(reinterpret_cast<void*>(p),n);
136 }
137
138 inline size_type max_size() const
139 {
140 return std::numeric_limits<size_type>::max();
141 }
142
143 static size_type capacity()
144 {
145 return MAX_OBJECTS;
146 }
147
148 template<typename U, typename ... Args>
149 void construct(U* p, Args&&... args) {
150 std::printf("construct %p\n",p);
151 ::new ((void*)p) U(std::forward<Args>(args)...);
152 }
153
154 template<typename U>
155 void destroy(U* p)
156 {
157 std::printf("destroy %p\n",p);
158 p->~U();
159 }
160
161 private:
162
163 static allocator(1) S_alloc8_;
164 static allocator(2) S_alloc16_;
165 static allocator(3) S_alloc32_;
166 static allocator(4) S_alloc256_;
167 };
168
169 template<typename T>
170 allocator(5) block_allocator<T>::S_alloc8_;
171
172 template<typename T>
173 allocator(6) block_allocator<T>::S_alloc16_;
174
175 template<typename T>
176 allocator(7) block_allocator<T>::S_alloc32_;
177
178 template<typename T>
179 allocator(8) block_allocator<T>::S_alloc256_;
180
181 /* voidパラメーターのエラーチェックのためにvoid型のクラステンプレートを用意 */
182
183 template <>
184 class block_allocator<void>
185 {
186 public:
187 typedef void* pointer;
188 typedef const void* const_pointer;
189 typedef void value_type;
190
191 template<typename U>
192 struct rebind
193 {
194 typedef block_allocator<U> other;
195 };
196
197 explicit block_allocator() noexcept {
198 }
199
200 template<typename U>
201 block_allocator(const block_allocator<U>&){}
202
203 template<typename U>
204 block_allocator(std::allocator<U>&){}
205
206 };
207
208 struct A{
209 A(int x, int y, int z, int a) :
210 x_(x),
211 y_(y),
212 z_(z),
213 a_(a)
214 {}
215 int x_,y_,z_,a_;
216 };
217
218 int main()
219 {
220 using int_allocator = block_allocator<int>;
221 using a_allocator = block_allocator<A>;
222
223 int_allocator alloc;
224
225 std::cout << "//// std::vector<int> の動作確認 " << '\n';
226 std::vector<int,int_allocator> vec;
227 std::cout << "============= push_back(10)" << '\n';
228 vec.push_back(10);
229 std::cout << "============= reserve(8)" << '\n';
230 vec.reserve(8);
231 std::cout << "============= push_back(20)" << '\n';
232 vec.push_back(20);
233 std::cout << "============= push_back(30)" << '\n';
234 vec.push_back(30);
235 std::cout << "============= push_back(50)" << '\n';
236 vec.push_back(50);
237 std::cout << "============= push_back(60)" << '\n';
238 vec.push_back(60);
239
240 std::cout << "============= data: ";
241 for(auto const& x : vec)
242 std::cout << x << " ";
243 std::cout << '\n';
244
245 std::cout << "============= pop_back" << '\n';
246 vec.pop_back();
247 std::cout << "============= pop_back" << '\n';
248 vec.pop_back();
249 std::cout << "============= reserve(64)" << '\n';
250 vec.reserve(64);
251 std::cout << "============= push_back(100)" << '\n';
252 vec.push_back(100);
253 std::cout << "============= push_back(110)" << '\n';
254 vec.push_back(110);
255 std::cout << "============= push_back(120)" << '\n';
256 vec.push_back(120);
257
258 std::cout << "============= data: ";
259 for(auto const& x : vec)
260 std::cout << x << " ";
261 std::cout << '\n';
262
263 std::cout << "//// std::vector<A> の動作確認 " << '\n';
264 std::vector<A,a_allocator> vec2;
265 std::cout << "============= emplace_back(1,2,3,4)" << '\n';
266 vec2.emplace_back(1,2,3,4);
267 std::cout << "============= emplace_back(5,6,7,8)" << '\n';
268 vec2.emplace_back(5,6,7,8);
269
270 std::cout << "//// std::list<int> の動作確認 " << '\n';
271 std::list<int,int_allocator> lst;
272 std::cout << "============= push_back(10)" << '\n';
273 lst.push_back(10);
274 std::cout << "============= push_back(20)" << '\n';
275 lst.push_back(20);
276 std::cout << "============= pop_back()" << '\n';
277 lst.pop_back();
278 std::cout << "============= push_back(30)" << '\n';
279 lst.push_back(30);
280 std::cout << "============= push_back(40)" << '\n';
281 lst.push_back(40);
282 std::cout << "============= pop_back()" << '\n';
283 lst.pop_back();
284 std::cout << "============= push_front(100)" << '\n';
285 lst.push_front(100);
286 std::cout << "============= data: ";
287 for(auto const& x : lst)
288 std::cout << x << " ";
289 std::cout << '\n';
290
291 using map_allocator = block_allocator<std::pair<const int,int>>;
292
293 map_allocator palloc;
294 std::less<int> comp;
295
296 std::cout << "//// std::map<int,int> の動作確認 " << '\n';
297 std::map<int,int,std::less<int>,map_allocator> m(comp,palloc);
298 std::cout << "============= insert({2,4})" << '\n';
299 m.insert({2,4});
300 std::cout << "============= insert({3,5})" << '\n';
301 m.insert({3,5});
302 std::cout << "============= auto y = m.find(2)" << '\n';
303 auto y = m.find(2);
304 std::cout << "============= erase(y)" << '\n';
305 m.erase(y);
306 std::cout << "============= insert({4,6})" << 'n';
307 m.insert({4,6});
308 std::cout << "============= insert({7,8})" << '\n';
309 m.insert({7,8});
310 std::cout << "============= auto z = m.find(4)" <<'\n';
311 auto z = m.find(4);
312 std::cout << "============= erase(z)" << '\n';
313 m.erase(z);
314 std::cout << "============= insert({9,10})" << '\n';
315 m.insert({9,10});
316 std::cout << "============= data: ";
317 for(auto const& x : m)
318 std::cout << x.second << " ";
319 std::cout << '\n';
320
321 return 0;
322 }
まずコンストラクターの説明をしたいところですが、2 つのクラステンプレートの違いを先に説明しますね。
82 template<typename T>
83 class block_allocator
84 {
85 public:block_allocator はアロケーターと STL コンテナとのインターフェースになります。
このクラステンプレートは内部ロジックは基本的に空でして、実装するクラステンプレートのインスタンスのメンバー関数を呼び出す役割があります。
保持したい状態は無いので、コンストラクターとデストラクターは空にします。
18 template<std::size_t N>
19 class allocator
20 {
21 public:allocator クラスはカスタムスタックアロケーターの実装箇所となりますね。
テンプレートパラメーターの N はアロケーターの持つメモリープールが 1 個分の要素の割り当てに使うバイトサイズです。
通常は N=8 ならば 8 バイトの要素、N=32 ならば 32 バイトの要素を割り当てます。
これを便宜上ブロックサイズと呼べないことも無いのですが、このカスタムアロケーターのブロックサイズは T 型によって変動します。
15 #define MAX_OBJECTS 1024
16 #define MAX_ALLOCS 4
17
18 template<std::size_t N>
19 class allocator
20 {
21 public:
22 typedef std::size_t size_type;
23 typedef std::map<size_type,std::vector<void*>> free_list_t;
24 typedef std::map<void*,size_type> size_list_t;
25
26 explicit inline allocator()
27 :
28 M_block_size_(sizeof(std::byte[N])),
29 M_max_objects_(MAX_OBJECTS),
30 M_pool_index_(0)
31 {
32 std::cout << "M_block_size_: " << M_block_size_ << '\n';
33 Mp_pool_ = new (&Mp_Mem_) std::byte[sizeof(std::byte[N])*MAX_OBJECTS];
34 }
35
36 inline ~allocator(){
37 } 15 #define MAX_OBJECTS 1024
16 #define MAX_ALLOCS 4
17
18 template<std::size_t N>
19 class allocator
20 {
// 中略
70 private:
71 const size_t M_block_size_;
72 const unsigned M_max_objects_;
73 free_list_t M_free_list_;
74 size_list_t M_size_list_;
75 std::byte* Mp_pool_;
76 unsigned M_pool_index_; //新規割当時にインクリメント、下がることはない
77 std::byte Mp_Mem_[sizeof(std::byte[N])*MAX_OBJECTS];
78 };T 型が std::pair 型でないなら N バイトに MAX_OBJECTS を乗じた値が配列サイズとなります。
それと class allocator にはフリーリストも定義されています。
36 typedef std::map<size_type,std::vector<void*>> free_list_t; 37 typedef std::map<void*,size_type> size_list_t;
free_list_t ではブロックサイズをキーとして、データを std::vector<void*> とします。
std::vector<void*> は解放済みの領域のメモリーアドレスを保管するリストです。
つまりサイズをインデックスにして検索すると std::vector<void*> 型のリストが返ってくるみたいなイメージですね。
size_list_t はメモリーアドレスをキーとして、データをブロックサイズとします。
それとスタティックインスタンスについては以下のように定義しています。
82 template<typename T>
83 class block_allocator
84 {
85 public:
// 中略
161 private:
162
163 static allocator(1) S_alloc8_;
164 static allocator(2) S_alloc16_;
165 static allocator(3) S_alloc32_;
166 static allocator(4) S_alloc256_;
167 };
168
169 template<typename T>
170 allocator(5) block_allocator<T>::S_alloc8_;
171
172 template<typename T>
173 allocator(6) block_allocator<T>::S_alloc16_;
174
175 template<typename T>
176 allocator(7) block_allocator<T>::S_alloc32_;
177
178 template<typename T>
179 allocator(8) block_allocator<T>::S_alloc256_;8, 16, 32, 256 バイトの 4 種類のアロケーターのインスタンスを作っています。
次になぜか今回はブロックサイズはコンストラクターではなく allocate() 関数で取るようにしていますね。
110 inline pointer allocate(size_type n, typename std::allocator<T>::const_pointer = 0)
111 {
112 size_t s = sizeof(T);
113 std::printf("request size: %lu\n",s);
114
115 if(s <= 8)
116 return reinterpret_cast<T*>(S_alloc8_.allocate(n));
117 else if(s <= 16)
118 return reinterpret_cast<T*>(S_alloc16_.allocate(n));
119 else if(s <= 32)
120 return reinterpret_cast<T*>(S_alloc32_.allocate(n));
121 else
122 return reinterpret_cast<T*>(S_alloc256_.allocate(n));
123 }これは STL コンテナ側の事情でコピーコンストラクターが使用されているので T はデフォルトコンストラクターの T ではなくなっているという状況でしょうね。
では実行結果を見てみたいと思います。
ビルドと実行結果.
$ g++ main.cpp -std=c++17
$ ./a.out
M_block_size_: 8
M_block_size_: 16
M_block_size_: 32
M_block_size_: 256
M_block_size_: 8
M_block_size_: 16
M_block_size_: 32
M_block_size_: 256
M_block_size_: 8
M_block_size_: 16
M_block_size_: 32
M_block_size_: 256
M_block_size_: 8
M_block_size_: 16
M_block_size_: 32
M_block_size_: 256
//// std::vector<int> の動作確認
============= push_back(10)
request size: 4
size / block size / pool size = 1/8/1
construct 0x556da7aff1bc
============= reserve(8)
request size: 4
size / block size / pool size = 8/8/9
construct 0x556da7aff1c4
destroy 0x556da7aff1bc
deallocate: 0x556da7aff1bc with size 1
============= push_back(20)
construct 0x556da7aff1c8
============= push_back(30)
construct 0x556da7aff1cc
============= push_back(50)
construct 0x556da7aff1d0
============= push_back(60)
construct 0x556da7aff1d4
============= data: 10 20 30 50 60
============= pop_back
destroy 0x556da7aff1d4
============= pop_back
destroy 0x556da7aff1d0
============= reserve(64)
request size: 4
size / block size / pool size = 64/8/73
construct 0x556da7aff204
construct 0x556da7aff208
construct 0x556da7aff20c
destroy 0x556da7aff1c4
destroy 0x556da7aff1c8
destroy 0x556da7aff1cc
deallocate: 0x556da7aff1c4 with size 8
============= push_back(100)
construct 0x556da7aff210
============= push_back(110)
construct 0x556da7aff214
============= push_back(120)
construct 0x556da7aff218
============= data: 10 20 30 100 110 120
//// std::vector<A> の動作確認
============= emplace_back(1,2,3,4)
request size: 16
size / block size / pool size = 1/16/1
construct 0x556da7b4f43c
============= emplace_back(5,6,7,8)
request size: 16
size / block size / pool size = 2/16/3
construct 0x556da7b4f45c
construct 0x556da7b4f44c
destroy 0x556da7b4f43c
deallocate: 0x556da7b4f43c with size 1
//// std::list<int> の動作確認
============= push_back(10)
request size: 24
size / block size / pool size = 1/32/1
construct 0x556da7ba16cc
============= push_back(20)
request size: 24
size / block size / pool size = 1/32/2
construct 0x556da7ba16ec
============= pop_back()
destroy 0x556da7ba16ec
deallocate: 0x556da7ba16dc with size 1
============= push_back(30)
request size: 24
reuse free address: 0x556da7ba16dc
construct 0x556da7ba16ec
============= push_back(40)
request size: 24
size / block size / pool size = 1/32/3
construct 0x556da7ba170c
============= pop_back()
destroy 0x556da7ba170c
deallocate: 0x556da7ba16fc with size 1
============= push_front(100)
request size: 24
reuse free address: 0x556da7ba16fc
construct 0x556da7ba170c
============= data: 100 10 30
//// std::map<int,int> の動作確認
============= insert({2,4})
request size: 40
size / block size / pool size = 1/256/1
construct 0x556da7bf795c
============= insert({3,5})
request size: 40
size / block size / pool size = 1/256/2
construct 0x556da7bf7a5c
============= auto y = m.find(2)
============= erase(y)
destroy 0x556da7bf795c
deallocate: 0x556da7bf793c with size 1
============= insert({4,6})nrequest size: 40
reuse free address: 0x556da7bf793c
construct 0x556da7bf795c
============= insert({7,8})
request size: 40
size / block size / pool size = 1/256/3
construct 0x556da7bf7b5c
============= auto z = m.find(4)
============= erase(z)
destroy 0x556da7bf795c
deallocate: 0x556da7bf793c with size 1
============= insert({9,10})
request size: 40
reuse free address: 0x556da7bf793c
construct 0x556da7bf795c
============= data: 5 8 10
destroy 0x556da7bf795c
deallocate: 0x556da7bf793c with size 1
destroy 0x556da7bf7b5c
deallocate: 0x556da7bf7b3c with size 1
destroy 0x556da7bf7a5c
deallocate: 0x556da7bf7a3c with size 1
destroy 0x556da7ba170c
deallocate: 0x556da7ba16fc with size 1
destroy 0x556da7ba16cc
deallocate: 0x556da7ba16bc with size 1
destroy 0x556da7ba16ec
deallocate: 0x556da7ba16dc with size 1
destroy 0x556da7b4f44c
destroy 0x556da7b4f45c
deallocate: 0x556da7b4f44c with size 2
destroy 0x556da7aff204
destroy 0x556da7aff208
destroy 0x556da7aff20c
destroy 0x556da7aff210
destroy 0x556da7aff214
destroy 0x556da7aff218
deallocate: 0x556da7aff204 with size 64
テストがなんでこんなに長いのか不思議に思われると思いますが、それなりの理由はあります。
各 STL コンテナには特性がありまして、特に std::vector は変り種です。
std::vector は可変長ベクターなので、一定サイズの配列を確保して、それが超えそうになったら、リサイズをして拡張します。
この拡張は reserve() 関数を使い、その後にコピーを行います。
これをテストするために以下のようなテストコードにしてみました。
225 std::cout << "//// std::vector<int> の動作確認 " << '\n'; 226 std::vector<int,int_allocator> vec; 227 std::cout << "============= push_back(10)" << '\n'; 228 vec.push_back(10); 229 std::cout << "============= reserve(8)" << '\n'; 230 vec.reserve(8); 231 std::cout << "============= push_back(20)" << '\n'; 232 vec.push_back(20); 233 std::cout << "============= push_back(30)" << '\n'; 234 vec.push_back(30); 235 std::cout << "============= push_back(50)" << '\n'; 236 vec.push_back(50); 237 std::cout << "============= push_back(60)" << '\n'; 238 vec.push_back(60); 239 240 std::cout << "============= data: "; 241 for(auto const& x : vec) 242 std::cout << x << " "; 243 std::cout << '\n'; 244 245 std::cout << "============= pop_back" << '\n'; 246 vec.pop_back(); 247 std::cout << "============= pop_back" << '\n'; 248 vec.pop_back(); 249 std::cout << "============= reserve(64)" << '\n'; 250 vec.reserve(64); 251 std::cout << "============= push_back(100)" << '\n'; 252 vec.push_back(100); 253 std::cout << "============= push_back(110)" << '\n'; 254 vec.push_back(110); 255 std::cout << "============= push_back(120)" << '\n'; 256 vec.push_back(120); 257 258 std::cout << "============= data: "; 259 for(auto const& x : vec) 260 std::cout << x << " "; 261 std::cout << '\n'; 262 263 std::cout << "//// std::vector<A> の動作確認 " << '\n'; 264 std::vector<A,a_allocator> vec2; 265 std::cout << "============= emplace_back(1,2,3,4)" << '\n'; 266 vec2.emplace_back(1,2,3,4); 267 std::cout << "============= emplace_back(5,6,7,8)" << '\n'; 268 vec2.emplace_back(5,6,7,8);
2 回の reserve() 関数へのコールをおこなっています。
//// std::vector<int> の動作確認 ============= push_back(10) request size: 4 size / block size / pool size = 1/8/1 construct 0x556da7aff1bc ============= reserve(8) request size: 4 size / block size / pool size = 8/8/9 construct 0x556da7aff1c4 destroy 0x556da7aff1bc deallocate: 0x556da7aff1bc with size 1 ============= push_back(20) construct 0x556da7aff1c8 ============= push_back(30) construct 0x556da7aff1cc ============= push_back(50) construct 0x556da7aff1d0 ============= push_back(60) construct 0x556da7aff1d4 ============= data: 10 20 30 50 60 ============= pop_back destroy 0x556da7aff1d4 ============= pop_back destroy 0x556da7aff1d0 ============= reserve(64) request size: 4 size / block size / pool size = 64/8/73 construct 0x556da7aff204 construct 0x556da7aff208 construct 0x556da7aff20c destroy 0x556da7aff1c4 destroy 0x556da7aff1c8 destroy 0x556da7aff1cc deallocate: 0x556da7aff1c4 with size 8
この出力では reserve() 関数への呼び出しを行うことで construct() と destroy() が呼ばれていますね。
std::vector はアロケーターで適正なメモリー管理をしなくても、最初に reserve() 関数でメモリーを予め使用する予定以上の領域を割り当てとけば、動作をさせることは簡単です。
次に std::list も見てみましょう。
まずはテストコードです。
270 std::cout << "//// std::list<int> の動作確認 " << '\n'; 271 std::list<int,int_allocator> lst; 272 std::cout << "============= push_back(10)" << '\n'; 273 lst.push_back(10); 274 std::cout << "============= push_back(20)" << '\n'; 275 lst.push_back(20); 276 std::cout << "============= pop_back()" << '\n'; 277 lst.pop_back(); 278 std::cout << "============= push_back(30)" << '\n'; 279 lst.push_back(30); 280 std::cout << "============= push_back(40)" << '\n'; 281 lst.push_back(40); 282 std::cout << "============= pop_back()" << '\n'; 283 lst.pop_back(); 284 std::cout << "============= push_front(100)" << '\n'; 285 lst.push_front(100); 286 std::cout << "============= data: "; 287 for(auto const& x : lst) 288 std::cout << x << " "; 289 std::cout << '\n';
このテストコードを実行すると以下のように出力します。
//// std::list<int> の動作確認 ============= push_back(10) request size: 24 size / block size / pool size = 1/32/1 construct 0x556da7ba16cc ============= push_back(20) request size: 24 size / block size / pool size = 1/32/2 construct 0x556da7ba16ec ============= pop_back() destroy 0x556da7ba16ec deallocate: 0x556da7ba16dc with size 1 ============= push_back(30) request size: 24 reuse free address: 0x556da7ba16dc construct 0x556da7ba16ec ============= push_back(40) request size: 24 size / block size / pool size = 1/32/3 construct 0x556da7ba170c ============= pop_back() destroy 0x556da7ba170c deallocate: 0x556da7ba16fc with size 1 ============= push_front(100) request size: 24 reuse free address: 0x556da7ba16fc construct 0x556da7ba170c ============= data: 100 10 30
前の項目で説明した通り std::list のリクエストサイズは 24 バイトになってますね。
双方向連結リストなので 2 個のポインターとデータサイズが最低でも必要ですが、それにデータパディングも入ってるのは間違いなさそうです。
最後に std::map もチェックしてみましょう。
291 using map_allocator = block_allocator<std::pair<const int,int>>;
292
293 map_allocator palloc;
294 std::less<int> comp;
295
296 std::cout << "//// std::map<int,int> の動作確認 " << '\n';
297 std::map<int,int,std::less<int>,map_allocator> m(comp,palloc);
298 std::cout << "============= insert({2,4})" << '\n';
299 m.insert({2,4});
300 std::cout << "============= insert({3,5})" << '\n';
301 m.insert({3,5});
302 std::cout << "============= auto y = m.find(2)" << '\n';
303 auto y = m.find(2);
304 std::cout << "============= erase(y)" << '\n';
305 m.erase(y);
306 std::cout << "============= insert({4,6})" << 'n';
307 m.insert({4,6});
308 std::cout << "============= insert({7,8})" << '\n';
309 m.insert({7,8});
310 std::cout << "============= auto z = m.find(4)" <<'\n';
311 auto z = m.find(4);
312 std::cout << "============= erase(z)" << '\n';
313 m.erase(z);
314 std::cout << "============= insert({9,10})" << '\n';
315 m.insert({9,10});
316 std::cout << "============= data: ";
317 for(auto const& x : m)
318 std::cout << x.second << " ";
319 std::cout << '\n';std::map のテストでは (2,4), (3,5) ペアを挿入してから (2,4) を削除します。
次に (4,6), (7,8) を挿入してから (4,6) を削除します。
最後に (9,10) ペアを挿入します。
この結果は以下のように出力されます。
//// std::map<int,int> の動作確認
============= insert({2,4})
request size: 40
size / block size / pool size = 1/256/1
construct 0x556da7bf795c
============= insert({3,5})
request size: 40
size / block size / pool size = 1/256/2
construct 0x556da7bf7a5c
============= auto y = m.find(2)
============= erase(y)
destroy 0x556da7bf795c
deallocate: 0x556da7bf793c with size 1
============= insert({4,6})nrequest size: 40
reuse free address: 0x556da7bf793c
construct 0x556da7bf795c
============= insert({7,8})
request size: 40
size / block size / pool size = 1/256/3
construct 0x556da7bf7b5c
============= auto z = m.find(4)
============= erase(z)
destroy 0x556da7bf795c
deallocate: 0x556da7bf793c with size 1
============= insert({9,10})
request size: 40
reuse free address: 0x556da7bf793c
construct 0x556da7bf795c
============= data: 5 8 10(3,5), (7,8), (9,10) が残っているので正常に動作していることが分かります。
リクエストサイズやプールサイズは以下の箇所だけを見ると良いです。
============= insert({2,4})
request size: 40
size / block size / pool size = 1/256/1またデータサイズは 40 バイトになっているので、これまた正しい値になっていますね。
セレクターについては 256 バイト均等間隔のアロケーターの allocate() を実行しています。
110 inline pointer allocate(size_type n, typename std::allocator<T>::const_pointer = 0)
111 {
112 size_t s = sizeof(T);
113 std::printf("request size: %lu\n",s);
114
115 if(s <= 8)
116 return reinterpret_cast<T*>(S_alloc8_.allocate(n));
117 else if(s <= 16)
118 return reinterpret_cast<T*>(S_alloc16_.allocate(n));
119 else if(s <= 32)
120 return reinterpret_cast<T*>(S_alloc32_.allocate(n));
121 else
122 return reinterpret_cast<T*>(S_alloc256_.allocate(n));
123 }40 バイトは 32 バイトを超えるので、次のアロケーターは 256 バイトアロケーターになりますよね。
Copyright 2018-2019, by Masaki Komatsu