独自イテレータの実装方法を解説します。
次のような文字列コンテナを例に、イテレータ(反復子)の作成方法を解説していきます。
// 範囲ベースfor文
for (char c : String{"abc"})
printf("%c, ", c); // 出力: "a, b, c, "
// イテレータによる手動での逐次処理
String s = {"abc"};
for (Iterator ite = s.begin(), end = s.end(); ite != end; ++ite)
printf("%c, ", *ite); // 出力: "a, b, c, "
文字列コンテナ(String
)は単純にC言語文字列をラップしたクラスとして宣言します。
struct String {
const char* s;
};
目次
イテレータの作成
C++でのイテレータはポインタを模した形で実装される点が特徴です。ポインタ演算を実現するためにクラス側で複数の演算子オーバーロードが必要になります。
struct Iterator {
const char* p;
const char& operator*() { return *p; }
Iterator& operator++() { ++p; return *this; }
bool operator!=(const Iterator& v) { return p != v.p; }
};
クラス側では主に以下の3つの演算子オーバーロードが必要になります。
演算子 | 意味 | 目的 |
---|---|---|
T& operator*() | 間接参照演算子 | イテレータが指す値を取得 |
Iterator& operator++() | インクリメント | イテレータを進める |
bool operator!=() | 比較演算子 | イテレータの不一致を判定 |
型T
には各自コンテナの要素型を指定します。
イテレータの内部表現には通常、インデックスやポインタのアドレスを使用することがほとんどです。今回はポインタのアドレスを活用しています(const char* p;
)。
なおインデックスを用いる場合は、参照先の配列やポインタ、またはコンテナクラスの参照をセットで管理する必要があります(例: struct { int index; char* array; }
)。
コンテナの作成
コンテナクラス側では、イテレータを取得するためのメンバ関数を2つ実装する必要があります(begin
メンバ関数とend
メンバ関数)。
Iterator begin() | 先頭を表すイテレータ |
Iterator end() | 末尾を表すイテレータ |
struct String {
const char* s;
Iterator begin() { return {s}; }
Iterator end() { return {s + strlen(s)}; }
};
ちなみにメンバ関数の代わりとして非メンバ関数を実装する方法もあります。
Iterator begin(const T&); | 先頭を表すイテレータ |
Iterator end(const T&); | 末尾を表すイテレータ |
Iterator begin(const String& s) { return {s.s}; };
Iterator end(const String& s) { return {s.s + strlen(s.s)}; };
イテレータの使い方
今回の方法で作成したイテレータとコンテナは範囲ベースfor文(Range-based for Statement)に対応しているため、for (値 : コンテナ) {}
という記法でコンテナへの反復処理が可能になります。
for (const char& c : String{"abc"})
printf("%c,", c); // 出力: "a,b,c,"
// `char c`の場合は値コピーが発生
for (char c : String{"abc"})
printf("%c,", c); // 出力: "a,b,c,"
従来の方法でイテレータを走査する場合は、次の方法を用います。
String s = {"abc"};
for (Iterator ite = s.begin(), end = s.end(); ite != end; ++ite)
printf("%c,", *ite); // 出力: "a,b,c,"
範囲ベースfor文では上記のコードと概ね同等の処理が行われます。
標準ライブラリのコレクション系の関数やアルゴリズム系の関数にも対応出来ます。
String s = {"abc"};
std::for_each(s.begin(), s.end(), [] (char c) {
printf("%c,", c); // "a,b,c,"
});
String t = {"abc"};
Iterator i = std::find_if(t.begin(), t.end(), [] (char c) {
return c == 'b';
});
printf("%c", *i); // "b"
puts(i != t.end() ? "見つかりました" : "見つかりません");
もっとも簡単な範囲ベースfor文対応
ポインタの場合
配列やポインタが既に存在する場合は対応が簡単です。イテレータの作成も不要です。
配列やポインタの先頭アドレスと末尾アドレスをそれぞれbegin
関数とend
関数で返すだけで、簡単に範囲ベースfor文に対応することが出来ます。
struct String {
const char* str;
const char* begin() { return str; }
const char* end() { return str + strlen(str); }
};
for (char c : String{"abc"})
printf("%c,", c); // "a,b,c,"
コンテナの場合
コンテナを保有するクラスが既にある場合は、そのコンテナのイテレータを活用・再利用することが出来ます。
次のようにコンテナのイテレータをラップしたbegin
関数とend
関数を定義します。
struct schemes { // URI Schemes
std::vector<std::string> a = {"http", "ssh", "ftp"};
std::vector<std::string>::iterator begin() { return a.begin(); }
std::vector<std::string>::iterator end() { return a.end(); }
};
schemes sc;
for (std::string& s : sc)
printf("%s, ", s.c_str()); // "http, ssh, ftp, "
Rangeコンテナの作り方
イテレータの仕組みを応用すると、Rangeクラス(範囲クラス)やrange関数の実現が可能となります。
Rangeクラス
struct Iterator {
int i;
int& operator*() { return i; }
Iterator& operator++() { ++i; return *this; }
bool operator!=(const Iterator& v) { return i != v.i; }
};
struct Range {
int location, length;
Iterator begin() { return {location}; }
Iterator end() { return {location + length}; }
};
for (int v : Range{0, 4})
printf("%ld,", v); // "0,1,2,3,"
for (int v : Range{4, 2})
printf("%d,", v); // "4,5,"
Range r = {6, 3};
for (Iterator ite = r.begin(), end = r.end(); ite != end; ++ite)
printf("%ld,", *ite); // "6,7,8,"
Range e = {0, 2};
std::for_each(e.begin(), e.end(), [] (int v) {
printf("%ld, ", v); // "0, 1, "
});
Range f = {0, 10};
Iterator ite = std::find_if(f.begin(), f.end(), [] (int v) {
return v > 5;
});
printf("%ld", *ite); // 6
puts(ite != f.end() ? "見つかりました" : "見つかりません");
range関数
Range range(int start, int end) { return {start, end - start}; }
Range range(int end) { return {0, end}; }
for (int position : range(4, 6))
printf("%d,", position); // "4,5,"
for (int i : range(3))
printf("%d,", i); // "0,1,2,"