ロベールのC++入門講座でC++を初歩から入門する(8日目)

前回からだいぶ間が空いたけど、今日で終わらせる！
てかすでに読み終わっていて、例題が解けてなかっただけだけど。

15章 データ構造

リスト、スタック、キューなどのアルゴリズム、イテレータなど。

双方向リスト。STL listを使ってテスト。

/**
 * @file List.cpp
 */
#include <iostream>
#include <list>
using namespace std;

static const int DIR_FORWARD = 0;
static const int DIR_BACKWARD = 1;

template <typename T>
void Show(list<T>& lst, int dir = DIR_FORWARD) {
	typename list<T>::iterator itr;
	typename list<T>::iterator begin = lst.begin();
	typename list<T>::iterator end = lst.end();

	if (dir == DIR_BACKWARD) {
		for (--(itr = end); ; --itr) {
			cout << *itr << ' ';
			if (itr == begin) break;
		}
	} else {
		for (itr = begin; itr != end; ++itr) {
			cout << *itr << ' ';
		}
	}
	cout << endl;
}

int main() {
	list<int> lst;

	for (int i = 0; i < 5; ++i) lst.push_back(i);
	Show(lst);
	Show(lst, DIR_BACKWARD);

	for (int i = 5; i < 10; ++i) lst.push_front(i);
	Show(lst);

	lst.pop_back();
	lst.pop_back();
	lst.pop_front();
	Show(lst);

	return 0;
}

% ./List
0 1 2 3 4 
4 3 2 1 0 
9 8 7 6 5 0 1 2 3 4 
8 7 6 5 0 1 2 

スタックについて。STL stackは無限に積めるみたいなので、数に限りができるようSTL stackにwrapしてみる。

/**
 * @file Stack.cpp
 */
#include <iostream>
#include <stack>
#include <stdexcept>
using namespace std;

template <typename T>
class Stack
{
public:
	explicit Stack(size_t max) : max_(max), count_(0) {};
	virtual ~Stack() {};

	void Push(const T& value) {
		if (Full()) {
			throw std::overflow_error("stack overflow !!");
		}
		++count_;
		stck_.push(value);
	}
	void Pop() {
		if (Empty()) {
			throw std::underflow_error("stack empty !!");
		}
		--count_;
		stck_.pop();
	}
	T Top() const {
		if (Empty()) {
			throw std::underflow_error("stack empty !!");
		}
		return stck_.top();
	}
	bool Full() const {
		return count_ >= max_;
	}
	bool Empty() const {
		return count_ == 0;
	}

private:
	size_t max_;
	size_t count_;
	stack<T> stck_;
};

int main() {
	Stack<int> stck(10);

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

	while (!stck.Empty()) {
		cout << stck.Top() << ' ';
		stck.Pop();
	}
	cout << endl;

	return 0;
}

% ./Stack
stack overflow !!
9 8 7 6 5 4 3 2 1 0 

ちなみにウェブで調べていて気づいたけど、Cと違ってC++では前置インクリメント(++i)と後置インクリメント(i++)では異なる処理が走る。特別な事情がなければ、前置インクリメントの方が処理効率はよいのでおすすめ。

placement new。new(アドレス)とすると、指定したメモリを使ってコンストラクタを呼ぶことができる。色々と使えそう。

再帰関数きた！これはちゃんと分かった。

ツリー構造、こういうの好きだわ。試しに書いてみる。

/**
 * @file Tree.cpp
 */
#include <iostream>
#include <list>
#include <iomanip>
using namespace std;

template <typename T>
class Tree
{
public:
	struct Node {
		T value;
		list<Node*> children;
		Node(const T& value) : value(value) {};
	};

	explicit Tree(const T& value) {
		root_ = new Node(value);
	}
	virtual ~Tree() {
		ClearRecursive(root_);
		cout << "delete : " << root_->value << endl;
		delete root_;
	}
	Node* GetRoot() const {
		return root_;
	}
	static Node* Append(Node *node, const T& value) {
		Node* child = new Node(value);
		node->children.push_back(child);
		return child;
	}
	void Dump() const {
		DumpRecursive(root_);
	}

private:
	Node* root_;

	void ClearRecursive(Node* node) {
		list<Node*>& children = node->children;
		typename list<Node*>::iterator itr = children.begin();
		for (; itr != children.end(); ++itr) {
			ClearRecursive(*itr);
		}
		children.clear(); // リスト内の全ての要素を削除

		// root nodeはdeleteしない
		if (node != root_) {
			cout << "delete : " << node->value << endl;
			delete node;
		}
	}

	void DumpRecursive(Node *node, int depth = 0) const {
		cout << setw(depth*4) << " " << node->value << endl;

		list<Node*>& children = node->children;
		typename list<Node*>::iterator itr = children.begin();
		for (; itr != children.end(); ++itr) {
			DumpRecursive(*itr, depth + 1);
		}
	}
};


int main() {
	Tree<string> tree("foo");

	Tree<string>::Node* foo = tree.GetRoot();
	Tree<string>::Node* bar = tree.Append(foo, "bar");
	Tree<string>::Node* baz = tree.Append(foo, "baz");

	tree.Append(bar, "bar.hpp");
	tree.Append(bar, "bar.cpp");

	tree.Append(baz, "baz.hpp");
	tree.Append(baz, "baz.cpp");

	tree.Append(foo, "README");

	tree.Dump();

	return 0;
}

