M.Hiroi's Home Page

Linux Programming

お気楽C++プログラミング超入門

[ PrevPage | C++ | NextPage ]

連結リスト (テンプレート編)

今回は簡単な例題として、以前作成した 連結リスト をテンプレートを使って書き直してみましょう。名前は List とします。なお、C++の標準ライブラリには <list> や <forward_list> が用意されているので、私たちが List クラスを作成する必要はありませんが、テンプレートのお勉強ということで、あえてプログラムを作ってみましょう。

●セル Cell と連結リスト 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 を選択することができます。興味のある方はいろいろ試してみてください。

●参考 URL

  1. 本の虫: rvalue reference 完全解説, (江添亮さん)

●プログラムリスト

//
// 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;
}

初版 2015 年 10 月 25 日
改訂 2023 年 4 月 15 日

二分探索木 (テンプレート編)

今回は簡単な例題として、以前作成した 二分探索木 をテンプレートを使って書き直してみましょう。クラス名は Tree とします。なお、C++の標準ライブラリには <map> や <set> などの平衡二分木が用意されているので、私たちが単純な二分木を作る必要はありませんが、テンプレートのお勉強ということで、あえてプログラムを作ってみましょう。

●節 Node と二分木 Tree の定義

最初は、節 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;
}

初版 2015 年 10 月 25 日
改訂 2023 年 4 月 15 日

Copyright (C) 2015-2023 Makoto Hiroi
All rights reserved.

[ PrevPage | C++ | NextPage ]