単方向リストを自作する

はじめに

コーニグ『C++再考』では，STLのvectorに似たArrayクラスを自作しイテレータの役割をするPointerクラスを実装している．また，LispのListを参考にした要素の値が変更できない単方向リストSeqクラスを実装している．

この本で書かれていることを実際に使いながら身に着けるために，要素の値が変更できるようにSeqクラスを変更し，これにPointerクラスも実装する．

実際に書いてみると，単方向リストのPointerクラスは，（コーニグ本の）ArrayクラスにおけるPointerクラスのようにはいかないことが分かってきた．途中で試行錯誤があったがそれは適宜コメントすることにして，基本的にこの記事内のコードは最終的なものを載せる．

本記事の目的は，コンテナクラスの考え方を復習することなので，性能や実用性やコードの読みやすさは全く考慮していないことにご注意ください．

叩き台

叩き台として，何も考えず素朴に単方向リストを作ろうとすると，以下のようになると思う．（ただし，print_all()関数はデバグ用に使う関数）

List.h

template<class T>
class List {
  public:
    List(const T& d) : data(d), next(nullptr){}
    void connect_back(List<T>&);
    void print_all() const;
  private:
    T data;
    List<T>* next;
};

template<class T> 
void List<T>::connect_back(List<T>& p){
    if(next == nullptr){
        next = &p;
    }else{
        next->connect_back(p);
    }
}

template<class T>
void List<T>::print_all() const{
    std::cout << data << std::endl;
    if(next){
        next->print_all();
    }
}

例えば，以下のように使用することができる．

main.cpp

int main() {
    List<int> l1(1);
    List<int> l2(2);
    List<int> l3(3);

    l1.connect_back(l2);
    l1.connect_back(l3);

    l1.print_all();
}

実行結果

1
2
3

さて，今の状態ではデフォルトコピーコンストラクタが作成されているが，Listのメンバがポインタであることに注意．コピーしたものを変更すれば，コピー元も同様に変更される．先の例の後で以下のようにすれば，コピーl4の変更によりl1も変更される．

main.cpp

int main() {
    List<int> l1(1);
    List<int> l2(2);
    List<int> l3(3);

    l1.connect_back(l2);
    l1.connect_back(l3);

    //l1.print_all();

    List<int> l4 = l1;
    List<int> l5(5);
    l4.connect_back(l5);

    l1.print_all();

}

実行結果

1
2
3
5

これが即座に悪いコンテナであることを意味するわけではない．コンテナは，コピー元とコピー先は独立する「値的」なコンテナと，コピー元とコピー先が同じオブジェクトを指す「ポインタ的な」コンテナのどちらかである．組み込み型コンテナで言えば，構造体が値的で配列はポインタ的である．

どちらのコンテナを作るかであるが，値的なコンテナの方が直感的に使える（と思う）ので，値的なものを作ることにする．ただし，その場合，コピーにコストがかかるのでポインタ的に作成しコピーオンライトを行うことで値的に「振る舞う」コンテナを作っていくことにしよう．

最低限の機能

叩き台のクラスでは，Listは直接Listを指すことでつながっていたが，Listは自身は値をもたず，Listは値を持つList_nodeを指すことにする．つまり，List_nodeの列がデータを表し，その先頭をListが指すことにする．

また，Listのコピーではオブジェクトをコピーする必要はなく，同じList_nodeを指すようにする．List_nodeを変更する必要が生じた場合にコピーすれば良い．そのためには，List_nodeは幾つのListやList_nodeから参照されているかを記憶する必要がある．

いくつかのListが同じList_nodeを使っている場合以下のようになる．

この場合には，list1とlist2は共に{1,2,3,4}というデータを表し，list3は{5,3,4}というデータを表す．

副次的な効用として，Listがnullptrを指すことで要素が空のListが作成できるようになった．（実は叩き台のクラスでは要素が空のコンテナが作成できなかった．）

よって，ListとList_nodeのメンバ変数は以下のようになる．
ListはList_nodeオブジェクトを変更するので，List_nodeのfriendにしておこう．

template<class T>
class List {
  private:
    List_node<T>* node;
};

template<class T>
class List_node {
    friend List<T>;
  private:
    T data;
    List_node<T>* next;
    int use;
};

最初にやるべきことはオブジェクトのコンストラクタとデストラクタを作ることであるが，List_nodeに関しては特に悩む必要がない．特に，デストラクタは必要がない．（ここが実は罠だった．「反省」の節で述べるように，参照回数を記憶するuseはメモリリークに直結する重要な部分なので，どのように管理するかが以降のコードにじわじわと効いてくる．）

