C++のイテレータを視覚的に理解する（競プロ向け）
この記事はCompetitive Programming (2) Advent Calendar 2019 - Adventarの4日目の記事です。
私がC++で競技プログラミングをやり始めた際によく分からなかったものの筆頭がイテレータでした。便利でv.begin(), v.end()のようなお決まりの書き方はできても、少し普段と違うことをしようとすると混乱しがちです。
このようなものは手元で図を描いて整理できるようになる、つまり視覚的に理解できることがとても大事だと思います。そこでイテレータについて「こういう風に理解すると図示しやすくなるかもよ」という視覚的な理解を提示したいと思います。
競技プログラミングでよく使う処理を中心に扱っていきますが、それ以外でC++を書く人にとっても理解の助けになる…かもしれません。
std::vectorのイテレータ
まずは一番分かりやすいものからいきます。
イテレータの図示
std::vectorの要素は左から右に並べることとします。イテレータを以下のように図示してみます。
v.begin()などで得られる（順方向の）イテレータを、要素の区切り位置にいて、右を向いている人だと思うことにします。このように考えると多くの操作を「しっくりくる」ように理解することができます。
- イテレータ
itが指す値にアクセスする操作*itは、この人の目の前にある要素にアクセスすると思うことにします。*v.begin()で先頭の要素が得られる一方、*v.end()では末尾の要素ではなくvの範囲外にアクセスしてしまうことになります。 std::sort(v.begin(), v.end())などのように範囲を指定すると、これらの区切り位置の間が操作対象となります。
std::vectorのイテレータはランダムアクセスイテレータという性質*1を満たしています。これは好きな要素数の分だけ進めたり戻したり、またはイテレータ間の差（距離）を取る操作が でできるようなイテレータです。
例えばv.begin()+2とすると、v.begin()から見てこの人が向いている方向に2要素分進んだイテレータが得られます。イテレータit自身を2要素分進める場合はit += 2とします。逆にv.begin()から2要素分進んだイテレータをitとすると、it-v.begin()の演算結果は2になります。
逆イテレータの図示
v.begin()やv.end()とは別に、v.rbegin()やv.rend()というものを見たことがあるかもしれません。これは逆イテレータ*2と呼ばれるもので、先ほどの図と同じように描くと左を向いている人になります。
順方向のイテレータとは向いている方向が違うので、+や-によって進む向きが逆になります。そしてやはり*v.rend()のアクセス先は先頭要素ではなく範囲外です。
逆イテレータを一番よく使うのは降順ソートの時ではないかと思います。特に比較関数を指定しない場合、std::sort関数は始点側が小さい値になるように要素をソートします。範囲にv.rbegin(), v.rend()を指定した場合は始点であるv.rbegin()側が小さい値になるように、つまりvの先頭から見ると降順になるようにソートされます。
もう一つ、あまり使うことはないですが小ネタです。逆イテレータには対応する順方向のイテレータを取得するbaseという関数があります。このときitとit.base()では指す値が異なります。
#include <bits/stdc++.h> using namespace std; int main(){ vector<int> v = {0, 1, 2, 3, 4}; auto it = v.rbegin() + 3; cout << *it << " " << *it.base() << endl; // 出力:1 2 }
これも以下のように、同じ区切り位置に留まったまま振り向くと考えると整合性が取れています。
std::lower_bound/std::upper_boundの理解
二分探索を自前で書かなくても良い、これらの便利な関数。
std::lower_bound(v.begin(), v.end(), a)std::upper_bound(v.begin(), v.end(), a)
のように使い、これらはイテレータを返すので、v.begin()と引き算してインデックスに相当する値を取り出したりします。
これらはともにvが昇順ソートされている*3時に、aを挿入すべき区切り位置を返します。ただしvに値aが含まれている時にはこの2つは異なる結果となります。これを図示すると以下のようになります。
vにaが含まれている場合、上図のようにaが占める領域の左端と右端がそれぞれstd::lower_boundとstd::upper_boundが指す位置となります。
「a未満の最大の要素ってどうやって探すんだっけ…」「aより大きい要素の個数ってどうやって求めるんだっけ…」みたいなことを迷ったときは、是非この図を思い出して手元に描いてみてください。
ちなみにこのstd::lower_boundがちゃんと要素数 に対して で終わるためには、ランダムアクセスイテレータの性質が必要です。自分で二分探索を組む際にも、試す値が という風に飛び飛びになりますよね。std::lower_boundも同じように飛び飛びの場所を調べていくので、それらに でアクセスできる必要があります。
以上がstd::vectorのイテレータを代表とするランダムアクセスイテレータの解説です。他にもstd::dequeやstd::stringなどもランダムアクセスイテレータを持ちます。
std::setやstd::mapのイテレータ
次はこれらのコンテナに対するイテレータです。std::multisetやstd::multimapも含めて概ね同じですが、一番単純なstd::set<int>を題材にしましょう。
これらは平衡二分探索木として実装されることが多いようなので、そのように図示します。
std::vectorの時のような要素の区切り位置という概念が使いづらいのでちょっと苦しいですが、要領は同じです。木をベチャーッと平べったく一列に並べると数列になるので、先ほどの図と同じように理解するのも1つの手です。
ただしstd::setはランダムアクセスイテレータの性質は満たしません。それよりも弱い双方向イテレータという性質を満たします。
ランダムアクセスイテレータに対しては、it+2のように書くと任意の要素数ぶん移動したイテレータを で得ることができました。std::setなどのイテレータではそれができません。できるのはstd::next(it)やstd::prev(it)のように1つ隣の要素を求めることです。イテレータ自身を変更する場合はit++, it--のように書きます。
std::next(it, 3)のように回数を指定することもできますが、これは「1つ隣の要素を求める」ことを繰り返すだけで、その回数分の計算時間がかかっています。
std::next(it)やit++などの操作の計算量について触れておきます。規格上はならし計算量で 、つまり 個の要素全てを周る計算量が であると書かれているようです*4。構造が平衡二分探索木であることを仮定すると、1回で移動する辺数は最悪でも木の高さ（つまり ）以内には収まり、全要素を周ると各辺を1往復ずつするので計算量 であると理解することができます。
std::lower_boundとstd::set::lower_bound
std::setやstd::mapに対して二分探索することもあります。このときstd::vectorと同じようにstd::lower_bound(st.begin(), st.end(), a)と書けてしまうのですが…これは競プロあるあるトラップです。
std::vectorのところで書いたように、これらの関数は二分探索を行う過程で飛び飛びの場所にアクセスします。ランダムアクセスができない場合は、例えば見る値を100番目から50番目に変える時には「1つ隣に移動」の処理を50回やることになります。これでは は達成されず、具体的には になります。
一方st.lower_bound(a)のように書くと、平衡二分探索木の性質を利用して木を降りるように値を探しに行くので*5、木の高さ分の計算時間、すなわち が達成されます。
なおlower_bound/upper_boundの位置についてはstd::vectorのときと同じように理解できます。同じ値が複数あるような図にしたいのでここだけstd::multisetです。
おわりに
イテレータは怖くない！
とはいえ、イテレータはよく分からないままに書き慣れない演算をするとデバッグ困難なREを起こしがちです。まずは書き慣れた処理を増やしていって、ちょっと難しい使い方をする時には図を描いて整理できるようになれば、二分探索でガチャガチャしたりstd::setやstd::mapをこねこねしたりするような問題もしっかり通せるようになるでしょう。
クレジット
図中の横向きアイコンは以下のサイトよりお借りしました。
脚注
*1:「ランダムアクセスイテレータ」という型やクラスがあるわけではなく、特定の演算が可能であるという性質を指した用語であり、こういった性質は正式には「Named requirements」と呼ぶようです。参考：https://ja.cppreference.com/w/cpp/named_req/RandomAccessIterator
*2:用語はこのページに倣っています。https://cpprefjp.github.io/reference/vector/vector/rbegin.html
*3:実際の要件はソートされていることよりも少し緩いですが、ほとんどの場合はソート済みのvectorを対象とすると考えて良いと思います
*4:https://stackoverflow.com/questions/11779859/whats-the-time-complexity-of-iterating-through-a-stdset-stdmap
*5:たぶん。実際の実装がどうなっているかは分かりません