C++ 學習筆記 - iterator_traits

TL;DR

本篇筆記主要是介紹 C++ 中 STL 函式庫的 iterator_traits。平常用到這個功能的地方應該比較少，但如果需要寫自己的容器並希望它能與 STL 的 <algorithms> 函式庫一起使用的話可能就會需要用到。

前言: 什麼是迭代器 (Iterator)

簡介

本篇筆記要介紹的重點並不是迭代器，故這邊只做非常簡短的介紹。

在 STL 中，迭代器對於不同種類的容器中的元素，提供了一種統一的操作方式，包含了遍歷、取值等操作，讓我們能夠在不知道容器內部實作細節的情況下，對容器內部的元素進行操作。

我們可以將迭代器理解為容器與 STL 種演算法函式庫之間的溝通橋樑：容器不需要知道有哪些演算法，而演算法也不需要知道容器內部的具體實作。

Iterator brief

ref: Back to Basics: Classic STL - Bob Steagall - CppCon 2021

迭代器分類

迭代器是透過其所能進行的運算進行分類，而其分類方式類似於下圖中的階層結構，在圖中上方的迭代器能夠進行的運算，圖中下方的迭代器也要支援。

舉例來說，輸入迭代器 (Input Iterator) 支援箭號運算子 (->)，則圖中除了輸出迭代器 (Output Iterator) 以外的其他迭代器同樣都支援箭號運算子 (->)。

這樣的分類方式對於使用迭代器的演算法在實作上有很大的幫助，此筆記後面會做更詳細的介紹。

Iterator Categories

而迭代器主要分為以下幾類

輸入迭代器 (Input Iterator)

讀取，但不寫入; single-pass，僅遞增。
istream_iterator
詳細內容可參考 cppreference: LegacyInputIterator

輸出迭代器 (Output Iterator)

寫入，但不讀取; single-pass，僅遞增。
ostream_iterator
詳細內容可參考 cppreference: LegacyOutputIterator

正向迭代器 (Forward Iterator)

讀取及寫入; multi-pass，僅遞增。
forward_list
詳細內容可參考 cppreference: LegacyForwardIterator

雙向迭代器 (Bidirectional Iterator)

讀取及寫入; multi-pass，可遞增及遞減。
list, set, map
詳細內容可參考 cppreference: LegacyBidirectionalIterator

隨機存取迭代器 (Random-Access Iterator)

讀取及寫入; multi-pass，可隨機存取。
array, vector, deque, string
詳細內容可參考 cppreference: LegacyRandomAccessIterator

iterator_traits 簡介

什麼是 iterator_traits

iterator_traits 是一個模板結構 (Template struct)，它主要目的是以一種統一的方式，提取迭代器的型別，如值的型別 (value_type)、差值型別 (difference_type)、迭代器分類 (iterator_category) 等。

以下是 iterator_traits 的基本定義：

1
2
3
4
5
6
7
8


template <typename Iterator>
struct iterator_traits {
    using difference_type   = typename Iterator::difference_type;
    using value_type        = typename Iterator::value_type;
    using pointer           = typename Iterator::pointer;
    using reference         = typename Iterator::reference;
    using iterator_category = typename Iterator::iterator_category;
};

使用 iterator_traits 提取型別資訊

當我們需要使用迭代器所指向的值的型別時，可以使用 iterator_traits 進行提取。以下是一個簡單的範例:

1
2
3
4
5


template <typename Iterator>
typename iterator_traits<Iterator>::value_type 
get_val(Iterator it) {
    return *it;
}

在這個範例中，我們透過 std::iterator_traits<Iterator>::value_type 取得迭代器所指向的值的型別 (value_type)，並使用 *it 來取得實際的值。

iterator_category 的用途

iterator_category 是 iterator_traits 中的一個重要型別，用於標示迭代器的分類。它讓我們在撰寫迭代器的演算法時，可以針對不同迭代器所支援的運算進行最佳化，例如我們可以利用隨機存取迭代器的特性實作更高效的演算法，這部份在筆記後面的範例中會有更詳細的介紹。

指標型別的特化

為了讓原生指標（如 int*）也能與 iterator_traits 一起使用，標準庫對指標型別進行了模板特化 (Specialization)。這樣動態記憶體陣列也可使用迭代器相關的演算法。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


template <typename Tp>
struct iterator_traits<Tp*> {
    using difference_type   = std::ptrdiff_t;
    using value_type        = Tp;
    using pointer           = Tp*;
    using reference         = Tp&;
    using iterator_category = std::random_access_iterator_tag;
};

template <typename Tp>
struct iterator_traits<const Tp*> {
    using difference_type   = std::ptrdiff_t;
    using value_type        = Tp;
    using pointer           = const Tp*;
    using reference         = const Tp&;
    using iterator_category = std::random_access_iterator_tag;
};

iterator_traits 使用範例

std::distance

在這部分，我會透過觀察 llvm 中 std::distance 的原始碼，解釋 iterator_traits 的用法 (source code)。

下列程式碼為我們所使用的 API:

1
2
3
4
5
6
7


