イテレータ 解答ページ | Programming Place Plus Modern C++編【標準ライブラリ】 第9章

トップページModern C++編 C++編](../../index.html) – 第9章

Modern C++編は作りかけで、更新が停止しています。代わりに、C++14 をベースにして、その他の方針についても見直しを行った、新C++編を作成しています。
Modern C++編は削除される予定です。

問題①

問題① std::end関数が、末尾要素の「1つ後ろ」を指すイテレータを返すのはなぜでしょうか?


コンテナの要素を順番に参照していくループを作る際に、終了判定が単純になることが挙げられます。つまり、要素を参照するイテレータと、末尾要素の1つ後ろを指すイテレータが一致するまで繰り返せばよいということになります。
もし、std::end関数が、末尾要素を指すイテレータを返すとしたら(そして、それ以外に適当な関数がないとしたら)、末尾要素を飛び越えたときにループを終わらせるような終了判定が必要になり、厄介なコードになってしまいます。

この発想は、配列の要素を for文で順次参照するとき、末尾要素の1つ後ろを意味する添字を使うことと同じです。

また、コンテナが空のときにも、特別扱いする必要がないという点も注目に値します。コンテナが空のときには、std::begin関数と std::end関数は同じイテレータを返すので、「!=」を終了条件に使うループは、つねに正しく動作します。

問題②

問題② std::distance関数はどのように実装されているか、想像して自作してみてください。


本編で解説しているとおり、std::distance関数は、ランダムアクセスイテレータの場合と、それ以外の場合とで処理が異なります。そのため、イテレータタグを使って実装関数を切り替える仕組みで実装します。

namespace mystd {
    // ランダムアクセスイテレータの場合
    template <class InputIt>
    typename std::iterator_traits<InputIt>::difference_type distance_impl(InputIt first, InputIt last, random_access_iterator_tag)
    {
        return last - first;
    }

    // 入力イテレータの場合
    template <class InputIt>
    typename std::iterator_traits<InputIt>::difference_type distance_impl(InputIt first, InputIt last, input_iterator_tag)
    {
        std::iterator_traits<InputIt>::difference_type n = 0;
        while (first != last) {
            ++n;
            ++first;
        }
        return n;
    }

    template <class InputIt>
    typename std::iterator_traits<InputIt>::difference_type distance(InputIt first, InputIt last)
    {
        return distance_impl(first, last, std::iterator_traits<InputIt>::iterator_category());
    }
}

ランダムアクセスイテレータの場合は、last - first で距離を算出します。それ以外のカテゴリのイテレータの場合(std::distance関数の最低要件は入力イテレータです)は、first から last までインクリメントを繰り返しながら、距離をカウントします。



参考リンク


更新履歴

’2017/12/21 新規作成。



第9章のメインページへ

Modern C++編のトップページへ

Programming Place Plus のトップページへ



はてなブックマーク に保存 Pocket に保存 Facebook でシェア
X で ポストフォロー LINE で送る noteで書く
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー
先頭へ戻る