データ構造のコンストラクタの書き方

c++0x書き始めた。データ構造書くたびに検索するのも効率悪いので覚える。

実態を持つ

データが小さいときはあり。しかし特にサイズが大きい配列を持つと良くない、局所変数にしづらい。

template<int SIZE> struct Array {
    int d[SIZE];

    Array() { 
	// primitive型の場合はmemsetでもいい
	fill(d, d+SIZE, 0);
    }

    Array(const Array &y) {
	// primitive型の場合は memcpy でもいい
	for (int i=0; i<SIZE; i++) d[i] = y.d[i];
    }

    // yは変更可能。ポインタが無いので特に必要ない
    Array(Array &&y) {
	for (int i=0; i<SIZE; i++) {
	    d[i] = y.d[i];
	    y.d[i] = 0;
	}
    }

    // メモリを動的に確保してないので不要
    ~Array() {}

    Array& operator=(const Array &y) {
	for (int i=0; i<SIZE; i++) d[i] = y.d[i];
	return *this;
    }
};

ポインタで持つ NULLを許さない

大分stlに近くて良い。

template<int SIZE> struct Array {
    int *d;

    Array() : d(new int[SIZE]()) {}

    Array(const Array &y) : d(new int[SIZE]) {
	for (int i=0; i<SIZE; i++) d[i] = y.d[i];
    }

    Array(Array &&y) : d(new int[SIZE]) {
	// yはゴミが入ることになるが有効
	swap(*this, y);
    }

    ~Array() {
	delete[] d; 
	d = nullptr;
    }

    Array& operator=(Array y) {
	swap(*this, y);
	return *this;
    }

    friend void swap(Array &x, Array &y) {
	swap(x.d, y.d);
    }
};

ポインタで持つ NULLを許す

NULLでも問題ない場合や可変長なデータ構造なら良い。そうでない場合はメモリ確保を利用者に任せる。運用でカバー。
デフォルトコンストラクタと右辺値代入が効率良くなる可能性があるが計算量は変わらない。

template<int SIZE> struct Array {
    int *d;

    Array() : d(nullptr) {}

    Array(const Array &y) : d(nullptr) {
	if (y.d) {
	    reserve();
	    for (int i=0; i<SIZE; i++) d[i] = y.d[i];
	}
    }

    Array(Array &&y) : d(nullptr) {
	// yはNULLになる
	swap(*this, y);
    }

    ~Array() { clear(); }

    void clear() {
	if (d) {
	    delete[] d;
	    d = nullptr;
	}
    }

    void reserve() {
	clear();
	d = new int[SIZE]();
    }

    Array& operator=(Array y) {
	swap(*this, y);
	return *this;
    }

    friend void swap(Array &x, Array &y) {
	swap(x.d, y.d);
    }
};

チェックリスト

1. コンストラクタ
   1. Array() デフォルトコンストラクタ
   2. Array(const Array &) コピーコンストラクタ
   3. Array(Array &&) moveコンストラクタ。swapだけで実装し、O(1)であると嬉しい。
2. デストラクタ
3. void swap(Array &, Array &) はO(1)。
4. Array&operator=(Array)はswapするだけ。引数のコピーはコンストラクタに任せる。
5. sizeof (Array) は空間計算量O(1)であるべき。配列を直接持っていなければOK。配列はポインタ・std::vectorに。