% ./Tree
./Tree
 foo
    bar
        bar.hpp
        bar.cpp
    baz
        baz.hpp
        baz.cpp
    README
delete : bar.hpp
delete : bar.cpp
delete : bar
delete : baz.hpp
delete : baz.cpp
delete : baz
delete : README
delete : foo

ツリーの走査は再帰関数を使うのがミソ。

続いて二分木。

/**
 * @file BinTree.cpp
 */
#include <iostream>
#include <iomanip>
using namespace std;

template <typename KEY_T, typename VAL_T>
class BinTree
{
	struct Node {
		KEY_T key;
		VAL_T value;
		Node* left;
		Node* right;
		Node(const KEY_T& key) : key(key), left(NULL), right(NULL) {}
	};

public:
	explicit BinTree() { root_ = NULL; }
	virtual ~BinTree() {
		ClearRecursive(root_);
	}

	Node*& Append(KEY_T key, VAL_T value) {
		Node*& node = FindNode(root_, key);
		if (node == NULL) {
			node = new Node(key);
		}
		node->value = value;
		return node;
	}

	void Dump() const {
		DumpRecursive(root_);
	}

private:
	Node* root_;

	Node*& FindNode(Node*& node, KEY_T key) {
		if (node == NULL) return node;

		if (key < node->key) return FindNode(node->left, key);
		else if (node->key < key) return FindNode(node->right, key);
		else return node; // node->key == key 
	}

	void ClearRecursive(const Node* node) {
		if (node == NULL) return;
		
		if (node->left != NULL) ClearRecursive(node->left);
		if (node->right != NULL) ClearRecursive(node->right);
		cout << "delete : " << node->key << endl;
		delete node;
	}

	void DumpRecursive(const Node* node, int depth = 0) const {
		if (node == NULL) return;
		cout << setw(depth*4) << " "
			 << node->key << "(" << node->value << ")" << endl;

		if (node->left != NULL) DumpRecursive(node->left, depth + 1);
		if (node->right != NULL) DumpRecursive(node->right, depth + 1);
	}
};


int main() {
	BinTree<string, int> yankees;

	yankees.Append("Ichiro", 31);
	yankees.Append("Jeter", 2);
	yankees.Append("Cano", 24);
	yankees.Append("Teixeira", 25);
	yankees.Append("Granderson", 14);
	yankees.Append("Nix", 17);
	yankees.Append("Chavez", 12);
	yankees.Append("A.Jones", 22);
	yankees.Append("Martin", 55);

	yankees.Dump();

	return 0;
}

./BinTree
 Ichiro(31)
    Cano(24)
        A.Jones(22)
        Granderson(14)
            Chavez(12)
    Jeter(2)
        Teixeira(25)
            Nix(17)
                Martin(55)
delete : A.Jones
delete : Chavez
delete : Granderson
delete : Cano
delete : Martin
delete : Nix
delete : Teixeira
delete : Jeter
delete : Ichiro

ポインタ変数の参照、便利すぎる！勉強になりました。テキストの例題では[]演算子をオーバーロードして連想配列を実装している。

16章 C++の落ち穂拾い

C++の比較的マニアックな事項について。でもこういうのがCでは割と当たり前だったり。

• 共用体(union)
• 無名構造体(unnamed structure)
• ビットフィールド
• 可変長配列メンバ
  • Cならreallocで代用？
• コンマ演算子
• トークン演算子##、文字列化演算子#
  • 僕の場合、デバッグ用のマクロ定義で大活躍してます
• 配列へのポインタ
• extern "C"
• volatile
• set_terminate

Cでは当たり前というより、商品向けソフトとか組み込みの世界では当たり前というだけかも。

付録

充実してます。特に「CとC++の重要な相違点」が勉強になる。てかC99ちゃんとわかってねぇ。。。
Boostはまたどこかで勉強する。

感想

長かったけど無事に読み終わりました！というわけで、感想。

とにかく丁寧。読んでわからないということはない。例題を写して動かせば必ずわかるようにできている。これはすごく難しい気がします。ある意味Head Firstシリーズにも近いけど、もっとぐっと丁寧にした感じ。これを超えるC++の入門書はなかなか難しいんじゃないかな。

読む前にCの基礎的な知識はあった方がよいと思う。なくても理解できるようには配慮されているけど、それでも例えば出てくる用語の全てががわかりやすく解説されている訳ではないので。逆に僕みたいにCは普通に使えるんだけど、C++て何？て人にはもってこいだと思う。まあ実際のユースケースとしては、C++で実装する場合はCも分かってないと使えないと思うので、プログラミング初級者の場合、前もってCをさらっと他の本で勉強しておくことをおすすめします。（CなんてC++と
比べたら1/5位の勉強量で習得できると思うし。言い過ぎ？）

id:higeponさんもブログで書いているけど、この本はオブジェクト指向の入門書ではないので、それが勉強したいのであれば他の本がいいと思います。個人的にはオブジェクト指向はC++以外で勉強する方がいいかも。RubyとかObjective-CとかJavaとか。あんまり言うとボロが出るのでやめてときます(笑)

とにかく、読むのに時間はかかりましたが、得られるものも大きいです。投資回収は余裕でできそう。ヘタな入門書を行ったりきたりするよりは本書でガツンと勉強した方がずっと効率的だと思います。というわけで個人的には超おすすめしたいと思います^^