C++/標準ライブラリ/iterator

C++ 教科書 標準ライブラリ編「<iterator> ヘッダー」の章

はじめに

この章では、C++ 標準ライブラリにおけるイテレータの仕組みと使用方法について解説します。イテレータは、コンテナなどの範囲を効率的に処理するための強力なツールであり、様々なアルゴリズムやデータ構造と密接に連携します。

イテレータとは

定義と役割

イテレータは、範囲内の要素を順に参照したり、操作したりするためのオブジェクトです。具体的には、以下の操作を実行できます。

• 範囲内の要素を 参照 する
• 範囲内の要素を 変更 する
• 範囲内の要素を 削除 する
• 範囲内の要素を 挿入 する

イテレータは、コンテナなどの範囲に密接に関連しており、コンテナ内の要素を効率的に処理するために使用されます。

イテレータの種類

イテレータは、以下の4種類に分類されます。

入力イテレータ

範囲内の要素を 参照 することしかできないイテレータです。

出力イテレータ

範囲内の要素を 変更 することしかできないイテレータです。

双方向イテレータ

範囲内の要素を 参照 と 変更 の両方を行うことができるイテレータです。

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

範囲内の要素に 直接アクセス することができるイテレータです。

それぞれのイテレータは、使用できる操作が異なります。例えば、入力イテレータは要素の参照しかできないため、要素の変更や削除はできません。

イテレータのカテゴリ

イテレータは、以下の2つのカテゴリに分類されます。

コンスタントイテレータ

範囲内の要素を 参照 することしかできないイテレータです。要素を変更することはできません。

リビジョンイテレータ

範囲内の要素を 参照 と 変更 の両方を行うことができるイテレータです。ただし、要素を削除することはできません。

コンスタントイテレータは、範囲内の要素を変更しないことを保証する必要がある場合に使用されます。リビジョンイテレータは、範囲内の要素を削除しないことを保証する必要がある場合に使用されます。

イテレータ操作

イテレータの取得

コンテナからイテレータを取得するには、以下の方法があります。

• begin() メンバ関数：コンテナの最初の要素を指すイテレータを取得します。
• end() メンバ関数：コンテナの最後の要素の次の要素を指すイテレータを取得します。
• cbegin() メンバ関数：コンテナの最初の要素を指すコンスタントイテレータを取得します。
• cend() メンバ関数：コンテナの最後の要素の次の要素を指すコンスタントイテレータを取得します。

例えば、以下のコードは、std::vector の最初の要素と最後の要素を指すイテレータを取得します。

auto v = std::vector{1, 2, 3, 4, 5};
auto iter_begin = v.begin();
auto iter_end = v.end();

イテレータの比較

イテレータ同士を比較するには、以下の比較演算子を使用できます。

==

2つのイテレータが同じ要素を指しているかどうかを比較します。

!=

2つのイテレータが異なる要素を指しているかどうかを比較します。

<

1番目のイテレータが2番目のイテレータよりも前の要素を指しているかどうかを比較します。

<=

1番目のイテレータが2番目のイテレータよりも前の要素を指しているか、または同じ要素を指しているかどうかを比較します。

>

1番目のイテレータが2番目のイテレータよりも後の要素を指しているかどうかを比較します。

>=

1番目のイテレータが2番目のイテレータよりも後の要素を指しているか、または同じ要素を指しているかどうかを比較します。

例えば、以下のコードは、std::vector の最初の要素と最後の要素を比較します。

auto v = std::vector{1, 2, 3, 4, 5};
auto iter_begin = v.begin();
auto iter_end = v.end();

if (iter_begin == iter_end) {
    // ...
}

イテレータのインクリメントとデクリメント

イテレータを次の要素または前の要素へ移動するには、以下の演算子を使用できます。

++

イテレータを次の要素へ移動します。

--

イテレータを前の要素へ移動します。

例えば、以下のコードは、std::vector のすべての要素をイテレータで順に処理します。

auto v = std::vector{1, 2, 3, 4, 5};
for (auto iter = v.begin(); iter != v.end(); iter++) {
    std::cout << *iter << std::endl;
}

