C++ イテレータとアルゴリズム 書いて覚えるための初心者自己中記事

前回までは単方向・双方向の循環リストとノードの勉強をした。

nenechi.hatenablog.com

この時、ノードの操作はfor文の条件式内で結構むき出しで行われていた。

for (const Node* node = head; node != eol; node = node->*dir) {
	cout << node->value << ' ';
}

これを演算子オーバーロードですっきり分かりやすい操作が出来るようにする。

typedef DList<int> List;
typedef List::Node Node;
 
class Iterator {
public:
	Iterator(const Node* node) :m_node(node) {}
protected:
	const Node* m_node;//現在のノード
};

クラスIterator を作ります。こういう目的のクラスをイテレータというのでしょうか。

コンストラクタではノードを受け取りイテレータクラスのメンバ変数として保存しています。このノードが基準になるんですね。

//現在のノードを取得
int operator*() { return m_node->value; }

イテレータクラスにまずこれ、*をオーバーロード。

これはつまり、イテレータクラスのオブジェクトを作ってそのオブジェクトに*を付けたら、ノードのvalue が返ってくるということですね。

//違うノードを指しているか判定
bool operator!=(const Iterator& other)const {
	return m_node != other.m_node;
}

なるほど、これは別のイテレータと比較するのに != を使えるようにオーバーロードしたんですね。

//次のノードに進む
void operator++() { m_node = m_node->next; }

イテレータオブジェクトに++ を付ければ次のノードになる。

void Show(Iterator begin, Iterator end) {
	for (Iterator it = begin; it != end; ++it) {
		cout << *it << ' ';
	}
	cout << endl;
}

Show関数はグローバル名前空間に置かれてマス。

さっきイテレータクラスでオーバーロードした演算子が使われている。

非常に見やすくなりました。

int main() {
	List list;
	for (int i = 0; i < 5; ++i) {
		list.Push(i);
	}
	Show(Iterator(list.GetFirst()), Iterator(list.Eol()));
 
system("pause");
}

ややこしいなぁ。

とりあえず理解できた。

ポインタのように扱えるようになるクラスをイテレータというそうです。

おっと次のページが理解できない。

えっと、Show関数はまるでIterator というのがポインタ型をtypedef したものであるかのようなコードに見える。

？？？

あぁ、ただ、普通のポインタでもそのまま使える内容ですと言いたかったのか。

Show関数を関数テンプレートにすればできるぞ！って言っている。

template <typename TYPE>
void Show(TYPE begin, TYPE end) {
	for (TYPE it = begin; it != end; ++it) {
		cout << *it << ' ';
	}
	cout << endl;
}

Show<Iterator>(Iterator(list.GetFirst()), Iterator(list.Eol()));

 こういうことか！

 確かに動いた！

お？

ポインタのように振舞うクラスを

イテレータクラス

と言います。

はい。

vectorクラステンプレートと同じながれだ、

ノード管理をイテレータを使って行えるlist というクラステンプレートが標準で用意されている。

えっと、このlist というクラステンプレートはどうやって使うんんだ？

ノード構造体がメンバにいるクラスは自分で用意するのかな。

そのクラスにいろいろノードの操作するメンバ関数も書いてたけど。

それは必要なのかな。

え、全然わからない。

しらべた。

なんかあれだ、vector の友達だ。

どっちも配列のクラステンプレートっていうだけの話なんだね。

vector は配列で行っているからランダムアクセスに強い。要素の増減に弱い。

listはノードで行っているからランダムアクセスに弱い。要素の増減に強い。

処理内容に合わせて向いてるほうを選ぼう。的なかんじ。

少しでも慣れるために書いてみた

list<int> data(10,3);//vectorと同じ引数の使い方
cout << *data.begin() << endl;//リストの先頭要素を表すイテレータ
data.end();//終端を表すイテレータ（ダミーノード）
 
list<int>::iterator now = data.begin();//イテレータを取り出したところ
++now;//イテレータの位置を変えた
cout << *data.insert(now, 333) << endl;//指定したイテレータの位置に値を挿入
 
list<int> insert_data(3, 777);//挿入用のリストを作った
data.insert(now, insert_data.begin(), insert_data.end());//指定位置にリスト挿入
 
