C++
イテレータ

Cイテレータ（ポインタ）

// This creates an array with 5 values.
const int array[] = { 1, 2, 3, 4, 5 };

#ifdef BEFORE_CPP11

// You can use `sizeof` to determine how many elements are in an array.
const int* first = array;
const int* afterLast = first + sizeof(array) / sizeof(array[0]);

// Then you can iterate over the array by incrementing a pointer until
// it reaches past the end of our array.
for (const int* i = first; i < afterLast; ++i) {
    std::cout << *i << std::endl;
}

#else

// With C++11, you can let the STL compute the start and end iterators:
for (auto i = std::begin(array); i != std::end(array); ++i) {
    std::cout << *i << std::endl;
}

#endif

このコードは、次のように各行に1〜5の数字を出力します。

1
2
3
4
5

それを打ち砕く

const int array[] = { 1, 2, 3, 4, 5 };

この行は、5つの値を持つ新しい整数配列を作成します。 C配列は、各値が連続したブロックに一緒に格納されるメモリへのポインタに過ぎません。

const int* first = array;
const int* afterLast = first + sizeof(array) / sizeof(array[0]);

これらの行は2つのポインタを作成します。最初のポインタには、配列内の最初の要素のアドレスである配列ポインタの値が与えられます。 Cの配列で使用する場合のsizeof演算子は、配列のサイズをバイト単位で返します。要素のサイズで割って、これは配列の要素の数を与えます。これを使用して、配列の後のブロックのアドレスを見つけることができます。

