アロケータ（C++）

C++プログラミングにおいて、アロケータはC++標準ライブラリの構成要素です。標準ライブラリは、リストやセットなど、コンテナと呼ばれる様々なデータ構造を提供します。これらのコンテナに共通する特徴は、プログラムの実行中にサイズを変更できることです。これを実現するには、通常、何らかの動的なメモリ割り当てが必要です。アロケータは、特定のコンテナに対するメモリの割り当てと解放の要求をすべて処理します。C++標準ライブラリは、デフォルトで使用される汎用アロケータを提供しますが、プログラマが独自のアロケータを提供することもできます。

アロケータは、アレクサンダー・ステパノフによって標準テンプレートライブラリ（STL）の一部として考案されました。当初は、ライブラリの柔軟性を高め、基盤となるメモリモデルから独立させることで、プログラマがライブラリ内でカスタムポインタ型や参照型を利用できるようにすることを目的としていました。しかし、STLをC++標準に採用する過程で、C++標準化委員会は、メモリモデルを完全に抽象化すると、許容できないほどのパフォーマンス低下を招くことに気づきました。この問題を解決するため、アロケータの要件はより厳しくなりました。その結果、アロケータによって提供されるカスタマイズのレベルは、ステパノフが当初想定していたよりも制限されています。

とはいえ、カスタムアロケータが望ましい場面は数多く存在します。カスタムアロケータを作成する最も一般的な理由としては、メモリプールを使用して割り当てのパフォーマンスを向上させること、共有メモリやガベージコレクションされたメモリなど、異なる種類のメモリへのアクセスをカプセル化することなどが挙げられます。特に、少量のメモリを頻繁に割り当てるプログラムは、実行時間とメモリ使用量の両面で、専用のアロケータから大きな恩恵を受ける可能性があります。

標準ライブラリ内では、アロケータは以下のヘッダーファイルに含まれています。

• <memory>デフォルトのアロケータタイプの場合std::allocator<T>^{[ 1 ]}
• <memory_resource>^{実行時多態性アロケータ[ 2 ]}の場合std::pmr::polymorphic_allocator<T>
• <scoped_allocator>マルチレベルアロケータの場合std::scoped_allocator_adaptor<Out, In...>^{[ 3 ]}

アレクサンダー・ステパノフとメン・リーは、1994年3月にC++標準化委員会に標準テンプレートライブラリ（STL）を提出した。 ^{[ 4 ]}このライブラリは予備承認を受けたが、いくつかの問題が提起された。特に、ステパノフはライブラリコンテナを基盤となるメモリモデルから独立させるよう求められ、^{[ 5 ]}その結果、アロケータが作成された。したがって、すべてのSTLコンテナインターフェースはアロケータを受け入れるように書き直す必要があった。

C++標準ライブラリにSTLを組み込むにあたり、ステパノフはアンドリュー・ケーニッヒやビャルネ・ストロヴストルップを含む標準化委員会の数名のメンバーと緊密に協力し、カスタムアロケータが永続ストレージSTLコンテナの実装に使用できる可能性があることを指摘した。ステパノフは当時、これを「重要かつ興味深い洞察」とみなした。^{[ 5 ]}

当初のアロケータの提案には、委員会でまだ承認されていなかった言語機能、すなわちテンプレート引数自体がテンプレートである機能が含まれていました。これらの機能は既存のコンパイラではコンパイルできなかったため、Stepanov によれば、「未実装の機能を正しく使用していることを検証するために、Bjarne [Stroustrup] と Andy [Koenig] の時間が膨大に消費された」とのことです。^{[ 5 ]}ライブラリが以前はポインタ型と参照型を直接使用していたのに対し、今後はアロケータで定義された型のみを参照することになります。Stepanov は後にアロケータについて次のように説明しています。「STL の優れた点は、マシン関連の型に言及している箇所が、わずか 16 行程度のコード内にカプセル化されていることです。」^{[ 5 ]}

ステパノフは当初、メモリ モデルを完全にカプセル化するアロケータを意図していたが、標準化委員会はこのアプローチでは許容できない効率の低下を招くことに気づいた。^{[ 6 ] [ 7 ]}この問題を解決するために、アロケータの要件に文言が追加された。具体的には、コンテナの実装では、ポインタおよび関連する整数型のアロケータの型定義がデフォルトのアロケータによって提供されるものと同等であり、特定のアロケータ型のすべてのインスタンスが常に等しいと想定することができる。 ^{[ 8 ] [ 9 ]}これは、アロケータの当初の設計目標と事実上矛盾し、状態を保持するアロケータの有用性を制限するものである。^{[ 7 ]}

ステパノフは後に、アロケータは「理論的にはそれほど悪いアイデアではないが、（…）残念ながら実際には機能しない」とコメントした。彼は、アロケータを本当に有用なものにするには、参照に関するコア言語の変更が必要だと指摘した。^{[ 10 ]}

