c++0x書き始めた。データ構造書くたびに検索するのも効率悪いので覚える。
実態を持つ
データが小さいときはあり。しかし特にサイズが大きい配列を持つと良くない、局所変数にしづらい。
template<int SIZE> struct Array {
int d[SIZE];
Array() {
fill(d, d+SIZE, 0);
}
Array(const Array &y) {
for (int i=0; i<SIZE; i++) d[i] = y.d[i];
}
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]) {
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) {
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);
}
};
チェックリスト
- コンストラクタ
- Array() デフォルトコンストラクタ
- Array(const Array &) コピーコンストラクタ
- Array(Array &&) moveコンストラクタ。swapだけで実装し、O(1)であると嬉しい。
- デストラクタ
- void swap(Array &, Array &) はO(1)。
- Array&operator=(Array)はswapするだけ。引数のコピーはコンストラクタに任せる。
- sizeof (Array) は空間計算量O(1)であるべき。配列を直接持っていなければOK。配列はポインタ・std::vectorに。