template <class _InputIter>
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX17
typename iterator_traits<_InputIter>::difference_type
distance(_InputIter __first, _InputIter __last)
{
    return _VSTD::__distance(__first, __last, typename iterator_traits<_InputIter>::iterator_category());
}

由模板變數的命名方式 _InputIter 可看出，此函式主要用於輸入迭代器 (Input Iterator)，也就代表除了輸出迭代器以外的迭代器皆可使用。
在函式中，透過 typename iterator_traits<_InputIter>::iterator_category 提取迭代器的類別，並以此為參數呼叫內部的實作函式 __distance。這種方式稱為標籤分派 (Tag Dispatch)，可以根據不同的迭代器類別，呼叫對應的函式實作。

以下程式碼為對於輸入迭代器 (Input Iterator) 的實作:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


template <class _InputIter>
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX17
typename iterator_traits<_InputIter>::difference_type
__distance(_InputIter __first, _InputIter __last, input_iterator_tag)
{
    typename iterator_traits<_InputIter>::difference_type __r(0);
    for (; __first != __last; ++__first)
        ++__r;
    return __r;
}

由於輸入迭代器僅支援單向遞增，我們需要遍歷從 __first 到 __last 的整個範圍，逐一遞增 __r，以計算兩個迭代器之間的距離。
在函式中，input_iterator_tag 只是為了 Tag Dispatch，函式中並不需要使用它，故可忽略其變數名稱。

以下程式碼為對於隨機存取迭代器 (Random-Access Iterator) 的實作:

1
2
3
4
5
6
7


template <class _RandIter>
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX17
typename iterator_traits<_RandIter>::difference_type
__distance(_RandIter __first, _RandIter __last, random_access_iterator_tag)
{
    return __last - __first;
}

隨機存取迭代器支援兩個迭代器之間的減法運算，因此我們可以直接透過 __last - __first 計算距離，而不需要遍歷整個範圍。這大大提高了效率。

std::reverse

接下來，我們以 llvm 中的 std::reverse 為例，進一步說明 iterator_traits 的應用 (source code)。

以下為我們使用的 API:

1
2
3
4
5


template <class _BidirectionalIterator>
inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void
reverse(_BidirectionalIterator __first, _BidirectionalIterator __last) {
    std::__reverse<_ClassicAlgPolicy>(std::move(__first), std::move(__last));
}

以下為其內部的實作函式，與 std::distance 有些不同，std::reverse 多了一層

1
2
3
4
5


template <class _AlgPolicy, class _BidirectionalIterator, class _Sentinel>
_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __reverse(_BidirectionalIterator __first, _Sentinel __last) {
    using _IterCategory = typename _IterOps<_AlgPolicy>::template __iterator_category<_BidirectionalIterator>;
    std::__reverse_impl<_AlgPolicy>(std::move(__first), std::move(__last), _IterCategory());
}

在此實作細節中，其透過 using _IterCategory = ... 取出 iterator 的 iterator_category。
在內部實作細節 __reverse_impl 中，透過 _IterCategory() 的方式建構一個以 _IterCategory 為型別的變數。
一樣是透過標籤分派 (Tag Dispatch) 的方式，將不同的 iterator_catagory 分配到其對應的實作。

以下程式碼為對於雙向迭代器 (Bidirectional Iterator) 的實作:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


template <class _AlgPolicy, class _BidirectionalIterator>
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
void
__reverse_impl(_BidirectionalIterator __first, _BidirectionalIterator __last, bidirectional_iterator_tag)
{
    while (__first != __last)
    {
        if (__first == --__last)
            break;
        _IterOps<_AlgPolicy>::iter_swap(__first, __last);
        ++__first;
    }
}

以下程式碼為對於隨機存取迭代器 (Random-Access Iterator) 的實作:

1
2
3
4
5
6
7
8
9


template <class _AlgPolicy, class _RandomAccessIterator>
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
void
__reverse_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, random_access_iterator_tag)
{
    if (__first != __last)
        for (; __first < --__last; ++__first)
            _IterOps<_AlgPolicy>::iter_swap(__first, __last);
}

當使用不支援雙向操作的迭代器時 (如 forward_list 的正向迭代器)，會產生編譯錯誤，因為沒有針對 std::forward_iterator_tag 的 __reverse_impl 實作:

1
2


std::forward_list<int> list = {1, 2, 3};
std::reverse(list.begin(), list.end());

錯誤訊息:

error: no matching function for call to '__reverse_impl'

參考資料

C++ Primer, 5ed - Ch10.5

TL;DR#

前言: 什麼是迭代器 (Iterator)#

簡介#

迭代器分類#

輸入迭代器 (Input Iterator)#

輸出迭代器 (Output Iterator)#

正向迭代器 (Forward Iterator)#

雙向迭代器 (Bidirectional Iterator)#

隨機存取迭代器 (Random-Access Iterator)#

iterator_traits 簡介#

什麼是 iterator_traits#

使用 iterator_traits 提取型別資訊#

iterator_category 的用途#

指標型別的特化#

iterator_traits 使用範例#

std::distance#

std::reverse#

參考資料#