2011 年の C++ 標準の改訂では、特定の型のアロケータが常に等価性を比較し、通常のポインタを使用することを要求する曖昧な表現が削除されました。これらの変更により、ステートフル アロケータがはるかに便利になり、アロケータがプロセス外の共有メモリを管理できるようになりました。 ^{[ 11 ] [ 12 ]}現在のアロケータの目的は、基盤となるハードウェアのアドレス モデルを適応させることではなく、コンテナ内のメモリ割り当てをプログラマに制御させることです。実際、改訂された標準では、アロケータが C++ アドレス モデルへの拡張を表す機能が削除され、正式に (そして意図的に) 本来の目的がなくなりました。^{[ 13 ]}

アロケータの要件を満たすクラスであれば、どれでもアロケータとして使用できます。特に、型のオブジェクトのメモリを割り当てることができるクラスは、型のオブジェクトと、型のオブジェクトへの参照（またはポインタ）を汎用的に宣言するための型、、、、、を提供する必要があります。また、によって定義される割り当てモデルにおけるオブジェクトの最大サイズを表すことができる符号なし型である型、および同様に、割り当てモデルにおける任意の 2 つのポインタの差を表すことができる符号付き整数型も提供する必要があります。^{[ 14 ]}ATA::pointerA::const_pointerA::referenceA::const_referenceA::value_typeTA::size_typeAA::difference_type

準拠した標準ライブラリの実装では、アロケータのA::pointerと がA::const_pointer単に とのtypedef でT*あると想定することが許可されていますが、ライブラリの実装者はより一般的なアロケータをサポートすることが推奨されています。^{[ 15 ]}constT*

A型のオブジェクトのためのアロケータは、T次のシグネチャを持つメンバ関数を持つ必要があります。

A ::ポインタA::allocate ( A :: size_type n , A < void >:: const_pointer hint = 0 );

nこの関数は、型のオブジェクトを格納するのに十分な大きさの、新しく割り当てられた配列の最初の要素へのポインタを返しますT。メモリのみが割り当てられ、オブジェクトは構築されません。さらに、オプションのポインタ引数（によって既に割り当てられたオブジェクトを指す）は、局所性Aを向上させるために新しいメモリをどこに割り当てるべきかについての実装へのヒントとして使用できます。^{[ 16 ]}ただし、実装は引数を無視しても構いません。

対応するメンバ関数は、前回のメンバ関数の呼び出しから返されたポインタと、解放する（ただし破棄しない）要素の数を受け取ります。voidA::deallocate(A::pointerp,A::size_typen)A::allocate

メンバー関数は、の呼び出しによって正常に割り当てられると予想されるA::max_size()型のオブジェクトの最大数を返します。返される値は通常です。^{[ 17 ]}また、メンバー関数は、が与えられた場合にオブジェクトのアドレスを示すを返します。TA::allocateA::size_type(-1)/sizeof(T)A::addressA::pointerA::reference

オブジェクトの構築と破棄は、割り当てと解放とは別に実行されます。^{[ 17 ]}アロケータには、オブジェクトの構築と破棄をそれぞれ処理する 2 つのメンバ関数 (両方の関数は C++17 で非推奨A::constructとA::destroyなり、C++20 で削除されました) が必要です。これらの関数のセマンティクスは、次のものと同等である必要があります。^{[ 14 ]}

template < typename T > void A :: construct ( A :: pointer p , A :: const_reference t ) { new (( void * ) p ) T ( t ); }template < typename T > void A :: destroy ( A :: pointer p ){ (( T * ) p ) ->~ T (); }

上記のコードは配置new構文を使用し、デストラクタを直接呼び出しています。

アロケータはコピー構築可能であるべきである。型のオブジェクトのアロケータは、T型のオブジェクトのアロケータから構築できるU。アロケータがAメモリ領域を割り当てる場合R、Rはと等しいと比較されるアロケータによってのみ解放できるA。^{[ 14 ]}

アロケータはテンプレートクラスメンバーを提供する必要がありますrebind。

template < typename U > struct A :: rebind { using other = A < U > ; };

これにより、異なる型でパラメータ化された関連アロケータを取得することが可能になります。たとえば、IntAllocator型のオブジェクトのアロケータ型が与えられた場合int、型オブジェクトの関連アロケータ型はlongを使用して取得できます。^{[ 17 ]}IntAllocator::rebind<long>::other

カスタムアロケータを作成する主な理由の 1 つはパフォーマンスです。専用のカスタムアロケータを使用すると、プログラムのパフォーマンスまたはメモリ使用量、あるいはその両方が大幅に改善される可能性があります。^{[ 7 ] [ 18 ]}デフォルトのアロケータは、operator newメモリを割り当てるために を使用します。^{[ 19 ]}これは、通常、大きなメモリ ブロックのまれな割り当てに最適化されているC のチープ割り当て関数の周りに薄いレイヤーとして実装されることがよくあります。^{[ 20 ]}このアプローチは、 std::vectorやstd::dequeのように、主に大きなメモリ チャンクを割り当てるコンテナではうまく機能する可能性があります。^{[ 18 ]}ただし、 std::map (赤黒木マップ) やstd::list (二重リンク リスト)のように、小さなオブジェクトの頻繁な割り当てを必要とするコンテナでは、デフォルトのアロケータを使用すると一般的に遅くなります。^{[ 7 ] [ 20 ]} mallocベースのアロケータのその他の一般的な問題には^、参照の局所性の低さ[ ^{7 ]}や、メモリの断片化の過剰^{[ 7 ] [ 20 ]}などがあります。

