源码剖析：STL中迭代器概念与Traits编程方法

Wild_Pointer

601人浏览 · 2024-05-19 19:23:37

Wild_Pointer · 2024-05-19 19:23:37 发布

前言

迭代器的设计在STL的实现中起到了至关重要且十分基础的作用，本篇文章也皆在对迭代器的设计思想以及迭代器的实现进行分析讲解，其中文章出现的Traits方法就属于迭代器设计的基础，对于迭代器的正确使用有着不可替换的地位，所以本篇文章也将重点对Traits方法进行讲解

迭代器的设计思想

在讲解迭代器的设计思想之前，我想先唠唠STL的中心思想：将数据容器和算法分开，彼此进行独立的设计，最后再以某个对象进行相互使用。而这个能使数据容器和算法相互使用的对象就是迭代器，故设计迭代器的原因即是使设计的数据容器和算法相互使用。

在对Traits编程方法进行讲解时，我们先看一小段简单的代码，活跃一下脑子，防止后续使用Traits方法设计迭代器时脑子瓦特。该段代码演示的是如何对模板传入的参数的类型进行推导，思路是传入对象的指针，通过借用模板的特性对传入的对象指针进行推导：

int main(){
    int i;
    func(&i);    // func()的目标是对传入的地址进行类型推导
    //此处传入的是一个int类型的指针
}

template <class I>
inline void fun(I iter){    //接收任意类型的迭代器
    func_impl(iter, *iter);  //调用func_impl()函数传入迭代器和通过迭代器解引用得到的元素值
}

template <class I, class T>
void func_impl(I iter, T t){    //iter是迭代器类型，t是该迭代器解引用后的元素值
    T tmp;    //声明tmp为类型T的对象
    T* ptr = &tmp;    //ptr是指向T类型对象的指针，这里指向tmp

    //现在ptr是一个指向T类型数据的指针，可以进行指针相关的操作
}

Traits编程方法

Traits编程方法是为了解决对迭代器类型的判断而产生的一种编程思想，在此小节之前曾展示过一段代码，该段代码也是Traits编程方法的一种简单体现。接下来我们将重点对如何判断迭代器类型，判断模板函数返回值的类型，处理模板函数接受元素为原生指针的情况，针对模板函数接受的元素为const的情况进行特化以及针对迭代器类型进行高效率的函数设计，一共五种解决问题都会在该小节进行讲解(原生指针：该类型由*操作符定义的对象，指向某一个对象的内存地址，该类型没有方法或成员变量，只提供基本的指针操作。例如：int*)：

1.判断参数类型：

上一小节代码以及为我们对如何判断参数类型提供了实现思路(PS：并不是偷懒不想重新写示例，哈哈哈！其实就是懒)：

int main(){
    int i;
    func(&i);    // func()的目标是对传入的地址进行类型推导
    //此处传入的是一个int类型的指针
}

template <class I>
inline void fun(I iter){    //接收任意类型的迭代器
    func_impl(iter, *iter);  //调用func_impl()函数传入迭代器和通过迭代器解引用得到的元素值
}

template <class I, class T>
void func_impl(I iter, T t){    //iter是迭代器类型，t是该迭代器解引用后的元素值
    T tmp;    //声明tmp为类型T的对象
    T* ptr = &tmp;    //ptr是指向T类型对象的指针，这里指向tmp

    //现在ptr是一个指向T类型数据的指针，可以进行指针相关的操作
}

2.判断函数返回值的类型：

如何判断函数返回值的类型，较于判断参数类型也是大同小异，其思路是通过模板函数，判断传入参数的类型，最后由模板函数返回传入参数的类型，重点在于函数应如何要判断传回的参数类型是什么？对此我们定义的对象中都内含一个成员对象ptr，其代表指向初始化对象的指针，以下便是代码实现：

template<class T>
struct MyIter {
    T* ptr;                //定义ptr为迭代器所指对象的指针
    typedef T value_type;  //定义value_type为迭代器类型（别名）
    MyIter(T* p = nullptr) : ptr(p) {}
    T& operator*() const { return *ptr; }  //重载解引用操作符
};

template<class I>
typename I::value_type func(I ite) {  //I::value_type代表返回值为传入的类型的指针
    return *ite;  //返回传入参数的解引用
}

int main() {
    MyIter<int> ite(new int(3020));
    cout << func(ite);  // 输出3020，注意释放动态分配的内存
    return 0;
}

3.处理模板函数接受元素为原生指针的情况：

因为我们希望当传入的对象为原生指针时，应该返回的左值而非右值，所以我们不能单纯依赖判断参数类型来解决这种情况，以下代码将对为什么希望传入的对象为原生指针时返回值应该是左值：

int* ptr = 6;
*ptr = 8;    //*ptr返回值为左值，即可以使用赋值

