差分表示
#freeze
*&date(Y-n-j[lL],2012/12/14); boost::container で俺俺アロケータ
これは [[C++ Advent Calender 2012>http://partake.in/events/a02d7049-1473-4b69-b5ad-25ed416c5557]] 14日目 の記事です。
C++11やboostをまだロクに使っていない人間なので、雰囲気を掴むために boost1.52 の boost/container フォルダを一寸覗いてみました。
new,delete等メモリーアロケート のコストを無視できないターゲットを扱うことも多いので、俺俺アロケータを渡してみたいってのもあり。
C++11仕様でアロケータが今までより楽にかけるようだし、scoped_allocator_adaptor も何か使えそうですし.
※いまだvc9をおもに使ってるので(vc12も使いますが)、C++11の記述はさけてます.
** boost::container
boost::container ですが、C++11で仕様拡張された vector,list,map,set,deque 等のコンテナの機能を C++03コンパイラでもなるべく使えるようにした互換コンテナ群+α です。
C++11 で増えたコンテナ(array, unorderd_map 等)については すでにboostに実装があるためか(?) boost::container には含まれていません。詳しいことは
[[こちら>http://d.hatena.ne.jp/faith_and_brave/20110823/1314080258]]
とか他のサイトにあたってください。
将来的にどんどん変わっていく部分も多々あるでしょうが、とりあえず boost_1_52_0/boost/container/ フォルダで wc してみると、41ファイル 27613 行（detailフォルダ含)。
実際には container 外のboostヘッダをいろいろinclude しているので実質はもっと大きいです（map,set(tree)等は boost::intrusive のものを使っているようです）。
(ちなみに boost_1_52_0/boost/ では 8779ファイル 約172万行、やっぱりデカいです)
boost/container/ 直下にあるファイルは
|allocator_traits.hpp | std::allocator_traits 互換 |
|string.hpp| std::string 互換 |
|vector.hpp| std::vector 互換 |
|deque.hpp| std::deque 互換 |
|list.hpp| std::list 互換 |
|map.hpp| std::map・std::multimap 互換 |
|set.hpp| std::set・std::multiset 互換 |
|scoped_allocator.hpp| std::scoped_allocator 互換 |
|scoped_allocator_fwd.hpp| (scoped_allocator の最小宣言) |
|slist.hpp| 古のslist の拡張版 |
|stable_vector.hpp | vector<T*>で要素を別途アロケートのvector |
|flat_map.hpp| vector< pair<KEY,VALUE> > 風実装で mapインターフェースを持つコンテナ |
|flat_set.hpp| (上記の std::set 風実装) |
|container_fwd.hpp| boost::container |
|detail/ | 詳細実装のファイル群 |
(ptr_container のような)既存のstdコンテナを継承して拡張(メンバー関数追加)とかではないです。
（といっても boost::intrusive 等 boost内の他のライブラリはよく使われています）
次に、いくつかコンテナについて。
** vector
ざっくりメンバー変数の部分だけ抜き出してみて、
template <class Allocator>
class vector_alloc_holder {
struct members_holder : public Allocator {
pointer m_start;
size_type m_size;
size_type m_capacity;
}
}
template <class T, class Allocator>
class vector : vector_alloc_holder<Allocator>;
(SGI版派生等)他の実装だと全てポインタで管理していることが多いですが、この実装はsize,capacityを個数で持っています（個人的にはデバッグ時にメンバー変数で見れるので好み）。
Allocatorは、(非static)メンバー変数がない場合に実質 0バイトになるよう struct の継承元になっています。~
stlの実装では 多少の差違はあれ Allocator は (非static)メンバー変数になっていることが多いですが、
C++03 の場合 static メンバー変数で持つのも有りだったようで、実際そうなっていたコンパイラもありました。~
C++11 では scoped_allocator_adaptor のこともあるし Allocator は (非static)メンバー変数必須のようです。
ということで C++11なら
// １回 N個 アロケートするだけの Allocator
template<typename T, unsigned N>
class SampleAllocator1 {
public:
typedef T value_type;
SampleAllocator1() { }
T* allocate(unsigned n) { assert(n == N); return reinterpret_cast<T*>(buf_); }
void deallocate(T*, unsigned) { }
bool operator == (SampleAllocator1 const & ) const { return false; }
bool operator != (SampleAllocator1 const & ) const { return true; }
private:
typedef double buf_t;
buf_t buf_[(N*sizeof(T)+sizeof(buf_t)-1) / sizeof(buf_t)];
};
//typedef std::vector<int, SampleAllocator1<int,1024> > Int1024Vector;
typedef boost::container::vector<int, SampleAllocator1<int,1024> > Int1024Vector;
Int1024Vector g_intVec;
みたいな真似をしても大丈夫のはず...と書いたけど上記はたぶん boost::container に依存しています.~
（ターゲット環境で mallocの準備前に(固定サイズの)コンテナを使いたい...こともあった)
** list
実装は boost::intrusive の定義も多く面倒なので、かなり端折って (boost::container としてでなく) ありそうな list 実装のメンバーの雰囲気として以下
（すみません、後付で boost::container からめたはいいけど対処しきれず...)
class Node_Base {
Node_Base* next_;
Node_Base* prev_;
};
template<typename T>
class Node : Node_Base {
T value_;
};
template<typename T, class A >
class List : A {
ListNode_Base root_;
size_t size_;
};
かなりいい加減ですが、メモリーの雰囲気がわかれば... ~
//（slist はメモリー的にはNodeのもつリンク(ポインタ)が１個のもの。）
** map,multimap, set, multiset
map,set は たいてい赤黒木 実装のようで、boost::container では boost::intrusive を使ってるようです。~
で、これも メモリーの雰囲気だけ...
class Node_Base {
Node_Base* left_;
Node_Base* right_;
Node_Base* parent_;
bool balance_;
};
template<typename T>
class Node : Node_Base {
T value_;
};
template<typename T >
class Tree : A {
Node_Base root_;
size_t size_;
};
~
List や Map は 渡された アロケータをそのまま使うのではなくて、allocator のメンバーの~
template <class U> struct rebind { typedef allocator<U> other; };
を用いて、 T でなく Node<T> の allocator を使っています。
また、allocator への要求は通常 1個単位になると思います。
ということで、list や map の俺俺アロケータとしては、ノードサイズ固定のメモリーをプールしておく、というのが考えられます。
template<unsigned B, unsigned N>
class SampleAlloc2 {
public:
SampleAlloc2() {
for (unsigned i = 0; i < N-1; ++i)
buf_[i].link = &buf_[i+1];
buf_[N-1].link = NULL;
root_ = &buf_[0];
}
void* allocate(unsigned n) {
assert(n == 1 && root_);
Link* p = root_;
root_ = p->link;
return p;
}
void deallocate(void* t, unsigned n) {
if (t) {
assert(n == 1);
Link* p = reinterpret_cast<Link*>(t);
p->link = root_;
root_ = p;
}
}
private:
union Link {
Link* link;
char b[B];
};
private:
Link* root_;
Link buf_[N];
};
enum { ELM_SIZE = 32 }; // コンテナのノードを含んだ要素のバイト数.
enum { MAX_SIZE = 16 };
template<typename T>
class SampleAllocator2 : public SampleAlloc2<ELM_SIZE,MAX_SIZE> {
typedef SampleAlloc2<ELM_SIZE,MAX_SIZE> base_type;
public:
typedef T value_type;
SampleAllocator2() {BOOST_STATIC_ASSERT(sizeof(T) <= ELM_SIZE);}
T* allocate(unsigned n) { return reinterpret_cast<T*>(base_type::allocate(n)); }
void deallocate(T* t, unsigned n) { base_type::deallocate(t, n); }
bool operator == (SampleAllocator2 const & ) const { return false; }
bool operator != (SampleAllocator2 const & ) const { return true; }
};
// list
typedef SampleAllocator2<int> IntAllocator;
typedef boost::container::list<int, IntAllocator > IntList;
// map
struct cstr_less {
bool operator()(const char* l, const char* r) const { return strcmp(l,r) < 0; }
};
typedef std::pair<char const* const,int> smpPair_t;
typedef SampleAllocator2<smpPair_t> SmpPairAllocator;
typedef boost::container::map<const char*, int, cstr_less, SmpPairAllocator > StrIntMap;
※ 要素(ノード)サイズ(ELM_SIZE)が直うちでみっともないですが、とりあえずは。
** deque
（実装面倒なのと、ターゲットであまり使わないし... いえ、時間切れ. 後日に何か)
** string
std::stringは(C++03では)ライブラリごとに結構実装がばらけています(EffectiveSTL に載ってるのとか)。
c++11 で縛りがきつくなったので多少にかよってくるかもですが、それでもいろいろできそうです。
最小限としては vector と同様の内容になりそうですが...
boost::container::string から端折って抜き出してみると
struct long_t {
size_type is_short : 1;
size_type length : (sizeof(size_type)*CHAR_BIT - 1);
size_type storage;
pointer start;
};
struct short_header {
unsigned char is_short : 1;
unsigned char length : (CHAR_BIT - 1);
};
struct short_t {
short_header h;
value_type data[UnalignedFinalInternalBufferChars];
// UnalignedFinalInternalBufferChars ≒ (sizeof(long_t)-sizeof(short_header))/sizeof(value_type)
};
union repr_t {
long_raw_t r;
short_t s;
};
long_t は長い文字列でアロケータを用いる場合で、sizeof(long_t)-α 以内におさまる短い場合は short_t のようにして領域をバッファとして使い動的確保せずにすませる、という工夫がされています。
64bit CPUだと、vector互換でもsizeof(ポインタ)*3=24bytesになりますし、結構ありがたい実装です。
（最近作ってた 俺俺string がまさにこのタイプだった... もうboostのでよく）
※ メモ: ビットフィールドは エンディアン問わず、先に書かれたものが低アドレスに配置される.
** stable_vector, flat_map, flat_set
stl コンテナの代用品でなく、vector 実装をベースにした特化版。
~
stable_vector は、vector<T*> と要素を別途アロケートしたもの。(boost::ptr_vectorの類似品?)~
flat_map,flat_set は、vector<T> (mapはT=pair<KEY,VALUE>) にソート状態で登録して、インターフェースがmapやsetになったもの。~
各自で俺俺コンテナを作ってそうな類なので（ええ作ってました）、boost にあると楽になりそうです。
（できれば stable_vector を flat_map 化したものもあればうれしいところ）
詳しいことは他のサイトにあたってください。
** scoped_allocator_adaptor
C++11 で増えた アロケータです。~
//vector のところでも少し触れたとおり C++03 まではアロケータをstlコンテナのメンバーにできない実装のものがありえるため、stlコンテナに渡すアロケータは実質 staticインスタンスのみのものだけでしたが、C++11 ではコンテナのメンバーに持てるようになったようです。~
scoped_allocator_adaptor を用いれば、例えば map<string,int> のようなコンテナで、ローカルなアロケータをstringとmapで共通で使えるようにできます。~
※ 内側のコンテナ(この場合 string)のコンストラクタとして、デフォルトコンストラクタでなくアロケータを引数にとるコンストラクタが使われるようになります。
アロケータをコンテナのメンバーにするので、当然メモリー使用量も増えます（とくに内側のコンテナは数が多くなりやすく）。
ので、コンテナのメンバーにするアロケータはポインタだけにし、実装はさらにその先に用意、といった感じにすることになると思います。
詳しいことは [[こちら> http://d.hatena.ne.jp/faith_and_brave/20081128/1227867484]] のサイトとかみてもらったほうがいいです。
正直なところ一見ではよくわからず、試してみてなんとなく納得の状態です。
以下、試してみたソース.
#include <stdio.h>
#include <boost/container/map.hpp>
#include <boost/container/string.hpp>
#include <boost/container/scoped_allocator.hpp>
#include <boost/foreach.hpp>
// mapで解放しないこと前提に、スタックで解放無視の簡易アロケータ.
template<unsigned N>
class SampleAlloc3 {
public:
SampleAlloc3() : size_(0) { }
void* allocate(unsigned n) {
assert(size_+n <= N);
void* p = ptr(size_);
size_ += n;
return p;
}
void deallocate(void*, unsigned) { /*dummy*/ }
private:
typedef double buf_t;
void* ptr(unsigned n=0) { return (char*)buf_ + ((n + sizeof(buf_t)-1) & ~(sizeof(buf_t)-1)); }
private:
unsigned size_;
buf_t buf_[N / sizeof(buf_t)];
};
// map<string,int> のメモリー
template<unsigned SAMPLE_ALLOC3_SIZE>
class Hoge {
public:
Hoge() : strIntMap_(std::less<String>(), MapAllocator(StrIntPairAlloc(&smpAlc3_))) {}
void insert(const char* name, int val) {
//strIntMap_[String(name, &smpAlc3_)] = val;
strIntMap_.emplace( name, val );
}
void printAll() {
BOOST_FOREACH(StrIntPair p , strIntMap_)
printf("%s = %d\n", p.first.c_str(), p.second);
}
private:
typedef SampleAlloc3<SAMPLE_ALLOC3_SIZE> Alloc;
template<typename T>
class SampleAllocator3 {
public:
typedef T value_type;
// SampleAllocator3() : alc_(0) {} // デフォルトコンストラクタは用意しないほうが安全.
SampleAllocator3(Alloc* alc) : alc_(alc) { }
template<typename U> SampleAllocator3(SampleAllocator3<U> const& r) : alc_(r.detail_get_ptr()) { }
T* allocate(unsigned n) { return reinterpret_cast<T*>(alc_->allocate(n*sizeof(T))); }
void deallocate(T* p, unsigned n) { alc_->deallocate(p,n*sizeof(T)); }
bool operator == (SampleAllocator3 const & ) const { return false; }
bool operator != (SampleAllocator3 const & ) const { return true; }
Alloc* detail_get_ptr() const { return alc_; }
private:
Alloc* alc_;
};
typedef boost::container::basic_string<char, std::char_traits<char>, SampleAllocator3<char> > String;
typedef std::pair<const String, int> StrIntPair;
typedef SampleAllocator3<StrIntPair> StrIntPairAlloc;
typedef boost::container::scoped_allocator_adaptor< StrIntPairAlloc > MapAllocator;
typedef boost::container::map<String, int, std::less<String>, MapAllocator > StrIntMap;
private:
SampleAlloc3<SAMPLE_ALLOC3_SIZE> smpAlc3_;
StrIntMap strIntMap_;
};
void sample3()
{
Hoge<1024> hoge;
hoge.insert("xyz", 1);
hoge.insert("abcdefghijklmnopqrstuvwxyz", 2);
hoge.insert("1234567890", 3);
hoge.printAll();
}
emplace, emplace_back、単に(コピー)コンストラクタの頻度さげるだけじゃなくて、今回のような場合まさに必須の類でした。~
共通で使うアロケータ(SampleAllocator3)には デフォルトコンストラクタをつけちゃダメ、というのを実感。~
( デフォルトコンストラクタつけてると insertや push_back 使ってもコンパイル通るため... ハマりました)
** おわりに
遅刻したうえに、
グダグダな内容ですみません。~
（当初の目論見からずれまくり...そもそも deque 調べるため boost::container 見始めたはずが)
例に挙げたソースのとおり allocator の記述に関してはすごく楽でした。
が、boost::contaneier を std:: にかえて vc12 でコンパイルすると全く×だったので
boost::contaneier に結構依存していると思います。
時間の余裕なくなってるので、たぶん後日 補足修正書くことになりそうですが...
おつきあいいただきありがとうございました。
~
[CR]
//明日 15日は (てもう今日）、@yohhoy さんです。
15日目は、@yohhoy さんです。
----
追記: [[コンパイル試したときのソース>http://www.6809.net/tenk/html/prog/BoostContainerSample.zip]]
----
#comment