2,646行もあるUE4のTArrayのヒミツ
ということで、Unreal Engine 4 (UE4) Advent Calendar 2017、18日目ですので、唐突にUnreal Engine 4のTArrayの話をします。
TArrayは一言で言えば、Epic Games, Inc.が考えた最強の可変長配列です。
（誇張あり）
そもそもC++で可変長配列を扱うならばstd::vectorを使うべきだ！
そう主張する人もおられるでしょう。
確かにそういった主張は一理あるのですが、
（私もNintendoDSの開発ではstd::vectorを使っていましたが）
ゲーム開発で求められる厳密なメモリ操作などをするには
std::vectorでは不十分なケースが多いため、
速度とメモリを優先したい、
または本来セーフティではないが、どうしてもこの操作を行いたい、
という状況を求められる環境では多くの場合自作のコンテナが必要となります。
ゲーム会社がこうしたコンテナ類を自作していることは数多くあり、
外部に公開されている一番有名なものとしてはEASTL(Electronic Arts STL)が挙げられるでしょう。
Unreal Engine 4においても同様にゲームを作るために向いた標準コンテナというものが存在しています。
今回はこちらの中でも普段よく使うであろうTArray(可変長配列)を簡単に説明していきます。
C++に馴染みがない方に向けていうと、
JavaのArrayList<Type>や、C#のList<Type>などに相当するものです。
Unreal C++のTArrayの設計／実装に興味がない人は恐らく全く面白くありませんので、ここで読むのを中断することをオススメします。
TArrayが実装されているArray.hはタイトルの通り2,646行もあり、
そこそこの長さを持っていますが、
サッと機能だけ確認していくとしましょう。
検証バージョンは、4.18.2を利用しています。
また、単に使うだけならばTArrayのドキュメントを読むだけでも十分かもしれません。
また、行数に関してはSTLportのvector実装も1,000行ちょいなので、メチャクチャ長いというほどでもありません。
注意書き
多分にもれず、TArrayの要素はメモリ上で再配置されます。
（再配置されないようにプログラムすることはできる）
すなわち、それはコンテナがコピーコンストラクタを使わずとも、
新しいメモリに透過的に移動できる、ということを意味しています。
言い換えれば、配列の要素を追加／削除することによって、
TArrayの要素が配置されてるアドレスが移動する（事がある）ため、
要素を指していたポインタが不意に無効になるわけです。
勿論、TArrayの各要素を指していたポインタは不正になります。
また、要素の削除はO(N)で、
削除した場合、後続要素のインデックスは無効になります。
（TArrayの注意書きより抜粋と意訳）
簡単に言えば、
使い方によってメモリは破壊されるかもしれないし、
不正なアクセスでゲームは止まるかもしれない、
そして、削除は遅いよ、って話です。
それならなぜC++を使うのか、TArrayを使うのか、
というと「危険だが自由でかつ速い」の一点が強いといえるでしょう。
“C makes it easy to shoot yourself in the foot; C++ makes it harder, but when you do it blows your whole leg off”.Cでは自分の足を撃ち抜くことは容易い。
C++ではそれが起きにくくしたが、
もしやってしまったときは、足が無くなる。（C++の開発者より）
メモリ戦略
では、TArrayの中身を覗いてみましょう。
[EnginePath]/Engine/Source/Runtime/Core/Public/Containers/Array.hがそれです。
まず見るべきはメモリを確保するシーンですね。
要素を追加したりした際にメモリが足らなくなったら要素を格納するためにメモリを確保する場所があるはずです。
privateなので外から呼び出すことはできませんが、
ResizeGrowがそれです。
一般的に要素の追加で呼び出されるAddは、
内部的に Emplace(std::vector::emplaceと等価)を呼び出します。
Emplaceは AddUninitialized(初期化せずに要素を追加)したあとに、
そのメモリ領域に new(GetData() + Index)で直接要素を割り当てます。
GetDataは先頭のメモリ領域を指しており、そこからインデックスを加算したアドレスに要素を構築するわけです。
AddUninitializedは、
上記のように要素を初期化せずに要素のメモリ領域を追加する（利用中にする）のですが、
この際に、すでに確保しているメモリ領域を超える追加が行われるならば、
TArrayはメモリを再確保する ResizeGrowを呼び出すのです。
結果として ResizeGrowの中で AllocatorInstance.ResizeAllocationが呼ばれ、
TArrayは通常アロケータに FDedaultAllocatorが指定されており、
この実体は FHeapAllocatorであるため、
FHeapAllocatorの CalculateSlackGrowと ResizeAllocationが呼び出されます。
CalculateSlackGrowは DefaultCalculateSlackGrowを呼び出すことで
必要なメモリの確保量を決め、
ResizeAllocationがそれを FMemory::Reallocに渡します。
DefaultCalculateSlackGrowはどのような戦略をとるか？
TArrayが DefaultCalculateSlackGrowに渡すのは、
ArrayNum= 現在の要素数（新しく必要となった要素数）
ArrayMax= 現在の確保数（既に確保している要素数）
sizeof(ElementType)= 要素のバイト数
です。
ArrayMaxが既にあるか（メモリが既に確保されているか）
もしくは、 ArrayNumが Growの既定値の4を超えていたら、
// Allocate slack for the array proportional to its size.
Grow = SIZE_T(NumElements) + 3 * SIZE_T(NumElements) / 8 + 16;という式を用いて Growを新しく求めます。
NumElements は現在必要な要素数ですから、
例えば10なら、
10 + 3 * 10 / 8 + 16で、29。
100なら、100 + 3 * 100 / 8 + 16で、153。
1000なら、1000 + 3 * 1000 / 8 + 16で、1391。
と、+16の補正があるので、
要素が小さければ小さいほど余分に確保します。
余分に確保しなければならない理由として、
ピッタリのメモリ領域を用意してしまうと、
連続で Addされた場合に、何回も Reallocを呼び出す羽目になるためです。
（メモリの確保はコストが馬鹿みたいに高い）
Retval = FMemory::QuantizeSize(Grow * BytesPerElement, Alignment) / BytesPerElement;その後、アライメントのサイズを指定し、断片化対策のために QuantizeSizeを求めて、このサイズのメモリを Reallocするようにします。
このメモリの確保に関しては一般的なものなので、
余程きちんとメモリを管理したい、
というのでなければ Allocatorにまかせて良いはずです。
（ですが、カスタマイズもできる）
もし Addしかしない、というのであればこれがすべてなのですが、
ザッとどのような機能があるか見ていきましょう。
コンストラクタ
一般的な作りになっています。
何も指定しないもの、
生配列からコピーで生成するもの、
初期化子から受けるもの、
TArrayからコピーされるもの、と至って普通です。
もちろん、代入演算子もサポートしています。
ただし、ソースにも記載があるのですが、
初期化子で受ける際の std::initializer_listの Iterator、
実際にはポインタであることは保証されていないため、
厳密に言えば合法ではありません。
現状は大丈夫ですが、新しい実装でポインタでなくなった場合、
ひどい振る舞いをするのではなく、
コンパイルに失敗するようになる、と書かれています。
FORCEINLINE TArray(const TArray& Other, int32 ExtraSlack)他のTArrayからコピーしてくる場合、
ここで引数として「予め余分なメモリを確保する」ことができます。
ExtraSlackがそれですね。
なぜ余分なメモリを確保するのかというと、
あとから追加することがわかっているようなケースで、
メモリの確保を一度に抑えたいからです。
（繰り返すが、メモリのアロケーションは遅い）
勿論、ムーブコンストラクタも存在しています。
デストラクタ
DestructItemsによって要素を格納していたメモリが開放されます。delete []を使っていないので、
内部的には要素を回してデストラクタを呼び出しています。
各種操作
前述の通り、 GetDataで生ポインタもとれます。
GetAllocatedSizeで割り当てられたメモリ量をとったり、
GetSlackで、あとどれくらいメモリを確保せずに割り当てられるかを得たり、
IsValidIndexで指定インデックスが範囲内に収まっているかの取得もできます。
キューとして扱いたい場合の、
Pushや Popもありますし、
先頭や終端の要素を取るための Top、 Lastもあります。
また、 ArrayMax（割り当てられたメモリ）が
ArrayNum（実際の要素数）を上回っているときに
メモリを縮小する Shrinkなどもあります。
bAllowShrinkingオプション
TArrayの要素の削除を発生させるような操作には、
bAllowShrinkingフラグが指定でき、これはデフォルトではtrueになっています。
これがtrueだと何が起こるかというと、
要素の削除後に ResizeShrinkを呼び出し、メモリ割り当てサイズを減らそうとします。
しかしながら、この削除が一時的なものであればこれは不要なはずです。
よって、 bAllowShrinkingをfalseにすることを検討できます。
検索
コンテナから要素を探すための Findも用意されています。
とはいえ、TArrayはデータ構造的には連続したメモリ領域なので、
先頭から終端まで舐めてくれるだけです。
FindLastもありますので、終端から舐めることもできますし、
FindByPredicate、 FindLastByPredicate、 IndexOfByPredicateなどで、
Predicate(評価式)を渡すこともできます。
TArray<int>* IntArray1 = new TArray<int>({1, 2, 3, 4, 5, 6, 7, 8, 9, 10});int32 Index = IntArray1->FindLastByPredicate([](const int& Value){ return Value == 5; });
FindByKey、 IndexOfByKeyでキー（オーバーロード演算子==）の検索もできます。
FilterByPredicateでフィルターした結果や、
Contains、 ContainsByPredicateで要素が含まれているか、も知ることができます。
特殊な追加／挿入／削除
AddUninitialized、 InsertUninitializedはコンストラクタを呼び出さずに要素を追加／挿入します。
InsertZeroedはコンストラクタを呼び出さずに、0で埋められた要素を挿入します。
InsertDefaultedはデフォルトコンストラクタを呼び出して、要素を挿入します。
Addにも、 AddZeroed、 AddDefaultedが存在します。
また、 Addには AddUniqueが存在し、
その要素が存在しなければ追加する、といったことができます。
（内部では Findして等価性の要素を探しているだけですが）
削除には効率がO(ArrayNum)の代わりに
O(Count)になる RemoveAtSwapも存在します。
どういうことかというと、
削除すべきIndexに達したらそこの要素と別の要素を入れ替えて
削除を終了します。
すなわち、削除後、削除前の順番が保証されなくなる代わりに高速ということです。
RemoveSingleは、最初に見つかった指定した要素だけを削除します。
RemoveAllは、指定した Predicateと一致するものをすべて削除します。
RemoveAllSwapは、指定したInstanceと一致するものをすべて削除しますが、削除の際に RemoveAtSwapを使用します。
RemoveSingleSwapは、最初に見つかった指定した要素だけを削除し、
削除に RemoveAtSwapを使用します。
RemoveSwapは、指定したインスタンスを削除しますが、削除に RemoveAtSwapを使用します。
Resetは要素を0にしますが、メモリを開放しません。
（もしくは指定した新しいサイズにします）
Emptyは要素を空にして指定した分だけメモリを残します。
SetNumは、指定された数に配列を広げるか縮めます。
SetNumZeroedは指定された数に配列を広げるか縮めますが、
広げるときに0でフィルします。
SetNumUninitializedは指定された数に配列を広げるか縮めますが、
広げるときに初期化しません。
SetNumUnsafeInternalは要素数を変更しますが、
要素に対してデストラクタなどを呼び出しませんし、
メモリもいじりません。
（ ArrayNumだけ強制的に書き換える＝ Unsafe）
概ね、ゲーム開発に欲しそうなものが揃っています。
通常の追加／挿入／削除
Appendで単一の要素を追加したり、TArrayを追加したり、初期化子リストを追加できます。
もちろん、通常の Insertもありますし、
削除を担当する RemoveAtもあります。
特殊な操作
Emplace、 EmplaceAtで、確保されているメモリ要素に対して、
コンストラクタ引数を受取、直接要素を構築します。
Reserveは、指定したサイズにコンテナのメモリを拡張します。
（ ArrayMaxを増やします）
Initは、指定した要素と数でそのコンテナを埋めます。
（すでにあった要素は解放され、指定した要素で埋められます）
SwapMemoryは、指定したインデックス同士のメモリを入れ替えます。
インデックスなどを全くチェックしないので指定を間違えるとメモリが壊れます。
Swapの方はインデックスがおかしくないか、確認してからメモリを入れ替えます。
クラスを指定した検索
FindItemByClassを利用するとクラスを指定した検索が行なえます。
中身は、 UClass* SearchClass = SearchType::StaticClass();を見ているため、
クラスならなんでも検索できるわけではありません。
ソート
ソートも、 operator <を利用したものと、
Predicate class(評価式)を利用したソートが行なえます。
また、 Sortと StableSort、 HeapSortが存在します。
ヒープ化
TArrayの特殊な性質として、配列をヒープ化できる機能があります。
(std::make_heapのように）
メンバ関数である Heapifyを呼び出すことで、
TArrayをバイナリヒープ（二分ヒープ）に変える事ができます。
バイナリヒープ、そもそも何に使うのでしょうか？
バイナリヒープは、
最小または最大の値が必ず最初のキーに来るようになるデータ構造です。
要するに配列を舐めなくても、
最小か最大の値をすぐに取得できるようになります。
ただし、 HeapifyしたTArrayに Addすると構造が壊れます。
必ず HeapPush使って値を追加しなければなりません。
また、削除する場合は HeapPopで先頭の要素のコピーを受け取り、
先頭を削除します。
HeapPopDiscardを使えば先頭の要素のコピーを受け取らずにそのまま先頭を削除できます。
HeapRemoveAtを使うことで、指定のインデックス番号で配列から要素を削除し、ヒープ構造も維持します。
ヒープ構築や追加、削除の条件にはPredicate classで評価式を指定できます。
指定しなければ operator <で評価されます。
ゲームでバイナリヒープを扱う利点として1,000個を超えるようなデータ、
もしくはオブジェクトから条件に合う（最大の攻撃力など）ものを取り出すのに、
配列要素全てを舐めることなく実現できることです。
また、ヒープを再構築する時間も最小にすることができます。
（1,000個なら、最大9回比較するだけでヒープ構造が維持できる）
最後に
長々とTArrayについて書いてきましたが、
見ていただけたようにTArrayはstd::vectorのように汎用性を目指したものとは異なり、
ゲーム開発、特にUnreal Engine 4ならではの思想によって安全面よりも速度と自由度に傾いて構築されています。
また、同じゲームエンジンでもUnityが提供しているGeneric Listなどとは異なり、普段使うようなコンテナでさえ、
（逆にいうと普段使いするコンテナだからこそ）
Engineのコア部分と密接に関係しているといえます。
また、危険を承知で速度を優先して使うべきメソッドも含まれています。
メモリの挙動をよく理解せずに使えば、アプリが落ちるどころか、
メモリ破壊によって不可解なバグを生み出しかねないものです。
しかしながら、Unreal Engine 4は自分たちでコンテナのソースコードに手を加えて、
それらとうまく付き合っていくことができる構造になっています。
（Unityがソースに手を入れられない、という意味ではない）
だからこそ「Unreal Engine 4」はカスタマイズの自由度が高い、といえるわけですし、
世界に誇るゲームを作っているエンジンの中身を無料で垣間見えるということが、どれだけ素晴らしく価値のあることなのか、少しでも伝われば幸いです。
私たちが頭のなかで考えているプログラミング言語と想像している問題と解決策との間のつながりは極めて密接な関係にあります。
このため、プログラマーのエラーを無くす目的で言語機能を制限することは、最も危険なことです。
ビャーネ・ストロヴストルップ