イテレータの代入

イテレータを別のイテレータに代入するには、以下の代入演算子を使用できます。

=

イテレータが指す要素を別のイテレータが指す要素にコピーします。

例えば、以下のコードは、std::vector の最初の要素を指すイテレータを別のイテレータに代入します。

auto v = std::vector{1, 2, 3, 4, 5};
auto iter_begin = v.begin();
auto iter_copy = iter_begin;

イテレータの参照解像

イテレータが指す要素を参照するには、以下の矢印演算子を使用できます。

->

イテレータが指す要素のメンバーにアクセスします。

*

イテレータが指す要素の値を取得します。

例えば、以下のコードは、std::vector の最初の要素の値を出力します。

auto v = std::vector{1, 2, 3, 4, 5};
auto iter_begin = v.begin();
std::cout << *iter_begin << std::endl;

標準イテレータ

std::begin()とstd::end()

std::begin()とstd::end()は、コンテナの最初と最後のイテレータを取得する関数です。

std::begin(container)

コンテナcontainerの最初の要素を指すイテレータを取得します。

std::end(container)

コンテナcontainerの最後の要素の次の要素を指すイテレータを取得します。

例えば、以下のコードは、std::vector の最初と最後の要素を指すイテレータを取得します。

auto v = std::vector{1, 2, 3, 4, 5};
auto iter_begin = std::begin(v);
auto iter_end = std::end(v);

std::advance()

std::advance()は、イテレータを指定された距離だけ移動する関数です。

std::advance(iter, distance)

イテレータiterをdistanceだけ移動します。distanceが正の場合、イテレータは次の要素へ移動します。distanceが負の場合、イテレータは前の要素へ移動します。

例えば、以下のコードは、std::vector のイテレータを3つ進めます。

auto v = std::vector{1, 2, 3, 4, 5};
auto iter = v.begin();
std::advance(iter, 3);

std::distance()

std::distance()は、2つのイテレータ間の距離を計算する関数です。

std::distance(iter_begin, iter_end)

イテレータiter_beginとiter_end間の距離を計算します。

例えば、以下のコードは、std::vector の要素数を計算します。

auto v = std::vector{1, 2, 3, 4, 5};
auto iter_begin = v.begin();
auto iter_end = v.end();
int size = std::distance(iter_begin, iter_end);

std::next()とstd::prev()

std::next()とstd::prev()は、イテレータを次の要素または前の要素へ移動する関数です。

std::next(iter, n)

イテレータiterをn個の要素だけ進めます。

std::prev(iter, n)

イテレータiterをn個の要素だけ戻します。

例えば、以下のコードは、std::vector のイテレータを2つ進め、その後3つ戻します。

auto v = std::vector{1, 2, 3, 4, 5};
auto iter = v.begin();
iter = std::next(iter, 2);
iter = std::prev(iter, 3);

std::find()

std::find()は、範囲内で特定の要素を検索するアルゴリズムです。

std::find(iter_begin, iter_end, value)

範囲[iter_begin, iter_end)内で値valueと等しい要素を検索します。見つかった場合は、その要素を指すイテレータを返します。見つからない場合は、iter_endを返します。

例えば、以下のコードは、std::vector 内に値3が含まれているかどうかを調べます。

auto v = std::vector{1, 2, 3, 4, 5};
auto iter = std::find(v.begin(), v.end(), 3);
if (iter != v.end()) {
    std::cout << "値3が見つかりました" << std::endl;
} else {
    std::cout << "値3が見つかりませんでした" << std::endl;
}

std::copy()

std::copy()は、範囲内の要素を別の範囲へコピーするアルゴリズムです。

std::copy(iter_begin, iter_end, dest_begin)

範囲[iter_begin, iter_end)内の要素を範囲[dest_begin, dest_end)へコピーします。

例えば、以下のコードは、std::vector の要素を別のstd::vectorへコピーします。