List_node(const T& t, List_node<T>* n) : data(t), next(n), use(1){
    if(n){
        n->use++;
    }
}

さて，このようにList_nodeを生成するならば，Listのコンストラクタは自然と以下のようになる．

List() : node(nullptr) {}
List(const T& t) : node(new List_node<T>(t,nullptr)) {}
List(const T& t,const List<T>& list) : node(new List_node<T>(t, list.node)) {}

newでList_nodeを生成しているので，deleteのタイミングが非常に大切である．破棄を失敗しないために，destroy()関数を定義し，これを用いてデストラクタを作成する．

template<class T>
List<T>::~List() { destroy(node);}

template<class T>
void List<T>::destroy(List_node<T>* n){
    while(n && --n->use == 0){
        List_node<T>* next = n->next;
        delete n;
        n = next;
    }
}

出来たクラス

以上をまとめると，以下のようなクラスができた．(チェック用にprintAll()関数を加えている．また，クラスの前方宣言も必要なことに注意．)

List2.h

template<class T> class List_node;

template<class T>
class List {
  public:
    List() : node(nullptr) {}
    List(const T& t) : node(new List_node<T>(t,nullptr)) {}
    List(const T& t,const List<T>& list) : node(new List_node<T>(t, list.node)) {}
    ~List() { destroy(node);}
    bool isEmpty() { return node == nullptr;}
    void printAll();
    void destroy(List_node<T>*);
  private:
    List_node<T>* node;
};

template <class T>
void List<T>::printAll(){
    if(node){
        node->printAll();
    }
}

template<class T>
void List<T>::destroy(List_node<T>* n){
    while(n && --n->use == 0){
        List_node<T>* next = n->next;
        delete n;
        n = next;
    }
}

template<class T>
class List_node {
    friend List<T>;
  private:
    List_node(const T& t, List_node<T>* n) : data(t), next(n), use(1){
        if(n){
            n->use++;
        }
    }
    void printAll();

    T data;
    List_node<T>* next;
    int use;
};

template < class T>
void List_node<T>::printAll(){
    std::cout << data << std::endl;
    if(next){
        next->printAll();
    }
}

これで以下のようなプログラムが動く．

main.cpp

int main() {
    List<int> list(3,List<int>(2, List<int>(4, List<int>(1))));
    list.printAll();
}

実行結果

3
2
4
1

ここで，定義したメンバ関数の仮引数はすべて参照かポインタであるためうまく動くことに注意する．そうでなければ，引数の受け渡しにデフォルトコピーコンストラクタが使われてうまく動かない．

コピーコンストラクタとコピー代入

次にコピーコンストラクタとコピー代入を定義しよう．

コピーでは単にListが同じ要素を指すように決めたのでコピーコンストラクタの定義は簡単である．

template<class T>
List<T>::List(const List<T>& l) : node(l.node) {
    if(node){
        node->use++;
    }
}

コピーコンストラクタが簡単ならばコピー代入も簡単だと思ってしまうが，コピー代入では自分を代入するケースに必ず注意する必要がある．この難しさの元を辿れば，代入が代入される側の「破棄」を行うというところに起因すると思う．

今回は，代入元のuseを先に上げることで，代入先と代入元が同じ場合でもnodeのdeleteが起こらないようにしている．

template<class T>
List<T>& List<T>::operator=(const List<T>& l){
    if(l.node){
        l.node->use++;
    }
    destroy(node);
    node = l.node;
    return *this;
}

ここまでは難しくない

Pointerの作成

イテレータの役割をするPointerを作成する．イテレータやポインタを使うときには，コンテナが破棄されたときにその要素を指していたイテレータやポインタはどうなるかということが常に問題になる．

コーニグ本では配列のように連続領域にデータを記憶するArrayクラスに対してPointerを作成している．このArrayでもデータはArray_nodeに記憶し，Listクラスと同様に無駄なコピーが起こらないようにしている．これを踏まえて以下のような仕様にしている．

• PointerがArray_nodeを指すときにもそのuseを増やす．
• これにより，Arrayが破棄されてもPointerが要素を指していればArray_nodeは破棄されない．

これにより，コンテナが破棄されてもPointerが無効な要素を指す心配をする必要がなくなった．

