見出し画像

C++ 再入門 その27 - STLとイテレータ

kzn

前回、C++にはテンプレートという仕組みがあって、それを使って複数のデータをまとめて扱うことの出来るSTLというライブラリが用意されていて…なんていう話を書きました。

C++ 再入門 その26 - STLコンテナ(1）vector

この便利な仕組みを使うには「イテレータ」というものを知る必要があるんだよというところで終えていましたが、今回はこの「イテレータ」を説明してみます。

イテレータは、おおよそ21世紀に入った頃（入る少し前？）から多くのプログラミング言語に取り入れられた概念で、ひとかたまりのデータ構造に対して「それぞれ」を取り出す仕組みです。JISでは「反復子」と翻訳されています。それまでは単に for や while といったループを使って配列などから各要素を取り出していたのですが、ループの作り方や終了条件の判断のタイミングはプログラマに任されており、これが多くのバグを作り出してきたことも事実です。ループ処理は繰り返し実行されるからこそパフォーマンスが求められる部分でもあり、如何にループを高速化するかが古のFORTRANなどの時代からコンパイラの最適化テクニックとして競われてきた部分でもあります。私見ですがイテレータが導入された時期はCPUのマルチコア化が始まった時代でもあることから、文法のレベルでループの最適化を支援する必要もあって広く導入されたのではないかと思っています。

イテレータ

イテレータの説明には結構小難しいことが書いてあるのですが、ポイントは

  • （コンテナごとに）イテレータという「型」が用意されている

  • （コンテナに対して）順方向と逆方向または任意の要素の取り出しが出来る

  • 全ての要素を取り出すループの作り方が決められている

ことだけわかれば充分ですが、注意点としては

  • 最初の要素を取り出すbegin()は有効なイテレータはだが、最後の要素を取り出すend()のイテレータは無効である

  • コンテナに変更を加えるとイテレータは無効となる

ということがあります。

#include <iostream>
#include <vector>
using namespace std;
int main() {
  // ベクターの宣言と初期化
  vector<int> v = { 1, 2, 3, 4, 5 };
  for (int i = 0; i < v.size(); i++) {
    cout << v[i] << " ";
  }
  cout << endl;
  for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
    cout << *it << " ";
  }
  cout << endl;
  return 0;
}

1 2 3 4 5
1 2 3 4 5

実行結果

for ループが begin() から始まり、end()まで（但しend()は無効なのでここでループを抜ける）という定石がコレです。イテレータはコンテナ要素への「参照」なので、インクリメント演算子で次に進め、アクセスするときには”*”を付ける訳です。

イテレータ

やらかし易いのが要素へのインデックスのように end()判定で大小比較をしてしまうことですが、イテレータの大小は定義されていません。必ず一致するか否かで判定します。また逆順に辿りたい時はend()を代入してbegin()と一致するまで「ではなく」逆イテレータという型を使います。

#include <iostream>
#include <vector>
using namespace std;
int main() {
  // ベクターの宣言と初期化
  vector<int> v = { 1, 2, 3, 4, 5 };
  for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
    cout << *it << " ";
  }
  cout << endl;
  for (vector<int>::reverse_iterator rit = v.rbegin(); rit != v.rend(); rit++) {
    cout << *rit << " ";
  }
  cout << endl;
 return 0;
}

1 2 3 4 5
5 4 3 2 1

実行結果

逆向きに rbegin() から rend() までで、次の要素へ進むにはデクリメントではなくインクリメントなのを間違わないでください。定石から外れると運が良ければコンパイル時にエラーとなりますが、書き方によってはスルーされてて未定義な動作になるケースもあります。

イテレータ

第31回目 イテレータの仕組みと範囲ベースforの仕組み

ちなみにイテレータには「constイテレータ」という型もあり、これはコンテナの「値」を書き換えることが出来ないようにするときに使います。イテレータ自体がconstになるわけでもありませんし、コンテナを変更できなくなるわけでもありません。C++の constあるあるで、constがどこに係るのかが面倒な話のひとつでもあります。

[C++] ポインタを要素として持つコンテナのconst_iterator

そしてコンテナの値ではなく、コンテナに変更を加えるとイテレータは無効になります。vectorであれば要素を追加(push_backなど)したり削除(eraseなど)した場合が該当します。これを実行するとイテレータの指す先が正しいことが保証されなくなるので、あらためてイテレータをbegin()などを使って作り直さなければなりません。これに関しては文法的な検出はされないので細心の注意が必要ですし、困ったことに運が良ければ動くというケースもあります。イテレータが有効であるにはコンテナが変更されていないことが必要なので、引き数で渡したりプロパティとして保存して使うには向きません。

C++のイテレータを視覚的に理解する（競プロ向け）

イテレータの概念は便利なようで、なかなかややこしいところもあり、結局コンテナの実装を理解しなければエラーやバグが出た時に対応できないということも多いのですがSTLを使うには避けては通れないものなので慣れてしまうしかありません。

そして、このイテレータですが、最近の規格では大きな変更があったところで、今までの書き方、使い方が非推奨となりました。というところで次回は昨今のイテレータ事情を調べるつもりです。

ヘッダ画像は、以下のものを使わせていただきました。https://commons.wikimedia.org/wiki/File:ISO_C%2B%2B_Logo.svg
Jeremy Kratz - https://github.com/isocpp/logos , パブリック・ドメイン,
https://commons.wikimedia.org/w/index.php?curid=62851110による

#プログラミング #プログラミング言語 #プログラミング講座 #CPP #テンプレート #STL #イテレータ #逆イテレータ #constイテレータ

いいなと思ったら応援しよう！

kzn
頂いたチップは記事を書くための資料を揃えるために使わせていただきます！