如何实现当传入的对象为原生指针时，返回的值为左值而非右值？其思路是对原本实现的判断参数类型和判断函数返回值类型的模板函数进行偏特化，对原本上文提供的实现MyIter对象的代码进行偏特化，增加新的参数类型typedef typename I::value_type value_type：

template <class T>
struct iterator_traits {    //模板结构体的定义
    typedef typename T::value_type value_type;
};

//实现判断参数类型的偏特化
template <class T>
struct iterator_traits<T*> { //模板结构体针对原生指针类型进行偏特化
    typedef T value_type; // 原生指针指向的对象的类型
};

//实现判断函数返回值类型的偏特化
template <class T>
typename iterator_traits<T*>::value_type func(T* ite) {
    return *ite;     //返回解引用指针得到的对象
}

4.针对模板函数接受的元素为const的情况：

针对模板函数接受的元素为const的情况，我们习惯下以为会一样返回的是const修饰的对象类型，但是针对该情况我们返回的值也将是一个无法使用的临时变量，对此我们针对接收的元素const的情况应使其返回值为非const，其实现思路与实现模板函数接受元素为原生指针的情况大同小异，也是针对接受的元素为const的情况进行偏特化：

template <class T>
struct iterator_traits{    //模板结构体的定义
    typedef typename T::value_type value_type;
};

//实现判断参数类型的偏特化
template <class T>
struct iterator_traits<cosnt T*>{    //模板结构体针对const类型进行偏特化
    typedef T value_type;
};

//实现判断函数返回值类型的偏特化
template <class T>
typename iterator_traits<const T*>::value_type func(T* ite) {
    return *ite;     //返回解引用指针得到的对象
}

针对迭代器类型设计高效率函数

在上一小节中解决了所描述的四个问题，此小节将针对最后一个问题：针对迭代器类型设计高效率的函数进行单独解决，因为设计内容多，实现细节多，所以单独开一个小节。在上一个小节，我们对模板传入的类型进行了判断，对模板函数的返回值进行了判断，还针对了原生指针和传入const元素的情况进行了偏特化。本节内容也是针对Traits编程方法进行讲解，结合上一小节内容设计一个对象能完整的实现Traits编程方法所解决的问题，以下就是我们设计的一个能完整实现Traits编程方法的对象结构：

//实现以下封装，能正确的实现Traits编程方法的思想等
template <class I>
struct iterator_traits{
    //以下是所有STL类型都应实现的封装
    typedef typename I::iterator_category iterator_category;//用于标记五种类型的迭代器
    typedef typename I::value_type value_type;              //用于标记迭代器所指对象的类型
    typedef typename I::pointer pointer;                    //用于标记指向迭代器所指的类型指针
    typedef typename I::reference reference;              
    //用于标记当使用*对迭代器进行解引用返回的是一个左值
    typedef typename I::difference_type difference_type;
    //用于标记从一个迭代器所指向的元素到另一个迭代器所指向的元素之间的元素个数    
}

以上便是针对Traits编程方法设计的结构，实现结构内的五种封装，便可以在数据容器与算法相互调用，而iterator_traits对象相当于一个照妖镜，把传入的对象的原型提取出来，方便调用对应的算法实现高效率的函数设计，下面将对如何设计实现这五种封装进行讲解：

1.value_type：

value_type还是跟上文代码如此，用于判断参数类型，代码实现如下(还是跟上文一模一样的代码，嘎嘎)：

template<class T>
struct iterator_traits{
    typedef typename T::value_type value_type;  //定义value_type为迭代器类型（别名）
};

//针对原生指针的特化
template<class T>
struct iterator_traits<T*> {
    typedef T* value_type;
};

//针对const原生指针的特化
template<class T>
struct iterator_traits<const T*> {
    typedef const T& value_type;
};

//定义判断参数类型的函数
template<class I>
typename iterator_traits<I>::value_type func(I ite) {
    return *ite;  //返回迭代器或指针指向的对象
}

2.difference_type：

difference_type的作用是表示两个迭代器之间的距离(尽管迭代器执行的对象类型不一样，但是还是可以判断两个迭代器之间存在的元素个数)，以STL的count()函数为例：

//实现STL中的count()函数
template <class InputIt, class T>
typename std::iterator_traits<InputIt>::difference_type 
count(InputIt first, InputIt last, const T& value) {
    typename std::iterator_traits<InputIt>::difference_type n = 0;
    for (; first != last; ++first) {
        if (*first == value) {
            ++n;
        }
    }
    return n;
}

//针对原生指针的偏特化
template <class T>
struct iterator_traits<T*> {
    typedef ptrdiff_t difference_type;
};

