コンテンツにスキップ

C++/イテレータ

出典: フリー教科書『ウィキブックス（Wikibooks）』
< C++
コルーチン C++
イテレータ 		遅延評価メソッドチェイン

イテレータ

[編集]

C++におけるイテレータは、コンテナの要素を順に処理するための抽象化された方法です。イテレータを使うことで、配列やリスト、ベクターなどのコンテナを抽象的に扱い、データの処理を効率的に行うことができます。この章では、イテレータの基本的な使い方から、さまざまな種類のイテレータ、そしてイテレータを活用した操作方法について学びます。

イテレータの基本

[編集]

イテレータは、通常ポインタのように振る舞い、コンテナ内の要素を一つずつ指し示すことができます。C++の標準ライブラリにおけるイテレータは、以下の操作をサポートしています。

  • dereferencing（デリファレンス）: *it を使って、イテレータが指し示す要素を取得できます。
  • インクリメント: ++it を使って、次の要素に移動できます。
  • 比較: イテレータ同士の比較が可能です。例えば、it != container.end() でイテレータがコンテナの終端に到達していないかを確認できます。
#include <iostream>
#include <vector>

auto main() -> int {
    std::vector<int> vec = {1, 2, 3, 4, 5};

    // イテレータを使って要素にアクセス
    for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it << " "; // イテレータが指し示す要素を出力
    }
    std::cout << std::endl;

    return 0;
}

このコードでは、std::vector<int>::iterator を使って、ベクター内の全要素を出力しています。

イテレータの種類

[編集]

C++にはいくつかの種類のイテレータが存在し、それぞれ異なる用途に適しています。主なイテレータの種類は以下の通りです。

前方イテレータ (Forward Iterator)

[編集]

前方イテレータは、コンテナを1方向にのみ進むことができ、繰り返し操作を行うために使われます。たとえば、std::list や std::forward_list では、前方イテレータが使われます。

双方向イテレータ (Bidirectional Iterator)

[編集]

双方向イテレータは、前方にも後方にも移動できるイテレータです。std::list など、前後両方の方向にアクセス可能なコンテナで使われます。

ランダムアクセスイテレータ (Random Access Iterator)

[編集]

ランダムアクセスイテレータは、配列やベクターなどのコンテナで使われ、任意の位置に直接アクセスできる最も効率的なイテレータです。std::vector や std::deque はランダムアクセスイテレータをサポートしています。

出力イテレータ (Output Iterator)

[編集]

出力イテレータは、データをコンテナに挿入するために使います。例えば、std::ostream_iterator はデータを標準出力に書き込むための出力イテレータです。

入力イテレータ (Input Iterator)

[編集]

入力イテレータは、コンテナからデータを読み取るために使用します。std::istream_iterator はストリームからデータを入力するために使われます。

イテレータとコンテナの関係

[編集]

C++のイテレータは、コンテナと密接に関連しています。コンテナは、イテレータを提供することによって、要素へのアクセスを容易にします。例えば、std::vector や std::list は、begin() と end() メソッドを提供しており、これによりイテレータを使った反復処理が可能になります。 

std::vector<int> vec = {1, 2, 3, 4, 5};
std::vector<int>::iterator it = vec.begin(); // begin() で先頭要素を指すイテレータ

イテレータの安全性

[編集]

イテレータを使用する際は、範囲外アクセスを避けるために注意が必要です。特に、end() イテレータに到達した際は、それ以上進んではいけません。また、イテレータはコンテナの変更によって無効になる可能性があるため、コンテナのサイズを変更する操作（例えば、push_back や erase）の後でイテレータを再度使用する際には、その有効性を確認することが重要です。

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

[編集]

C++の標準ライブラリには、イテレータを活用した多数のアルゴリズムが提供されています。これらのアルゴリズムは、イテレータを使ってコンテナ内のデータを操作します。例えば、std::sort はイテレータを使ってデータをソートします。 

#include <algorithm>
#include <iostream>
#include <vector>

