C++ 単方向リスト 書いて覚えるための初心者自己中記事

配列の途中の要素を削除して詰める作業は配列には向いていない。

テキストでその効率の悪さを表現するために書かれたコードは、

vectorクラステンプレートの型に関数ポインタを設定。

関数ポインタの型は引数なし、戻り値の型がbool型。

vector配列関数ポインタに入れる関数は実行されるとカウンターが減っていき、０になったらflase を返す。

false の場合にその要素は削除され、後の要素は一つずつ順に手前に代入されていく。

というもののようです。

要素の数が増えたら増えた分だけ処理が増える。

要素数の変化に向いていないという話。

で、向いているのは何かというと

リスト（連結リスト）

だそうです。

配列は一列に順番に並んでいるのに対して、リストはそもそもバラバラに存在しているデータをつないでいる。

このバラバラの１単位をノードという。

ノードの中にはデータと次のノードへのポインタが入っている。

ポインタが無いノードが最後尾。

データを途中に挿入する場合には手前になるノードが持つポインタが、挿入されるノードに向かえばよく、挿入されるノードは割り込まれて一つ後ろにいったノードを指すポインタを持てば解決。

途中のデータを削除して詰める場合も削除されるデータ目線で、手前のデータが持っているポインタを自分ではなく次のデータに向ければOK。

テキストいきなりドバっとコード出てきた。

ちょっとこれも簡単に理解できないな・・・。

少しずつ行こう。

まずノードとは。こういうものらしい。

template <typename TYPE>
struct Node {
	TYPE value;
	Node* next;
};

テンプレートは置いといて、

構造体Node のメンバをみるとvalue はわかる。データ入れるやつね。

次の next は自分の所属している構造体のポインタになっている。

これ、テキストでなんの説明もないんですけど・・・。

調べたら、自己参照構造体というらしい。

さっきまでのノードの話だと、ノードの中身はデータと次のノードのポインタは入っているという話。

そうか、俺はてっきり次のノードのアドレスとかを入れておいて・・・、とか思ってたけど違うのかもしれない。

いや、ポインタだからアドレスなのだろうけど。

データ|

*next   |← データ|

　　　 |　  *next  |← データ|

　　　　　　　　|　  *next  |　← データ|

　　　　　　　　　　　  　|　　*next　 |← データ|

　　　　　　　　　　　　　　　　　　 |　　*next |　←......

こういうことなのか。

 このままだと永久に続いていくのでは・・。

と思ったけどどこかしらの*next に NULL を入れれば止まるようだ。

で、テキストだとこれをクラスのメンバにしている。

template <typename TYPE>
class SList {
public:
	struct Node {
		TYPE value;
		Node* next;
	};
 };

でこの構造体Nodeを実体化させるためにNode構造体のオブジェクトをクラスのメンバ変数に用意している。（合ってるのかな・・？）

template <typename TYPE>
class SList {
public:
	struct Node {
		TYPE value;
		Node* next;
	};
public:
        SList() { m_eol.next = NULL; }
	virtual ~SList() { clear(); }
 
private:
	//リストの端(end of list)を表すノード
	//next に先頭ノードが入れられる
	Node m_eol;
};

 はずなんだけど、注釈を呼んでフリーズ。

next に先頭ノードが入れられると書いてあるのに、リストの端を表すノードとも書いてある。

コンストラクタでm_eol の*next がNULLで初期化されている。

この状態は

m_eol . value    未初期化

m_eol . next　　NULL

の状態？

このままだとまだ分からないけど、先に進めばわかるかもしれない。

template <typename TYPE>
class SList {
public:
	struct Node {
		TYPE value;
		Node* next;
	};
public:
	SList() { m_eol.next = NULL; }
	virtual ~SList() { clear(); }
	//先頭位置に値を挿入
	Node* Unshift(const TYPE& value) {
		return Insert(&m_eol, value);
	}
	//nodeの次の位置にノードを挿入
	Node* Insert(Node* node, const YTPE& value) {
		assert(node != NULL);
		Node* next = new Node();
		next->value = value;
		next->next = node->next;
		return node->next = next;
	}
private:
	//リストの端(end of list)を表すノード
	//next に先頭ノードが入れられる
	Node m_eol;
};

 Unshift関数に値を入れるとInsert関数にその値とm_eol が渡るんだな。

Insert関数ではまず、assertマクロでnode(m_eol)がNULLでなければOKの判定をしている。m_eolってコンストラクタでm_eol.nextにNULL入れてたけど。

一部のメンバがNULLというのと構造体オブジェクトそのものがNULLというのは違うということかな。

で、newであらたにNodeを作っている。のだと思うのだけれどカッコはなんだ・・・？

初期化しているということかな。

新しく作った構造体オブジェクトnext

(同じ名前を使われると混乱するんですけど・・）

この新しいnextのメンバに、引数で渡ってきたデータを入れる。

（参照とかポインタとかだからアドレスを入れるのかな。）

newで作ったnextの valueには初めから引数として渡されてきたvalueを、

newで作ったnextのnext にはコンストラクタでNULLを入れられていたm_eol.nextを。

今の状態は

new で作ったnext

next->value  渡されてきた値

next->next  NULL

 そして最後の行でreturn されているのは

m_eolのnext(NULL) に newで作ったnext を入れている。

つまり最終的には

m_eol.value  未初期化

m_eol.next  ←   next.value(渡ってきた値入り)

                           next.next (NULL)

こんな状態になるのかぁ。

//リストの端(end of list)を表すノード
//next に先頭ノードが入れられる
Node m_eol;

 nextに先頭ノードが入れられる。は分かった。

リストの端とは・・？

end of list ??  front of list ではなくて？

まぁ、それでreturn されて return されて

Node* Unshift(const TYPE& value) {
	return Insert(&m_eol, value);
}

Unshift関数呼び出したところには、引数value が追加されたNodeのポインタが返ってくると。

まだまだ、いろいろ同じようなのがあるぞ・・。

		Node* next;
	};
public:
	SList() { m_eol.next = NULL; }
	virtual ~SList() { clear(); }

	//先頭ノードを取得
	Node* GetFirst() { return m_eol.next; }
	const Node* GetFirst() const{ return m_eol.next; }

	//先頭位置に値を挿入
	Node* Unshift(const TYPE& value) {
		return Insert(&m_eol, value);
	}
	//nodeの次の位置にノードを挿入
	Node* Insert(Node* node, const YTPE& value) {

先頭ノードを取得

これはさっきの勉強でわかるわ。

m_eol.next にはvalue に値の入っている最初のノードがあるから。

よし、つぎ。

//node の次のノードを削除
void EraseNextNode(Node* node) {
	assert(node != NULL);
	Node* next = node->next;
	assert(next != NULL);
	node->next = next->next;
	delete next;
}

これはあれか、引数に渡したノードの次のノードを削除という意味か？

まず、assertマクロを使って渡されてきたnodeをチェック。これはさっきのInsert関数と同じ。

次に、引数で渡されてきたnodeのnextをNodeポインタに渡している。

そしたらNodeポインタ(next)をassertマクロでチェック。

そしたら引数で来たnode->next に さっき取り出したnext->next を渡している。

引数のnodeの次のnodeを用意してそのnodeのさらに次のnodeを引数のnodeのnextに入れている。

最後にさっき作ったNodeポインタをdelete。

なるほど。

//node の次のノードを削除
void EraseNextNode(Node* node) {
	assert(node != NULL);
	Node* next = node->next;
	assert(next != NULL);
	node->next = next->next;
	delete next;
}
//先頭にあるノードを削除
void Shift() {
	EraseNextNode(&m_eol);
}

これはそのままだな。OK。

つぎ、

//全削除
void Clear() {
	Node* next;
	for (Node* node = m_eol.next; node != NULL; node = next) {
		next = node->next;
		delete node;
	}
	m_eol.next = NULL;
}

まず、nextというNodeポインタを作っている。

for文ではnodeというNodeポインタを作りm_eol.next (先頭のノード)を入れている。

そのnodeがNULLになるまでfor文は続ける。

for文の処理は

最初に作ったNodeポインタ next に先頭のノードの次のノード(2番目ってことかな) を入れて、delete で先頭のノードを削除。

その後for文の条件の最後で、とっておいた次のノードをnodeに入れる。

繰り替えてしていけば最後にはNULLのノードが入ってきてfor文終了。

最後にm_eol.nextにNULLを入れたら終了。

よし。OK。

 つぎ

	//i番目の値にアクセス
private:
	const TYPE& At_(int i) const {
		const Node* node = m_eol.next;
		for (int j = 0; j < i; ++j) {
			node = node->next;
		}
		return node->value;
	}

 At_関数

_ って何なんだろうな・・。

まぁいいや。

引数にいれた数値の位置の値をだすのかな。

まず、Nodeポインタ node を作って、m_eol.next(先頭行のノード)をいれる。

次にfor文で引数の数値に達するまで次のノードを受け取る。

でreturn node->value;　

よし。OK。

ん？ _ って何だろうと思ったら下に関係してそうなコードがあるじゃん・・。

public:
	TYPE& AT(int i) { return const_cast<TYPE&>(At_(i)); }
	const TYPE& At(int i)const { return At_(i); }

 なんだこれ・・。

さっきのAt_関数の窓口的なやつかな？

const_castって前に勉強したな

 ～～～～～～

//const_cast の場合
//constを外すキャスト
int main() {
	const int* p;
	int* n;
	n = p;//こっちはpがconstなのでエラー
	n = const_cast<int*>(p); //constを外すキャスト
 
	system("pause");
}

～～～～～～

constを外すキャストか。

 引数にconstがついてたら外してからやるためにって事か。

constついてたら二行目のほうでね。

よし、ノード本体のクラスはここまでだ。

テキストに気になる記述あり、

コピーコンストラクタの実装と

代入演算子オーバーロードは割愛します。

なるほど・・。

コピーコンストラクタも代入演算子オーバーロードの勉強したけど、あれだな、どういうときに必要なのかちゃんとわかってないな。

あれだっけ、コピーコンストラクタはクラスを引数にするときに参照とかで受け取るからアドレスが本体のままでやばいから(関数の終わりでデストラクタでが本体のアドレスを消しちゃうから)、コピーコンストラクタ内の処理で別の場所に作ったメモリ領域に内容をコピーするんだっけ？

とするとこれの場合はどの関数で必要になるんだ？

//nodeの次の位置にノードを挿入
Node* Insert(Node* node, const YTPE& value) {
	assert(node != NULL);
	Node* next = new Node();
	next->value = value;
	next->next = node->next;
	return node->next = next;
}

 コレの場合って、引数でNode* node なのですが、

渡ってきたnodeって

node->value  のアドレス

node->next 　次のノードのアドレス？

仮にnode->value のアドレスに有る値を別の場所にコピーしたとして、

node->next はどうなるんだ・・・？

 なんかこのままでもエラーにならないから必要ないのでは・・？

まあ、うん。

このリストの場合、次のノードへはnextから行けるけれども

前のノードに行くすべがありません。

一方通行です。

これを単方向リストと言います。

 双方向リストは次へ持ち越し。

ここまで。