C++标准模板库(STL)迭代器的原理与实现

时间：2022-07-03 21:40:03

引言

迭代器(iterator)是一种抽象的设计理念，通过迭代器可以在不了解容器内部原理的情况下遍历容器。除此之外，STL中迭代器一个最重要的作用就是作为容器(vector,list等)与STL算法的粘结剂，只要容器提供迭代器的接口，同一套算法代码可以利用在完全不同的容器中，这是抽象思想的经典应用。

使用迭代器遍历不同容器

如下所示的代码演示了迭代器是如何将容器和算法结合在一起的，其中使用了三种不同的容器，.begin()和.end()方法返回一个指向容器第一个元素和一个指向容器最后一个元素后面一个位置的迭代器，也就是说begin()和end()返回的迭代器是前闭后开的一般用[begin,end)表示。对于不同的容器，我们都使用同一个accumulate函数,原因就在于accumulate函数的实现无需考虑容器的种类，只需要容器传入的begin()和end() 迭代器能够完成标准迭代器的要求即可。

    std::vector<int>vec{ 1, 2, 3 };
std::list<int>lis{ 4, 5, 6 };
std::deque<int>deq{ 7, 8, 9 };

std::cout << std::accumulate(vec.begin(), vec.end(), 0) << std::endl \
        << std::accumulate(lis.begin(), lis.end(), 0) << std::endl \
        << std::accumulate(deq.begin(), deq.end(), 0) << std::endl;
//6
//15
//24

迭代器的实现

迭代器的作用就是提供一个遍历容器内部所有元素的接口，因此迭代器的内部必须保存一个与容器相关联的指针，然后重载各种运算操作来方便遍历，其中最重要的就是 ∗ 运算符和->运算符，以及++，–等可能需要的运算符重载。实际上这和C++标准库中的智能指针(smart pointer)很像，智能指针也是将一个指针封装，然后通过引用计数或是其它方法完成自动释放内存的功能，为了达到和原有指针一样的功能，也需要对*，->等运算符进行重载，下面参照智能指针实现了一个简单vector的迭代器，其中几个typedef暂时不用管，我们后面会提到。vecIter主要作用就是包裹一个指针，不同容器内部数据结构不相同，因此迭代器操作符重载的实现也会不同。比如++操作符，对于线性分配内存的数组来说，直接对指针执行++操作即可，但是如果容器是List就需要采用元素内部的方法，比如ptr->next()之类的方法访问下一个元素。因此，STL容器都实现了自己的专属迭代器。

template<class Item>
class vecIter{
    Item *ptr;
public:
typedef std::forward_iterator_tag iterator_category;
typedef Item value_type;
typedef Item* pointer;
typedef Item& reference;
typedef std::ptrdiff_t difference_type;
public:
    vecIter(Item *p = 0) :ptr(p){}
    Item& operator*()const{
return *ptr;
    }
    Item* operator->()const{
return ptr;
    }
//pre
    vecIter& operator++(){
        ++ptr;
return *this;
    }
    vecIter operator++(int){
        vecIter tmp = *this;
        ++*this;
return tmp;
    }

bool operator==(const vecIter &iter){
return ptr == iter.ptr;
    }
bool operator!=(const vecIter &iter){
return !(*this == iter);
    }

};
int main(){
int a[] = { 1, 2, 3, 4 };
std::cout << std::accumulate(vecIter<int>(a), vecIter<int>(a + 4), 0);//输出 10

}

迭代器的相应型别

我们都知道type_traits 可以萃取出类型的型别，根据不同型别可以执行不同的处理流程。那么对于迭代器来说，是否有针对不同特性迭代器的优化方法呢？答案是肯定的。拿一个STL算法库中的distance函数来说，distance函数接受两个迭代器参数，然后计算他们两者之间的距离。显然对于不同的迭代器计算效率差别很大。比如对于vector容器来说，由于内存是连续分配的，因此指针直接相减即可获得两者的距离；而list容器是链式表，内存一般都不是连续分配，因此只能通过一级一级调用next()或其他函数，每调用一次再判断迭代器是否相等来计算距离。vector迭代器计算distance的效率为O(1),而list则为O(n),n为距离的大小。