auto main() -> int {
    std::vector<int> vec = {5, 3, 8, 1, 2};

    // イテレータを使ってソート
    std::sort(vec.begin(), vec.end());

    for (const int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

この例では、std::sort を使用して、ベクター内の要素をソートしています。begin() と end() で取得したイテレータをアルゴリズムに渡すことで、汎用的なデータ操作を実現しています。

イテレータを整備したカスタムクラス

[編集]

C++では、標準ライブラリのコンテナに加えて、独自のデータ構造を作成し、イテレータを整備することも可能です。この節では、イテレータをサポートするカスタムクラスの作成方法について説明します。イテレータを実装することで、自作のデータ構造をstd::vector や std::list のように簡単に反復処理できるようになります。

イテレータの基本的な実装

[編集]

まず、イテレータを提供するためには、イテレータクラスを定義し、必要な操作（デリファレンス、インクリメント、比較）を実装します。次に、カスタムクラスでこのイテレータクラスを返すために、begin() と end() メソッドを用意します。

以下は、簡単なカスタムクラス Container を作成し、その中でイテレータを実装する例です。 

#include <cstddef>
#include <iostream>

template <typename T>
class Container {
   private:
    T* data;
    size_t size;

   public:
    explicit Container(size_t size) : data(new T[size]), size(size) {
        for (size_t i = 0; i < size; ++i) {
            data[i] = T();
        }
    }

    ~Container() { delete[] data; }

    [[nodiscard]] auto getSize() const -> size_t { return size; }

    auto operator[](size_t index) -> T& { return data[index]; }

    // イテレータクラスの定義
    class Iterator {
       private:
        T* ptr;

       public:
        explicit Iterator(T* ptr) : ptr(ptr) {}

        auto operator*() -> T& { return *ptr; }

        auto operator++() -> Iterator& {
            ++ptr;
            return *this;
        }

        auto operator!=(const Iterator& other) const -> bool {
            return ptr != other.ptr;
        }
    };

    // イテレータを返すbegin()とend()メソッド
    auto begin() -> Iterator { return Iterator(data); }

    auto end() -> Iterator { return Iterator(data + size); }
};

auto main() -> int {
    Container<int> container(5);

    // 要素を設定
    for (size_t i = 0; i < container.getSize(); ++i) {
        container[i] = i * 10;
    }

    // イテレータを使用して要素を表示
    for (int& it : container) {
        std::cout << it << " ";  // イテレータが指し示す要素を出力
    }
    std::cout << std::endl;

    return 0;
}

このコードでは、Container クラスが Iterator クラスを内部で定義しており、begin() と end() メソッドを通じてイテレータを提供しています。これにより、std::vector や std::list と同様に、for ループでカスタムクラスの要素を反復処理することができます。

イテレータクラスの詳細

[編集]

イテレータクラスは、少なくとも以下の操作をサポートする必要があります。

  • デリファレンス（operator*）: イテレータが指し示す要素を返します。
  • インクリメント（operator++）: 次の要素に移動する操作です。
  • 不等号比較（operator!=）: イテレータ同士を比較し、異なる場合に true を返します。

必要に応じて、以下の操作も実装することができます。

  • 代入（operator=）: イテレータのコピーや代入が必要な場合。
  • 後置インクリメント（operator++(int)）: 後置インクリメントの動作をサポートします。
  • ポインタ演算（operator->）: イテレータがポインタのように動作することを許可します。

より高度なカスタムコンテナの例

[編集]

次に、std::list のような双方向リストのイテレータを作成する例を示します。この場合、前後に進むことができるイテレータが必要になります。 

#include <iostream>

template <typename T>
class DoublyLinkedList {
   private:
    struct Node {
        T data;
        Node* prev;
        Node* next;

        explicit Node(const T& data)
            : data(data), prev(nullptr), next(nullptr) {}
    } __attribute__((packed)) __attribute__((aligned(32)));

    Node* head;
    Node* tail;

   public:
    DoublyLinkedList() : head(nullptr), tail(nullptr) {}

    ~DoublyLinkedList() {
        Node* current = head;
        while (current) {
            Node* nextNode = current->next;
            delete current;
            current = nextNode;
        }
    }

    auto push_back(const T& value) -> DoublyLinkedList& {
        Node* newNode = new Node(value);
        if (tail == nullptr) {
            head = tail = newNode;
        } else {
            tail->next = newNode;
            newNode->prev = tail;
            tail = newNode;
        }
        return *this;
    }

    // 双方向イテレータ
    class Iterator {
       private:
        Node* node;

       public:
        explicit Iterator(Node* node) : node(node) {}

        auto operator*() -> T& { return node->data; }

        auto operator++() -> Iterator& {
            node = node->next;
            return *this;
        }

        auto operator--() -> Iterator& {
            node = node->prev;
            return *this;
        }

        auto operator!=(const Iterator& other) const -> bool {
            return node != other.node;
        }
    };

    auto begin() -> Iterator { return Iterator(head); }

    auto end() -> Iterator { return Iterator(nullptr); }
};

auto main() -> int {
    DoublyLinkedList<int> list;
    list.push_back(10).push_back(20).push_back(30);

    // 双方向イテレータを使用
    for (auto it = list.begin(); it != list.end(); it++) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // 範囲FORではイテレータが暗黙に使用される
    for (auto& x : list) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    return 0;
}

この例では、双方向リストのイテレータを実装し、前後に移動できるようにしています。++ と -- のオペレータを定義することで、リストを前後に反復処理できます。

カスタムクラスでイテレータを実装することで、C++標準ライブラリのコンテナと同様に、データ構造を簡単に操作できるようになります。begin() と end() メソッドを提供することで、標準のアルゴリズムや反復処理を利用できるため、柔軟で効率的なプログラムを書くことができます。イテレータを正しく実装することで、自作のデータ構造をより一般的な用途に適用できるようになります。

まとめ

[編集]

C++のイテレータは、コンテナの要素にアクセスするための強力なツールです。イテレータを使うことで、ポインタのようにデータを順に処理することができ、さまざまな種類のコンテナに対応する柔軟な操作が可能になります。また、標準ライブラリにはイテレータを利用したアルゴリズムが豊富に用意されており、効率的なデータ操作が可能です。イテレータを使いこなすことで、C++のプログラムをより洗練されたものにすることができます。


コルーチン C++
イテレータ 		遅延評価メソッドチェイン
"https://ja.wikibooks.org/w/index.php?title=C%2B%2B/イテレータ&oldid=264947" より作成