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