当初，Listの場合でもこれと同じ仕様にするつもりだった．しかし，これはうまくいかない．．．と思っていたが，この記事を書いているときに実は同じようにできるかもしれないと気がついてしまった．これはコンテナに何を求めるかという問題なので，今回はそのようにしないようにする．

つまり，PointerがList_nodeを指していてもuseは上げないことにする．これにより，コンテナが破棄された場合にはPointerは使ってはならないこととする．（これはCでポインタを使ってるのと同じである．）コーニグ本とは違うPointerの仕様なので，方針を変えなければコーディングが進まない．今回はPointerによって
　STLのforward_listのイテレータができること
を実現していくことにする．

list1の3番目の要素を指すPointer p がある時の図が以下のようになるが，図を見てわかるように，List_nodeが他のListでも使われている場合，どのリストのPointerであるかは分からない．

Pointerの参照でuseが上がらないので，Pointerの実装は非常に簡単である．データを変更する以外の機能は以下のようになる．

template<class T> class Pointer {
  public:
    Pointer(List<T>& a) : node(a.node){}
    ~Pointer(){}
    T operator*() const;
    Pointer& operator=(const Pointer<T>& p){
        node = p.node;
    }
    Pointer& operator++(){
        node = node->next;
        return *this;
    }
    Pointer operator++(int){
        Pointer p = *this;
        node = node->next;
        return p;
    }

    int operator==(const Pointer<T>& p){
        return node == p.node;
    }

    int operator!=(const Pointer<T>& p){
        return node != p.node;
    }

    operator bool() const { return node != nullptr;} 

  private:
    List_node<T>* node;
};



template<class T>
T Pointer<T>::operator*() const {
    if(node == nullptr){
        throw "* of unbound Pointer";
    }
    return node->data;
}

Pointerを使えばすべての要素の表示が簡単にできるようになった．Listのデータが連続領域に保存されているわけではないのにポインタと同様に記述することができる．

main.cpp

int main() {
    List<int> list1 = List<int>(3,List<int>(1,List<int>(4)));
    Pointer<int> p(list1);

    while(p){
        std::cout << *p << std::endl;
        ++p;
    }
}

実行結果

3
1
4

データを変更するメンバ関数

コピーオンライトを採用したので，データを変更するときに注意が必要だ．

コーニグ本ではListのデータの順番を反転させるflip関数で初めてデータを変更する．

この節ぐらいから正しくコーディングするのが珍しく，特にメモリに関するバグが頻出する．そのためAddressSanitizerを用いてメモリエラーを検出した．ただし，自分の環境では実行時にASAN_OPTIONS=detect_leaks=1をつけないとメモリリークを検出しなかった．

データを変更する前に，もしList_nodeが他のListで参照している場合には、他のリストから参照されていないコピーを作る必要がある．ここで初めて実際にコピーする．最後のノードまでを自分だけが所有するという意味のowntail関数が必要となる．

owntail()の前

owntail()の後

useが1でないものがあれば，それは他のListで使われているのでそれ以降のList_nodeは全てコピーする必要がある．

template<class T>
List_node<T>* List<T>::owntail(){
    //空なら何もしない
    if(node == nullptr){
        return nullptr;
    }
    //
    List_node<T>* i = node;
    List_node<T>** p = &node;

    //useが1のものをスキップしていく
    while(i->use == 1){
        if(i->next == nullptr){
            return i;
        }
        p = &i->next;
        i = i->next;
    }

    //useが1でないものの処理
    //コピーを作って繋げる
    *p = new List_node<T> (i->data);
    --i->use;
    i=i->next;

    //元のデータを見ていく i と
    //このリストに繋げるコピーを指し示す j
    List_node<T>* j = *p;
    while(i) {
        j->next = new List_node<T> (i->data);
        i = i->next;
        j = j->next;
    }
    return j;
}

あとでポインタを使ってデータを変更する関数を作る際に，このowntail関数を参考にした関数を作る．

この関数さえできてしまえば，flip関数は簡単である．

template<class T>
List<T>& List<T>::flip(){
    if(node) {
        List_node<T>* k = owntail();
        List_node<T>* curr = node;
        List_node<T>* behind = nullptr;

        do {
            List_node<T>* ahead = curr->next;
            curr->next = behind;
            behind = curr;
            curr = ahead;
        }while(curr);

        node = k;
    }
    return *this;
}

コピー元のリストを変更しても，コピー先のデータが変化しない．

main.cpp

List<int> list1 = List<int>(1,List<int>(2,List<int>(3)));
List<int> list2 = list1;

