え？ カスタムアロケーターの STL コンテナのサポートって難しいの？
おら、やてるよ…… (´・ω・｀)
そう考えていた時も筆者にはありましたね。
ええ…
でも new や delete でメモリー管理されているヒープ領域のアロケーターで STL コンテナをサポートするのは、まあできるっちゃできます。
メモリーの管理は new や delete がやってくれるので、後はアロケーター要件（ Allocator Requirement ）に準拠すれば勝手に動きそうです。
まあ難しいこと考えずに、試しにそれっぽいのをコーディングしてみましょう。
main.cpp.
1 #include <climits>
2 #include <limits>
3 #include <cstdlib>
4 #include <memory>
5 #include <vector>
6 #include <list>
7 #include <map>
8 #include <iostream>
9
10 template<typename T>
11 class my_allocator
12 {
13 public:
14 typedef T value_type;
15 typedef value_type* pointer;
16 typedef const value_type* const_pointer;
17 typedef value_type& reference;
18 typedef const value_type& const_reference;
19 typedef std::size_t size_type;
20 typedef std::ptrdiff_t difference_type;
21
22 template<typename U>
23 struct rebind {
24 typedef my_allocator<U> other;
25 };
26
27 inline explicit my_allocator(){
28 std::cout << "sizeof(T) @ default constructor: " << sizeof(T) << '\n';
29 }
30
31 inline ~my_allocator(){}
32
33 inline explicit my_allocator(my_allocator const&){}
34
35 template<typename U>
36 inline explicit my_allocator(my_allocator<U> const&){
37 std::cout << "sizeof(U) @ copy constructor: " << sizeof(U) << '\n';
38 }
39
40 inline pointer allocate(size_type cnt,
41 typename std::allocator<void>::const_pointer = 0)
42 {
43 std::cout << "sizeof(T) @ allocate(): " << sizeof(T) << '\n';
44 return reinterpret_cast<pointer>(new char[cnt*sizeof(T)]);
45 }
46
47 inline void deallocate(pointer p, size_type)
48 {
49 ::operator delete(p);
50 }
51
52 inline size_type max_size() const
53 {
54 return std::numeric_limits<size_type>::max();
55 }
56 };
57
58 template<typename T>
59 using rebind_t = typename my_allocator<T>::template rebind<T>::type;
60
61 template<typename T, typename T2>
62 inline bool operator==(my_allocator<T> const&,
63 my_allocator<T2> const&)
64 {
65 return true;
66 }
67
68 template<typename T, typename OtherAllocator>
69 inline bool operator==(my_allocator<T> const&,
70 OtherAllocator const&)
71 {
72 return false;
73 }
74
75 int main()
76 {
77 using alloc = my_allocator<int>;
78 std::vector<int,alloc> vec;
79
80 vec.push_back(5);
81 vec.push_back(10);
82 vec.push_back(15);
83 vec.pop_back();
84 vec.push_back(20);
85
86 std::cout << "std::vector<int> values: ";
87 for(auto const& x : vec)
88 std::cout << x << " ";
89 std::cout << '\n';
90
91 std::list<int,alloc> lst;
92
93 lst.push_back(5);
94 lst.push_back(10);
95 lst.push_back(15);
96 lst.pop_back();
97 lst.push_back(20);
98
99 std::cout << "std::list<int> values: ";
100 for(auto const& x : lst)
101 std::cout << x << " ";
102 std::cout << '\n';
103
104 using map_alloc = my_allocator<std::pair<const int,int>>;
105 std::less<int> comp;
106 map_alloc palloc;
107 std::map<const int,int,std::less<int>,map_alloc> mp(comp,palloc);
108 mp.insert({1,2});
109 mp.insert({2,3});
110 mp.insert({4,5});
111 auto key = mp.find(4);
112 mp.erase(key);
113 mp.insert({5,6});
114
115 std::cout << "std::map<const,int> values: ";
116 for(auto const& x : mp){
117 std::cout << x.second << " ";
118 }
119 std::cout << '\n';
120
121 return 0;
122 }
ビルドと実行結果.
$ g++ main.cpp $ ./a.out sizeof(T) @ default constructor: 4 sizeof(T) @ allocate(): 4 sizeof(T) @ allocate(): 4 sizeof(T) @ allocate(): 4 std::vector<int> values: 5 10 20 sizeof(T) @ default constructor: 24 sizeof(T) @ allocate(): 24 sizeof(T) @ allocate(): 24 sizeof(T) @ allocate(): 24 sizeof(T) @ allocate(): 24 std::list<int> values: 5 10 20 sizeof(T) @ default constructor: 8 sizeof(U) @ copy constructor: 8 sizeof(T) @ allocate(): 40 sizeof(T) @ allocate(): 40 sizeof(T) @ allocate(): 40 sizeof(T) @ allocate(): 40 std::map<const,int> values: 2 3 6
ううん… 動いておる… (´・ω・｀)
それで STL コンテナの動作は分かるのですが、このソースコードでは allocate() 関数が割り当てるバイトサイズを出力するようにしています。
何の変哲もない実装なんですけど。。。
40 inline pointer allocate(size_type cnt,
41 typename std::allocator<void>::const_pointer = 0)
42 {
43 std::cout << "sizeof(T) @ allocate(): " << sizeof(T) << '\n';
44 return reinterpret_cast<pointer>(new char[cnt*sizeof(T)]);
45 }
46
47 inline void deallocate(pointer p, size_type)
48 {
49 ::operator delete(p);
50 }まあ new char[] と delete[] を使ってるので、メモリーの管理は malloc とかが裏でよろしくやってくれてます。
そりゃ動きますよね。
それと ::operator new と ::operator delete でも対応できるので試してみてくださいね。
ということで allocate() をコールするどうなるのか、テストをしたいと思います。
まずは std::vector をチェックします。
77 using alloc = my_allocator<int>; 78 std::vector<int,alloc> vec; 79 80 vec.push_back(5); 81 vec.push_back(10); 82 vec.push_back(15); 83 vec.pop_back(); 84 vec.push_back(20); 85 86 std::cout << "std::vector<int> values: "; 87 for(auto const& x : vec) 88 std::cout << x << " "; 89 std::cout << '\n';
この例では 5,10,15 をプッシュして 15 をポップ、最後に 20 をプッシュしているので 5,10,20 の要素があることになります。
出力と照合してみましょう。
sizeof(T) @ default constructor: 4 sizeof(T) @ allocate(): 4 sizeof(T) @ allocate(): 4 sizeof(T) @ allocate(): 4 std::vector<int> values: 5 10 20
パット見た限りでは誤ったところは無いですね。
ちなみにデフォルトコンストラクターで出力させた sizeof(T) の結果は 4 でした。
次は std::list です。
91 std::list<int,alloc> lst; 92 93 lst.push_back(5); 94 lst.push_back(10); 95 lst.push_back(15); 96 lst.pop_back(); 97 lst.push_back(20); 98 99 std::cout << "std::list<int> values: "; 100 for(auto const& x : lst) 101 std::cout << x << " "; 102 std::cout << '\n';
やってることは std::vector のケースと全く同じです。
では該当する出力です。
sizeof(T) @ default constructor: 24 sizeof(T) @ allocate(): 24 sizeof(T) @ allocate(): 24 sizeof(T) @ allocate(): 24 sizeof(T) @ allocate(): 24 std::list<int> values: 5 10 20
コンストラクターと allocate() 関数内の sizeof(T) 関数は 24 に評価されています。
この 24 が何を示すかは後に説明しますが、双方向連結リストにはポインターが 2 個とデータが必要なので、それっぽい値ですね。
最後は std::map についてです。
104 using map_alloc = my_allocator<std::pair<const int,int>>;
105 std::less<int> comp;
106 map_alloc palloc;
107 std::map<const int,int,std::less<int>,map_alloc> mp(comp,palloc);
108 mp.insert({1,2});
109 mp.insert({2,3});
110 mp.insert({4,5});
111 auto key = mp.find(4);
112 mp.erase(key);
113 mp.insert({5,6});
114
115 std::cout << "std::map<const,int> values: ";
116 for(auto const& x : mp){
117 std::cout << x.second << " ";
118 }
119 std::cout << '\n';std::map については (1,2), (2,4), (4,5) のペアをプッシュして (4,5) をポップします。
次に (5,6) のペアをプッシュしています。
では該当する出力もみてみましょう。
sizeof(T) @ default constructor: 8 sizeof(U) @ copy constructor: 8 sizeof(T) @ allocate(): 40 sizeof(T) @ allocate(): 40 sizeof(T) @ allocate(): 40 sizeof(T) @ allocate(): 40 std::map<const,int> values: 2 3 6
これによると allocate() 関数を呼び出すときには sizeof(T) は 40 バイトになり、コンストラクターを呼び出すときには 8 バイトになっています。
なぜ 40 バイトなのだろう？
謎の挙動です…
(´・ω・｀)
これはアルゴリズムを実装するためのデータらしいですが、筆者も詳しい実装は知らないですね…
Copyright 2018-2019, by Masaki Komatsu