目次

1.はじめに
2.エラーメッセージ付きassert
3.Slot map
4.Sparse set
5.traitによる静的実装分岐
6.おわりに

はじめに

この記事はCCS Advent Calendar 2022の21日目の記事です。

昨日の記事は、kakira9618さんの「 AtCoder の過去問埋めを超楽にするサービスを作った話（ダイジェスト）」です。
競プロクソ雑魚でWA×2を一生出している民なので、非常にありがたく凄いサービスな気がします。活用してみたいです。

明日の記事は、Zukashunさんの「ChatGPIはウミガメのスープの味を知るか？」です。ChatGPTは自分もいじってみましたが正直かなり面白いので、注目記事です。

お初に(裏の記事を見ていただいた方は2度目に)お目にかかります。
20(編入)のゆういちろうと申します。低レベル描画周りとC++が好きで色々勉強していますが、コードより恥をかく方が得意です。

この記事では、筆者が割と好んでいる技法、設計、データ構造等を紹介します。以下、注意点です。

• 新しいアイデアとかではありません。筆者がせっせと作っているのは全て車輪です。ググれば素晴らしい解説がたくさん出ます。
• はちゃめちゃに嘘や誤りを含む可能性があります。そのマサカリで撃ち抜いてください。
• 主にC++の話です。(別の言語で使える話もあります)
• 多分、知ってから使うまでのコストが低い順に並んでいます。
• そんなことよりまずDoxygenを使いましょう。こんなボロ記事を読んでいる場合ではありません。

エラーメッセージ付きassert

C/C++にはassertというマクロがあります。（assert.h/cassertに定義されています)

void hoge(int foo)
{
    // ここでfooがbarなのはあり得ない話し!
}

void hoge(int foo)
{
    assert(foo != bar);
    // ここでfooがbarなのはあり得ない話し!
}

assert(条件式 || !"エラーメッセージ");

こう書きます。すると、このassertが発生した場合、

