std::ranges::distance

出自cppreference.com
 
C++
 
迭代器庫
迭代器概念
迭代器原語
算法概念與工具
間接可調用概念
常用算法要求
(C++20)
(C++20)
(C++20)
工具
(C++20)
迭代器適配器
範圍訪問
(C++11)(C++14)
(C++14)(C++14)  
(C++11)(C++14)
(C++14)(C++14)  
(C++17)(C++20)
(C++17)
(C++17)
 
在標頭 <iterator> 定義
調用簽名
 
template< class I, std::sentinel_for<I> S >
    requires (!std::sized_sentinel_for<S, I>)
constexpr std::iter_difference_t<I>
    distance( I first, S last );
(1) (C++20 起) 
template< class I, std::sized_sentinel_for<std::decay_t<I>> S >
constexpr std::iter_difference_t<std::decay_t<I>>
    distance( I&& first, S last );
(2) (C++20 起) 
template< ranges::range R >
constexpr ranges::range_difference_t<R>
    distance( R&& r );
(3) (C++20 起)
1,2) 返回從 first 到 last 的自增次數。
3) 以有符號整數返回 r 的大小。

此頁面上描述的函數式實體是算法函數對象（非正式地稱為 niebloid），即：

參數

first - 指向首元素的迭代器
last - 哨位，代表 first 作為迭代器所指向的範圍的結尾
r - 要計算距離的範圍

返回值

1) 需要從 first 到 last 的自增次數。
2) last - static_cast<const std::decay_t<I>&>(first)。
3) 若 R 實現 ranges::sized_range 則返回 ranges::size(r)，否則返回 ranges::distance(ranges::begin(r), ranges::end(r))。

複雜度

1) 線性。
2) 常數。
3) 在 R 實現 ranges::sized_range 時，或者在 std::sized_sentinel_for<ranges::sentinel_t<R>, ranges::iterator_t<R>> 得到實現時是常數，否則是線性。

可能的實現

struct distance_fn
{
    template<class I, std::sentinel_for<I> S>
        requires (!std::sized_sentinel_for<S, I>)
    constexpr std::iter_difference_t<I> operator()(I first, S last) const
    {
        std::iter_difference_t<I> result = 0;
        while (first != last)
        {
            ++first;
            ++result;
        }
        return result;
    }
    
    template<class I, std::sized_sentinel_for<std::decay<I>> S>
    constexpr std::iter_difference_t<I> operator()(const I& first, S last) const
    {
        return last - first;
    }
    
    template<ranges::range R>
    constexpr ranges::range_difference_t<R> operator()(R&& r) const
    {
        if constexpr (ranges::sized_range<std::remove_cvref_t<R>>)
            return static_cast<ranges::range_difference_t<R>>(ranges::size(r));
        else
            return (*this)(ranges::begin(r), ranges::end(r));
    }
};

inline constexpr auto distance = distance_fn{};

示例

運行此代碼
#include <cassert>
#include <forward_list>
#include <iterator>
#include <vector>

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

    std::forward_list<int> l{2, 7, 1};
    // auto size = std::ranges::size(l); // 错误：不是有大小的范围
    auto size = std::ranges::distance(l); // OK，但要当心其复杂度为 O(N)
    assert(size == 3);
}

缺陷報告

下列更改行為的缺陷報告追溯地應用於以前出版的 C++ 標準。

缺陷報告 應用於 出版時的行為 正確行為
LWG 3392 C++20 重載 (1) 按值接收迭代器，從而拒絕擁有具大小哨位的僅移動迭代器左值 添加重載 (2)
LWG 3664 C++20 LWG 問題 3392 的解決方案導致 ranges::distance 拒絕數組實參 接受數組實參

參閱

(C++20)
 令迭代器前進給定的距離或到給定的邊界
(算法函數對象) [編輯]
(C++20)(C++20)
 返回滿足特定條件的元素數目
(算法函數對象) [編輯]
返回兩個迭代器間的距離
(函數模板) [編輯]