for (const int* i = first; i < afterLast; ++i) {

ここでは、イテレータとして使用するポインタを作成します。それは、私たちが反復処理する最初の要素のアドレスで初期化され、そして、私たちは限り反復し続けるだろうiより少ないafterLast限りを意味し、 i内のアドレスを指しているarray 。

    std::cout << *i << std::endl;

最後に、ループ内で私たちは私たちの価値反復子アクセスすることができiそれを逆参照によってを指しているの。逆参照演算子*は、 iのアドレスの値を返します。

概要

イテレータはポジションです

イテレータは、一連の要素をナビゲートして操作する手段であり、ポインタの一般化された拡張です。概念的には、イテレータは位置であり、要素ではないことを覚えておくことが重要です。たとえば、次のシーケンスを実行します。

A B C

シーケンスには3つの要素と4つの位置が含まれます

+---+---+---+---+
| A | B | C |   |
+---+---+---+---+

要素はシーケンス内のものです。位置は、シーケンスに意味のある操作が起こる場所です。例えば、一つの要素A の前または後に 、ない要素に、所定の位置に挿入します。要素の削除（ erase(A) ）は、最初にその位置を見つけて削除することによって行われます。

イテレータから値へ

位置から値に変換するには、イテレータを参照解除します。

auto my_iterator = my_vector.begin(); // position
auto my_value = *my_iterator; // value

イテレータは、シーケンス内で参照される値を逆参照すると考えることができます。これは、シーケンス内のend()イテレータを決して間接参照しない理由を理解する上で特に役に立ちます：

+---+---+---+---+
| A | B | C |   |
+---+---+---+---+
  ↑           ↑
  |           +-- An iterator here has no value. Do not dereference it!
  +-------------- An iterator here dereferences to the value A.

C ++標準ライブラリにあるすべてのシーケンスとコンテナで、 begin()はイテレータを最初の位置に返し、 end()はイテレータを最後の位置（最後の位置ではない ！）まで返します。結果として、アルゴリズムにおけるこれらのイテレータの名前は、しばしばfirstとlastラベル付けされる。

+---+---+---+---+
| A | B | C |   |
+---+---+---+---+
  ↑           ↑
  |           |
  +- first    +- last

空のシーケンスにも少なくとも1つの位置が含まれているので、 任意のシーケンスに対するイテレータを取得することもできます。

+---+
|   |
+---+

空のシーケンスでは、 begin()とend()は同じ位置になり、 どちらも参照解除できません。

+---+
|   |
+---+
  ↑
  |
  +- empty_sequence.begin()
  |
  +- empty_sequence.end()

イテレータの別の視覚化は、要素間の位置をマークすることです。

+---+---+---+
| A | B | C |
+---+---+---+
↑   ^   ^   ↑
|           |
+- first    +- last

イテレータの逆参照はイテレータの後に来る要素への参照を返します。このビューが特に有用な状況は次のとおりです。

• insert操作は、イテレータが示す位置に要素を挿入し、
• erase操作は、渡されたものと同じ位置に対応するイテレータを返し、
• イテレータとそれに対応する逆イテレータは、要素間の同じ位置に配置されます

無効なイテレータ

反復子は、（例えば操作の過程で）その位置がもはやシーケンスの一部ではない場合、 無効になります。無効化されたイテレータは、有効な位置に再割り当てされるまで参照解除できません。例えば：

std::vector<int>::iterator first;
{
    std::vector<int> foo;
    first = foo.begin(); // first is now valid
} // foo falls out of scope and is destroyed
// At this point first is now invalid

C ++標準ライブラリの多くのアルゴリズムとシーケンスメンバー関数には、イテレータが無効になったときに適用されるルールがあります。各アルゴリズムはイテレータを扱う方法（および無効にする方法）が異なります。

イテレータを使ったナビゲーション

わかっているように、イテレータはシーケンスをナビゲートするためのものです。これを行うためには、イテレータはシーケンス中の位置を移動させる必要があります。反復子は順番に進むことができ、また反復子は前進することができます。

auto first = my_vector.begin();
++first;                                             // advance the iterator 1 position
std::advance(first, 1);                              // advance the iterator 1 position
first = std::next(first);                            // returns iterator to the next element
std::advance(first, -1);                             // advance the iterator 1 position backwards
first = std::next(first, 20);                        // returns iterator to the element 20 position forward
first = std::prev(first, 5);                         // returns iterator to the element 5 position backward
auto dist = std::distance(my_vector.begin(), first); // returns distance between two iterators.

std :: distanceの2番目の引数は、最初の引数から到達可能でなければならないことに注意してください（つまり、 first second以下の値にする必要があります）。

イテレータで算術演算子を実行することはできますが、すべてのタイプのイテレータに対してすべての操作が定義されているわけではありません。 a = b + 3;ランダムアクセスイテレータでは動作しますが、フォワードまたは双方向イテレータでは動作しません。これは、まだb = a; ++b; ++b; ++b;ような3つの位置で進めることができますb = a; ++b; ++b; ++b; 。したがって、イテレータの種類がわからない場合（たとえば、イテレータを受け入れるテンプレート関数など）に特別な関数を使用することをお勧めします。

イテレータの概念

C ++標準には、いくつかの異なるイテレータの概念が記述されています。これらは、参照する順序でどのように動作するかに従ってグループ化されます。イテレータがモデル化する概念（動作は同様）が分かっていれば、 それが属するシーケンスに関係なく、そのイテレータの動作を保証することができます。それらは、多くの場合、次のイテレーターのコンセプトが前のコンセプトよりも優れているため、最も制限の少ない順に記述されます。

• 入力反復子：位置ごとに1 回のみ参照解除できます。進めることができるだけで、一度に1つのポジションしかありません。
• Forward Iterators：任意の回数参照解除できる入力イテレータ。
• 双方向イテレータ：また、一度に後方の位置を1つ進めることができ、前方イテレータ。
• ランダムアクセスイテレータ：一度に任意の数の位置を前または後に進めることができる双方向イテレータ。
• 連続イテレータ（C ++ 17以降）：基底のデータがメモリ内で連続していることを保証するランダムアクセスイテレータ。

アルゴリズムは、与えられたイテレータによってモデル化された概念に応じて変わることがあります。例えば、順方向イテレータに対してはrandom_shuffleを実装することができるが、ランダムアクセスイテレータを必要とするより効率的な変形を提供することができる。

イテレータの特性

イテレータの特性は、イテレータのプロパティに対する統一されたインタフェースを提供します。値、差分、ポインタ、参照型、イテレータのカテゴリを取得することができます：

template<class Iter>
Iter find(Iter first, Iter last, typename std::iterator_traits<Iter>::value_type val)  {
    while (first != last) {
        if (*first == val)
            return first;
        ++first;
    }
    return last;
}

イテレータのカテゴリを使用してアルゴリズムを特化することができます。

template<class BidirIt>
void test(BidirIt a, std::bidirectional_iterator_tag)  {
    std::cout << "Bidirectional iterator is used" << std::endl;
}
 
template<class ForwIt>
void test(ForwIt a, std::forward_iterator_tag)  {
    std::cout << "Forward iterator is used" << std::endl;
}
 
template<class Iter>
void test(Iter a)  {
    test(a, typename std::iterator_traits<Iter>::iterator_category());
}

イテレータのカテゴリは基本的にイテレータの概念ですが、反復イテレータは独自のタグを持っていませんが、コードを壊すことが判明しています。

逆イテレータ

リストやベクトルを逆方向​​に反復したい場合はreverse_iteratorを使うことができます。逆方向反復子は、 base()を通じてアクセスできるメンバーとして保持する双方向またはランダムアクセス反復子から作成されます。

rbegin()反復するには、コレクションの終わりのイテレーターとしてrbegin()とrend()をそれぞれ使用し、それぞれコレクションの開始点として使用します。

例えば、後方に反復するには：

std::vector<int> v{1, 2, 3, 4, 5};
for (std::vector<int>::reverse_iterator it = v.rbegin(); it != v.rend(); ++it)
{
    cout << *it;
} // prints 54321

逆イテレータは、 base()メンバ関数を介して順方向イテレータに変換できます。その関係は、逆イテレータがbase()イテレータよりも1つの要素を参照するということです。

std::vector<int>::reverse_iterator r = v.rbegin();
std::vector<int>::iterator i = r.base();
assert(&*r == &*(i-1)); // always true if r, (i-1) are dereferenceable
                        // and are not proxy iterators

 +---+---+---+---+---+---+---+
 |   | 1 | 2 | 3 | 4 | 5 |   |
 +---+---+---+---+---+---+---+
   ↑   ↑               ↑   ↑
   |   |               |   |
rend() |         rbegin()  end()
       |                   rbegin().base()
     begin()
     rend().base()

イテレータが要素間の位置をマークするビジュアライゼーションでは、関係はより簡単です。

  +---+---+---+---+---+
  | 1 | 2 | 3 | 4 | 5 |
  +---+---+---+---+---+
  ↑                   ↑
  |                   |
  |                 end()
  |                 rbegin()
begin()             rbegin().base()
rend()
rend().base()

ベクトルイテレータ

beginは、シーケンスコンテナの最初の要素にiteratorを返します。

endはiteratorを最初の要素のend返します。

ベクトルオブジェクトがconst場合、 beginとend両方begin const_iteratorます。あなたのベクトルがconstでなくてもconst_iteratorが返されるようにしたいなら、 cbeginとcend使うことができます。

例：

#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = { 1, 2, 3, 4, 5 };  //intialize vector using an initializer_list

    for (std::vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
        std::cout << *it << " ";
    }

    return 0;
}

