C++ Advent Calender 2013
をテンプレートにして作成
Check
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
]
開始行:
&size(30){&color(darkblue,#c0c0ff){''《 scoped_shared_pt...
#counter
この記事は、[[''C++ Advent Calendar 2013''>http://partake...
-Prev 5日目の記事 [[hotwatermorningさんによる、「VSTホス...
-Next 7日目の記事は、srz_zumixさんの予定です。
今年も参加させていただきました。昨年の「[[ゲームプログラ...
今年も都市伝説シリーズをやとうかと考えましたが、少し趣向...
今回紹介するプログラムは、私自身がゲームプログラミングを...
- shared_ptr
- vector
- string
- map
- unordered_map
これらの良く使くコンテナとスマートポインタをアロケータ無...
局所的に、ちょこっとmapを使いたいけど、アロケーターが自由...
少し長くなってしまいましたが、お楽しみいただければ幸いで...
———————————————————— 目次 ————————————————————
#contents
&br;
**更新履歴 [#y9108979]
- 2013/12/6 1:30 gcc4.8.1でビルドを通すために、allocator_...
- 2013/12/6 14:45 「課題」に、”operator == の実装が妖しい...
* shared_ptrの落とし穴 [#ke354407]
C++11で標準実装された、参照カウンタ方式によるスマートポイ...
古来のC++でもboostライブラリにより利用できたので、すっか...
なにせ、newしてもdeleteしなくて良いというお手軽さ。誰から...
しかし、無闇矢鱈と使うと、参照関係が矛盾してしまったり、...
スマートポインタと云えども、正しい設計の下に使うべきでし...
ありがちなトラブルの記事は、[[shared_ptrを要求する邪悪な...
**スコープから抜けたときに、参照が残っていたら教えてくれ...
すべてのソースコードが正しい設計とプログラミングを行って...
#sh(cpp){{
// std::shared_ptrをラップしたscoped_shared_ptr
// スコープから出る時に参照が残っていたら、assertする
template <typename T>
struct scoped_shared_ptr {
shared_ptr<T> value_;
template <typename ...Param>
scoped_shared_ptr(Param&&... params) : value_(new T(par...
{}
~scoped_shared_ptr() noexcept {
assert(value_.use_count() == 1); // 誰かが握っている...
}
template<typename TT>
operator shared_ptr<TT> () { return value_; }
T& get() { return value_.get(); }
};
}}
これは、shared_ptrを要求する関数に、ローカルで作成したク...
スコープから出るときに、誰かが参照を握っていて解放できな...
使用例
#sh(cpp){{
// shared_ptrを要求する、ちょっとイケてないapi
struct Fuga {};
void foo(shared_ptr<Fuga> ptr);
// コンストラクタで頂いたstringを保持するクラス
struct Hoge : Fuga {
string& msg_;
Hoge(string& msg) : msg_(msg) {};
~Hoge() { cout << msg; }; // 解放時に頂いた文字列を出力...
};
// Hogeとfooを使う関数。Hogeはこの関数のスコープ内でのみ...
void sometask() {
string msg("hello");
// hogeは、msgの参照を含んでいるので、sometask()から...
scoped_shared_ptr<Hoge> hoge(msg);
// shared_ptrを要求するAPIを呼ぶ。weak_ptrにしてくれ...
foo(hoge);
}
// もし、fooがhogeの参照を解放していなかったら、assertする
// std::shared_ptrを使用した場合、fooがhogeの参照を解除し...
// sometask()終了後の場合は、msgに対してアクセス違反が発...
}}
これで安心して使えます。わざわざWrapしたクラスを作らなく...
** スコープ内でしか使わないのに、newするのは勿体ない [#j6...
この簡単なshared_ptrのwrapperで、思わぬ参照が残っていてア...
shared_ptrは、インスタンスを削除するためのデリーターを指...
scoped_shared_ptrを make_sharedを使わない(newしない)様に...
#sh(cpp){{
// std::shared_ptrをラップしたscoped_shared_ptr。 スコー...
template <typename T>
struct scoped_shared_ptr {
using element_type = T;
// std::shared_ptrがクラスオブジェクトを破棄するときに...
struct deleter {
void operator() (element_type*) {}
};
// 共有するインンスタンスの実体。スコープ内で宣言された...
T body_;
// std:shared_ptrの実体。newしたクラスオブジェクトでな...
std::shared_ptr<T> value_;
template <typename ...Param>
scoped_shared_ptr(Param&&... params)
: body_(params...)
, value_(&body_, deleter())
{}
// デストラクタでshared_ptrのvalue_は解放されるが、イン...
~scoped_shared_ptr() noexcept {
assert(value_.use_count() == 1);
}
// shared_ptrへのアクセス用
template<typename TT>
operator shared_ptr<TT> () { return value_; }
};
}}
これで、Hogeが巨大なオブジェクトでもnewされることなく、ス...
しかし、よーく考えると、shared_ptrの内部で、参照カウンタ...
手元のclang3.4環境で調べてみたところ、48bytesのメモリを標...
&size(50){ゆるせん!};
ここまできたら、すべてスタック上のメモリで済ませたくなる...
乗りかかった船なので、アロケーターを使わないアロケーター...
*アロケートしないアロケーター、static_allocator [#r0994a30]
考え方は簡単です。サイズを指定して、そのサイズをスコープ...
&size(30){試行錯誤すること約1年!};(嘘)ホントは1日です。
ようやくできました。以下の様な書式で使えます。
#sh(cpp){{
// Static Allocator クラス
template<size_t BufferSizeByte, typename ElementType>
struct static_allocator; // ソースコードは巻末にあります
// 使用例
// int型で16byteのインスタンスを生成
static_allocator<16, int> alc; // 内部で、uint8_t[16]がス...
// アロケーターオブジェクトの取得
int* i = alc().allocate(1); // int x1つ分のメモリがalloca...
double* d = alc.get<double>().allocate(1); // 違う型のア...
}}
こんな感じです。さっそく、先ほど作成したscoped_shared_ptr...
#sh(cpp){{
// newを一切呼ばずにスコープ内で使えるshared_ptr ...
// インスタンスが破棄されるときに、参照が残っていたらエ...
template <typename T>
struct scoped_shared_ptr {
using element_type = T;
// インスタンスを解放するためのデリーター。何もしない
struct deleter {
void operator () (element_type*) {}
};
element_type body_; // クラスのインスタンス
static_allocator<64,element_type> allocator_; // ア...
std::shared_ptr<element_type> value_; // shared_pt...
// コンストラクタ
template <typename ...Param>
scoped_shared_ptr(Param&&... params)
: body_(params...)
, value_(&body_, deleter(), allocator_()) // sha...
{}
// デストラクタでは、shared_ptrの参照カウントが1(自...
~scoped_shared_ptr() {
assert(value_.use_count() == 1);
}
// shared_ptr<T>に変換するオペレーター
// 派生クラスへの変換を可能にするためテンプレート実装...
template <typename TT>
operator std::shared_ptr<TT> () { return value_; }
};
}}
参照カウンタのインスタンス確保用に64bytesを固定で確保して...
ここで、ふと思い出しました。boost::containerには、static_...
#sh(cpp){{
// boost static_vectorの使用例
boost::container::static_vector<int, 2> ivec; // int x ...
ivec.push_back(1);
ivec.push_back(2);
ivec.push_back(3); // エラー! 予約したサイズを超える事...
}}
つまり、今回作成したstatic_allocatorを使えば、普通のvecto...
static_vectorはboostライブラリにありますが、残念ながらsta...
&size(20){ならば、作ってしまおう};
ということで、作りました。
*static_vector と static_string [#c3df93f5]
boostにあるのに、なぜ作る? というツッコミはさておき、お...
しかし、実際に作ってみるとけっこう苦戦します。std:vector...
今回はコード量を減らすために安易に継承することにしました...
コンストラクタは以下のようになります。
#sh(cpp){{
template <typename T>
struct static_vector : std:vector<T> {
allocator alc_;
static_vector()
: std::vector<T>(alc.get_allocator()) {} // std::vect...
...
}}
この時、allocator alc;のコンストラクタよりも、基底クラス...
allocatorを外部に持てば解決できますが、それだと使い勝手が...
そこで、悪魔に魂を売って、&size(20){多重継承}; することに...
#sh(cpp){{
template <typename T>
struct static_vector : private allocator, std:vector<T> {
static_vector() : std::vector<T>(allocator::get_allocat...
...
}}
これで、allocatorが初期化されてから、std::vector<T>のコン...
できあがったstatic_vectorのコードです。
#sh(cpp){{
template<typename T, size_t Elements>
struct static_vector_detail {
using allocator = static_allocator<sizeof(T)*Elements...
using base = std::vector<T, typename allocator::alcty...
struct type : private allocator, base {
type() : base(allocator::get_allocator()) {
base::reserve(Elements);
}
type(const std::vector<T>&& other)
: base(other, allocator::get_allocator()) {
}
type(std::initializer_list<T> init)
: base(init, allocator::get_allocator()) {
}
};
};
template<typename T, size_t Elements>
using static_vector = typename static_vector_detail<T,E...
}}
これで、std::vector<Hoge>としていた箇所を、static_vector<...
** static_stringも思わぬ苦戦 [#s82955c6]
static_vectorができたから、static_stringは簡単だろうと思...
std::vectorはきっちりエレメントサイズ*Nしかメモリを要求し...
おまけに、basic_stringの内部で、? hogehoge == Allocator()...
static_stringは、こんなコードになりました。
#sh(cpp){{
template<typename T, size_t Elements>
struct static_string_detail {
// basic_stringは、文字列のサイズ + ポインタ3個分のメ...
using allocator = static_allocator<sizeof(void*) * 3 ...
using base = std::basic_string<T, std::char_traits<T>...
struct type : private allocator, base {
type()
: base(allocator::get_allocator())
{}
type(const T* text)
: base(text, allocator::get_allocator())
{}
type(const base&& other)
: base(other, allocator::get_allocator())
{}
type(std::initializer_list<T> init)
: base(init, allocator::get_allocator())
{}
struct hash {
std::size_t operator () ( type const & key ) cons...
return key.length();
}
};
};
};
template<size_t Elements>
using static_string = typename static_string_detail<cha...
template<size_t Elements>
using static_wstring = typename static_string_detail<wc...
}}
これで、std::string str("hoge"); を、static_string<5> str...
小さな文字列をローカルで使う場合、std::stringだとアロケー...
hashというサービスクラスがあります。これは、unordered_map...
これで、static_vectorと、static_stringは出来上がりです。
サンプルコードはこんな感じになります。
#sh(cpp){{
// static_vector test
static_vector<int,2> vec;
vec.push_back(1);
vec.push_back(2);
vec.push_back(3); // これを実行するとout_of_rangeがth...
static_vector<char,4>{1,2,3,4}; // 初期化リストもOK!
// static_string test
static_string<10> str;
str = "123456789";
static_string<10> str2("hogehoge");
static_wstring<10> str4{L"hogehoge!"};
cout << str << str2 << str4 << endl; // std::basic_st...
}}
いい感じでできてきました。次は、mapとunordered_mapです。
こいつらは、ちょいと手ごわいです。
* static_mapとstatic_unordered_map [#s2e1d3ef]
map系が手ごわいのは、内部でアロケートしまくりだからです。...
もはや、ステートフルなアロケーターでなければ対応不可能で...
static_mapの実装はこんな感じになりました。
#sh(cpp){{
template <typename Key, typename T, size_t MaxElements,...
struct static_map_detail {
using value_type = typename std::map<Key,T>::value_ty...
using sizetest = std::tuple<Key,T,static_allocator<0>...
using allocator = static_allocator<MaxElements * size...
using map_type = std::map<Key, T, Cmp, typename alloc...
struct type : private allocator, map_type {
type(const Cmp& comp = Cmp())
: map_type(comp, allocator::get_allocator()) {}
type(std::initializer_list<value_type> init
, const Cmp& comp = Cmp())
: map_type(init, comp, allocator::get_allocator()...
};
};
template <typename Key, typename T, size_t BufSz, class...
using static_map = typename static_map_detail<Key,T,Buf...
}}
意外とアッサリできたように見えますが、じつはstatic_alloca...
clangとgccでは動作が違うし、allocator_traitsはちゃんと機...
いちおう、エレメントの個数をテンプレートパラメーターで渡...
#sh(cpp){{
using sizetest = std::tuple<Key,T,static_allocator<0>::a...
}}
で、tupleクラスをsizeof()したサイズで代用しています。とり...
** static_unordered_mapは、実装系によってコンストラクタが...
なのです! 正確に言うと、gcc4.8.1には規定のコンストラクタ...
文句を言っても仕方ないので、両方のコンパイラで共通のコン...
#sh(cpp){{
// static_unordered_mapの実装
template <typename Key, typename T, size_t BufferBytes,...
struct static_unordered_map_detail {
using value_type = typename std::unordered_map<Key,T,...
using allocator = static_allocator<BufferBytes, value...
using map_type = std::unordered_map<Key,T,Hash,KeyEqu...
struct type : private allocator, map_type {
type() : map_type(0, typename map_type::hasher(), t...
{}
type(std::initializer_list<value_type> init)
: map_type(init, 0, typename map_type::hasher(), ...
{}
};
};
// std::unordered_mapと置き換え可能にするための定義
template <typename Key, typename T, size_t BufferBytes,...
using static_unordered_map = typename static_unordered_...
}}
なんでも、コンストラクタで初期サイズを整数で渡してやる必...
とりあえずゼロを食わせても動いているので、深く考えずにゼ...
std::unordered_mapは、オレオレクラスを渡す場合、std::hash...
#sh(cpp){{
// hash<>の特殊化をstatic_string<N>でやりたい
template<size_t N>
struct hash<static_string<N>>; // エラー! (;_;)
}}
ためしに、問題を切り出してサンプルコードを作ってみました。
http://melpon.org/wandbox/permlink/t8roOParscJnb7c3
どうやら、現状のコンパイラでは無理なようです。残念。
拙出のstatic_stringをハッシュするために、static_stringにh...
std::unordered_mapは、使用するメモリサイズがテンデバラバ...
サンプルプログラムはこんな感じになります。
#sh(cpp){{
//scoped_map_sample
static_map<int, int, 3> hoge = { {1,1} };
hoge.insert(make_pair(1,1.0));
hoge[1] = 2;
hoge[0] = 1;
hoge[2] = 3;
// scoped_unordered_map_sample
static_unordered_map<int, double, 1000> fuga{ {1,1.1}...
fuga[2] = 2.1;
fuga[0] = 1.1;
// static_stringをキーとする場合は、hasherとしてstati...
using string10 = static_string<10>;
static_unordered_map<string10, int, 1000, string10::h...
{"hoge",5}, {"fuga",4}, {"piyo",3}, {"apoon",2} };
cout << "fuga is " << strmap["fuga"] << endl;
}}
* static_allocatorの正体 [#d2d96051]
scoped_shared_ptr, static_vector, static_string, static_m...
書式は以下のようになります。
- template<size_t BufferByteSize, typename ElementType = ...
- 定義
-- alctype
--- ElementType型のアロケーター型
-- template<typename T> allocator
--- T型のアロケーター型
- メソッド
-- constructor: なし(デフォルトのみ)
-- alctype operator ()
-- alctype get_allocator()
--- ElementType型のアロケータオブジェクトを返す
-- template<typename T> allocator<T> get()
--- T型のアロケータオブジェクトを返す
仕組みを簡単に説明しますと、STDアロケータと互換のアロケー...
アロケートされるバッファは、static_allocatorクラス内部で ...
以下がソースコード全部です。イケてない部分もありますが、c...
#sh(cpp){{
template <size_t BufferByteSize, typename ElementType=v...
struct static_allocator {
template <typename T>
struct allocator_detail {
uint8_t** buffer_ = nullptr;
size_t* size_left_ = nullptr;
using value_type = T;
using element_type = T;
// これらの定義は、gcc4.8.1で必要になる。clang3.4で...
using pointer = T*;
using const_pointer = const T*;
using reference = T&;
using const_reference = const T&;
using size_type = size_t;
using difference_type = std::ptrdiff_t;
// 確保するメモリーのポインタをサイズを受け取る。
// statefulなallocatorで可能になりました。
allocator_detail(uint8_t** buffer, size_t* buffersi...
: buffer_(buffer), size_left_(buffersize)
{}
// rebindで異なるクラス向けのallocatorを生成すると...
// コンストラクタ。インスタンスを引き継ぐための重要...
template <class U> allocator_detail(const allocator...
: buffer_(other.buffer_), size_left_(other.size_l...
{}
// gcc4.8.1のbasic_stringでこれがないとエラーになる
allocator_detail() {}
// メモリをアロケート
pointer allocate(std::size_t n) const {
size_t required = n * sizeof(value_type);
return allocate_buffer(required);
}
// メモリを解放
void deallocate(pointer p, std::size_t n) const {
size_t deallocsize = n * sizeof(value_type);
// 解放するポインターが最後にアロケートしたバッフ...
if (reinterpret_cast<uint8_t*>(p) == *buffer_ - d...
allocate_buffer(-deallocsize);
}
}
// allocatorを異なる型用に再生成するためのクラス
template<class Other>
struct rebind : allocator_detail<Other> {
typedef allocator_detail<Other> other;
};
// clangではdestroyとconstructは記述しなくても実行...
static void destroy(pointer& p) { p->~T(); }
// clangでは、value_type以外の型で呼ばれるためテン...
template<typename U, typename ...Args>
static void construct(U* p, Args&&... args) {
::new (static_cast<void*>(p)) U(args...);
}
bool operator == (const allocator_detail<T>&) const {
return true;
}
bool operator != (const allocator_detail<T>&) const {
return false;
}
private:
// メモリ確保の処理 失敗したらout_of_rangeをthrow
pointer allocate_buffer(int32_t size) const {
if (size > 0 && *size_left_ < size) {
std::cerr << "out of memory capacity:" << *size...
throw std::out_of_range("static_allocator out o...
}
void* ptr = *buffer_;
*buffer_ += size;
*size_left_ -= size;
return static_cast<pointer>(ptr);
}
};
// static_allocatorの実装はここから
// ElementTypeのallocatorの型をtypeとして定義
template <typename T>
using allocator = allocator_detail<T>;
using alctype = allocator<ElementType>;
// allocator<ElementType>のインスタンスを得る
allocator<ElementType> operator () () {
return get<ElementType>();
}
allocator<ElementType> get_allocator() {
return get<ElementType>();
}
// allocator<T>のインスタンスを得る
template <typename T>
allocator<T> get() {
return allocator<T>(&buffer_ptr_, &size_left_);
}
private:
// これらのインスタンスは、スコープ内ならスタック領域...
// 必要なサイズは、バッファサイズ+ sizeof(*) + sizeof...
uint8_t buffer_[BufferByteSize]; // allocateさ...
uint8_t* buffer_ptr_ = buffer_; // 現在のバッ...
size_t size_left_ = BufferByteSize; // 確保可能な...
};
// アロケーターを比較するための演算子の定義が必要らしい
template <size_t B, typename V, typename T, typename U>
bool operator == (const typename static_allocator<B,V>:...
, const typename static_allocator<B,V>:...
{ return true; }
template <size_t B, typename V, typename T, typename U>
bool operator != (const typename static_allocator<B,V>:...
, const typename static_allocator<B,V>:...
{ return false; }
}}
* まとめ [#o144ea70]
いそいで作成したので手抜きな部分も多々ありますが、仕事で...
小さな領域を使う分だけ確保するという使い方を想定している...
開放した領域の再利用は、最後に開放した1つだけです。その代...
vector,string,map,unordered_mapには、アロケータを指定すれ...
たとえば、static_vectorの場合、
#sh(cpp){{
// static_allocatorで1000バイト(250エレメント)確保
static_allocator<1000, int> alc;
std::vector<int, typename alc::alctype> hoge(alc());
}}
これでOKです。~
この方式ならば、安全にほとんどすべてのコンテナに使えると...
**課題 [#v189376d]
- アロケートのポリシーをアダプターにして代えられる様にし...
- std::scoped_allocator_adaptorと連動できるようにしたい
- clangとgcc以外のc++に似たコンパイラでも動作するようにし...
- 多重継承やめたい
- スレッドセーフにするポリシーを入れたい
- アライメントを指定できるようにしたい
- %%gcc4.8.1でビルドを通すために、std::allocatorを継承し...
- operator == の実装が妖しいので検討中です
あー、課題だらけですね。精進せねば。
&size(30){長い間、ご拝読ありがとうございました。};
この記事は、[[''C++ Advent Calendar 2013''>http://partake...
次の記事は、srz_zumixさんによる7日目の記事になります。よ...
ソースコードは、[[こちら>http://ssa.techarts.co.jp/index....
gcc-4.8.1(Linux環境)と、clang3.4(MacOS環境)で動作確認して...
ソースは良識の範囲内でご自由にお使いください。
終了行:
&size(30){&color(darkblue,#c0c0ff){''《 scoped_shared_pt...
#counter
この記事は、[[''C++ Advent Calendar 2013''>http://partake...
-Prev 5日目の記事 [[hotwatermorningさんによる、「VSTホス...
-Next 7日目の記事は、srz_zumixさんの予定です。
今年も参加させていただきました。昨年の「[[ゲームプログラ...
今年も都市伝説シリーズをやとうかと考えましたが、少し趣向...
今回紹介するプログラムは、私自身がゲームプログラミングを...
- shared_ptr
- vector
- string
- map
- unordered_map
これらの良く使くコンテナとスマートポインタをアロケータ無...
局所的に、ちょこっとmapを使いたいけど、アロケーターが自由...
少し長くなってしまいましたが、お楽しみいただければ幸いで...
———————————————————— 目次 ————————————————————
#contents
&br;
**更新履歴 [#y9108979]
- 2013/12/6 1:30 gcc4.8.1でビルドを通すために、allocator_...
- 2013/12/6 14:45 「課題」に、”operator == の実装が妖しい...
* shared_ptrの落とし穴 [#ke354407]
C++11で標準実装された、参照カウンタ方式によるスマートポイ...
古来のC++でもboostライブラリにより利用できたので、すっか...
なにせ、newしてもdeleteしなくて良いというお手軽さ。誰から...
しかし、無闇矢鱈と使うと、参照関係が矛盾してしまったり、...
スマートポインタと云えども、正しい設計の下に使うべきでし...
ありがちなトラブルの記事は、[[shared_ptrを要求する邪悪な...
**スコープから抜けたときに、参照が残っていたら教えてくれ...
すべてのソースコードが正しい設計とプログラミングを行って...
#sh(cpp){{
// std::shared_ptrをラップしたscoped_shared_ptr
// スコープから出る時に参照が残っていたら、assertする
template <typename T>
struct scoped_shared_ptr {
shared_ptr<T> value_;
template <typename ...Param>
scoped_shared_ptr(Param&&... params) : value_(new T(par...
{}
~scoped_shared_ptr() noexcept {
assert(value_.use_count() == 1); // 誰かが握っている...
}
template<typename TT>
operator shared_ptr<TT> () { return value_; }
T& get() { return value_.get(); }
};
}}
これは、shared_ptrを要求する関数に、ローカルで作成したク...
スコープから出るときに、誰かが参照を握っていて解放できな...
使用例
#sh(cpp){{
// shared_ptrを要求する、ちょっとイケてないapi
struct Fuga {};
void foo(shared_ptr<Fuga> ptr);
// コンストラクタで頂いたstringを保持するクラス
struct Hoge : Fuga {
string& msg_;
Hoge(string& msg) : msg_(msg) {};
~Hoge() { cout << msg; }; // 解放時に頂いた文字列を出力...
};
// Hogeとfooを使う関数。Hogeはこの関数のスコープ内でのみ...
void sometask() {
string msg("hello");
// hogeは、msgの参照を含んでいるので、sometask()から...
scoped_shared_ptr<Hoge> hoge(msg);
// shared_ptrを要求するAPIを呼ぶ。weak_ptrにしてくれ...
foo(hoge);
}
// もし、fooがhogeの参照を解放していなかったら、assertする
// std::shared_ptrを使用した場合、fooがhogeの参照を解除し...
// sometask()終了後の場合は、msgに対してアクセス違反が発...
}}
これで安心して使えます。わざわざWrapしたクラスを作らなく...
** スコープ内でしか使わないのに、newするのは勿体ない [#j6...
この簡単なshared_ptrのwrapperで、思わぬ参照が残っていてア...
shared_ptrは、インスタンスを削除するためのデリーターを指...
scoped_shared_ptrを make_sharedを使わない(newしない)様に...
#sh(cpp){{
// std::shared_ptrをラップしたscoped_shared_ptr。 スコー...
template <typename T>
struct scoped_shared_ptr {
using element_type = T;
// std::shared_ptrがクラスオブジェクトを破棄するときに...
struct deleter {
void operator() (element_type*) {}
};
// 共有するインンスタンスの実体。スコープ内で宣言された...
T body_;
// std:shared_ptrの実体。newしたクラスオブジェクトでな...
std::shared_ptr<T> value_;
template <typename ...Param>
scoped_shared_ptr(Param&&... params)
: body_(params...)
, value_(&body_, deleter())
{}
// デストラクタでshared_ptrのvalue_は解放されるが、イン...
~scoped_shared_ptr() noexcept {
assert(value_.use_count() == 1);
}
// shared_ptrへのアクセス用
template<typename TT>
operator shared_ptr<TT> () { return value_; }
};
}}
これで、Hogeが巨大なオブジェクトでもnewされることなく、ス...
しかし、よーく考えると、shared_ptrの内部で、参照カウンタ...
手元のclang3.4環境で調べてみたところ、48bytesのメモリを標...
&size(50){ゆるせん!};
ここまできたら、すべてスタック上のメモリで済ませたくなる...
乗りかかった船なので、アロケーターを使わないアロケーター...
*アロケートしないアロケーター、static_allocator [#r0994a30]
考え方は簡単です。サイズを指定して、そのサイズをスコープ...
&size(30){試行錯誤すること約1年!};(嘘)ホントは1日です。
ようやくできました。以下の様な書式で使えます。
#sh(cpp){{
// Static Allocator クラス
template<size_t BufferSizeByte, typename ElementType>
struct static_allocator; // ソースコードは巻末にあります
// 使用例
// int型で16byteのインスタンスを生成
static_allocator<16, int> alc; // 内部で、uint8_t[16]がス...
// アロケーターオブジェクトの取得
int* i = alc().allocate(1); // int x1つ分のメモリがalloca...
double* d = alc.get<double>().allocate(1); // 違う型のア...
}}
こんな感じです。さっそく、先ほど作成したscoped_shared_ptr...
#sh(cpp){{
// newを一切呼ばずにスコープ内で使えるshared_ptr ...
// インスタンスが破棄されるときに、参照が残っていたらエ...
template <typename T>
struct scoped_shared_ptr {
using element_type = T;
// インスタンスを解放するためのデリーター。何もしない
struct deleter {
void operator () (element_type*) {}
};
element_type body_; // クラスのインスタンス
static_allocator<64,element_type> allocator_; // ア...
std::shared_ptr<element_type> value_; // shared_pt...
// コンストラクタ
template <typename ...Param>
scoped_shared_ptr(Param&&... params)
: body_(params...)
, value_(&body_, deleter(), allocator_()) // sha...
{}
// デストラクタでは、shared_ptrの参照カウントが1(自...
~scoped_shared_ptr() {
assert(value_.use_count() == 1);
}
// shared_ptr<T>に変換するオペレーター
// 派生クラスへの変換を可能にするためテンプレート実装...
template <typename TT>
operator std::shared_ptr<TT> () { return value_; }
};
}}
参照カウンタのインスタンス確保用に64bytesを固定で確保して...
ここで、ふと思い出しました。boost::containerには、static_...
#sh(cpp){{
// boost static_vectorの使用例
boost::container::static_vector<int, 2> ivec; // int x ...
ivec.push_back(1);
ivec.push_back(2);
ivec.push_back(3); // エラー! 予約したサイズを超える事...
}}
つまり、今回作成したstatic_allocatorを使えば、普通のvecto...
static_vectorはboostライブラリにありますが、残念ながらsta...
&size(20){ならば、作ってしまおう};
ということで、作りました。
*static_vector と static_string [#c3df93f5]
boostにあるのに、なぜ作る? というツッコミはさておき、お...
しかし、実際に作ってみるとけっこう苦戦します。std:vector...
今回はコード量を減らすために安易に継承することにしました...
コンストラクタは以下のようになります。
#sh(cpp){{
template <typename T>
struct static_vector : std:vector<T> {
allocator alc_;
static_vector()
: std::vector<T>(alc.get_allocator()) {} // std::vect...
...
}}
この時、allocator alc;のコンストラクタよりも、基底クラス...
allocatorを外部に持てば解決できますが、それだと使い勝手が...
そこで、悪魔に魂を売って、&size(20){多重継承}; することに...
#sh(cpp){{
template <typename T>
struct static_vector : private allocator, std:vector<T> {
static_vector() : std::vector<T>(allocator::get_allocat...
...
}}
これで、allocatorが初期化されてから、std::vector<T>のコン...
できあがったstatic_vectorのコードです。
#sh(cpp){{
template<typename T, size_t Elements>
struct static_vector_detail {
using allocator = static_allocator<sizeof(T)*Elements...
using base = std::vector<T, typename allocator::alcty...
struct type : private allocator, base {
type() : base(allocator::get_allocator()) {
base::reserve(Elements);
}
type(const std::vector<T>&& other)
: base(other, allocator::get_allocator()) {
}
type(std::initializer_list<T> init)
: base(init, allocator::get_allocator()) {
}
};
};
template<typename T, size_t Elements>
using static_vector = typename static_vector_detail<T,E...
}}
これで、std::vector<Hoge>としていた箇所を、static_vector<...
** static_stringも思わぬ苦戦 [#s82955c6]
static_vectorができたから、static_stringは簡単だろうと思...
std::vectorはきっちりエレメントサイズ*Nしかメモリを要求し...
おまけに、basic_stringの内部で、? hogehoge == Allocator()...
static_stringは、こんなコードになりました。
#sh(cpp){{
template<typename T, size_t Elements>
struct static_string_detail {
// basic_stringは、文字列のサイズ + ポインタ3個分のメ...
using allocator = static_allocator<sizeof(void*) * 3 ...
using base = std::basic_string<T, std::char_traits<T>...
struct type : private allocator, base {
type()
: base(allocator::get_allocator())
{}
type(const T* text)
: base(text, allocator::get_allocator())
{}
type(const base&& other)
: base(other, allocator::get_allocator())
{}
type(std::initializer_list<T> init)
: base(init, allocator::get_allocator())
{}
struct hash {
std::size_t operator () ( type const & key ) cons...
return key.length();
}
};
};
};
template<size_t Elements>
using static_string = typename static_string_detail<cha...
template<size_t Elements>
using static_wstring = typename static_string_detail<wc...
}}
これで、std::string str("hoge"); を、static_string<5> str...
小さな文字列をローカルで使う場合、std::stringだとアロケー...
hashというサービスクラスがあります。これは、unordered_map...
これで、static_vectorと、static_stringは出来上がりです。
サンプルコードはこんな感じになります。
#sh(cpp){{
// static_vector test
static_vector<int,2> vec;
vec.push_back(1);
vec.push_back(2);
vec.push_back(3); // これを実行するとout_of_rangeがth...
static_vector<char,4>{1,2,3,4}; // 初期化リストもOK!
// static_string test
static_string<10> str;
str = "123456789";
static_string<10> str2("hogehoge");
static_wstring<10> str4{L"hogehoge!"};
cout << str << str2 << str4 << endl; // std::basic_st...
}}
いい感じでできてきました。次は、mapとunordered_mapです。
こいつらは、ちょいと手ごわいです。
* static_mapとstatic_unordered_map [#s2e1d3ef]
map系が手ごわいのは、内部でアロケートしまくりだからです。...
もはや、ステートフルなアロケーターでなければ対応不可能で...
static_mapの実装はこんな感じになりました。
#sh(cpp){{
template <typename Key, typename T, size_t MaxElements,...
struct static_map_detail {
using value_type = typename std::map<Key,T>::value_ty...
using sizetest = std::tuple<Key,T,static_allocator<0>...
using allocator = static_allocator<MaxElements * size...
using map_type = std::map<Key, T, Cmp, typename alloc...
struct type : private allocator, map_type {
type(const Cmp& comp = Cmp())
: map_type(comp, allocator::get_allocator()) {}
type(std::initializer_list<value_type> init
, const Cmp& comp = Cmp())
: map_type(init, comp, allocator::get_allocator()...
};
};
template <typename Key, typename T, size_t BufSz, class...
using static_map = typename static_map_detail<Key,T,Buf...
}}
意外とアッサリできたように見えますが、じつはstatic_alloca...
clangとgccでは動作が違うし、allocator_traitsはちゃんと機...
いちおう、エレメントの個数をテンプレートパラメーターで渡...
#sh(cpp){{
using sizetest = std::tuple<Key,T,static_allocator<0>::a...
}}
で、tupleクラスをsizeof()したサイズで代用しています。とり...
** static_unordered_mapは、実装系によってコンストラクタが...
なのです! 正確に言うと、gcc4.8.1には規定のコンストラクタ...
文句を言っても仕方ないので、両方のコンパイラで共通のコン...
#sh(cpp){{
// static_unordered_mapの実装
template <typename Key, typename T, size_t BufferBytes,...
struct static_unordered_map_detail {
using value_type = typename std::unordered_map<Key,T,...
using allocator = static_allocator<BufferBytes, value...
using map_type = std::unordered_map<Key,T,Hash,KeyEqu...
struct type : private allocator, map_type {
type() : map_type(0, typename map_type::hasher(), t...
{}
type(std::initializer_list<value_type> init)
: map_type(init, 0, typename map_type::hasher(), ...
{}
};
};
// std::unordered_mapと置き換え可能にするための定義
template <typename Key, typename T, size_t BufferBytes,...
using static_unordered_map = typename static_unordered_...
}}
なんでも、コンストラクタで初期サイズを整数で渡してやる必...
とりあえずゼロを食わせても動いているので、深く考えずにゼ...
std::unordered_mapは、オレオレクラスを渡す場合、std::hash...
#sh(cpp){{
// hash<>の特殊化をstatic_string<N>でやりたい
template<size_t N>
struct hash<static_string<N>>; // エラー! (;_;)
}}
ためしに、問題を切り出してサンプルコードを作ってみました。
http://melpon.org/wandbox/permlink/t8roOParscJnb7c3
どうやら、現状のコンパイラでは無理なようです。残念。
拙出のstatic_stringをハッシュするために、static_stringにh...
std::unordered_mapは、使用するメモリサイズがテンデバラバ...
サンプルプログラムはこんな感じになります。
#sh(cpp){{
//scoped_map_sample
static_map<int, int, 3> hoge = { {1,1} };
hoge.insert(make_pair(1,1.0));
hoge[1] = 2;
hoge[0] = 1;
hoge[2] = 3;
// scoped_unordered_map_sample
static_unordered_map<int, double, 1000> fuga{ {1,1.1}...
fuga[2] = 2.1;
fuga[0] = 1.1;
// static_stringをキーとする場合は、hasherとしてstati...
using string10 = static_string<10>;
static_unordered_map<string10, int, 1000, string10::h...
{"hoge",5}, {"fuga",4}, {"piyo",3}, {"apoon",2} };
cout << "fuga is " << strmap["fuga"] << endl;
}}
* static_allocatorの正体 [#d2d96051]
scoped_shared_ptr, static_vector, static_string, static_m...
書式は以下のようになります。
- template<size_t BufferByteSize, typename ElementType = ...
- 定義
-- alctype
--- ElementType型のアロケーター型
-- template<typename T> allocator
--- T型のアロケーター型
- メソッド
-- constructor: なし(デフォルトのみ)
-- alctype operator ()
-- alctype get_allocator()
--- ElementType型のアロケータオブジェクトを返す
-- template<typename T> allocator<T> get()
--- T型のアロケータオブジェクトを返す
仕組みを簡単に説明しますと、STDアロケータと互換のアロケー...
アロケートされるバッファは、static_allocatorクラス内部で ...
以下がソースコード全部です。イケてない部分もありますが、c...
#sh(cpp){{
template <size_t BufferByteSize, typename ElementType=v...
struct static_allocator {
template <typename T>
struct allocator_detail {
uint8_t** buffer_ = nullptr;
size_t* size_left_ = nullptr;
using value_type = T;
using element_type = T;
// これらの定義は、gcc4.8.1で必要になる。clang3.4で...
using pointer = T*;
using const_pointer = const T*;
using reference = T&;
using const_reference = const T&;
using size_type = size_t;
using difference_type = std::ptrdiff_t;
// 確保するメモリーのポインタをサイズを受け取る。
// statefulなallocatorで可能になりました。
allocator_detail(uint8_t** buffer, size_t* buffersi...
: buffer_(buffer), size_left_(buffersize)
{}
// rebindで異なるクラス向けのallocatorを生成すると...
// コンストラクタ。インスタンスを引き継ぐための重要...
template <class U> allocator_detail(const allocator...
: buffer_(other.buffer_), size_left_(other.size_l...
{}
// gcc4.8.1のbasic_stringでこれがないとエラーになる
allocator_detail() {}
// メモリをアロケート
pointer allocate(std::size_t n) const {
size_t required = n * sizeof(value_type);
return allocate_buffer(required);
}
// メモリを解放
void deallocate(pointer p, std::size_t n) const {
size_t deallocsize = n * sizeof(value_type);
// 解放するポインターが最後にアロケートしたバッフ...
if (reinterpret_cast<uint8_t*>(p) == *buffer_ - d...
allocate_buffer(-deallocsize);
}
}
// allocatorを異なる型用に再生成するためのクラス
template<class Other>
struct rebind : allocator_detail<Other> {
typedef allocator_detail<Other> other;
};
// clangではdestroyとconstructは記述しなくても実行...
static void destroy(pointer& p) { p->~T(); }
// clangでは、value_type以外の型で呼ばれるためテン...
template<typename U, typename ...Args>
static void construct(U* p, Args&&... args) {
::new (static_cast<void*>(p)) U(args...);
}
bool operator == (const allocator_detail<T>&) const {
return true;
}
bool operator != (const allocator_detail<T>&) const {
return false;
}
private:
// メモリ確保の処理 失敗したらout_of_rangeをthrow
pointer allocate_buffer(int32_t size) const {
if (size > 0 && *size_left_ < size) {
std::cerr << "out of memory capacity:" << *size...
throw std::out_of_range("static_allocator out o...
}
void* ptr = *buffer_;
*buffer_ += size;
*size_left_ -= size;
return static_cast<pointer>(ptr);
}
};
// static_allocatorの実装はここから
// ElementTypeのallocatorの型をtypeとして定義
template <typename T>
using allocator = allocator_detail<T>;
using alctype = allocator<ElementType>;
// allocator<ElementType>のインスタンスを得る
allocator<ElementType> operator () () {
return get<ElementType>();
}
allocator<ElementType> get_allocator() {
return get<ElementType>();
}
// allocator<T>のインスタンスを得る
template <typename T>
allocator<T> get() {
return allocator<T>(&buffer_ptr_, &size_left_);
}
private:
// これらのインスタンスは、スコープ内ならスタック領域...
// 必要なサイズは、バッファサイズ+ sizeof(*) + sizeof...
uint8_t buffer_[BufferByteSize]; // allocateさ...
uint8_t* buffer_ptr_ = buffer_; // 現在のバッ...
size_t size_left_ = BufferByteSize; // 確保可能な...
};
// アロケーターを比較するための演算子の定義が必要らしい
template <size_t B, typename V, typename T, typename U>
bool operator == (const typename static_allocator<B,V>:...
, const typename static_allocator<B,V>:...
{ return true; }
template <size_t B, typename V, typename T, typename U>
bool operator != (const typename static_allocator<B,V>:...
, const typename static_allocator<B,V>:...
{ return false; }
}}
* まとめ [#o144ea70]
いそいで作成したので手抜きな部分も多々ありますが、仕事で...
小さな領域を使う分だけ確保するという使い方を想定している...
開放した領域の再利用は、最後に開放した1つだけです。その代...
vector,string,map,unordered_mapには、アロケータを指定すれ...
たとえば、static_vectorの場合、
#sh(cpp){{
// static_allocatorで1000バイト(250エレメント)確保
static_allocator<1000, int> alc;
std::vector<int, typename alc::alctype> hoge(alc());
}}
これでOKです。~
この方式ならば、安全にほとんどすべてのコンテナに使えると...
**課題 [#v189376d]
- アロケートのポリシーをアダプターにして代えられる様にし...
- std::scoped_allocator_adaptorと連動できるようにしたい
- clangとgcc以外のc++に似たコンパイラでも動作するようにし...
- 多重継承やめたい
- スレッドセーフにするポリシーを入れたい
- アライメントを指定できるようにしたい
- %%gcc4.8.1でビルドを通すために、std::allocatorを継承し...
- operator == の実装が妖しいので検討中です
あー、課題だらけですね。精進せねば。
&size(30){長い間、ご拝読ありがとうございました。};
この記事は、[[''C++ Advent Calendar 2013''>http://partake...
次の記事は、srz_zumixさんによる7日目の記事になります。よ...
ソースコードは、[[こちら>http://ssa.techarts.co.jp/index....
gcc-4.8.1(Linux環境)と、clang3.4(MacOS環境)で動作確認して...
ソースは良識の範囲内でご自由にお使いください。
ページ名: