C++ スタックとキュー　書いて覚えるための初心者自己中記事 - C++ ⇒ VBA 書いて覚えるための初心者自己中記事

リストの先頭と末尾だけ操作できれば十分、といった状況では多機能なリストを使わないほうがいい場合があるらしい。

そんな時にじゃあどうするのか。という話。

リストのデータを順に処理するような場合

先に入れた順に先に出すのを

FIFO First in First out

この性質をもったデータ構造を

キュー　queue

後に入れた順に先に出す

LIFO Last in First out

この性質をもったデータ構造を

スタック　stack

という。

スタックは本を積み重ねて上からとっていくイメージ

要素数固定でやるのが前提。

スタックを配列で行うには。

要素の最大サイズ

現在のサイズ（積みあがったサイズ）

配列

この三つのメンバ変数で可能。

現在のサイズの要素に新しくデータを入れる。

現在のサイズを１増やす。

現在のサイズのデータを取り出す。

現在のサイズのを１減らす。

といった感じ。

キューを配列で行うには。

キューは先入れ先出しなので、そのまま考えると配列の先頭要素から削除して

後続の要素を手前にずらさなければならない。

しかし、それはしない。

要素の最大サイズ

現在のデータの個数

現在の先頭の位置

配列

をつかい、

削除された要素の次の要素番号が先頭位置になるようにする。

追加されるデータは、現在の先頭位置 + データの個数の位置に入れられる。

配列の最大要素番号まで来てしまったら、０要素番号に行く。

最大要素数のなかで、ぐるぐる回る。

これをリングバッファという。

このリングバッファは、先頭から順に追加したり、末尾から値を取り出したりもできるようになります。

こういったデータ構造を両端キューと呼びます。

これまで勉強した

キュー

スタック

両端キュー

はクラステンプレートが標準で用意されている。

それぞれ

queue

stack

deque

ヘッダファイルは同名

メンバ関数は

データを追加するpush

データを削除するpop

順番が来たデータの参照は

queue が front あとback

stack が top

他にはsize empty

くらいらしい。

deque は別格感がある。

[ ] 演算子を使ったアクセスも可能。

push_front

push_back

pop_front

pop_back

insert

erase

イテレータはランダムアクセスイテレータ

別格！！

queueとstack はイテレータ持ってない。

つぎ、

キューやスタックを標準クラステンプレートを使わない場合の話かな？

自分でキューやスタックのコードを作る場合に、コンストラクタでは配列の要素数を指定して

m_array = new TYPE[sizeMax];

new で動的に配列のアドレスを確保している。

で、テキストだとこれは問題があると言っていて、

TYPEがデフォルトコンストラクタを持たないクラスだった場合に使えない。

配列型のnewだとコンストラクタに引数を指定できないのでコンパイルエラーになってしまう。

と書いてある。

えーと。

何か引数付きコンストラクタがあるクラスを作って、そのクラスを型に指定してキューやスタックを作る場合って事でいいのかな？

stack<classA(引数)> n;

こんな風に出来ないと言っているのか？

また、デフォルトコンストラクタがあるクラスなら良いのかというとそうでもなくて、

全く使わないかもしれないオブジェクトまで初期化するのは無駄だと書いてある。

？？？

使わないかもしれないオブジェクトっていうのは、例えば100要素のスタックを作ったけど30要素しか使わなかったから残りの70要素のオブジェクトの初期化は無駄だったね。って事かな？

あとpopしたときにデストラクタが呼ばれないのも嫌だと書いている。

そうか、popしたときにその要素の中身が消されるけど、その時に型が消されるわけではないからデストラクタが呼ばれるわけでは無いということなのかもしれない・・・。

教本なんだから、知ってる人同士で会話するような説明は困る・・。

もっと優しくして。

とにかくクラスをTYPEに指定するのはよろしくないと言いたいのかな。

そうだと仮定してテキストを進めよう。

えー、この問題を回避するには

メモリは確保するけどコンストラクタは呼ばない。

pushするときにはじめて(コピー)コンストラクタを呼ぶ。

popするときにデストラクタを呼ぶ。

この三点を実現すればいい。

なるほど。

メモリを確保（コンストラクタ呼ばない）

これは、同サイズのchar配列としてメモリを確保する。

例えばこんなのはどうでしょう？

ってかんじでこんなコード登場

void* p = new char[sizeof(Hoge)];
static_cast<Hoge*>(p)->Hoge(hoge);

１行目は理解できる。多分Hoge はクラスのことなんだと思う。

new char の要素数がHogeクラスのサイズになっているんだろう。

それを何でも入るvoidポインタへ。

２行目はなんだ・・？

ポインタをHogeクラスのポインタへキャストして引数付きHogeコンストラクタを呼ぼうとしているのか。

テキストには続けて、コンストラクタは直接呼べないようになっているためコンパイルエラーになると書いてある。

これはダメなんだ。

new演算子を使うと出来ると書いてあり、

通常は

new Hoge(hoge)

とすれば新しくメモリを確保してコンストラクタHoge(hoge) を呼ぼうとする。

ここで新しくメモリ確保ではなく既存のメモリ領域を指定することが出来る

Hoge* pHoge = new(p) Hoge(hoge);

と書いてある。

ちょっと気になったんだけど、

new Hoge(hoge)

赤字の部分はコンストラクタなの？

クラス名（引数）

という認識だったんだけど、さっきの言い方だとコンストラクタっぽい言い方。・・・。

あとこのコードはさっきの２行目の部分の代わりということで良いのかな？

１行目のvoidポインタのくだりは有効なんだよね・・？

とにかく、new の後に確保済みアドレス領域を指定して使用することが出来る。

これはコンストラクタ呼ぼうとしているからpush の話なのかな？

このような既存のメモリ領域を使ったnew を

placement new　（placement == 配置）

と言います。

やばいテキストがさらに加速してる

inline void* operator new(size_t, void* p)throw() {
	return p;
}

これでplacement newは実現できるらしい。

まず、演算子をオーバーロードした場合普通はそのoperatorが呼ばれるだけ。

しかし、new と delete は違うそうで、operator new がまず呼ばれて返されたアドレスを使ってコンストラクタが呼ばれる。

delete の場合はデストラクタが呼ばれて、そのあとでoperator delete が呼ばれる。

うん、それは分かった。

で、第一引数には確保するメモリのバイト数が渡ってくる。

？？

普通はこのサイズを使ってnew以外のものを使ってメモリを確保して、そのアドレスを返す。

？？？？？？？？

そうすると確保されたメモリを使ってコンストラクタが呼ばれる。

第二引数以降（？？）にはnewの実引数が渡されてきます。？？

・・・・あ、

new と operator new で言葉を使い分けてる。

もう一回意識して読んでみよう。

いや、そうか、そもそも勘違いがあるんだ。

operator new の話だからオーバーロードの事だと思い込んでたけど、operator new でオーバーロード出来るということはもともとoperator new はあるんだ。ほかの演算子オーバーロードもそうだ。

あー、もともとのoperator new の引数に void* p を追加したということか。

で本来はoperator new の中で(?)メモリ領域を確保してそのアドレスを返すところなのに、追加した引数void* p をそのまま返してるということか。

new が使われたらoperator new が呼ばれて返ってきたアドレスでコンストラクタを呼ぶから、operator newはvoid* pをそのまま返せばいいということか。

inline void operator delete(void*, void*) throw() {}
delete(p)pHoge;

delete演算子をオーバーロードしたときも第一引数にはオブジェクトのメモリアドレスが渡されてくる。もうこれはそういうものだ。

第二引数以降はオーバーロードしたoperator new に合わせる。

これを placement delete というそうだ。

ただし、operator delete をオーバーロードした場合

operator delete(pHoge, p);

こう呼ぶ必要があるらしい。

しかしこの呼び方だとデストラクタが呼ばれないらしい。

なので

pHoge-> =~Hoge();
operator delete(pHoge, p);

直接呼ぶらしい。

コンストラクタと違ってデストラクタは直接呼べるらしい。

さらに、delete と newでオーバーロードしたoperator の引数は合わせなければならないらしいけど、必ず使わなければならないわけでは無いらしい。

なので

pHoge-> =~Hoge();

これだけでOKだそうです。

で、実装すると、

わけわからんので少しずつ・・・

class Hoge {
public:
	explicit Hoge(int n) :m_n(n) {}
	int Get() const { return m_n; }
	
private:
	int m_n;
};

最初にスタックに使いたいクラスHoge

コンストラクタが引数付き

Get関数でメンバ変数m_nを返す。

これは大丈夫。

次。

template<typename TYPE>
class Stack {
public:
	//コンストラクタ
	explicit Stack(size_t sizeMax) :m_sizeMax(sizeMax), m_size(0) {
		m_array = new char[m_sizeMax * sizeof(TYPE)];
	}
	//デストラクタ
	virtual ~Stack() {
		Clear();
		delete[] m_array;
	}

private:
	char* m_array; //スタック
	size_t m_sizeMax; //スタックの最大サイズ
	size_t m_size;//現在のサイズ
};

スタックのクラスstack

コンストラクタで要素の数を貰ってm_sizeMaxに入れる。

m_sizeを０で初期化、でchar型ポインタ m_arrayに対してnew演算子を使って

入れたいクラスのサイズ×送られてきた要素数をかけたもの（必要なサイズ）

を持ったcharを作ってアドレスを渡す。

この状態は

m_array charポインタ(使いたいクラスのサイズ×要素数、のメモリ領域)

m_sizeMax 要素の最大サイズ

m_size 現在の使っている要素数(0)

の状態。

今の状態だとHogeクラスのコンストラクタで必要な引数とかはいらない。

Hogeのコンストラクタを呼ばれていないしHogeオブジェクトも作られていない。と。

	//スタックが一杯かどうかチェック
	bool Full() const { return m_size == m_sizeMax; }
	//スタックが空かどうかチェック
	bool Empty() const { return m_size == 0; }
private:
	//スタックが一杯だと例外を投げる
	void CheckOverflow() const {
		if (Full()) {
			throw overflow_error("スタックオーバーフロー");
		}
	}
	//スタックが空だと例外を投げる
	void CheckUnderflow() const {
		if (Empty()) {
			throw underflow_error("スタックが空です");
		}
	}

スタックを操作する際に必要なチェックまわり

メンバ関数Fullとメンバ関数Emptyはそれぞれ

m_sizeMax

m_size

を使って現在のスタックの要素数が上限一杯か、それとも0かを判定している。

それを使って

Checkoverflow

CheckUnderflow

は例外を投げる。

よし、次。

private:
	//i番目の要素への参照を取得
	const TYPE& GetAt_(size_t i) const {
		return reinterpret_cast<const TYPE&> (m_array[i * sizeof(TYPE)]);
	}
 
	TYPE& GetAt(size_t i) { return const_cast<TYPE&>(GetAt_(i)); }
	const TYPE& GetAt(size_t i) const { return GetAt_(i); }

GetAt関数では要素の番号を受け取る。

それを使って、m_arrayのアドレス領域で要素番号とTYPE(Hogeクラス)のサイズをかけて、送られてきた要素番号が、あらかじめ領域を確保していたcharポインタm_arrayのどの位置からなのかを導き出している。

m_arrayはcharポインタ

それをreinterpret_cast（ポインタや参照がかかわる強引な型変換）

でTYPE(Hogeクラス)の参照に変換している。

むむ、つまりm_arrayで、求められた要素のアドレスをだして

そのアドレスから始まるのはHogeクラスだよってしてるのか。

そしてそのTYPE(Hoge)の参照を返す。

GetAt関数は引数に要素番号を指定すると、そのアドレス位置から始まるTYPEの参照を返してくれるということか。

うん、次。

public:
	//一番上にデータを積む
	void Push(const TYPE& value) {
		CheckOverflow();
		new(&GetAt(m_size)) TYPE(value);
		++m_size;
	}

メンバ関数pushはTYPEの参照で値を受け取る・・？

ちょっと飲み込めない。

CheckOverflow関数でスタックの要素数が一杯になっていないか確認する。

ここでnew登場。

newの引数にはさっきGetAt関数でキャストしたTYPE型のメモリ領域を指定。

newで作る型はTYPE(送られてきた引数)を指定。

この、アドレス領域を指定するnew演算子で呼び出されるoperator new がplacement newということか？

こうすれば、Stackクラスのコンストラクタであらかじめ確保していたメモリ領域から必要な部分だけを使ってTYPE型に引数を持たせてnewが行えるということで良いんだろうか。

最後にm_sizeを１増やして完了。

難しい。

次。

//一番上に積まれたデータを削除
void Pop() {
	CheckUnderflow();
	--m_size;
	GetAt(m_size).~TYPE();
}

こんどはデストラクタだな。

メンバ関数Popでは最初にCheckUnderflow関数でスタックの要素が０でないか確認。

その後m_sizeを１減らして。

GetAt関数にm_sizeを指定する。実際の要素数とインデックスは１ずれるからこれでいいのか。で操作したい要素番号のアドレスがTYPE参照で返ってくるから、そのTYPEのデストラクタを呼ぶ。と。今回はHogeクラスのデストラクタね。

なるほど。

次、

	//一番上に積まれたデータを参照への参照を取得
private:
	const TYPE& Top_() const {
		CheckUnderflow();
		return GetAt(m_size - 1);
	}
 
public:
	TYPE& Top() { return const_cast<TYPE&>(Top_()); }
	const TYPE& Top() const { return Top_(); }

StackオブジェクトでTopメンバ関数を使って、中のTYPE参照が返ってくる。つぎ、

//全消去
void Clear() {
	while (m_size > 0) {
		Pop();
	}
}

メンバ関数Clearを使うと、m_sizeが０になるまでPop関数（一番上に積まれたデータを削除）を使うと。

次、

あ、Stackクラスはこれで終わりだ。

1つずつの意味は理解できた、でも実際に引数を送る感覚がわからないからmain関数内の処理も確認しよう。

int main() {
	Stack<Hoge> stack(10);

最初にStackを作る。

Stackのコンストラクタはこうだったから

template<typename TYPE>
class Stack {
public:
	//コンストラクタ
	explicit Stack(size_t sizeMax) :m_sizeMax(sizeMax), m_size(0) {
		m_array = new char[m_sizeMax * sizeof(TYPE)];
	}

templateなのでStack<型指定>でオブジェクト名(引数)

うん、これでStackオブジェクト（アドレス領域確保）が出来た。

ここでの<型指定>はまだ、型のサイズを知るためにしか使われていないんだな。

つぎ、

try {
	for (int i = 0; i < 20; ++i) {
		stack.Push(Hoge(i));
	}
}
catch (const overflow_error& e) {
	cerr << e.what() << endl;
}

Push関数の引数で

メンバ関数pushはTYPEの参照で値を受け取る・・？

ちょっと飲み込めない。

と書いてたところだな。下にPush関数。

void Push(const TYPE& value) {
	CheckOverflow();
	new(&GetAt(m_size)) TYPE(value);
	++m_size;
}

TYPE(Hoge)の初期化を行うようにするのか。

Stackオブジェクトを作るときにTYPEをHogeで指定したけど、ここでHoge(i)じゃなくて違うクラスを使ったらエラーになりそう。あ、でもサイズが同じクラスなら行けたりするんじゃないかな。あ、でも構造体やらクラスやらはパディングをとるアライメントだっけ？があるから危ないのかな。

でもメンバ変数が１個だけでメンバ関数がいろいろとかだと行けるのかな。

まぁ、いい。

for (int i = 0; i < 20; ++i) {
	stack.Push(Hoge(i));

スタックに１～順にした引数でHogeを初期化していくのか。

i が１０になったらCheckOverflowで例外が投げられるからそこで終了。

したでcatchするわけね。

次、

while (!stack.Empty()) {
	cout << stack.Top().Get() << ' ' << flush;
	stack.Pop();
}
cout << endl;

Empty関数はm_sizeが０かどうかの判定だった。

要素があった場合に、

Top().Get() ・・・。なんだっけ？

あ、Top()は一番上に積まれた要素をTYPE参照で返すのか、でTYPE参照だからTYPE(Hoge)のメンバ関数Getが使えるのか。

そうか、スタックにクラスを入れると、中身を見るときにはクラスのメンバ関数を使ってみるのか。

で、中身見たらPop関数で削除ね。

よし。わかった。

１から自分で作れと言われたら無理だね！

いろいろ勉強していったら自然と身についていてくれると願おう。

placement new に関しては珍しくテキストが意味不明。

別の本で勉強したほうがいいかな。

ここまで。