最終更新日時(UTC): 2020年02月20日 14時43分22秒
Mitsuru Kariya が更新

履歴 編集

function template
<iterator>

# std::distance

    namespace std {
      template <class InputIterator>
      typename iterator_traits<InputIterator>::difference_type
        distance(InputIterator first, InputIterator last);     // C++03

      template <class InputIterator>
      constexpr typename iterator_traits<InputIterator>::difference_type
        distance(InputIterator first, InputIterator last);     // C++17
    }

## 概要

イテレータ間の距離を求める。

この関数は、以下のような状況で活用できる：

- `std::find()`や`std::find_if()`で検索し、見つかった要素が先頭から何番目かを調べる。

      std::vector<int> v = { … };
      auto it = std::find_if(v.begin(), v.end(), pred);
      std::size_t index = std::distance(v.begin(), it);

- `std::forward_list`のような、要素数を直接取得できないコンテナに対して、イテレータ範囲で要素数を求める。

      std::forward_list<int> ls = { … };
      std::size_t size = std::distance(ls.begin(), ls.end());

## 要件

- `InputIterator`がランダムアクセスイテレータの場合、`first`は`last`に到達可能、もしくは`last`から`first`に到達可能であること。
- それ以外のイテレータの場合には、`first`から`last`に到達可能であること。

## 効果

- `InputIterator`がランダムアクセスイテレータの場合は、`last - first`が返る。
- それ以外のイテレータの場合は、`first`から`last`までイテレータをインクリメントしていき、距離をカウントする。

## 戻り値

`first`から`last`までの距離

## 計算量

`InputIterator`がランダムアクセスイテレータの場合はO(1)。それ以外のイテレータの場合はO(n)。

## 例

    #include <iterator>
    #include <iostream>
    #include <vector>
    #include <list>

    int main()
    {
      {
        std::vector<int> v = {3, 1, 4};
        std::size_t d = std::distance(v.begin(), v.end());

        std::cout << d << std::endl;
      }
      {
        std::list<int> ls = {3, 1, 4, 5, 2};
        std::size_t d = std::distance(ls.begin(), ls.end());

        std::cout << d << std::endl;
      }
    }

### 出力

    3
    5

## 実装例

    template <class InputIterator>
    typename std::iterator_traits<InputIterator>::difference_type
        distance_impl(InputIterator first, InputIterator last,
                      std::input_iterator_tag)
    {
      using result_type = typename std::iterator_traits<InputIterator>::difference_type;

      result_type n = 0;
      for (; first != last; ++first) {
        ++n;
      }
      return n;
    }

    template <class RandomAccessIterator>
    typename std::iterator_traits<RandomAccessIterator>::difference_type
        distance_impl(RandomAccessIterator first, RandomAccessIterator last,
                      std::random_access_iterator_tag)
    {
      return last - first;
    }

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

## 参照

- P0031R0 A Proposal to Add Constexpr Modifiers to `reverse_iterator`, `move_iterator`, `array` and Range Access