std::cout << "list1" << std::endl;
list1.flip().printAll();
std::cout << "list2" << std::endl;
list2.printAll();

実行結果

list1
3
2
1
list2
1
2
3

出来たクラス

ここまでを出来たクラスは以下のようになる．

list4.h

template<class T> class List_node;
template<class T> class Pointer;

template<class T>
class List {
    friend Pointer<T>;
  public:
    List() : node(nullptr) {}
    List(const T& t) : node(new List_node<T>(t,nullptr)) {}
    List(const T& t,const List<T>& list) : node(new List_node<T>(t, list.node)) {}
    List(List_node<T>* s): node(s) { if(s) s->use++;}
    List(const List&);
    List& operator=(const List&);
    ~List() { destroy(node);}
    bool empty() const { return node == nullptr;}
    operator bool() const { return node != nullptr;}
    void printAll() const;
    List& flip();
    List& operator++();
    T hd() const {if(node) {return node->data;}else{ throw "hd of a empty List";} }
    List tl() const {return List<T>(node->next);}
    List& push_front(const T&);
  private:
    void destroy(List_node<T>*);
    List_node<T>* owntail();

    List_node<T>* node;
};

template<class T>
List<T>& List<T>::operator++(){
    if(node){
        List_node<T>* p = node->next;
        if(p){
            p->use++;
        }
        if(--node->use == 0){
            delete node;
            p->use--;           //コーニグ本ではこの行がない
        }
        node = p;
    }
    return *this;
}

template<class T> List<T> cons(const T& t, const List<T>& s){
    return List<T>(t,s);
}

template<class T>
List<T>::List(const List<T>& l) : node(l.node) {
    if(node){
        node->use++;
    }
}

template<class T>
List<T>& List<T>::operator=(const List<T>& l){
    if(l.node){
        l.node->use++;
    }
    destroy(node);
    node = l.node;
    return *this;
}

template <class T>
void List<T>::printAll() const{
    if(node){
        node->printAll();
    }
}

template<class T>
void List<T>::destroy(List_node<T>* n){
    while(n && --n->use == 0){
        List_node<T>* next = n->next;
        delete n;
        n = next;
    }
}

template<class T>
List_node<T>* List<T>::owntail(){
    //空なら何もしない
    if(node == nullptr){
        return nullptr;
    }
    //
    List_node<T>* i = node;
    List_node<T>** p = &node;

    //useが1のものをスキップしていく
    while(i->use == 1){
        if(i->next == nullptr){
            return i;
        }
        p = &i->next;
        i = i->next;
    }

    //useが1でないものの処理
    //コピーを作って繋げる
    *p = new List_node<T> (i->data);
    --i->use;
    i=i->next;

    //元のデータを見ていく i と
    //このリストに繋げるコピーを指し示す j
    List_node<T>* j = *p;
    while(i) {
        j->next = new List_node<T> (i->data);
        i = i->next;
        j = j->next;
    }
    return j;
}

template<class T>
List<T>& List<T>::flip(){
    if(node) {
        List_node<T>* k = owntail();
        List_node<T>* curr = node;
        List_node<T>* behind = nullptr;

        do {
            List_node<T>* ahead = curr->next;
            curr->next = behind;
            behind = curr;
            curr = ahead;
        }while(curr);

        node = k;
    }
    return *this;
}


template<class T>
List<T>& List<T>::push_front(const T& t){

    //Listからの参照が消えるのでuseを減らしておく
    //コーニグ本のinsertではバグがある
    if(node){
        node->use--;
    }
    node = new List_node<T>(t,node);


    return *this;
}


template<class T>
class List_node {
    friend List<T>;
    friend Pointer<T>;
  private:
    List_node(const T& t, List_node<T>* n) : data(t), next(n), use(1){
        if(n){
            n->use++;
        }
    }
    List_node(const T& t) : data(t), next(nullptr), use(1) {}
    void printAll();


    T data;
    List_node<T>* next;
    int use;
};

template < class T>
void List_node<T>::printAll(){
    std::cout << data << std::endl;
    if(next){
        next->printAll();
    }
}


//Pointerが参照していてもuseは増やさないことにする