std::vector<int> v1 = {1, 2, 3, 4, 5};
std::vector<int> v2;
std::copy(v1.begin(), v1.end(), std::back_inserter(v2));

std::copy_if()

std::copy_if()は、条件を満たす要素を別の範囲へコピーするアルゴリズムです。

std::copy_if(iter_begin, iter_end, dest_begin, predicate)

範囲[iter_begin, iter_end)内の要素のうち、条件predicateを満たす要素を範囲[dest_begin, dest_end)へコピーします。

例えば、以下のコードは、偶数の要素のみを別のstd::vectorへコピーします。

auto v = std::vector{1, 2, 3, 4, 5};
std::vector<int> v2;
std::copy_if(v.begin(), v.end(), std::back_inserter(v2), [](int x) { return x % 2 == 0; });

std::for_each()

std::for_each()は、範囲内のすべての要素に対して関数を適用するアルゴリズムです。

std::for_each(iter_begin, iter_end, func)

範囲[iter_begin, iter_end)内のすべての要素に対して関数funcを適用します。

例えば、以下のコードは、std::vector のすべての要素を平方します。

auto v = std::vector{1, 2, 3, 4, 5};
std::for_each(v.begin(), v.end(), [](int& x) { x *= x; });

イテレータと範囲ベースForの関係

イテレータと範囲ベースforは、C++における範囲処理において密接に関連する重要な概念です。それぞれの特徴と役割を理解し、適切に使い分けることで、コードをより簡潔かつ効率的に記述することができます。

範囲ベースfor

範囲ベースforは、イテレータを用いて範囲内の要素を効率的に処理するための構文です。以下の形式で記述されます。

for (変数 : 範囲) {
    // 処理内容
}

この構文は、以下の処理を実行します。

1. 範囲の begin() イテレータを 変数 に代入します。
2. 変数 が range.end() になるまでループします。
3. ループごとに、変数 が指す要素を処理します。
4. ループ終了後、変数 は未定義になります。

範囲ベースforは、イテレータを明示的に操作することなく、範囲内の要素を処理することができます。そのため、コードがより簡潔かつ読みやすくなります。

イテレータと範囲ベースforの使い分け

• イテレータは、より詳細な制御が必要な場合や、イテレータ操作そのものを目的とする場合に使用します。
• 範囲ベースforは、単純な範囲処理を行う場合や、コードの簡潔性を重視する場合に使用します。

例

以下のコードは、std::vector の要素をすべて平方します。

auto v = std::vector{1, 2, 3, 4, 5};
 
// イテレータを使用
for (auto iter = v.begin(); iter != v.end(); iter++) {
    *iter *= *iter;
}
 
// 範囲ベースforを使用
for (int& x : v) {
    x *= x;
}

上記のように、同じ処理でもイテレータと範囲ベースforのいずれでも記述することができます。状況に応じて適切な方法を選択することが重要です。

イテレータアダプタ

標準ライブラリが提供するイテレータアダプタ

C++ 標準ライブラリは、以下のイテレータアダプタを提供します。

std::reverse_iterator

範囲内の要素を逆順にイテレートするイテレータアダプタです。

std::filtered_iterator

条件を満たす要素のみをイテレートするイテレータアダプタです。

std::counting_iterator

0から始まり、イテレーションごとに1ずつ増える値を生成するイテレータアダプタです。

std::transform_iterator

関数によって変換された値を生成するイテレータアダプタです。

これらのイテレータアダプタは、標準イテレータと組み合わせて使用することで、様々な処理を実現することができます。

例

std::reverse_iterator を使用して、std::vector の要素を逆順に表示するコード:

auto v = std::vector{1, 2, 3, 4, 5};
for (auto iter = std::rbegin(v); iter != std::rend(v); iter++) {
    std::cout << *iter << std::endl;
}

std::filtered_iterator を使用して、偶数の要素のみを std::vector にコピーするコード:

auto v = std::vector{1, 2, 3, 4, 5};
std::vector<int> v2;
std::copy_if(std::make_filtered_iterator(v.begin(), v.end(), [](int x) { return x % 2 == 0; }),
             std::make_filtered_iterator(v2.begin(), v2.end(), [](int) { return true; }),
             v2.begin());

