今回は簡単な例題として、以前作成した 連結リスト をテンプレートを使って書き直してみましょう。名前は List とします。なお、C++の標準ライブラリには <list> や <forward_list> が用意されているので、私たちが List クラスを作成する必要はありませんが、テンプレートのお勉強ということで、あえてプログラムを作ってみましょう。
最初に、セル Cell と連結リスト List のクラステンプレートを定義します。次のリストを見てください。
リスト : セルのクラステンプレート template<class T> class List; template<class T> ostream& operator<<(ostream&, const List<T>&); // セル template<class T> class Cell { T item; Cell* next; public: explicit Cell(Cell* cp) : item(T()), next(cp) {} Cell(const T& x, Cell* cp) : item(x), next(cp) {} Cell(T&& x, Cell* cp) : item(move(x)), next(cp) {} T& car() { return item; } Cell* cdr() { return next; } void set_car(const T& x) { item = x; } void set_car(T&& x) { item = move(x); } void set_cdr(Cell* cp) { next = cp; } };
Vector クラスと同様に、List と operator<< がテンプレートであることを宣言します。セル Cell はデータ型 T のデータをメンバ変数 item に格納します。1 引数のコンストラクタはヘッダセルを生成するために使います。2 引数のコンストラクタは、引数 x の型を T に変更して、右辺値参照を受け取るコンストラクタを追加します。car の返り値は T の参照 (T&) とし、set_car の引数 x の型も T に変更します。また、右辺値参照を受け取る set_car も追加します。
リスト : 連結リストのクラステンプレート template<class T> class List { Cell<T>* top; // メンバ変数 static Cell<T>* nth_cell(Cell<T>*, int); // n 番目のセルを求める static Cell<T>* copy_cell(Cell<T>*); // リストのコピー public: List() : top(new Cell<T>(0)) { } ~List() { clear(); delete top; } List(const List&); // コピーコンストラクタ List& operator=(const List&); // 代入演算子 List(List&&); // ムーブコンストラクタ List& operator=(List&&); // ムーブ代入演算子 // メンバ関数 T& nth(int); void set(int, const T&); void set(int, T&&); void insert(int, const T&); void insert(int, T&&); void remove(int); int length(); void clear(); bool empty(); // 演算子の多重定義 friend ostream& operator<< <T> (ostream&, const List&); // // イテレータは省略 // };
List のテンプレート仮引数は T なので、セルのデータ型は Cell<T> になります。メンバ変数 top のデータ型は Cell<T>* になります。それから、ムーブコンストラクタとムーブ代入演算子を定義して、引数に右辺値参照を受け取る set と insert を追加します。あとはデータ型を int から T に変更するだけです。
次はメンバ関数を定義します。静的なメンバ関数は次のようになります。
リスト : 静的メンバ関数の定義 // n 番目のセルを求める template<class T> Cell<T>* List<T>::nth_cell(Cell<T>* cp, int n) { int i = -1; while (cp) { if (n == i) break; cp = cp->cdr(); i++; } return cp; } // リストのコピー template<class T> Cell<T>* List<T>::copy_cell(Cell<T>* cp) { return !cp ? cp : new Cell<T>(cp->car(), copy_cell(cp->cdr())); }
関数定義の先頭に template<class T> を付けます。クラス名は List<T> になります。そして、Cell を Cell<T> に、格納するデータの型を int から T に変更するだけです。コンストラクタ Cell を呼び出すときは、Cell の後ろに <T> を付けてください。
右辺値参照を受け取る set と insert は次のようになります。
リスト : 右辺値参照を受け取る set と insert template<class T> void List<T>::insert(int n, T&& x) { Cell<T>* cp = nth_cell(top, n - 1); if (!cp) throw out_of_range("List::insert out of range"); cp->set_cdr(new Cell<T>(forward<T>(x), cp->cdr())); } template<class T> void List<T>::set(int n, T&& x) { Cell<T>* cp = nth_cell(top, n); if (!cp) throw out_of_range("List::set out of range"); cp->set_car(forward<T>(x)); }
テンプレート関数で引数の右辺値参照を他のテンプレート関数に渡す場合、引数をそのまま渡すと右辺値参照型の関数ではなく、参照型の関数が呼び出されます。具体的には、コンストラクタは Cell(T&&, Cell*) ではなく Cell(const T&, Cell*) が呼び出され、set_car は set_car(const T&) が呼び出されます。
テンプレート関数の引数 x を右辺値参照型として他の関数に渡すには、テンプレート関数 forward を使います。forward<T>(x) とすると、Cell(T&&, Cell*) や set_car(T&&) が呼び出されます。参考 URL によると、この機能を「Perfect Forwarding」と呼ぶそうです。詳しい説明は参考 URL をお読みください。
あとのメンバ関数の変更は簡単なので説明は割愛します。詳細は プログラムリスト をお読みください。
次はイテレータを定義します。
リスト : イテレータ class Iterator : public iterator<forward_iterator_tag, T> { Cell<T>* idx; public: Iterator(Cell<T>* cp) : idx(cp) {} // 間接参照 T& operator*() { return idx->car(); } T* operator->() { return &(idx->car()); } // ++ 演算子, -- 演算子は無し Iterator& operator++() { if (idx) idx = idx->cdr(); return *this; } Iterator operator++(int n) { Iterator iter(idx); if (idx) idx = idx->cdr(); return iter; } // 比較演算子 bool operator==(const Iterator& iter) const { return idx == iter.idx; } bool operator!=(const Iterator& iter) const { return idx != iter.idx; } }; Iterator begin() { return Iterator(top->cdr()); } Iterator end() { return Iterator(0); }
今回は単方向連結リストなので、イテレータの種類は前方向イテレータになります。Iterator は iterator<forward_iterator_tag, T> を継承します。多重定義する演算子は *, ->, ++, ==, != になります。-- 演算子やイテレータを移動する +=, -=. +, - 演算子は定義しません。プログラムは簡単なので説明は割愛します。詳細はプログラムリストをお読みください。
それでは簡単なテストを行ってみましょう。
リスト : 簡単なテスト int main() { List<int> a; for (int i = 0; i < 8; i++) a.insert(i, i); cout << a << endl; List<int> b; for (int i = 0; i < 8; i++) b.insert(0, i); cout << b << endl; { List<int> c = a; a = b; b = c; cout << a << endl; cout << b << endl; } { List<int> c = move(a); a = move(b); b = move(c); cout << a << endl; cout << b << endl; } for (auto iter = a.begin(); iter != a.end(); ++iter) cout << *iter << " "; cout << endl; auto iter = b.begin(); while (iter != b.end()) cout << *iter++ << " "; cout << endl; for (auto x : a) cout << x << " "; cout << endl; for_each(b.begin(), b.end(), [](int x){ cout << x << " "; }); cout << endl; List<pair<string,int>> c; c.insert(0, pair<string,int>{"foo", 1}); c.insert(0, pair<string,int>{"bar", 2}); c.insert(0, pair<string,int>{"baz", 3}); c.insert(0, pair<string,int>{"oops", 4}); for (auto iter = c.begin(); iter != c.end(); ++iter) cout << iter->first << "," << iter->second << endl; pair<string,int> p = {"OOPS", 40}; c.set(0, p); c.set(1, pair<string,int>{"BAZ",30}); for (auto iter = c.begin(); iter != c.end(); ++iter) cout << iter->first << "," << iter->second << endl; }
$ clang++ list.cpp $ ./a.out (0 1 2 3 4 5 6 7) (7 6 5 4 3 2 1 0) (7 6 5 4 3 2 1 0) (0 1 2 3 4 5 6 7) (0 1 2 3 4 5 6 7) (7 6 5 4 3 2 1 0) 0 1 2 3 4 5 6 7 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 7 6 5 4 3 2 1 0 oops,4 baz,3 bar,2 foo,1
コピーコンストラクタ、代入演算子、ムーブコンストラクタ、ムーブ代入演算子は正常に動作しています。STL の仕様に合わせてイテレータを実装すると、範囲 for 文や、for_each など algorithm の関数も利用することができます。また、List に pair<string, int> を格納することもできます。演算子 -> で pair のメンバ変数 first, second を選択することができます。興味のある方はいろいろ試してみてください。
// // list.cpp : 連結リスト (テンプレート版) // // Copyright (C) 2015-2023 Makoto Hiroi // #include <iostream> #include <stdexcept> #include <iterator> #include <algorithm> using namespace std; // 宣言 template<class T> class List; template<class T> ostream& operator<<( ostream&, const List<T>&); // セル template<class T> class Cell { T item; Cell* next; public: explicit Cell(Cell* cp) : item(T()), next(cp) {} Cell(const T& x, Cell* cp) : item(x), next(cp) {} Cell(T&& x, Cell* cp) : item(move(x)), next(cp) {} T& car() { return item; } Cell* cdr() { return next; } void set_car(const T& x) { item = x; } void set_car(T&& x) { item = move(x); } void set_cdr(Cell* cp) { next = cp; } }; template<class T> class List { Cell<T>* top; // メンバ変数 static Cell<T>* nth_cell(Cell<T>*, int); // n 番目のセルを求める static Cell<T>* copy_cell(Cell<T>*); // リストのコピー public: List() : top(new Cell<T>(0)) { } ~List() { clear(); delete top; } List(const List&); // コピーコンストラクタ List& operator=(const List&); // 代入演算子 List(List&&); // ムーブコンストラクタ List& operator=(List&&); // ムーブ代入演算子 // メンバ関数 T& nth(int); void set(int, const T&); void set(int, T&&); void insert(int, const T&); void insert(int, T&&); void remove(int); int length(); void clear(); bool empty(); // 演算子の多重定義 friend ostream& operator<< <T> (ostream&, const List&); // イテレータ class Iterator : public iterator<forward_iterator_tag, T> { Cell<T>* idx; public: Iterator(Cell<T>* cp) : idx(cp) {} // 間接参照 T& operator*() { return idx->car(); } T* operator->() { return &(idx->car()); } // ++ 演算子, -- 演算子は無し Iterator& operator++() { if (idx) idx = idx->cdr(); return *this; } Iterator operator++(int n) { Iterator iter(idx); if (idx) idx = idx->cdr(); return iter; } // 比較演算子 bool operator==(const Iterator& iter) const { return idx == iter.idx; } bool operator!=(const Iterator& iter) const { return idx != iter.idx; } }; Iterator begin() { return Iterator(top->cdr()); } Iterator end() { return Iterator(0); } }; // 作業用の静的メンバ関数 template<class T> Cell<T>* List<T>::nth_cell(Cell<T>* cp, int n) { int i = -1; while (cp) { if (n == i) break; cp = cp->cdr(); i++; } return cp; } // リストのコピー template<class T> Cell<T>* List<T>::copy_cell(Cell<T>* cp) { return !cp ? cp : new Cell<T>(cp->car(), copy_cell(cp->cdr())); } // コピーコンストラクタ template<class T> List<T>::List(const List<T>& ls) : top(new Cell<T>(T(), 0)) { top->set_cdr(copy_cell(ls.top->cdr())); } // 代入演算子 template<class T> List<T>& List<T>::operator=(const List<T>& ls) { if (this != &ls) { clear(); top->set_cdr(copy_cell(ls.top->cdr())); } return *this; } // ムーブコンストラクタ template<class T> List<T>::List(List<T>&& ls) : top(ls.top) { ls.top = 0; } // ムーブ代入演算子 template<class T> List<T>& List<T>::operator=(List<T>&& ls) { if (this != &ls) { clear(); delete top; top = ls.top; ls.top = 0; } return *this; } // メンバ関数 template<class T> T& List<T>::nth(int n) { Cell<T>* cp = nth_cell(top, n); if (cp) return cp->car(); throw out_of_range("List::nth out of range"); } template<class T> void List<T>::insert(int n, const T& x) { Cell<T>* cp = nth_cell(top, n - 1); if (!cp) throw out_of_range("List::insert out of range"); cp->set_cdr(new Cell<T>(x, cp->cdr())); } template<class T> void List<T>::insert(int n, T&& x) { Cell<T>* cp = nth_cell(top, n - 1); if (!cp) throw out_of_range("List::insert out of range"); cp->set_cdr(new Cell<T>(forward<T>(x), cp->cdr())); } template<class T> void List<T>::set(int n, const T& x) { Cell<T>* cp = nth_cell(top, n); if (!cp) throw out_of_range("List::set out of range"); cp->set_car(x); } template<class T> void List<T>::set(int n, T&& x) { Cell<T>* cp = nth_cell(top, n); if (!cp) throw out_of_range("List::set out of range"); cp->set_car(forward<T>(x)); } template<class T> void List<T>::remove(int n) { Cell<T>* cp = nth_cell(top, n - 1); if (!cp || !cp->cdr()) throw out_of_range("List::remove out of range"); Cell<T>* cp1 = cp->cdr(); cp->set_cdr(cp1->cdr()); delete cp1; } template<class T> int List<T>::length() { int n = 0; Cell<T>* cp = top->cdr(); while (cp) { n++; cp = cp->cdr(); } return n; } template<class T> void List<T>::clear() { if (top) { Cell<T>* cp = top->cdr(); while (cp) { Cell<T> *tmp = cp->cdr(); delete cp; cp = tmp; } top->set_cdr(0); } } template<class T> bool List<T>::empty() { return !top->cdr(); } template<class T> ostream& operator<<(ostream& output, const List<T>& xs) { Cell<T>* cp = xs.top->cdr(); output << "("; while (cp) { output << cp->car(); if (cp->cdr()) output << " "; cp = cp->cdr(); } output << ")"; return output; } // 簡単なテスト int main() { List<int> a; for (int i = 0; i < 8; i++) a.insert(i, i); cout << a << endl; List<int> b; for (int i = 0; i < 8; i++) b.insert(0, i); cout << b << endl; { List<int> c = a; a = b; b = c; cout << a << endl; cout << b << endl; } { List<int> c = move(a); a = move(b); b = move(c); cout << a << endl; cout << b << endl; } for (auto iter = a.begin(); iter != a.end(); ++iter) cout << *iter << " "; cout << endl; auto iter = b.begin(); while (iter != b.end()) cout << *iter++ << " "; cout << endl; for (auto x : a) cout << x << " "; cout << endl; for_each(b.begin(), b.end(), [](int x){ cout << x << " "; }); cout << endl; List<pair<string,int>> c; c.insert(0, pair<string,int>{"foo", 1}); c.insert(0, pair<string,int>{"bar", 2}); c.insert(0, pair<string,int>{"baz", 3}); c.insert(0, pair<string,int>{"oops", 4}); for (auto iter = c.begin(); iter != c.end(); ++iter) cout << iter->first << "," << iter->second << endl; }
今回は簡単な例題として、以前作成した 二分探索木 をテンプレートを使って書き直してみましょう。クラス名は Tree とします。なお、C++の標準ライブラリには <map> や <set> などの平衡二分木が用意されているので、私たちが単純な二分木を作る必要はありませんが、テンプレートのお勉強ということで、あえてプログラムを作ってみましょう。
最初は、節 Node と 二分木 Tree のクラステンプレートを定義します。
リスト : 節の定義 template<class T> class Node { T item; Node* left; Node* right; public: explicit Node(const T& x) : item(x), left(0), right(0) { } explicit Node(T&& x) : item(move(x)), left(0), right(0) { } T& get_item() { return item; } Node* get_left() const { return left; } Node* get_right() const { return right; } void put_item(const T& x) { item = x; } void put_item(T&& x) { item = move(x); } void put_left(Node* l) { left = l; } void put_right(Node* r) { right = r; } };
コンストラクタは引数に const T& を受け取るものと右辺値参照 (T&&) を受け取るものの 2 つを用意します。二分探索木の場合、要素 item の値を書き換えると、二分探索木の条件を満たさなくなる危険性がありますが、move を使いたい場合があるので、返り値は T& とします。あとはデータ型を int から T に変更するだけです。
リスト : 二分探索木の定義 template<class T> class Tree { Node<T>* root; public: Tree() : root(0) { } ~Tree() { destroy_node(root); } // コピーコンストラクタ Tree(const Tree& tree) { root = copy_node(tree.root); } // 代入演算子 Tree& operator=(const Tree& tree) { if (this != &tree) { destroy_node(root); root = copy_node(tree.root); } return *this; } // ムーブコンストラクタ Tree(Tree&& tree) : root(tree.root) { tree.root = 0; } // ムーブ代入演算子 Tree& operator=(Tree&& tree) { if (this != &tree) { destroy_node(root); root = tree.root; tree.root = 0; } return *this; } // メンバ関数 bool empty() const { return !root; } bool search(const T& x) const { return search_node(x, root); } const T& min() const { if (!root) throw std::runtime_error("Tree::min empty tree"); return search_min(root); } const T& max() const { if (!root) throw std::runtime_error("Tree::max empty tree"); return search_max(root); } void insert(const T& x) { root = insert_node(x, root); } void insert(T&& x) { root = insert_node(forward<T>(x), root); } void remove(const T& x) { root = delete_node(x, root); } void remove_min() { if (root) root = delete_min(root); } void remove_max() { if (root) root = delete_max(root); } // // イテレータ (省略) // };
Tree のテンプレート仮引数は T なので、節のデータ型は Node<T> になります。メンバ変数 root のデータ型は Node<T>* になります。あとは、ムーブコンストラクタとムーブ代入演算子を定義して、データ型を int から T に変更します。このとき、要素の値 (item) を返すメンバ関数 max と min は、返り値の型を const T& とすることに注意してください。
それから、引数に右辺値参照を受け取るメンバ関数 insert を追加します。これに対応するため、作業用関数 insert_node に右辺値参照を受け取る関数を追加します。insert_node を呼び出すとき、引数 x に forward を適用することをお忘れなく。
次は insert_node に右辺値参照を受け取る関数を追加します。
リスト : データの挿入 (右辺値参照) template<class T> Node<T>* insert_node(T&& x, Node<T>* node) { if (!node) return new Node<T>(forward<T>(x)); if (x < node->get_item()) node->put_left(insert_node(forward<T>(x), node->get_left())); else if (x > node->get_item()) node->put_right(insert_node(forward<T>(x), node->get_right())); return node; }
引数 x は右辺値参照なので、Node のコンストラクタを呼び出すときと、insert_node を再帰呼び出しするときは、引数 x に forward を適用してください。これで、引数 x の所有権を新しい節に移動することができます。
もう一つ、データを削除する作業用関数 delete_node を修正します。
リスト : データの削除 template<class T> Node<T>* delete_node(const T& x, Node<T>* node) { if (!node) return node; if (x == node->get_item()) { if (!node->get_left()) { Node<T>* x = node->get_right(); delete node; return x; } if (!node->get_right()) { Node<T>* x = node->get_left(); delete node; return x; } node->put_item(move(search_min(node->get_right()))); node->put_right(delete_min(node->get_right())); } else if (x < node->get_item()) node->put_left(delete_node(x, node->get_left())); else node->put_right(delete_node(x, node->get_right())); return node; }
右部分木から最小値を探して、それを item にセットします。このとき、search_min の返り値に move を適用して、ムーブ操作が定義されていれば、それを行うようにします。作業用関数 search_min と search_max の返り値の型は const T& ではなく、T& とすることに注意してください。
次はイテレータを作ります。
リスト : イテレータ class Iterator : public iterator<forward_iterator_tag, T> { vector<Node<T>*> stack; // 次の node へ進める void next_node(Node<T>* node) { while (node) { stack.push_back(node); node = node->get_left(); } } public: Iterator(Tree* tree, bool end) { if (!end) next_node(tree->root); } // 間接参照 const T& operator*() const { return stack.back()->get_item(); } const T* operator->() const { return &(stack.back()->get_item()); } // 前置の ++ 演算子 Iterator& operator++() { Node<T>* node = stack.back(); stack.pop_back(); next_node(node->get_right()); return *this; } // 後置の ++ 演算子 Iterator operator++(int n) { Iterator iter(*this); Node<T>* node = stack.back(); stack.pop_back(); next_node(node->get_right()); return iter; } // 比較演算子 bool operator==(const Iterator& iter) { return stack == iter.stack; } bool operator!=(const Iterator& iter) { return stack != iter.stack; } }; Iterator begin() { return Iterator(this, false); } Iterator end() { return Iterator(this, true); }
イテレータの基本的な操作は以前作成した IntVec と同じです。ただし、たどってきた節は vector<Node<T>*> stack に格納します。この場合、単純な配列よりも vector を使ったほうが簡単です。
ところで、ムーブコンストラクタとムーブ代入演算子は、宣言されていないとコンパイラが自動的に生成してくれます。ただし、デストラクタ、コピーコンストラクタ、代入演算子のどれか一つでも宣言されていると、自動生成されないことに注意してください。
デフォルトの動作は非静的メンバ変数をムーブすることなので、Iterator のメンバ変数 stack を vector で定義すると、ムーブ操作にも対応できるのでとても便利です。
それから、間接参照の演算子 * と -> の返り値を const で修飾します。これで節の値 (item) を書き換えることができなくなります。あとのプログラムは簡単なので説明は割愛します。詳細は プログラムリスト をお読みください。
それでは簡単なテストを行ってみましょう。
リスト : 二分探索木のテスト int main() { vector<int> a = {5, 7, 3, 4, 2, 1, 8, 6, 9}; vector<int> b = {15, 17, 13, 14, 12, 11, 18, 16, 19}; Tree<int> tree_a; Tree<int> tree_b; for (int x : a) tree_a.insert(x); for (int x : tree_a) cout << x << " "; cout << endl; for (int x : b) tree_b.insert(x); for (int x : tree_b) cout << x << " "; cout << endl; { Tree<int> tree_c = tree_a; tree_a = tree_b; tree_b = tree_c; for (int x : tree_a) cout << x << " "; cout << endl; for (int x : tree_b) cout << x << " "; cout << endl; } { Tree<int> tree_c = move(tree_a); tree_a = move(tree_b); tree_b = move(tree_c); for (int x : tree_a) cout << x << " "; cout << endl; for (int x : tree_b) cout << x << " "; cout << endl; } for (int x = 0; x <= 10; x++) cout << tree_a.search(x) << " "; cout << endl; for (auto iter = tree_a.begin(); iter != tree_a.end(); ++iter) cout << *iter << " "; cout << endl; auto iter = tree_b.begin(); while (iter != tree_b.end()) cout << *iter++ << " "; cout << endl; for_each(tree_a.begin(), tree_a.end(), [](int x){ cout << x << " "; }); cout << endl; for (int i = 0; i < 9; i++) { tree_a.remove(a[i]); for_each(tree_a.begin(), tree_a.end(), [](int x){ cout << x << " "; }); cout << endl; } while (!tree_b.empty()) { cout << tree_b.min() << endl; cout << tree_b.max() << endl; tree_b.remove_min(); tree_b.remove_max(); for (int x : tree_b) cout << x << " "; cout << endl; } Tree<string> tree_c; tree_c.insert("foo"); tree_c.insert("bar"); tree_c.insert("baz"); tree_c.insert("oops"); for (auto& x : tree_c) cout << x << " "; cout << endl; tree_c.remove("foo"); for (auto& x : tree_c) cout << x << " "; cout << endl; tree_c.remove("bar"); for (auto& x : tree_c) cout << x << " "; cout << endl; tree_c.remove("oops"); for (auto& x : tree_c) cout << x << " "; cout << endl; tree_c.remove("baz"); for (auto& x : tree_c) cout << x << " "; cout << endl; }
$ clang++ tree.cpp $ ./a.out 1 2 3 4 5 6 7 8 9 11 12 13 14 15 16 17 18 19 11 12 13 14 15 16 17 18 19 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 11 12 13 14 15 16 17 18 19 0 1 1 1 1 1 1 1 1 1 0 1 2 3 4 5 6 7 8 9 11 12 13 14 15 16 17 18 19 1 2 3 4 5 6 7 8 9 1 2 3 4 6 7 8 9 1 2 3 4 6 8 9 1 2 4 6 8 9 1 2 6 8 9 1 6 8 9 6 8 9 6 9 9 11 19 12 13 14 15 16 17 18 12 18 13 14 15 16 17 13 17 14 15 16 14 16 15 15 15 bar baz foo oops bar baz oops baz oops baz
コピーコンストラクタ、代入演算子、ムーブコンストラクタ、ムーブ代入演算子は正常に動作しています。イテレータを実装すると、範囲 for 文や、for_each() など algorithm の関数も利用することができます。また、int 以外にも string を指定すると、文字列を格納することができます。興味のある方はいろいろ試してみてください。
// // tree.cpp : 二分探索木 (テンプレート版) // // Copyright (C) 2015-2023 Makoto Hiroi // #include <iostream> #include <stdexcept> #include <iterator> #include <vector> #include <algorithm> using namespace std; // 節 template<class T> class Node { T item; Node* left; Node* right; public: explicit Node(const T& x) : item(x), left(0), right(0) { } explicit Node(T&& x) : item(move(x)), left(0), right(0) { } T& get_item() { return item; } Node* get_left() const { return left; } Node* get_right() const { return right; } void put_item(const T& x) { item = x; } void put_item(T&& x) { item = move(x); } void put_left(Node* l) { left = l; } void put_right(Node* r) { right = r; } }; // 探索 template<class T> bool search_node(const T& x, Node<T>* node) { while (node) { if (x == node->get_item()) return true; else if (x < node->get_item()) node = node->get_left(); else node = node->get_right(); } return false; } // 挿入 template<class T> Node<T>* insert_node(const T& x, Node<T>* node) { if (!node) return new Node<T>(x); if (x < node->get_item()) node->put_left(insert_node(x, node->get_left())); else if (x > node->get_item()) node->put_right(insert_node(x, node->get_right())); return node; } template<class T> Node<T>* insert_node(T&& x, Node<T>* node) { if (!node) return new Node<T>(forward<T>(x)); if (x < node->get_item()) node->put_left(insert_node(forward<T>(x), node->get_left())); else if (x > node->get_item()) node->put_right(insert_node(forward<T>(x), node->get_right())); return node; } // 最小値を探す template<class T> T& search_min(Node<T>* node) { while (node->get_left()) node = node->get_left(); return node->get_item(); } // 最小値の節を削除 template<class T> Node<T>* delete_min(Node<T>* node) { if (!node->get_left()) { Node<T>* x = node->get_right(); delete node; return x; } node->put_left(delete_min(node->get_left())); return node; } // 最大値を探す template<class T> T& search_max(Node<T>* node) { while (node->get_right()) node = node->get_right(); return node->get_item(); } // 最大値の節を削除 template<class T> Node<T>* delete_max(Node<T>* node) { if (!node->get_right()) { Node<T>* x = node->get_left(); delete node; return x; } node->put_right(delete_max(node->get_right())); return node; } // 削除 template<class T> Node<T>* delete_node(const T& x, Node<T>* node) { if (!node) return node; if (x == node->get_item()) { if (!node->get_left()) { Node<T>* x = node->get_right(); delete node; return x; } if (!node->get_right()) { Node<T>* x = node->get_left(); delete node; return x; } node->put_item(move(search_min(node->get_right()))); node->put_right(delete_min(node->get_right())); } else if (x < node->get_item()) node->put_left(delete_node(x, node->get_left())); else node->put_right(delete_node(x, node->get_right())); return node; } // コピー template<class T> Node<T>* copy_node(Node<T>* node) { if (!node) return 0; Node<T>* new_node = new Node<T>(node->get_item()); new_node->put_left(copy_node(node->get_left())); new_node->put_right(copy_node(node->get_right())); return new_node; } // 廃棄 template<class T> void destroy_node(Node<T>* node) { if (node) { destroy_node(node->get_left()); destroy_node(node->get_right()); delete node; } } // 二分探索木 template<class T> class Tree { Node<T>* root; public: Tree() : root(0) { } ~Tree() { destroy_node(root); } // コピーコンストラクタ Tree(const Tree& tree) { root = copy_node(tree.root); } // 代入演算子 Tree& operator=(const Tree& tree) { if (this != &tree) { destroy_node(root); root = copy_node(tree.root); } return *this; } // ムーブコンストラクタ Tree(Tree&& tree) : root(tree.root) { tree.root = 0; } // ムーブ代入演算子 Tree& operator=(Tree&& tree) { if (this != &tree) { destroy_node(root); root = tree.root; tree.root = 0; } return *this; } // メンバ関数 bool empty() const { return !root; } bool search(const T& x) const { return search_node(x, root); } const T& min() const { if (!root) throw std::runtime_error("Tree::min empty tree"); return search_min(root); } const T& max() const { if (!root) throw std::runtime_error("Tree::max empty tree"); return search_max(root); } void insert(const T& x) { root = insert_node(x, root); } void insert(T&& x) { root = insert_node(forward<T>(x), root); } void remove(const T& x) { root = delete_node(x, root); } void remove_min() { if (root) root = delete_min(root); } void remove_max() { if (root) root = delete_max(root); } // イテレータ class Iterator : public iterator<forward_iterator_tag, T> { vector<Node<T>*> stack; // 次の node へ進める void next_node(Node<T>* node) { while (node) { stack.push_back(node); node = node->get_left(); } } public: Iterator(Tree* tree, bool end) { if (!end) next_node(tree->root); } // 間接参照 const T& operator*() const { return stack.back()->get_item(); } const T* operator->() const { return &(stack.back()->get_item()); } // 前置の ++ 演算子 Iterator& operator++() { Node<T>* node = stack.back(); stack.pop_back(); next_node(node->get_right()); return *this; } // 後置の ++ 演算子 Iterator operator++(int n) { Iterator iter(*this); Node<T>* node = stack.back(); stack.pop_back(); next_node(node->get_right()); return iter; } // 比較演算子 bool operator==(const Iterator& iter) { return stack == iter.stack; } bool operator!=(const Iterator& iter) { return stack != iter.stack; } }; Iterator begin() { return Iterator(this, false); } Iterator end() { return Iterator(this, true); } }; int main() { vector<int> a = {5, 7, 3, 4, 2, 1, 8, 6, 9}; vector<int> b = {15, 17, 13, 14, 12, 11, 18, 16, 19}; Tree<int> tree_a; Tree<int> tree_b; for (int x : a) tree_a.insert(x); for (int x : tree_a) cout << x << " "; cout << endl; for (int x : b) tree_b.insert(x); for (int x : tree_b) cout << x << " "; cout << endl; { Tree<int> tree_c = tree_a; tree_a = tree_b; tree_b = tree_c; for (int x : tree_a) cout << x << " "; cout << endl; for (int x : tree_b) cout << x << " "; cout << endl; } { Tree<int> tree_c = move(tree_a); tree_a = move(tree_b); tree_b = move(tree_c); for (int x : tree_a) cout << x << " "; cout << endl; for (int x : tree_b) cout << x << " "; cout << endl; } for (int x = 0; x <= 10; x++) cout << tree_a.search(x) << " "; cout << endl; for (auto iter = tree_a.begin(); iter != tree_a.end(); ++iter) cout << *iter << " "; cout << endl; auto iter = tree_b.begin(); while (iter != tree_b.end()) cout << *iter++ << " "; cout << endl; for_each(tree_a.begin(), tree_a.end(), [](int x){ cout << x << " "; }); cout << endl; for (int i = 0; i < 9; i++) { tree_a.remove(a[i]); for_each(tree_a.begin(), tree_a.end(), [](int x){ cout << x << " "; }); cout << endl; } while (!tree_b.empty()) { cout << tree_b.min() << endl; cout << tree_b.max() << endl; tree_b.remove_min(); tree_b.remove_max(); for (int x : tree_b) cout << x << " "; cout << endl; } Tree<string> tree_c; tree_c.insert("foo"); tree_c.insert("bar"); tree_c.insert("baz"); tree_c.insert("oops"); for (auto& x : tree_c) cout << x << " "; cout << endl; tree_c.remove("foo"); for (auto& x : tree_c) cout << x << " "; cout << endl; tree_c.remove("bar"); for (auto& x : tree_c) cout << x << " "; cout << endl; tree_c.remove("oops"); for (auto& x : tree_c) cout << x << " "; cout << endl; tree_c.remove("baz"); for (auto& x : tree_c) cout << x << " "; cout << endl; }