shared_ptrを用いた永続データ構造(配列)

プログラム

#include <boost/shared_ptr.hpp>
#include <stdio.h>
using namespace std;
using boost::shared_ptr;

template<class T>
struct PersistentArray {
	static const int kShiftSize = 4;
	int shift_, size_;
	shared_ptr<PersistentArray> data_[1 << kShiftSize];
	shared_ptr<T> leaf_;
	
	PersistentArray(): size_() {}
	PersistentArray(const long size): size_(size) {
		if (!size) return;
		for (shift_ = 0; (1 << (shift_ * kShiftSize)) < size; shift_++);
		if (shift_ == 0) {
			leaf_.reset(new T());
			return;
		}
		long child_size = 1 << ((shift_ - 1) * kShiftSize);
		for (long start = 0; start < size; start += child_size) {
			data_[start / child_size].reset(new PersistentArray(
			    (start + child_size < size) ? child_size : (size - start)));
		}
	}
	
	const T &Get(const long index) const {
		if (shift_ == 0) {
			assert(index == 0);
			return *leaf_;
		}
		int shift = (shift_ - 1) * kShiftSize;
		return data_[index >> shift]->Get(index & ~-(1 << shift));
	}
	
	void Set(const long index, const T &value) {
		if (shift_ == 0) {
			assert(index == 0);
			leaf_.reset(new T(value));
			return;
		}
		int shift = (shift_ - 1) * kShiftSize;
		PersistentArray *pa = new PersistentArray();
		*pa = *(data_[index >> shift]);
		data_[index >> shift].reset(pa);
		data_[index >> shift]->Set(index & ~-(1 << shift), value);
	}
};

int main() {
	PersistentArray<int> a(100000), b(100000), c(100000);
	a.Set(7000, 100);
	printf("% 6d % 6d % 6d\n", a.Get(7000), b.Get(7000), c.Get(7000));
	b.Set(7000, 200);
	printf("% 6d % 6d % 6d\n", a.Get(7000), b.Get(7000), c.Get(7000));
	c = b;
	printf("% 6d % 6d % 6d\n", a.Get(7000), b.Get(7000), c.Get(7000));
	b = a;
	printf("% 6d % 6d % 6d\n", a.Get(7000), b.Get(7000), c.Get(7000));
	a.Set(7000, 300);
	printf("% 6d % 6d % 6d\n", a.Get(7000), b.Get(7000), c.Get(7000));
	b.Set(7000, 400);
	printf("% 6d % 6d % 6d\n", a.Get(7000), b.Get(7000), c.Get(7000));
	for (int i = 0; i < 10000; i++) {
		a.Set(8000, 300);
		b.Set(8000, 400);
		assert(a.Get(8000) == 300);
		assert(b.Get(8000) == 400);
		a = b;
		assert(a.Get(8000) == 400);
		assert(b.Get(8000) == 400);
	}
}

出力結果

% time ./PersistentArray
   100      0      0
   100    200      0
   100    200    200
   100    100    200
   300    100    200
   300    400    200
./PersistentArray  0.36s user 0.17s system 55% cpu 0.966 total