data.erase(now);//指定位置の要素削除
list<int>::iterator end = data.end();//終端ノード（ダミーノード）
data.erase(data.begin(), --end);//指定範囲の要素削除
 
 
system("pause");
list<int>::iterator node = data.begin();
data.push_back(2);
data.push_back(3);
data.push_back(4);
data.push_back(5);
 
list<int> insert_data2(4, 2222);
data.splice(++node, insert_data2);//第一引数の位置に別のリストを接続
data.sort();//リストの内容をソート（すごい）
node = data.begin();
list<int>::iterator nend = data.end();
 
for (; node != nend; ++node) {
	cout << " : " << *node << endl;
}
system("pause");
 
cout << data.front() << endl;//最初の要素への参照
cout << data.back() << endl;//最後の要素への参照
cout << data.size() << endl;//リストの要素数
data.resize(15);//要素数の変更
data.clear();//リスト全削除
cout << data.empty() << endl;//リストの要素が０かどうかbool
data.push_front(1);//リストの最初に追加
data.push_back(3);//リストの最後に追加
data.pop_front();//リストの最初の要素削除
data.pop_back();//リストの最後の要素削除

 あとイテレータを使える関数テンプレート

bool test(const int a) {
	return a == 777;
};
 
int main() {
 
#define itera list<int>::iterator
	//イテレータを引数にとれる関数テンプレート
	list<int> data(20);//空要素２０個
 
	itera f = data.begin();
	itera e = data.end();
 
	fill(f, e, 333);//範囲内を第三引数の値で埋める
	cout << *fill_n(f, 5, 444) << endl;//第一引数から第二引数分の範囲を第三引数の値で埋める　戻り値Outiterator
 
	list<int> cpydata(0);//コピー用
	cpydata.push_back(777);
	cpydata.push_back(888);
	cpydata.push_back(999);
	copy(cpydata.begin(), cpydata.end(), f);//第一～第二引数の範囲を第三引数の位置に正順でコピーする（上書き）
	copy_backward(cpydata.begin(), cpydata.end(), e);//第一～第二引数の範囲を第三引数の位置に逆順(並びはそのまま)でコピーする（上書き）
 
	//sort(f, e);//エラーになる　ちょっとよくわからない
	stable_sort(f, e);//安定ソート（同じ値を持つ要素同士の前後関係が保たれる
 
	cout << *find(f, e, 777) << endl;//第一～第二引数の範囲で第三引数を探してノード（イテレータ）を返す
	cout << *find_if(f, e, test) << endl;//第一～第二引数の範囲で第三引数に渡したらtrueを返すノード（イテレータ）をさがして返す
	//見つからなかった場合は第二引数が返される
 
	cout << binary_search(f, e, 888) << endl;//ソートされたリストに使う高速サーチ　戻り値bool
	//sortでもだけど、引数Compare comp がよくわからない
 
	random_shuffle(data.begin(), data.end());//エラーになる。まだ手に負えない。
 
	f = data.begin();
	e = data.end();
	for (int i = 1; f != e; ++f, ++i) {
		printf("%2d : %3d | ", i, *f);
		if (i % 5 == 0) { cout << endl; }
	}
	cout << endl;
 
system("pause");
}

 エラーになるのが２つくらいあったけど、ちょっとまだ手に負えない。

いずれ。

おぉ、関数の型とかで何だろうと思っていたのが次のページにのってたし。

イテレータにも種類があってそれぞれで演算子オーバーロードに差異があるらしい！

なぜ！！

InIterator ( 入力イテレータ )

* による値の取得

++

OutIterator ( 出力イテレータ )

* による代入

++

FwdIterator ( 前進イテレータ )

* による値の取得と代入

++

BiIterator ( 双方向イテレータ )

* による値の取得と代入

++

--

RAIterator ( ランダムアクセスイテレータ )

ポインタと同じ演算がすべて可能

すっきりした。

関数テンプレートでエラーになったのは

RAIterator ( ランダムアクセスイテレータ )の奴だった。

list クラステンプレートのイテレータは

双方向イテレータ　BiIterator なのか。

でも同じRAIterator の stable_sort関数テンプレートは使えたんだけど。

 なぜだ？

vector や list などの複数のデータを統括するクラステンプレートを

コンテナ

というそう。

 これらのコンテナやそれを扱うアルゴリズムはテンプレートとして提供されていて、

標準テンプレートライブラリ( STL ) (standard template library)

と言います。

ここまで。