Open Data Structures 修正版について

情報数理科学IIではPat Morin: Open Data Structures, http://opendatastructures.org. C++ edition を教科書として使っているが，バグ等を修正したものを以下に置いて使う．

バグの多くはPat Morinさんのgithubに報告して修正されているが，現在も残っている違いは，以下の内容になる．オリジナル版の array.h では，

	array<T>& operator=(array<T> &b) {
		if (a != NULL) delete[] a;
		a = b.a;
		b.a = NULL;
		length = b.length;
		return *this;
	}

のように，代入演算子「=」を定義している．これは，

array の代入を要素数によらずに定数時間でおこないたい
しかし，ポインタ a をコピーして代入すると，確保された領域を delete するタイミングがなく，回収されないメモリ領域ができてしまう(memory leak)．

ことが原因と考えられる．2番目の問題があるので，C++のstd::vector の代入では新たに領域を確保してコピーするという要素数に比例して時間のかかる重い操作をおこなっている．

オリジナル版では，「array<T> 型のa, b の間で，

  a = b;

を実行すると，bの内容を破壊する」代入の意味を変更した上で使っている．

C++11 以降で導入された shared_ptr を用いれば，array の代入を要素数によらずに定数時間でおこなうように実現することもできるし，自己参照をおこなう場合を除けばメモリ領域の回収も可能ではあるが，本講義で使う修正版ではC++で一般的に用いられている

  a.swap(b);

のように，「a と b の中身を交換する」操作を基本的に使う方法を用いた．これに関しては pull request を送ってはいるが，本家では採用されていない　．