M.Hiroi's Home Page

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

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


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

今回は簡単な例題として、以前作成した「連結リスト」をテンプレートを使って書き直してみましょう。名前は List とします。なお、Ｃ++の標準ライブラリには <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: 本の虫: rvalue reference 完全解説 によると、この機能を「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 完全解説, (http://cpplover.blogspot.jp/2009/11/rvalue-reference_23.html)

●プログラムリスト

//
// 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 日