template<class T> class Pointer {
  public:
    Pointer(List<T>& a) : node(a.node){}
    ~Pointer(){}
    T operator*() const;
    Pointer& operator=(const Pointer<T>& p){
        node = p.node;
    }
    Pointer& operator++(){
        node = node->next;
        return *this;
    }
    Pointer operator++(int){
        Pointer p = *this;
        node = node->next;
        return p;
    }

    int operator==(const Pointer<T>& p){
        return node == p.node;
    }

    int operator!=(const Pointer<T>& p){
        return node != p.node;
    }

  private:
    List_node<T>* node;
};



template<class T>
T Pointer<T>::operator*() const {
    if(node == nullptr){
        throw "* of unbound Pointer";
    }
    return node->data;
}

ここで，Listの簡単なメンバ関数をいくつか追加している．ここで，コーニグ本の前置インクリメントは多分バグがある．さらに，最初に要素を加えるpush_front関数は，コーニグ本でのinsert関数であるがコーニグ本ではuseの処理が間違えていてメモリリークする．

Pointerを使ったデータの変更

forward_listのイテレータを参考にして，PointerでListのデータを変更する関数を作っていく．

Pointerが指す要素の後にデータを一つ挿入するinsert_afterが典型例なので，まずこれを作成する．Listの構造が変わるので，owntailのように変更前にコピーをとっておく必要がある．しかし，owntail()を使ってしまうと，Pointerはあくまでコピー元を指しており，コピー先の新しいデータを指してはくれない．つまり，コピー時にPointerは対応する新しいList_nodeを指すように変更する必要がある．今回作成していく関数では，Pointerが指す要素までのコピーを作る必要がある．つまり，Listの最後までのコピーを取る必要がない．以上を踏まえて，Pointerが指す要素までをコピーするownByPointer関数を作成した．

template<class T>
List_node<T>* List<T>::ownByPointer(Pointer<T>& pointer){
    //空なら何もしない
    if(node == nullptr){
        return nullptr;
    }
    //
    List_node<T>* i = node;
    List_node<T>** p = &node;

    //useが1のものをスキップしていく
    while(i->use == 1){
        if(i->next == nullptr || i == pointer.node){
            return i;
        }
        p = &i->next;
        i = i->next;
    }

    //useが1でないものの処理
    //コピーを作って繋げる
    *p = new List_node<T> (i->data);
    --i->use;

    //元のデータを見ていく i と
    //このリストに繋げるコピーを指し示す j
    List_node<T>* j = *p;
    while(i != pointer.node) {
        i=i->next;
        j->next = new List_node<T> (i->data);
        j = j->next;
    }

    //ここに来た時、 i == pointer.nodeでありコピー済み
    i = i->next;
    if(i){
        i->use++;
        j->next = i;
    }

    pointer.node = j;

    return j;
}

Listをこの関数で変更したとき，この関数で使ったPointerはこの後も有効である．しかし，同じListを指す別のPointerがあったとき，それは（コピーが行われた場合は）コピー前を指したままであり．コピー後のListのList_nodeを指してはない．つまり，一般にPointerは有効でなくなる．

insert_after

insert_afterは以下のように書ける．

template<class T>
Pointer<T> List<T>::insert_after(Pointer<T>& p, const T& t){
    if(p){
        ownByPointer(p);
        p.node->next->use--;

        List_node<T>* n = new List_node<T>(t,p.node->next);
        p.node->next = n;
        return Pointer<T>(n);
    }else {
        throw "invalid Pointer";
    }
}

Listの中身を詳しく教えてくれるprintData関数を使ってみると，insert_afterを使ったときの様子がわかる．

template<class T>
void List<T>::printData(){
    std::cout << "Print Data" << std::endl;
    if(node) node->printData();
}

template<class T>
void List_node<T>::printData(){
    std::cout << "Data:" << data << " Use:" << use << std::endl;
    if(next){
        next->printData();
    }
}

main.cpp

int main() {
    List<int> list1 = List<int>(1,List<int>(2,List<int>(3,List<int>(4))));
    Pointer<int> p(list1);
    List<int> list2 = list1;

    list1.printData();
    list2.printData();

    std::cout << "insert" << std::endl;
    p++;
    list1.insert_after(p,10);


    list1.printData();
    list2.printData();
}

実行結果

Print Data
Data:1 Use:2
Data:2 Use:1
Data:3 Use:1
Data:4 Use:1
Print Data
Data:1 Use:2
Data:2 Use:1
Data:3 Use:1
Data:4 Use:1
insert
Print Data
Data:1 Use:1
Data:2 Use:1
Data:10 Use:1
Data:3 Use:2
Data:4 Use:1
Print Data
Data:1 Use:1
Data:2 Use:1
Data:3 Use:2
Data:4 Use:1