イテレータアダプタの自作

独自のイテレータアダプタを作成することもできます。イテレータアダプタを作成するには、以下の要件を満たす必要があります。

• イテレータ型であること
• begin()とend()メンバ関数を提供すること
• イテレーション演算子++と--をサポートすること
• イテレータの比較演算子==、!=、<、<=、>、>=をサポートすること

例

2ずつ増える値を生成するイテレータアダプタ:

template <typename T>
class StepIterator {
  private:
    T value;
    T step;
 
  public:
    explicit StepIterator(T value, T step) : value(value), step(step) {}
 
    typedef T value_type;
    typedef typename std::ptr_traits<T>::pointer pointer;
    typedef typename std::ptr_traits<T>::const_pointer const_pointer;
    typedef std::input_iterator_tag iterator_category;
 
    T operator*() const { return value; }
    T& operator*() { return value; }
 
    StepIterator& operator++() { value += step; return *this; }
    StepIterator operator++(int) { return StepIterator(*this) += 1; }
 
    StepIterator& operator--() { value -= step; return *this; }
    StepIterator operator--(int) { return StepIterator(*this) -= 1; }
 
    bool operator==(const StepIterator& other) const { return value == other.value; }
    bool operator!=(const StepIterator& other) const { return value != other.value; }
    bool operator<(const StepIterator& other) const { return value < other.value; }
    bool operator<=(const StepIterator& other) const { return value <= other.value; }
    bool operator>(const StepIterator& other) const { return value > other.value; }
    bool operator>=(const StepIterator& other) const { return value >= other.value; }
};

このイテレータアダプタは、以下のコードのように使用することができます。

auto v = std::vector{1, 2, 3, 4, 5};
for (StepIterator<int> iter(v.begin(), 2); iter != StepIterator<int>(v.end(), 2); iter++) {
    std::cout << *iter << std::endl;
}

アルゴリズムとイテレータ

C++ 標準ライブラリには、イテレータを用いて範囲内の要素を処理する様々なアルゴリズムが提供されています。これらのアルゴリズムは、イテレータと組み合わせて使用することで、複雑な処理を簡潔に記述することができます。

例

std::sort() を使用して、std::vector の要素を昇順にソートするコード:

std::vector<int> v = {5, 2, 4, 1, 3};
std::sort(v.begin(), v.end());

std::count() を使用して、std::vector 内に値3が含まれている回数を数えるコード:

std::vector<int> v = {1, 2, 3, 3, 4, 5};
int count = std::count(v.begin(), v.end(), 3);
std::cout << "値3は " << count << " 回含まれています" << std::endl;

標準ライブラリが提供するアルゴリズムの例

検索アルゴリズム

std::find, std::search, std::count

ソートアルゴリズム

std::sort, std::stable_sort, std::partial_sort, std::partition

変換アルゴリズム

std::copy, std::copy_if, std::for_each, std::transform

これらのアルゴリズムは、イテレータを用いて効率的に処理を行うことができます。

まとめ

• イテレータは、C++ 標準ライブラリにおいて重要な役割を果たす
• イテレータを理解することで、コンテナやアルゴリズムを効果的に活用できる
• 標準ライブラリが提供する様々なイテレータとアダプタを活用することで、複雑な処理を簡潔に記述できる

章末問題

1. イテレータを用いて、ベクトルの要素を逆順に表示するプログラムを書きます。
2. イテレータを用いて、配列内の奇数のみを別の配列にコピーするプログラムを書きます。
3. イテレータを用いて、文字列内のすべての小文字を大文字に変換するプログラムを書きます。

この章は、C++ 標準ライブラリにおけるイテレータの仕組みと使用方法について解説しました。イテレータは、コンテナやアルゴリズムと密接に連携しており、様々な処理を効率的に行うための強力なツールです。この章で学んだ内容を理解することで、C++ 標準ライブラリを効果的に活用できるようになるでしょう。