//针对const原生指针的偏特化
template <class T>
struct iterator_traits<const T*> {
    typedef ptrdiff_t difference_type;
};

3.reference_type：

reference_type用于在对迭代器进行解引用的时候，返回值是一个左值而非右值，其代码实现如下：

template <class I>
struct iterator_traits{
    typedef typename I::reference reference;
}

//针对原生指针的偏特化
template <class I>
struct iterator_traits{
    typedef I& reference;
}

//针对cosnt原生指针的偏特化
template <class I>
struct iterator_traits{
    typedef const I& reference;
}

4.pointer_type：

pointer_type用于在对其STL对象进行解引用或者使用->解析运算符是，返回的是右值而不是左值，其代码实现如下：

template <class I>
struct iterator_traits{
    typedef typename I::pointer pointer;
    typedef typename I::reference reference;
}

//针对原生指针的偏特化
template <class I>
struct iterator_traits{
    typedef T* pointer;
    typedef T& reference;
}

//针对cosnt原生指针的偏特化
template <class I>
struct iterator_traits{
    typedef const T* pointer;
    typedef const T& reference;
}

5.iterator_category：

iterator_category用于针对迭代器的类型进行专门的偏特化，提高效率，针对迭代器类型下表将对其简单讲解：

迭代器名	备注
InputIterator(输入迭代器)	用于只读容器中的元素
OuptputIterator(输出迭代器)	用于只写容器中的元素
ForwardIterator(前向迭代器)	对容器中的元素有着可读可写的权限，但访问次序只能顺序，不能逆序
BidirectionalIterator(双向迭代器)	对容器中的元素有着可读可写的权限，可以顺序访问元素，也可以逆序访问
RandomAccessIterator(随机迭代器)	对容器中的元素有着可读可写的权限，可以逆序和顺序访问元素，也可以使用下标的方式随机访问元素

表1.迭代器简单讲解

针对上表，其中前向迭代器继承自输出迭代器和输入迭代器，双向迭代器继承于前向迭代器，而随机迭代器继承于双向迭代器。针对iterator_category，我们将对advance()函数(该函数用于将STL容器中的指针前进n次)的源码进行讲解：

//针对迭代器的类型，STL源码中在iterator_category设计了一下五种结构体
struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public bidirectional_iterator_tag {};

针对上述设计的结构体，只用于标记作用，没有任何接口以及成员。因此对advance()函数我们会有以下针对迭代器类型所进行的重载：

//advance函数的实现
template <class InputIterator, class Distance>
inline void advance(InputIterator& i,Distance n){
    _advance(i,n,iterator_traits<InputIterator>::iterator_category());
    //通过iterator_category获得迭代器的类型
}

//针对输入迭代器的偏特化
template <class InputIterator, class Distance>
inline void _advance(InputIterator& i, Distance n, input_iterator_tag){
    while(n--) ++i;
}

//针对前向迭代器的偏特化
template <class ForwardIterator, class Distance>
inline void _advance(ForwardIterator& i, Distance n, forward_iterator_tag){
    //对输入迭代器的偏特化进行调用
    _advance(i,n,input_iterator_tag());
}

//针对双向迭代器的偏特化
template <class BidiectionalIterator, class Distance>
inline void _advance(BidiectionalIterator& i, Distance n, bidiectional_iterator_tag){
    if(n >= 0)
        while(n--) ++i;
    else 
        while(n++) --i;
}

//针对随机迭代器的偏特化
template <class RandomAccessIterator, class Distance>
inline void _advance(RandomAccessIterator& i, Distance n, random_access_iterator_tag){
   i += n;
}

关于iterator_category的设计，还有一个distance()函数(用于计算两个迭代器之间的距离)，也使用了其iterator_category对迭代器的类型进行判断，并对其进行偏特化，其实现代码如下：

//distance()函数的实现
template <class InputIterator>
inline iterator_traits<InputIterator>::difference_type
_distance(InputIterator first, InputIterator last){
    typedef typename iterator_traits<InputIterator>::iterator_category category;
    return _distance(first,last,category());
}

//针对输入迭代器的偏特化
template <class InputIterator>
inline iterator_traits<InputIterator>::difference_type  //这是判断迭代器之间距离的封装
_distance(InputIterator first, InputIterator last, input_iterator_tag){
    iterator_traits<InputIterator>::difference_type n = 0;
    while(first != last){
        ++first;
        ++n;
    }
    return n;
}

//针对随机迭代器的偏特化
template <class RandomAccessIterator>
inline iterator_traits<RandomAccessIterator>::difference_type
_distance(RandomAccessIterator first, RandomAccessIterator last, random_access_iterator_tag){
    retuen last - first;
}

PS：以上便是该篇文章的所有内容，大多数都涉及到了模板，所以学好模板的使用对源码的阅读还是有所帮助的