この動作を図で説明する．最初は以下のような状態である．

まず，ownByPointerにより，Pointer pが指す場所までがコピーされる．このとき，pが指すのはコピー元からコピーへと変更されていることに注意する．

最後はノードを追加するだけである．

erace_after

別の関数として，Pointerが指す要素の次の要素を消去するerace_after関数を考える．この関数の場合Pointerが指す次までのデータが変更されるので，ownByPointerを使うときには1つ先のPointerを使う必要があるように錯覚するが，ownByPointerでコピーを取るのはPointerが指す要素までで十分である．以下のようにすれば良い．

template<class T>
Pointer<T> List<T>::erace_after(Pointer<T>& p){
    if(p){
        ownByPointer(p);
        List_node<T>* n = p.node->next;
        if(n){
            p.node->next = n->next;
            if(p.node->next){
                p.node->next->use++;
            }
            if(--n->use == 0){
                if(n->next){
                    n->next->use--;
                }
                delete n;
            }
            return Pointer<T>(p.node->next);
        }else{
            throw "Next doesn't exist";
        }
    }else{
        throw "Pointer is not valid";
    }
}

erace_afterは以下のように使える．

main.cpp

int main() {
    List<int> list1 = List<int>(1,List<int>(2,List<int>(3,List<int>(4))));
    Pointer<int> p(list1);
    List<int> list2 = list1;

    list1.printData();
    list2.printData();

    std::cout << "erace" << std::endl;
    p++;
    list1.erace_after(p);


    list1.printData();
    list2.printData();
}

実行結果

Print Data
Data:1 Use:2
Data:2 Use:1
Data:3 Use:1
Data:4 Use:1
Print Data
Data:1 Use:2
Data:2 Use:1
Data:3 Use:1
Data:4 Use:1
erace
Print Data
Data:1 Use:1
Data:2 Use:1
Data:4 Use:2
Print Data
Data:1 Use:1
Data:2 Use:1
Data:3 Use:1
Data:4 Use:2

出来たクラス

他にもいくつかの関数を加えて完成したのが以下のクラスである．すでに便利な関数を作っているので，forward_listに似た機能を加えるのは難しくはない．しかし，単方向リストの性質上ぎこちなくなってしまった．（特にremove関数）

list5.h

template<class T> class List_node;
template<class T> class Pointer;

template<class T>
class List {
    friend Pointer<T>;
  public:
    List() : node(nullptr) {}
    List(const T& t) : node(new List_node<T>(t,nullptr)) {}
    List(const T& t,const List<T>& list) : node(new List_node<T>(t, list.node)) {}
    List(List_node<T>* s): node(s) { if(s) s->use++;}
    List(const List&);
    List& operator=(const List&);
    ~List() { destroy(node);}
    bool empty() const { return node == nullptr;}
    operator bool() const { return node != nullptr;}
    void printAll() const;
    List& flip();
    List& operator++();
    T hd() const {if(node) {return node->data;}else{ throw "hd of a empty List";} }
    List tl() const {return List<T>(node->next);}
    void swap(List& a) {List_node<T>* n = a.node; a.node = node; node = n;}
    List& push_front(const T&);
    void pop_front(){ ++*this;}
    Pointer<T> insert_after(Pointer<T>&, const T&);
    Pointer<T> erace_after(Pointer<T>&);
    void clear();

    void remove(const T&);

    void printData() {std::cout << "Print Data" << std::endl; if(node) node->printData();} //デバグ用

  private:
    void destroy(List_node<T>*);
    List_node<T>* owntail();
    List_node<T>* ownByPointer(Pointer<T>&);


    List_node<T>* node;
};

template<class T>
void List<T>::remove(const T& t){
    Pointer<T> p(*this);
    while(p){
        if(p.node->next){
            if(p.node->next->data == t){
                erace_after(p);
            }else{
                ++p;
            }
        }else{
            ++p;
        }
    }
    //最後に先頭をみる
    if(node && node->data == t){
        pop_front();
    }
}

template<class T>
List<T>& List<T>::operator++(){
    if(node){
        List_node<T>* p = node->next;
        if(p){
            p->use++;
        }
        if(--node->use == 0){
            delete node;
            p->use--;
        }
        node = p;
    }
    return *this;
}

template<class T> List<T> cons(const T& t, const List<T>& s){
    return List<T>(t,s);
}