出力：

1 2 3 4 5

マップイテレータ

コンテナ内の最初の要素に対するイテレータ。

マップオブジェクトがconst修飾されている場合、関数はconst_iterator返します。それ以外の場合は、 iterator返しiterator 。

// Create a map and insert some values
std::map<char,int> mymap;
mymap['b'] = 100;
mymap['a'] = 200;
mymap['c'] = 300;

// Iterate over all tuples
for (std::map<char,int>::iterator it = mymap.begin(); it != mymap.end(); ++it)
    std::cout << it->first << " => " << it->second << '\n';

出力：

a => 200
b => 100
c => 300

ストリームイテレータ

ストリームイテレータは、シーケンスを読み込んだり、コンテナから書式設定されたデータを出力する必要がある場合に便利です。

// Data stream. Any number of various whitespace characters will be OK.
std::istringstream istr("1\t 2     3 4");
std::vector<int> v;

// Constructing stream iterators and copying data from stream into vector.
std::copy(
    // Iterator which will read stream data as integers.
    std::istream_iterator<int>(istr),
    // Default constructor produces end-of-stream iterator.
    std::istream_iterator<int>(),
    std::back_inserter(v));

// Print vector contents.
std::copy(v.begin(), v.end(),
    //Will print values to standard output as integers delimeted by " -- ".
    std::ostream_iterator<int>(std::cout, " -- "));

サンプルプログラムは、 1 -- 2 -- 3 -- 4 --を標準出力に出力します。

独自のジェネレータバックアップイテレータを作成する

他の言語の共通のパターンは、オブジェクトの「ストリーム」を生成し、それをループするためにループコードを使用できる機能を持つことです。

これをC ++でモデル化できます

template<class T>
struct generator_iterator {
  using difference_type=std::ptrdiff_t;
  using value_type=T;
  using pointer=T*;
  using reference=T;
  using iterator_category=std::input_iterator_tag;
  std::optional<T> state;
  std::function< std::optional<T>() > operation;
  // we store the current element in "state" if we have one:
  T operator*() const {
    return *state;
  }
  // to advance, we invoke our operation.  If it returns a nullopt
  // we have reached the end:
  generator_iterator& operator++() {
    state = operation();
    return *this;        
  }
  generator_iterator operator++(int) {
    auto r = *this;
    ++(*this);
    return r;
  }
  // generator iterators are only equal if they are both in the "end" state:
  friend bool operator==( generator_iterator const& lhs, generator_iterator const& rhs ) {
    if (!lhs.state && !rhs.state) return true;
    return false;
  }
  friend bool operator!=( generator_iterator const& lhs, generator_iterator const& rhs ) {
    return !(lhs==rhs);
  }
  // We implicitly construct from a std::function with the right signature:
  generator_iterator( std::function< std::optional<T>() > f ):operation(std::move(f))
  {
    if (operation)
      state = operation();
  }
  // default all special member functions:
  generator_iterator( generator_iterator && ) =default;
  generator_iterator( generator_iterator const& ) =default;
  generator_iterator& operator=( generator_iterator && ) =default;
  generator_iterator& operator=( generator_iterator const& ) =default;
  generator_iterator() =default;
};

ライブの例 。

生成された要素を早期に保存して、すでに終了しているかどうかを簡単に検出できます。

エンドジェネレーターイテレーターの機能は決して使用されないので、 std::function 1回コピーするだけで一連のジェネレーターイテレーターを作成することができます。デフォルトで構築されたジェネレータイテレータは、それ自身と等しく、他のすべてのエンドジェネレータイテレータと比較されます。