multi_index_container - 要素の更新

multi_index_container は各インデックスごとに std::listまたはstd::set、std::multisetとよく似たインターフェースを介して操作が行えるが、大きな違いのある部分の1つが要素の更新方法だ。
STLの場合
まずは std::listと std::set との間で要素の更新方法の違いについて考えてみる。
std::listの方は話は単純だ。イテレータitに対して *itを直接変更すればよい。
一方、std::set も *it の直接変更ができるが、場合によってはコンテナの整合性を破壊することがありえる。例えば以下のコードはコンパイル可能だが、要素の順序関係は当然破壊される。
class A {
  int id;
  std::string label;
public:
  A(int id_, const std::string& label_) : id(id_), label(label_) {}
  bool operator<(const A& a) const { return id < a.id; }
};

std::set<A> s = boost::assign::list_of<A>(3,"3")(1,"1")(2,"2");
s.begin()->id = 5;          //id=1が先頭のはずだが、無理やりid=5を代入
// この時点で idが 5,2,3 の順でsetに入ってしまっている。本来は2,3,5でなくてはならない。
つまり set の *it は要素の参照を返すが、決してその要素のキーの部分を書き換えてはならないという掟がある。
これは気をつけないと、はまりそうな罠だと思う。

replace()
さて肝心の multi_index_containerだが、イテレータitの *it はconst参照を返すようになっていて *it を書き換え不可能になっている。理由は std::setと同様に、勝手にキーの部分を書き換えられたらコンテナの順序関係が破壊されるからだ。
代わりに 要素の書き換えのために replace() というメンバ関数が用意されている。
typedef multi_index_container<
  A,
  indexed_by<
    sequenced<>,
    ordered_unique<member<A, int, &A::id> >
  >
> C;
typedef C::nth_index<0>::type Index0;
typedef C::nth_index<1>::type Index1;

C c = boost::assign::list_of<A>(3,"3")(1,"1")(2,"2");

Index1& index1 = c.get<1>();              // index1を取得
Index1::iterator it = index1.begin();     // index1の先頭イテレータ
A a = *it;                                // it->id = 5 はコンパイルエラーなので replace()を呼び出す
a.id = 5;
index1.replace(it, a);
// この時点で index0は idが 3,5,2の順、index1は 2,3,5の順となり整合がとれている。
std::setに比べて安全な仕様でいいと思う。なお、要素の順序関係が変わってしまうような場合もイテレータは無効にならない。要素への参照も依然として有効なままだ。
また、replace()の時間的コストだが、すべてインデックスでの位置関係が変わらない場合は、定数時間。それ以外は 位置関係が変わるインデックスごとに O(logN)の時間がかかるようで、時間複雑性の面では無駄がない。

modify()
しかし、replace()ではクラスの一部のメンバ変数を書き換えるだけでもクラス全体をコピーするので、コピーの負荷が高いクラスでは遅くなることもありえる。std::setが若干危険な仕様になっているのもこのためだろう。
ってことで modify()というメンバ関数も用意されている。こちらは以下のように要素の一部を書き換えるための関数オブジェクトを作成する必要がある。
// A::id を書き換えるための functor
struct ChangeID {
    ChangeID(int new_id) : id(new_id) {}
    void operator()(A& a) {
        a.id = id;
    }
private:
    int id;
};

C c = boost::assign::list_of<A>(3,"3")(1,"1")(2,"2");

Index1& index1 = c.get<1>();
index1.modify(index1.begin(), ChangeID(5));
modifyバージョンの方は 関数オブジェクトに A の参照を渡してくれるので replaceバージョンに比べて効率的だ。

modify()の欠点
じゃあ、いつでも modifyでいいじゃんって気もするのだが、やはり欠点はある。例えば以下のケースを考える。
C c = boost::assign::list_of<A>(3,"3")(1,"1")(2,"2");

Index1& index1 = c.get<1>();
assert(index1.rbegin()->id == 3);                   // 最後の要素はid=3
index1.modify(index1.begin(), ChangeID(3));         // id=3は最後の要素と重複している!
A::id を 1->3 に変更しようとしているが、id=3は 最後の要素と重複している。インデックス1は A::idをキーとする重複を許さないインデックスなので、これは非常にまずい。
このような場合、modify() は問答無用で it を指す要素を削除し、返り値として false を返すようになっている。
キーの重複が判明した時点ですでに関数オブジェクトによってAのどのメンバ変数が書き換えられたが知りようもないので、たしかにもう要素を削除するしか手はないような気がする。

一方の replace を使った以下のバージョンを見てみる。
C c = boost::assign::list_of<A>(3,"3")(1,"1")(2,"2");

Index1& index1 = c.get<1>();
index1.replace(index1.begin(), A(3, it->label));         // id=3はすでに登録されている!
当然A::id の重複は許されないので replace() が false を返すところまでは modify() と同様だが、modify()と異なり、replace()では元のコンテナに何の変更も及ぼさない。これは大きなメリットになるときもあるだろう。ケースバイケースで modify/replaceを使い分けるのが良さそうだ。

modify_key()
あと、個人的にあまり有効な使い方が思い浮かばないのだが、modify_key()という modify()の別バージョンのようなものがある。 modify()は関数オブジェクトに要素の参照を渡してくれたが、modify_key()は 抽出したキーの参照を渡してくれる。
// intを書き換える
struct ChangeInt {
    ChangeInt(int i_) : i(i_) {}
    void operator()(int& n) {
        n = i;
    }
private:
    int i;
};

C c = boost::assign::list_of<A>(3,"3")(1,"1")(2,"2");

Index1& index1 = c.get<1>();
index1.modify_key(index1.begin(), ChangeInt(5));
キーエクストラクタに const_mem_fun を使ったときのようにキーが直接データメンバでない場合は使えない。

<< Game Programming Gems 3 Site Top GT4 >>

Comments