template<class T>
List<T>::List(const List<T>& l) : node(l.node) {
    if(node){
        node->use++;
    }
}

template<class T>
List<T>& List<T>::operator=(const List<T>& l){
    if(l.node){
        l.node->use++;
    }
    destroy(node);
    node = l.node;
    return *this;
}

template <class T>
void List<T>::printAll() const{
    if(node){
        node->printAll();
    }
}

template<class T>
void List<T>::destroy(List_node<T>* n){
    while(n && --n->use == 0){
        List_node<T>* next = n->next;
        delete n;
        n = next;
    }
}

template<class T>
List_node<T>* List<T>::owntail(){
    //空なら何もしない
    if(node == nullptr){
        return nullptr;
    }
    //
    List_node<T>* i = node;
    List_node<T>** p = &node;

    //useが1のものをスキップしていく
    while(i->use == 1){
        if(i->next == nullptr){
            return i;
        }
        p = &i->next;
        i = i->next;
    }

    //useが1でないものの処理
    //コピーを作って繋げる
    *p = new List_node<T> (i->data);
    --i->use;
    i=i->next;

    //元のデータを見ていく i と
    //このリストに繋げるコピーを指し示す j
    List_node<T>* j = *p;
    while(i) {
        j->next = new List_node<T> (i->data);
        i = i->next;
        j = j->next;
    }
    return j;
}

template<class T>
void List<T>::clear(){
    destroy(node);
    node = nullptr;
}

template<class T>
List<T>& List<T>::flip(){
    if(node) {
        List_node<T>* k = owntail();
        List_node<T>* curr = node;
        List_node<T>* behind = nullptr;

        do {
            List_node<T>* ahead = curr->next;
            curr->next = behind;
            behind = curr;
            curr = ahead;
        }while(curr);

        node = k;
    }
    return *this;
}

template<class T>
List<T> merge(const List<T>& x, const List<T>& y){
    if(!x) return y;
    if(!y) return x;

    T xh = x.hd();
    T yh = y.hd();

    if(xh < yh) return cons(xh,merge(x.tl(),y));
    return cons(yh,merge(x,y.tl()));
}

template <class T>
void split(List<T> x, List<T>& y, List<T>& z){
    while(x){
        y.push_front(x.hd());
        if(++x){
            z.push_front(x.hd());
            ++x;
        }
    }
}

template<class T> List<T> sort(const List<T>& x){
    //空か要素が1つなら何もしない
    if(!x || !x.tl()){
        return x;

    }
    List<T> p,q;
    split(x,p,q);
    return merge(sort(p),sort(q));
}

template<class T>
List<T>& List<T>::push_front(const T& t){

    //Listからの参照が消えるのでuseを減らしておく
    if(node){
        node->use--;
    }
    node = new List_node<T>(t,node);


    return *this;
}

template<class T>
Pointer<T> List<T>::insert_after(Pointer<T>& p, const T& t){
    if(p){
        ownByPointer(p);
        p.node->next->use--;

        List_node<T>* n = new List_node<T>(t,p.node->next);
        p.node->next = n;
        return Pointer<T>(n);
    }else {
        throw "invalid Pointer";
    }
}

template<class T>
Pointer<T> List<T>::erace_after(Pointer<T>& p){
    if(p){
        ownByPointer(p);
        List_node<T>* n = p.node->next;
        if(n){
            p.node->next = n->next;
            if(p.node->next){
                p.node->next->use++;
            }
            if(--n->use == 0){
                if(n->next){
                    n->next->use--;
                }
                delete n;
            }
            return Pointer<T>(p.node->next);
        }else{
            throw "Next doesn't exist";
        }
    }else{
        throw "Pointer is not valid";
    }
}

template<class T>
List_node<T>* List<T>::ownByPointer(Pointer<T>& pointer){
    //空なら何もしない
    if(node == nullptr){
        return nullptr;
    }
    //
    List_node<T>* i = node;
    List_node<T>** p = &node;

    //useが1のものをスキップしていく
    while(i->use == 1){
        if(i->next == nullptr || i == pointer.node){
            return i;
        }
        p = &i->next;
        i = i->next;
    }

    //useが1でないものの処理
    //コピーを作って繋げる
    *p = new List_node<T> (i->data);
    --i->use;

    //元のデータを見ていく i と
    //このリストに繋げるコピーを指し示す j
    List_node<T>* j = *p;
    while(i != pointer.node) {
        i=i->next;
        j->next = new List_node<T> (i->data);
        j = j->next;
    }

    //ここに来た時、 i == pointer.nodeでありコピー済み
    i = i->next;
    if(i){
        i->use++;
        j->next = i;
    }

    pointer.node = j;

    return j;
}



