Twitterを見る限り大学2年では双方向リストの実装を課題として課されることが多いようだ。もちろん弊学もその課題がある。ご学友がイテレータやリストへの要素の削除などで苦労していた。別に難しいことはないのでリストの実装を書く。
リストというデータ構造
リストと言うのはそれぞれの要素が隣り合う*1要素へのポインタをもち、シーケンシャルにそれぞれにアクセスできるようなデータ構造だ。図で表すと以下のようなデータ構造を連結リストという。
リストの各要素を表現するnode型はユーザーが使いたい型の値へのポインタvalueと次と前の要素へのポインタを持つ。要素数が二つの場合それぞれのnodeは以下のようにリンクする。
nodeだけで実装
nodeを操作する関数だけで要素の追加、削除、移動を実装してみよう。
template<class T> struct node { T* value; node* next; node* prev; };
要素の追加
要素を追加するときは追加した前後のnodeのnextメンバとprevメンバを書き換えるとともに、追加したnodeのインスタンスのnextとprevにも前後の要素のポインタを代入しなければならない。
あるnodeのインスタンスの位置に新しいnodeのインスタンスを挿入するためにinsert関数を作成する。
insertでは挿入したい値と、挿入する位置にあるnodeへのポインタを取り、挿入してできた新しいノードへのポインタを返す。特別な場合として、引数のnodeのポインタがnullptrだった時は、新しく一つの要素を持つリストを作ることにしよう。
template<class T> node<T>* insert(node<T>* pos, T value) { node<T>* fresh = new node<T>; fresh->value = new T(value); fresh->next = fresh->prev = nullptr; if(!pos) return fresh; // posがi番目だったとき、新しいnodeをi番目に挿入 fresh->next = pos; fresh->prev = pos->prev; // ポインタの付けかえ if(pos->prev) pos->prev->next = fresh; pos->prev = fresh; return fresh; }
要素の削除
要素を削除するときは、削除する要素の前後のノードのポインタを付け替え、削除する要素をdeleteするだけでよい。削除するノードを指すポインタを受け取るerase関数を作って要素の削除を実装しよう。便利のためerase関数は削除されたノードの次の位置にあったノードへのポインタを返す。
template<class T> node<T>* erase(node<T>* pos) noexcept { auto n = pos->next; assert(pos); if(pos->next) pos->next->prev = pos->prev; if(pos->prev) pos->prev->next = pos->next; delete pos->value; delete pos; return n; }
要素間の移動
配列と違って、リストの要素間を移動するためには少し面倒な処理をしなければならない。配列ではポインタをインクリメントするだけだったが、リストでは必ずしもメモリ空間上に連続して並んでいるとは限らないので、普通はあるノードを指すポインタにそのノードの次 (前) のノードを指すポインタを代入して移動する。
// posを直接書き換えて見るnodeを変える template<class T> void advance(node<T>*& pos, size_t n = 1) noexcept { if(!n) return; assert(pos); pos = pos->next; advance(pos, n - 1); } // posを直接書き換えて見るnodeを変える template<class T> void backward(node<T>*& pos, size_t n = 1) noexcept { if(!n) return; assert(pos); pos = pos->prev; backward(pos, n - 1); } // posを書き換えずにposのn個あとのnodeを指すポインタを返す template<class T> node<T>* next(node<T>* pos, size_t n = 1) noexcept { return n ? next(pos->next, n - 1) : pos; } // posを書き換えずにposのn個まえのnodeを指すポインタを返す template<class T> node<T>* prev(node<T>* pos, size_t n = 1) noexcept { return n ? next(pos->prev, n - 1) : pos; }
今までの関数をクラスにまとめる
関数をクラスにまとめてつながっているノードの全体を一つのリストとしてインスタンス化することができるようになれば便利になる。リストを一つのコンテナとしてイメージしやすくなるからだ。
listクラスは最初と最後の要素だけを保持する。ユーザーの求めに応じて最初のnodeか最後のnodeを返したり、スコープを外れるときに自動でメモリを解放したりできる*2。せっかくなのでnodeにもコンストラクタとデストラクタを追加してポインタの付け替えやメモリの解放を自動化してみよう*3。
template<class T> class list{ public: struct node{ node* next; node* prev; T* value; node() : next {nullptr} , prev {nullptr} , value{nullptr} {} node(node* prev, node* next, T* vptr = nullptr) : next {next} , prev {prev} , value{vptr} { if(next) next->prev = this; if(prev) prev->next = this; } node(node* next, T* vptr) : node(next->prev, next, vptr) {} ~node() { if(next) next->prev = prev; if(prev) prev->next = next; delete value; } }; list() : first_{new node} , last_ {new node} { first_->next = last_; last_->prev = first_; } ~list() { while(first_) first_ = erase(first_); } node* insert(node* pos, T value) { auto* fresh = new node(pos, new T(std::move(value))); return fresh; } void push_back(T value) { insert(end(), std::move(value)); } node* erase(node* pos) { auto n = pos->next; delete pos; return n; } node* begin() const noexcept { return first_->next; } node* end() const noexcept { return last_; } private: node* first_; node* last_; }; int main() { list<int> l; for(auto i = 0; i < 5; ++i) l.push_back(i); for(auto i = l.begin(); i != l.end(); i = i->next) std::cout << *(i->value); }
イテレータを書く
イテレータを書けばC++の標準ライブラリと同じように扱えるようになる。ここでは先ほど作ったリストにおけるイテレータの簡易的な実装のみをする。
このリストは双方向連結リストなので標準で言うとBidirectionalIteratorが適合する。イテレータのすべての要件を満たすのは大変なので最低限イテレータとして使えるように++演算子、--演算子、*単項演算子、!=演算子のみを定義してみよう。また、イテレータを実装するとnodeの中身をlistの外に公開する必要がなくなるため、nodeやnode*を返す関数はイテレータに置き換えよう。
#include <iostream> #include <vector> #include <cstdint> #include <cassert> template<class T> class list{ struct node{ node* next; node* prev; T* value; node() : next {nullptr} , prev {nullptr} , value{nullptr} {} node(node* prev, node* next, T* vptr = nullptr) : next {next} , prev {prev} , value{vptr} { if(next) next->prev = this; if(prev) prev->next = this; } node(node* next, T* vptr) : node(next->prev, next, vptr) {} ~node() { if(next) next->prev = prev; if(prev) prev->next = next; delete value; } }; public: class iterator{ node* node_; public: friend list; /*implicit*/ iterator(node* c) : node_{c} {} iterator() : node_{nullptr} {} iterator& operator++() noexcept { node_ = node_->next; return *this; } iterator operator++(int) noexcept { auto cp = *this; ++(*this); return cp; } T& operator*() noexcept { return *(node_->value); } friend bool operator!=(const iterator& a, const iterator& b) noexcept { return a.node_ != b.node_; } }; list() : first_{new node} , last_ {new node} , size_ {0} { first_->next = last_; last_->prev = first_; } ~list() { while(first_) first_ = erase(first_).node_; } iterator insert(iterator pos, T value) { auto* fresh = new node(pos.node_, new T(std::move(value))); ++size_; return iterator{fresh}; } void push_back(T value) { insert(end(), value); } iterator erase(iterator pos) { auto n = pos.node_->next; delete pos.node_; --size_; return iterator{n}; } iterator begin() const noexcept { return first_->next; } iterator end() const noexcept { return last_; } private: node* first_; node* last_; size_t size_; }; int main() { list<int> l; for(auto i = 0; i < 5; ++i) l.push_back(i); for(auto i : l) std::cout << i; }
