イテレータ破壊の問題

これはC++アドベントカレンダー2014の8日目の記事です。

ゲームの修羅場10に投稿した記事で「プログラムの落ちるポイント」の中で
4つほどポイントを紹介したのですが、その中の一つがイテレータ破壊です。
これは、ややこしいので、本の方では軽く触れるだけで終わったのですが、
今回、あたらめて紹介したいと思います。

vectorやmapというコンテナを使う機会は多いのですが、
知らず知らずのうちに破壊されたイテレータを使っていることがあります。

まずイテレータ破壊について簡単に書きます。

void foo(){
 std::vector<int> a = {1, 2, 3, 4, 5};
 auto it1 = a.begin();
 a.push_back(6);
 std::cout << *it1 << std::endl;
}

こういうソースがイテレータ破壊の例となります。
vectorの場合、要素の数が変わるpush_backやpop_backを使った場合、
それまでに確保していたイテレータが破壊されます。

dequeやlistを使うとイテレータ破壊に関しては起きにくくなります。
dequeを使えば、push_back,pop_back,push_front,pop_frontではイテレータ破壊が起きません。
erase、insertは先頭、末尾に対するもの(上記の関数に置き換えられるもの)ならイテレータ破壊は起きませんが、
それ以外の部分に追加、削除するとイテレータ破壊を起こします。
listを使うと、どの関数を使ってもイテレータ破壊が起きません。
ただし、deque,list共に、自分自身の指す要素がerase等で消されるとイテレータ破壊になります。

mapやunordered_mapはvectorと同じくinset,eraseなどを使うとイテレータ破壊が起きます。

イテレータ破壊の何が厄介かというと、あくまで可能性にすぎない事です。
状況にも依りますが、問題なく動くことのほうが多いのです。
テストをすり抜けてある程度動いていると思っていたらいきなり落ちる、
しかもダングリングポインタを生成しているので原因追求も大変、と最悪のバグになります。

気をつけておけば対応できるか、というとそうではなく、
実際に起きていた現象をミニマムコードで書くとこういう例になります。

void Data::execute(int id){
// std::vector<int> list; メンバー変数としてこれが定義されている
 auto it = std::find(list.begin(), list.end(), id);
 if (it != list.end()){
   execute(this, *it);
   list.erase(it);
  }
}

listの値に応じて何らかのスクリプトを呼び出して使う、という例です。
このexecute関数にはthisが渡されています。
要するに、内部でこのlistにアクセスできる手段が提供されているわけです。
そして、execute関数内部でlistの要素を操作してしまうとイテレータ破壊になります。

上記のようなソースはイテレータ破壊のケースを想定して、
eraseを行う前に再度イテレータを確保し直す必要があります。

void Data::execute(int id){
// std::vector<int> list; メンバー変数としてこれが定義されている
 auto it = std::find(list.begin(), list.end(), id);
 if (it != list.end()){
   execute(this, *it);
   auto eit = std::find(list.begin(), list.end(), id);
   list.erase(eit);
  }
}

しかし、ループを使って全要素を舐めている最中ですと、先ほどのように再取得して…というわけにも行きません。

void Data::allexecute(){
  for(auto i : list)
   execute(this, i);
  }
}

こういう場合は、追加する場合は別のリストを作り、ループを抜けた後改めて追加します。
削除に関しては削除フラグを持たせて、ループを抜けた後に
削除フラグのついたもののみ削除するとよいでしょう。

とにかく込み入ってくると色々と厄介なので起こさないように気をつけるではちょっと厳しい物があります。

そこで、そういうイテレータ破壊を検出する方法を考えてみました。

アイデアとしてはこんなかんじです
・isdestoryという、shared_ptrを使った共有オブジェクトを作る。
・iteratorを派生してisdestoryを持たせる。
・vectorを派生して、iteratorを生成する時に内部に持っているisdestoryを渡す。
・push_backやpop_backを使用したら、古いisdestoryを破壊して新しいisdestoryを生成する。
　古いisdestoryは破壊済みの値になる。
・iteratorを使う時、isdestoryを見て壊れてないかチェックする。

そうやって出来たのがこれです。

guard_vector.cpp

#include <vector>
#include <boost/shared_ptr.hpp>

class destory_iterator{};

template<typename T>
class guard_iterator : public std::vector <typename T>::iterator {
  boost::shared_ptr<bool> isdestory;
  typedef typename std::vector < typename T >::iterator base;

public:
  void check() const {
    if (*isdestory) throw destory_iterator();
  }

  guard_iterator(typename std::vector < T >::iterator it, boost::shared_ptr<bool> isdestory) :
    std::vector < T >::iterator(it), isdestory(isdestory){}

  guard_iterator operator++(){
    return guard_iterator(base::operator++(), isdestory);
  }

  guard_iterator operator++(int){
    return guard_iterator(base::operator++(0), isdestory);
  }

  guard_iterator operator+(int n){
    return guard_iterator(base::operator+(n), isdestory);
  }

  guard_iterator operator-(int n){
    return guard_iterator(base::operator-(n), isdestory);
  }

  T &operator*() const{
    check();
    return base::operator *();
  }

  T* operator->() const {
    check();
    return base::operator ->();
  }
};


template<typename T>
class guard_vector : public std::vector < T > {
  mutable boost::shared_ptr<bool> isdestory;
  typedef std::vector < T > base;

  void destory(){
    if (isdestory.use_count() != 1){
      if (isdestory) *isdestory = true;
      isdestory = boost::shared_ptr<bool>(new bool(false));
    }
  }
  boost::shared_ptr<bool> get_destory(){
    if (!isdestory) isdestory = boost::shared_ptr<bool>(new bool(false));
    return isdestory;
  }

public:
  typedef guard_iterator<T> iterator;

  iterator begin(){
    return iterator(base::begin(), isdestory);
  }

  iterator end(){
    return iterator(base::end(), get_destory());
  }

  guard_vector<T>(){
  }

  void push_back(value_type&& _Val){
    destory();
    base::push_back(_Val);
  }

  void pop_back(){
    destory();
    base::pop_back();
  }

  iterator erase(iterator it){
    it.check();
    destory();
    return iterator(base::erase(it), get_destory());
  }

  iterator insert(iterator it, const T &t){
    it.check();
    destory();
    return iterator(base::insert(it, t), get_destory());
  }

};

int main()
{
  typedef guard_vector<int> IntArray;
  IntArray a;
  a.push_back(1);
  a.push_back(2);
  a.push_back(3);

  auto it1 = a.begin();
  a.push_back(100);
  it1++;
  *it1 = -1; // ここでiterator_breakの例外が投げられる

  return 0;
}

ってことで、作りかけなのですが、このへんまで作ってて
・こんなの作って嬉しい人いるのか？
・すでに似たものがあるんじゃないか
・vectorとか派生しちゃっていいの？
・イテレータのインクリメントだけでは直ちに駄目とはいえないけどこの時点でiterator_break投げた方がいい？
・ゲームで忙しい
とか色々疑問点や問題点が出てきたので、一旦識者のコメントをもらったところで
また作り進めようかと思っています。