template<class T>
class List_node {
    friend List<T>;
    friend Pointer<T>;
  private:
    List_node(const T& t, List_node<T>* n) : data(t), next(n), use(1){
        if(n){
            n->use++;
        }
    }
    List_node(const T& t) : data(t), next(nullptr), use(1) {}
    void printAll();

    void printData(){
        std::cout << "Data:" << data << " Use:" << use << std::endl;
        if(next){
            next->printData();
        }
    }

    T data;
    List_node<T>* next;
    int use;
};

template < class T>
void List_node<T>::printAll(){
    std::cout << data << std::endl;
    if(next){
        next->printAll();
    }
}


//Pointerが参照していてもuseは増やさないことにする

template<class T> class Pointer {
    friend  List<T>;
  public:
    Pointer(List<T>& a) : node(a.node){}
    Pointer(List_node<T>* n) : node(n){}
    Pointer(List<T>* n) : node(n) {};
    ~Pointer(){}
    T operator*() const;
    Pointer& operator=(const Pointer<T>& p){
        node = p.node;
    }
    Pointer& operator++(){
        node = node->next;
        return *this;
    }
    Pointer operator++(int){
        Pointer p = *this;
        node = node->next;
        return p;
    }

    int operator==(const Pointer<T>& p){
        return node == p.node;
    }

    int operator!=(const Pointer<T>& p){
        return node != p.node;
    }

    operator bool() const { return node != nullptr;}
  private:
    List_node<T>* node;
};



template<class T>
T Pointer<T>::operator*() const {
    if(node == nullptr){
        throw "* of unbound Pointer";
    }
    return node->data;
}

反省

メモリ管理

生のポインターを使っているのでメモリ管理に注意が必要．通常，deleteのタイミングに注意が向けられる印象があるが，参照回数useを見てdeleteするかどうかを決めるのでuseが正しく処理されている必要がある．バグこのuseに由来するものがほとんどだった．

よって，useを自動的に処理するような関数を作っておくべきだったと思う．useはList_nodeを参照するとき/参照が外れるときに1増える/1減るだけなので，他のListまたはList_nodeから参照する関数と参照を外す関数を作って，その関数の内部だけでuseが変わるようにすれば十分だと思う．

なぜこのような事態になったかというと，コーニグ本におけるList_nodeのコンストラクタは自動的にuseを1にしているからである．つまり，すぐに参照されるという理由で生成した時点でuseを1にしているが，やはり実際に参照するときにuseを上げるべきだったのだと思う．

単方向リストとイテレータ

コーニグ本にあるようにデータを変化させない単方向リストSeqはポインターがなくても強力である．実際，マージソートを簡単に記述することができる．そもそも，コーニグ本のSeqや今回作成したListはある一つのノードを指すものなので，それ自体がそもそもポインタのようなものである．あるコンテナを操作するというイメージだとイテレータが必要な気分になるが，新しいSeqを次々と作っていくことでポインタでやりたいことはだいたい出来るのである．

とはいえ，何か意味のあるデータが入った集合を表す単方向リストがあるとき，そのデータを順番に一つずつに何らかの処理をしたり，その結果によりノードを消去したりノードを加えたりするならばイテレータはあるべきだ．単方向リストは探索の向きに制限がある分，コンテナを変更してもイテレータは無効にならないことが多いという利点がある．（STLのforward_listを参照せよ．）よって，せっかく単方向リストにイテレータを導入するなら，イテレータが無効にならないような工夫をもたせたい．PointerはあくまでList_nodeを指しているので，どのListのポインターであるかを把握できるような工夫が必要になってくる．

C++11の機能

せっかくなのでムーブコンストラクタやムーブ代入も実装したいところだ．とはいえ，コピーオンライトを採用しているので，コピーだけではほとんどコストはかからず，ムーブを導入するメリットがそれほどない．（ムーブを使わないとコストがかかる例は少なくとも今回の記事ではないはず）

生のポインタではなくスマートポインタを使ってコンテナを書いてみたいものだ．今回の記事で生のポインタを使う大変さがある程度実感できたと思うので，これまでよく分からなかったスマートポインタにも手が出せる気がする．

参考文献

• コーニグ『C++再考』，紀伊国屋書店
• cpprefjp:forward_list