パフォーマンスを向上させる一般的なアプローチは、メモリ プールベースのアロケータを作成することです。^{[ 18 ]}コンテナにアイテムが挿入または削除されるたびにメモリを割り当てる代わりに、大きなメモリ ブロック (メモリ プール) を事前に割り当てます。これは、プログラムの起動時に行う場合があります。カスタム アロケータは、プールからメモリへのポインタを返すだけで、個々の割り当て要求に対応します。実際のメモリの解放は、メモリ プールの有効期間が終了するまで延期できます。メモリ プール ベースのアロケータの例は、Boost C++ ライブラリにあります。^{[ 18 ]}

カスタムアロケータのもう1つの有効な用途は、メモリ関連のエラーのデバッグです。 ^{[ 21 ]}これは、デバッグ情報を格納するための追加メモリを割り当てるアロケータを作成することで実現できます。^{[ 22 ]}このようなアロケータを使用すると、メモリが同じタイプのアロケータによって割り当ておよび解放されることを保証し、オーバーランに対する限定的な保護も提供できます。^{[ 22 ]}

カスタムアロケータのテーマは、Scott Meyers のEffective STLやAndrei AlexandrescuのModern C++ Designなど、多くのC++ の専門家や著者によって取り上げられてきました。Meyers は、C++98 ではすべてのアロケータのインスタンスが同等でなければならないことを強調し、これにより移植可能なアロケータは事実上状態を持たないように強制されていると指摘しています。C++98 標準ではライブラリの実装者に状態を持つアロケータをサポートするよう奨励していましたが、^{[ 15 ]} Meyers は関連する段落を「素敵な考え」であり「ほとんど何も提供しない」と呼び、この制限を「厳しすぎる」と特徴づけています。^{[ 7 ]}

一方、ビャルネ・ストロヴストルップは著書『C++プログラミング言語』の中で、「アロケータにおけるオブジェクトごとの情報に対する一見厳格な制限は、それほど深刻なものではない」と主張している[6]。これは、ほとんどのアロケータは^{状態を必要}とせず、状態がない方がパフォーマンスが向上することを指摘している。彼は、カスタムアロケータの3つのユースケース、すなわちメモリプールアロケータ、共有メモリアロケータ、およびガベージコレクションメモリアロケータについて言及している。彼は、内部メモリプールを使用して小さなメモリチャンクを高速に割り当ておよび解放するアロケータの実装を紹介しているが、このような最適化は、実装によって提供されるアロケータによって既に実行されている可能性があると述べている^{[ 6 ] 。}

namespace std { template < typename T , typename Alloc = allocator < T >> class vector ;// ...namespace pmr { template < typename T > using vector = :: std :: vector < T , polymorphic_allocator < T >> ;// ... } }

次の例では、GNU Compiler Collectionのlibstdc++<bits/new_allocator.h>のヘッダーを使用しています。^{[ 25 ]}

import < bits / new_allocator.h > import std ;​​using std :: bad_alloc ; using std :: string ; using std :: string_view ; using __gnu_cxx :: new_allocator ;class RequiredAllocation { private : static constexpr string_view DEFAULT_NAME = "Hello, world! \n " ; public : const string name ;RequiredAllocation ( string_view name = DEFAULT_NAME ) : name { string ( name )} { std :: println ( "RequiredAllocation コンストラクタ" ); }~ RequiredAllocation () { std :: println ( "RequiredAllocation デストラクタ" ); } };void alloc ( new_allocator <RequiredAllocation> & all , size_t size , void * p , RequiredAllocation & t ) { try { all.allocate ( size , p ) ; std :: println ( "{}" , all- > max_size ( )); for ( char c : t.name ) { std :: println ( c ) ; } } catch ( const bad_alloc & e ) std :: println ( stderr , " Bad allocation exception: {}" , e.what ( )) ; } }int main () { new_allocator < RequiredAllocation > all ;RequiredAllocation t ; void * pt = & t ;// new が割り当てるストアを見つけられない場合、// デフォルトでは、アロケータは std::bad_alloc をスローします。 constexpr size_t BAD_SIZE = 1073741824 ; alloc ( all , BAD_SIZE , & pt , t );constexpr size_t SMALL_SIZE = 1 ; alloc ( all , SMALL_SIZE , & pt , t );return 0 ; }

• CodeGuru: アロケータ (STL) 2012年2月13日にWayback Machineにアーカイブされました。
• 入門記事「C++標準アロケータ、概要と実装」。
• malloc に基づくカスタムアロケータの実装