因此，根据迭代器不同的特性，将迭代器分为5类:

  • Input Iterator:这种迭代器所指的对象为只读的。
  • Ouput Iterator: 所指对象只能进行一次写入操作。
  • Forward Iterator: 允许”读写型”算法在迭代器区间内进行读写操作，比如说replace函数需要读取区间内容，根据所读内容决定是否写入
  • Bidirectional Iterator : 可双向移动。某些算法需要反向遍历某个迭代器区间
  • Random Access Iterator : 前四种迭代器只提供部分指针算数能力(前三种支持++运算符，后一种还支持–运算符),第五种则支持所有指针的算术运算，包括p + n,p - n,p[n],p1 - p2,p1 < p2

这五种迭代器的继承关系如下所示。

C++标准模板库(STL)迭代器的原理与实现

了解了迭代器的类型，我们就能解释vector的迭代器和list迭代器的区别了。显然vector的迭代器具有所有指针算术运算能力，而list由于是双向链表，因此只有双向读写但不能随机访问元素。故vector的迭代器种类为Random Access Iterator,list 的迭代器种类为Bidirectional Iterator。我们只需要根据不同的迭代器种类，利用traits编程技巧萃取出迭代器种类，然后由C++的重载机制就能够对不同型别的迭代器采用不同的处理流程了。为此，对于每个迭代器都必须定义型别iterator_category,也就是上文代码中的typedef std::forward_iterator_tag iterator_category; 实际中可以直接继承STL中定义的iterator模板,模板后三个参数都有默认值，因此继承时只需要指定前两个模板参数即可。如下所示，STL定义了五个空类型作为迭代器的标签。

template<class Category,class T,class Distance = ptrdiff_t,class Pointer=T*,class Reference=T&>
class iterator{
typedef Category iterator_category;
typedef T        value_type;
typedef Distance difference_type;
typedef Pointer  pointer;
typedef Reference reference;
};

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{};

利用迭代器种类更有效的实现distance函数

回到distance函数，有了前面的基础，我们可以根据不同迭代器种类实现distance函数。

    template<class InputIterator>
inline typename std::iterator_traits<InputIterator>::difference_type distance(InputIterator first, InputIterator last){
return __distance(first, last, std::iterator_traits<InputIterator>::iterator_category());
    }
template<class InputIterator>
inline typename std::iterator_traits<InputIterator>::difference_type __distance(InputIterator first, InputIterator last, std::input_iterator_tag){
std::iterator_traits<InputIterator>::difference_type n = 0;
while (first != last){
                ++first; ++n;
            }
return n;
        }

template<class InputIterator>
inline typename std::iterator_traits<InputIterator>::difference_type \
        __distance(InputIterator first, InputIterator last, std::random_access_iterator_tag){
return last - first;
        }


int main(){
int a[] = { 1, 2, 3, 4 };
std::vector<int> vec{ 1, 2, 3, 4 };
std::list<int> lis{ 1, 2, 3, 4 };
std::cout<<"vec distance:"<<WT::distance(vec.begin(), vec.end())<<std::endl;
std::cout << "list distance:" << WT::distance(lis.begin(), lis.end())<<std::endl;
std::cout << "c-array distance:" << WT::distance(a,a + sizeof(a) / sizeof(*a)) << std::endl;
//输出 vec distance:4
// list distance:4
// c-array distance:4
}

这里通过STL 定义的iterator_traits模板可以将萃取不同种类的迭代器特性，iterator_traits还对指针和常量指针有特化版本，因此也可以萃取原生指针的特性。具体实现如下:

    template <class Iterator>
struct iterator_traits{
typedef typename Iterator::iterator_category iterator_category;
typedef typename Iterator::value_type value_type;
typedef typename Iterator::pointer pointer;
typedef typename Iterator::reference reference;
typedef typename Iterator::difference_type difference_type;

    };
template <class T>
struct iterator_traits<T*>{
typedef std::random_access_iterator_tag iterator_category;
typedef T value_type;
typedef T* pointer;
typedef T& reference;
typedef ptrdiff_t difference_type;
    };

template <class T>
struct iterator_traits<const T*>{
typedef std::random_access_iterator_tag iterator_category;
typedef T value_type;
typedef const T* pointer;
typedef const T& reference;
typedef ptrdiff_t difference_type;
    };

小结

STL使用迭代器将算法和容器结合，利用迭代器型别可以针对不同迭代器编写更加高效的算法，这里一点很重要的思想就是：利用C++重载机制和参数推导机制将运行期决议问题提前到编译期决议，也就是说，我们不需要在运行时判断迭代器的类型，而是在编译期就已经决定。这很符合C++模板编程的理念。在后续的STL学习中，我们会实现自己的各种容器，也必须实现各种各样的迭代器，因此迭代器的学习还远没有停止。
标签：

相关文章