【C++】ループの正しい逆順走査

2022年8月26日

ループ(for文)の逆順走査には

する方法が代表的です．

イテレータ（rbegin()，rend()）を使用している場合，std::distanceなどでインデックスを得ることが出来ます．

しかしながら，std::distanceを使用すると著しく速度が低下します．

そのため，インデックスを参照する場合は「インデックスをデクリメントする方法」を使用する方が有利です．

「インデックスをデクリメントする方法」には注意点があるためここで紹介します．

ループ逆順(std::size_t)

まず，ループの正順走査を下記に示します．

/* TODO */はなんらかの処理をすることを想定しています．


for (std::size_t i = 0; i < vec.size; ++i) 
{
    /* TODO */
}

まず単に，正順を逆順走査にした例を下記に示します．


for (std::size_t i = vec.size; i >= 0; --i) 
{
    /* TODO */
}

一見，問題なさそうに見えますが，大問題があります．

具体的には，std::size_tは符号なし整数型であるため，ループの際にデクリメントするとi=0にてデクリメントを行うとアンダーフローし，不正な値がiに代入され無限ループに陥いります．

上記の例は，アンダーフローが原因で適切に動作しません．

つまり，std::size_tの代わりにlongを使用することで負の値を許容し，アンダーフローを回避することができます．


for (long i = vec.size; i >= 0; --i) 
{
    /* TODO */
}

この方法は，多くの場合動作しますが，まだ問題点があります．

しかし，この方法には問題点があります．

それは，std::size_t (unsigned long)とlongの値の範囲が違うことである．

64bit環境における値の範囲は，下記の通りです．（参考）

すなわち，範囲(vec.size())が 2,147,483,647 を超えている場合オーバーフローしてしまします．

多くの場合，このような大きな値は取られないため気が付きにくいですが，十分に注意しなければいません．

逆順走査にはこのコードを使用すべし！

上記に挙げた問題（オーバーフロー，アンダーフロー）を解消したものが，以下のコードです．


for (std::size_t i = 0; i < vec.size(); ++i)
{
    const auto irev = vec.size() - 1 - i;
    /* TODO */ 
}

解決案はものすごく簡単で，逆順走査用のインデックスirevを用意するだけです．

結論としては，簡単なコードですが，逆順走査では型範囲をしっかりと考えないといけません．

よかったらシェアしてね！