Assertion `条件式 || !"エラーメッセージ"' failed.

と表示されるため、エラーメッセージも確認できます。

Q. そもそもassertなんて使わずに例外使った方がいいんじゃない?
A. リアルタイムな感じだと例外なんて重くて使えねえよ!!!!!(言い過ぎ)

noexceptは、代表的には以下の2つの用途で使用できる：

1. パフォーマンス向上
   例外を送出しないという保証があることで、コンパイラは例外送出によるスタック巻き戻しのためのスタックを確保する必要がなくなる

(こちらより引用)
大して意味ないらしいですねこれ

Slot map

これは連想コンテナの1種であり、C/C++に限った話ではありません。(Rustには標準で用意されています)
C++による実装はこちら等にあります。(ググったらたくさん出ます)
ここでは、このコンテナの特徴と、雑な実装の紹介をします。
(雑でいいならすぐ作れます。ただしslotの実装のやり方によっては配置newでメモリを塗るので、注意が必要です。筆者は飲み会でオールした日の午後に作った結果、生活リズムとヒープのcorruptionがdetected)

特徴

このコンテナの特徴は、キーの型が予めコンテナ側によって決められていること(たいてい大きめの符号なし整数)、要素の挿入/削除/アクセスが全てO(1)であることです。ゲームにおけるオブジェクト管理等、オブジェクトに対する弱い参照が必要な場合に最適です。

雑な実装紹介

格納する要素の配列(ここではページとする)の配列、つまり2次元配列に対し、その要素のIDを

ID = (ページを指すindex) × (各ページのサイズ) + (各ページ上での要素のindex)

とすることで、除算(ページがわかる)と剰余算(ページ上での位置がわかる)のみで各要素にアクセスできるというものです。しかもページのサイズを2のべき乗に制限すればビットシフトとビットマスクだけで済むため、さらに高速化可能です。コンテナ側では、現在フリーな場所のIDをqueue等に記録しておき、要素の追加ごとにIDを渡してpopします。もしフリーなIDがなければ、新しいページを確保し、そのページ上の要素のIDをpushします。要素を削除するときは、デストラクタを呼んだのち、そのIDをフリーなものとしてpushします。

しかし、これだけでは、一度削除した要素のIDを再利用した場合、直前に削除したIDと重複してしまい、なんかワイルドでいい感じになる可能性があります。そこで、このIDと、スロットと呼ばれる整数値を合わせた組をキーとします(64bit符号なし整数をキーとし、その半分の32bitをID、もう半分の32bitをスロットとする実装が一般的だと思います)。このスロットを、要素が削除され、IDが再利用されるごとに1加算してIDと組み合わせ、新しいキーとします。これにより、少なくともスロットの最大値までは、キーを再利用しても値は重複しません(64bit符号なし整数キーではスロットは32bitなので約21億回です)。正しくスロットのデータ型を決めればこの重複は現実的でないので、不正アクセスを防げるという仕組みです。

他の説明はこちら(Internet Archiveですが)等にあります。

Sparse set

こちらも(ほぼ)連想コンテナです。実装は超簡単です。そして例に違わず、Rustには標準で用意されています。C++での最強実装はこちらにあります。
感覚としてはバケットを用いるアルゴリズムに近いと思っています。Entity Component System(ECS)というゲーム設計パターンがあり、(筆者はここ1年ほど執心しています)その実装スタイルには主に2つの宗派があるのですが、その片方の根幹を成す非常に重要なものです。しかし、他の用途があまり思いつきません。適用可能な状況が限られ過ぎています。

It can be useful in some very narrow and specific cases,
namely when the universe of possible values is very large
but used very sparingly and the set is iterated often or cleared often.

(こちらより引用)

特徴

このコンテナの特徴は、キーが単純にvectorのindexであり、要素が入っていないキーを大量に生成したとしても、値は実際に存在する要素の数だけしか確保されないことです。そのため、全走査が高速です。(ただしキーは大量に確保されます。)
挿入/削除/アクセスは、それぞれvectorに対する同じ操作2回分程度の計算量で行えます。

雑な実装紹介

vectorを2つ用意します。
※ECSでは諸般の理由により3つ必要なため、3つ出てくる例が多いかもしれません。
1つ目はsparse(疎)なindex、2つ目はdense(密)な実際の要素をそれぞれ格納するものです。

std::vector<std::size_t> sparseVec;
std::vector<T> denseVec;

こんな感じです。以下、一瞬で終わる各操作の実装説明です。

挿入するとき

    // 注 : keyは消されたindexから再利用したり新しくsparseVecをリサイズしたりして作る
    // 再利用する場合は、SlotMapと同様の不正アクセス防止措置を施すなど
    sparseVec[key] = denseVec.size();
    denseVec.emplace_back(args...);

アクセスするとき

    denseVec[sparseVec[key]] = T();

削除するとき

    // 要素が整列されている必要がない場合はswap_remove(backとswapしてからpop_back)すればO(1)です
    denseVec.erase(denseVec.begin() + sparseVec[key]);

つまりsparseVecは(denseVecの)indexが入ってたり入ってなかったりするスカスカ(疎)なvectorで、denseVecは実際に確保されている値が連続して(密)格納されているvectorです。

使い道

筆者がこいつの主な使い道について話をしようとすると、ECSとはなんぞやという話になってしまいます。そのため、ECSの話をします。隙を見せたあなたが悪いです。

    // 定数
    constexpr std::size_t kNum = 10000;
    constexpr float kGravity = -9.8f;
    Registry registry;// ここに今のシーンで動くものを入れていく
    std::vector<Entity> cubes(kNum);// 各キューブのID(Entity)たち

    // キューブ作成
    for (std::size_t i = 0; i < kNum; ++i)
    {
        auto cube = registry.create();
        registry.add<RigidBody>(cube, RigidBodyType::Cube, 10.f, 5.f);// 辺の長さと質量的なやつ(適当)
        registry.add<Transform>(cube, 1.f * (i / 10) , 10.f, 1.f * (i % 10));// (x, y, z)的なやつ(適当2)
        cubes.emplace_back(cube);
    }

    // メインループ(終了条件は適当)
    while(!finished())
    {
        // これがSystemにあたる、これでRigidBodyを持つすべてのEntityに対して重力がはたらいたことになる
        registry.each<RigidBody>([kGravity](RigidBody& rigidBody)
            {
                // なんか物理エンジンに大体あるこういうフラグ
                if (rigidBody.isDynamic())
                {
                    rigidBody.addForce(0, rigidBody.mass * kGravity, 0);
                }
            });

        auto view = registry.view<RigidBody, Transform>();
        view.each([](RigidBody& rigidBody, Transform& transform)
            {
                // めんどくさくなった
                // なんかここでRigidBodyのforceとか解決してtransform.accに反映してください
            });

        // 描画!?めんどくさくて書けるわけありません!
    }

traitによる静的実装分岐

traitに関する話は、ググれば本当にいくらでも出てきます。ただし大体黒魔術です。筆者にはわけがわかりません。
ここではtraitを用いた、バックエンドとするAPIが変わる場合の簡単な設計パターンを紹介します。有名なやつです。お客様の中にマサカリをお持ちの方はいらっしゃいませんか。いたら危ないので降りてください。

    /**
     * @brief  Vulkan APIを表す型
     * @details APIとしてこの型を渡せばVulkan APIをバックエンドとして動作する
     */
    struct Vulkan 
    {};

    /**
     * @brief  DirectX12を表す型
     * @details APIとしてこの型を渡せばDirectX12をバックエンドとして動作する
     */
    struct DirectX12 
    {};

    /**
     * @brief  APIのtrait
     * @details この特殊化を用いてAPIごとの実装分岐を表現する
     * @tparam API バックエンドとして動作させたいAPI型
     */
    template<typename API>
    struct APITrait;

    template<>
    struct APITrait<Vulkan>
    {
        constexpr static auto APIName = "Vulkan";

        using Device                    = VulkanDevice;
        using WindowImpl                = VulkanWindow;
        using VRAMAllocatorImpl         = VulkanVRAMAllocator;
        // 略
    };

    template<>
    struct APITrait<DirectX12>
    {
        constexpr static auto APIName = "DirectX12";

        using Device                    = DirectX12Device;
        using WindowImpl                = DirectX12Window;
        using VRAMAllocatorImpl         = DirectX12VRAMAllocator;
        // 略
    };

で、実際にユーザが使用する型では、

    template<typename API>
    class Device
    {
        using APIDevice = APITrait<API>::Device;
        // 略、APIDeviceをメンバとして持ち、処理をいい感じにAPIDeviceにリダイレクトする
    }

のようにすれば、内部実装が使用するAPIに応じて展開されます。静的な処理であるため、当然ながらvtableによるコストがありません。インタフェースはテンプレートクラスなので、多分各メソッドはinlineになるはずです(理解が浅くてすいません)
また，APIごとの定数やヘルパ関数等もここに定義すればいい感じに共通化できます。代わりに、当然ですが実行中にバックエンドを変更することはできません。そんな状況を考えたくありませんが... まあ、いい感じにis-aを避けられているということで許してください。委譲にあるべき柔軟性がねえだろ
type_traitsの各種traitや、SFINAE、C++20であればconcept等を用いて、使用できるAPI型を制限したり、逆に特殊化で定める各クラスが適格であれば後からAPIを追加実装することも可能であり、柔軟性も高いです。

おわりに

以上です。おまけとして、C++20を最近になってちゃんと使い始めた結果、std::spanの存在を知らなかった筆者が揃えて脱いだ靴とともに浜辺に遺したゴミを置いておきます。(言い訳していいですか?std::spanはinitializer_listを普通にはとれないじゃないですか...)

初めて見た、という話があれば幸いです。ここに書いてある説明は雑すぎるため、各項目については是非ググっていただければと思います。
また、3D描画ライブラリやEntity Component System等について詳しい方、救いを.........
あと、C++に詳しい方、救いを........