本日の抽象化「遅延更新配列」

やあ子どもたち。夏も真っ盛りだ。楽しくやっているか。一緒に遊びに行ってることなんて実は何とも思ってなくて、それよりも付き合っているのかいないのか、そこの線引きを自分でするかしないかが大事らしいぞ。早い段階でそこをはっきりとさせる申し出をするかしないかで、ポイントが決まることがあるから気をつけろ。
さて、2年前の日記でも書いたように、配列の各要素を巡るループの中で、その配列に対して要素の[追加/削除]を行うことは未定義動作を招きやすく、絶対にやるべきではないアンチパターンだとおじさんは考えているよ。でも、実際にはそういう要求はしばしば現れたりする場合もあるね。具体的には粒子シミュレーションだとかゲームエンジン的なものかな。他にもありそうだけど、とにかく、インスタンスの生成削除要求が、既存インスタンスの状態に依存して不定期に発生するシチュエーション全般だ。そこで今回はアナザーソリューションとしておじさんがよく使っている方法を抽象化した概念を紹介するぞ。
まず、配列の各要素を巡るループの中で要素の追加要求が発生した場合は「追加待機リスト」にその要素を加えるということをする。また、同ループ中に削除したい要素が判明した場合は、その要素の削除フラグを立てておく。あとは、ループの外側で、追加待機リストにある要素を配列に追加し、また削除フラグの立っている要素を配列から削除するというものだ。こうすることで、配列要素の[追加/削除]要求と、実際の配列内容の更新とを、非同期化することができ、上述のアンチパターン実装を回避することができる。
以上の実装を今回はテンプレートクラスに抽象化したよ。それは以下のようになった。

// 遅延更新配列
template< class T >
// concept T::bool _tobe_deleted;
class DelayedUpdateArray
{
    // 要素の[追加/削除]要求の登録と、配列内容の更新とを、
    // 非同期に行うための仕掛け。
    // 1)要素の追加要求登録:Add()を使います。
    // 2)要素の削除要求登録:該当要素の_tobe_deletedメンバの値を
    //    trueにします。
    // 3)配列の更新:Update()を呼び出します。
    // ※配列が更新された時点で、
    // ・追加要求登録にある要素が配列末尾に追加されます。
    // ・追加要求登録はゼロ件にリセットされます。
    // ・削除要求登録された要素が配列から削除されます。
    // ・削除された要素のデストラクタが呼ばれます。
    // ※削除されなかった要素の静的並び順は保持されます。
    // ※Tはポインタ型であることを想定しています。
public:
    void Add( T t )
    {
        _adder.push_back( t );
    }
    void Clear( void )
    {
        _arr.clear();
        _adder.clear();
    }
    void Update( void )
    {
        // 本メソッドは、_arrの各要素を巡るループの外側で呼びます。
        auto& l = _arr;
        // add
        l.insert( l.end(), _adder.begin(), _adder.end() );
        _adder.clear();
        // remove
        auto it =
        stable_partition( l.begin(), l.end(),
                         [](T m){return !m->_tobe_deleted;} );
        for_each( it, l.end(), [](T m){ delete m; } );
        l.erase( it, l.end() );
    }
    const vector< T >& Arr(void) const { return _arr; }
private:
    vector< T > _arr, _adder;
};

使用例を見てみよう。
Kazuクラスは、本DelayedUpdateArrayの要素としての要件である_tobe_deletedメンバを持つ、整数値を記憶しておくための単純すぎるクラスだ。0から9までの数字をそれぞれ覚えたこいつのインスタンスを10個作り、その各要素を巡るループの中で、それが覚えている整数値が偶数の場合は削除要求登録し、奇数の場合は、同じ整数値を覚えるインスタンスを生成して追加要求登録をするというものだ。

// Kazuクラスの宣言
class Kazu
{
public:
    Kazu( const int val ):_val(val), _tobe_deleted(false)
    {}
    int _val;
    bool _tobe_deleted;
};
// 内容の確認用
void lc_check( const DelayedUpdateArray< Kazu* >& l )
{
    for( auto ikazu: l.Arr() )
        cout << ikazu->_val <<", ";
    cout << endl;
}
// テストプログラムメイン
int main(int argc, const char * argv[])
{   
    DelayedUpdateArray< Kazu* > kazu_dua;
    // 初期化
    {
        for( int i=0; i<10; ++i )
            // ●追加要求登録
            kazu_dua.Add( new Kazu( i ) );
        kazu_dua.Update();// ●更新
    }
    // 内容の確認
    lc_check( kazu_dua );
    // 偶数なら削除、奇数なら倍増
    for( auto ikazu: kazu_dua.Arr() )
    {
        // 各要素を巡るループ内にて
        if( ikazu->_val & 1 )
            // ●追加要求登録
            kazu_dua.Add( new Kazu( ikazu->_val ) );
        else
            // ●削除要求登録
            ikazu->_tobe_deleted = true;
    }// ikazu
    kazu_dua.Update();// ●更新
    // 内容の確認
    lc_check( kazu_dua );
    return 0;
}

結果は以下のようになったよ。

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 
1, 3, 5, 7, 9, 1, 3, 5, 7, 9, 

ちゃんと配列を巡るループの中で要素の[追加/削除]要求を出しながらも、配列の実際の更新をループの外側で安全に行えているね。
今回はstable_partitionさまさまって感じの内容だったかな。いやーSTLって本当にいいものですね!!
じゃ今日の話は終わりだよ。チャオ!

Dyson digital slim DC45MH

Dyson digital slim DC45MH