STL源码分析

2024-01-30 19:46| 来源: 网络整理| 查看: 265

往期回顾(更多精彩内容，请专注微信公众号：悟空者说) STL源码分析--内存分配器 STL源码分析--vector STL源码分析--string STL源码分析--list STL源码分析--hashtable STL源码分析--deque

1 相关头文件 iterator iterator.h stl_iterator.h stl_iterator_base.h 2 输入迭代器 2.1 iterator的种类

在STL中，迭代器分为输入迭代器、输出迭代器、前向迭代器、双向迭代器、随机访问迭代器。这里先讲输入迭代器这个大类。

输入迭代器: input_iterator 输入迭代器指向的位置只能被顺序读取(iterator_category类型为input_iterator_tag)。在每种迭代器类型中，必须定义iterator_category表示迭代器种类，value_type表示迭代器指向的实例类型，difference_type表示迭代器距离的类型，pointer表示迭代器指向的实例的指针类型，reference表示实例应用类型。 template struct input_iterator { typedef input_iterator_tag iterator_category; typedef _Tp value_type; typedef _Distance difference_type; typedef _Tp* pointer; typedef _Tp& reference; }; 输出迭代器：ouput_iterator 输出迭代器指向的位置只能被顺序写入(iterator_category类型为output_iterator_tag) struct output_iterator { typedef output_iterator_tag iterator_category; typedef void value_type; typedef void difference_type; typedef void pointer; typedef void reference; }; 前向迭代器: forward_iterator 前向迭代器只能自增不能自减，它是一种特殊的输入迭代器(iterator_category类型为forward_iterator_tag，而后者正是input_iterator_tag的派生类) template struct forward_iterator { typedef forward_iterator_tag iterator_category; typedef _Tp value_type; typedef _Distance difference_type; typedef _Tp* pointer; typedef _Tp& reference; }; struct forward_iterator_tag : public input_iterator_tag {}; 双向迭代器：bidirectional_iterator 双向迭代器既能自增，又能自减，它是一种特殊的前向迭代器（能够自减的前向迭代器）。注意iterator_category类型为bidirectional_iterator_tag，而后者正是forward_iterator_tag的派生类。 template struct bidirectional_iterator { typedef bidirectional_iterator_tag iterator_category; typedef _Tp value_type; typedef _Distance difference_type; typedef _Tp* pointer; typedef _Tp& reference; }; struct bidirectional_iterator_tag : public forward_iterator_tag {}; 随机访问迭代器：random_access_iterator 随机访问迭代器，是一种特殊的双向迭代器，除了自增自减1之外，还能自增自减n。注意iterator_category类型为random_access_iterator_tag，而后者正是bidirectional_iterator_tag的派生类。 template struct random_access_iterator { typedef random_access_iterator_tag iterator_category; typedef _Tp value_type; typedef _Distance difference_type; typedef _Tp* pointer; typedef _Tp& reference; }; 2.2 iterator类型萃取

作用：将不同种类迭代器中定义的iterator_category, value_type, difference_type, pointer, reference类型转化为萃取器自身的类型。当上层调用萃取器iterator_traits时，迭代器类型(作为iterator_traits的模板参数)对上层是透明的。

实现如下，由于2.1中所有迭代器中，都定义了iterator_category等类型，iterator_traits便可将迭代器中的类型导出作为自身类型。

template struct iterator_traits { typedef typename _Iterator::iterator_category iterator_category; typedef typename _Iterator::value_type value_type; typedef typename _Iterator::difference_type difference_type; typedef typename _Iterator::pointer pointer; typedef typename _Iterator::reference reference; };

某些特殊情况下，原始指针_Tp*也可作为iterator使用(例如数组中的原始指针)。因为_Tp*内部并未定义以上类型，因此iterator_traits需要对_Tp*和const _Tp*进行特化。

template struct iterator_traits { typedef random_access_iterator_tag iterator_category; typedef _Tp value_type; typedef ptrdiff_t difference_type; typedef _Tp* pointer; typedef _Tp& reference; }; template struct iterator_traits { typedef random_access_iterator_tag iterator_category; typedef _Tp value_type; typedef ptrdiff_t difference_type; typedef const _Tp* pointer; typedef const _Tp& reference; };

有了iterator_traits，迭代器操作便可根据不同的类型进行不同的实现。

2.3 iterator_category函数(返回迭代器种类)

实现如下，模板入参为迭代器，iterator_category函数所返回的是迭代器中iterator_category类型的实例。

template inline typename iterator_traits::iterator_category iterator_category(const _Iter& __i) { return __iterator_category(__i); } template inline typename iterator_traits::iterator_category __iterator_category(const _Iter&) { typedef typename iterator_traits::iterator_category _Category; return _Category(); } 2.4 distance函数(返回两迭代器之间距离)

实现如下，首先通过iterator_category函数获取迭代器种类，再将其值作为参数传给__distance函数。

template inline void distance(_InputIterator __first, _InputIterator __last, _Distance& __n) { __STL_REQUIRES(_InputIterator, _InputIterator); __distance(__first, __last, __n, iterator_category(__first)); }

返回结果关键在于__distance函数。对于不同的迭代器类型，重载了不同的__distance实现，这些实现使用了迭代器中的iterator_category类型进行区分。

例如：对于随机访问迭代器类型，计算distance只需将两个迭代器相减即可。

template inline void __distance(_RandomAccessIterator __first, _RandomAccessIterator __last, _Distance& __n, random_access_iterator_tag) { __STL_REQUIRES(_RandomAccessIterator, _RandomAccessIterator); __n += __last - __first; }

对于其他迭代器(都属于input_iterator类型)，实现上则需要从__first步步递进并计数，直到到达__last为止，最后返回计数值

template inline void __distance(_InputIterator __first, _InputIterator __last, _Distance& __n, input_iterator_tag) { while (__first != __last) { ++__first; ++__n; } } 2.5 advance函数(迭代器偏移n个位置)

对于advance函数, 不同类型迭代器其实现也不尽相同。

random_access_iterator：随机访问迭代器支持一次跳转多步，因此可一次跳转至目标位置 bidirectional_iterator: 双向迭代器同时支持前向自增1和后向自增1。如果n>=0, 迭代器重复执行n次自增1, 如果n= 0) while (__n--) ++__i; else while (__n++) --__i; } template inline void __advance(_InputIter& __i, _Distance __n, input_iterator_tag) { while (__n--) ++__i; } 2.6 反向迭代器

反向迭代器一般用于逆向遍历容器。其自增和自减的方向与其封装的迭代器正好是反过来的。

iterator_type base() const { return current; } reference operator*() const { _Iterator __tmp = current; return *--__tmp; } _Self& operator++() { --current; return *this; } _Self operator++(int) { _Self __tmp = *this; --current; return __tmp; } _Self& operator--() { ++current; return *this; } _Self operator--(int) { _Self __tmp = *this; ++current; return __tmp; }

构造时，输入类型为_Iterator的迭代器对象__x, reverse_iterator即为_Iterator的逆操作。API如下：

base: 返回被封装的__x迭代器 operator*: 返回*(__x-1) (容器的end iterator为虚边界，当基于end iterator生成反向迭代器时，执行operator*应当返回容器的最后一个元素) operator++: __x自减1 operator--: __x自增1 3 输出迭代器

back_inserter_iterator, front_insert_iterator, insert_iterator中都定义了iterator_category类型为output_iterator_tag。因此它们都是输出迭代器。

举back_insert_iterator为例，其中模板参数_Container为STL容器类型，iterator_category为output_iterator_tag类型。

template class back_insert_iterator { protected: _Container* container; public: typedef _Container container_type; typedef output_iterator_tag iterator_category; ... }; 3.1 back_insert_iterator

用于向容器尾部插入元素

back_insert_iterator& operator=(const typename _Container::value_type& __value) { container->push_back(__value); return *this; }

back_inserter_iterator执行operator=操作时，总是对容器push_back(容器必须实现push_back接口)

3.2 front_insert_iterator

用于向容器头部插入元素

explicit front_insert_iterator(_Container& __x) : container(&__x) {} front_insert_iterator& operator=(const typename _Container::value_type& __value) { container->push_front(__value); return *this;

front_inserter_iterator执行operator=操作时，总是对容器push_front(容器必须实现push_front接口)

3.3 insert_iterator

用于向容器指定位置插入元素

insert_iterator(_Container& __x, typename _Container::iterator __i) : container(&__x), iter(__i) {} insert_iterator& operator=(const typename _Container::value_type& __value) { iter = container->insert(iter, __value); ++iter; return *this; }

insert_iterator构造时传入容器和迭代器iter，执行operator=操作时，总是对容器执行insert, 插入位置由迭代器iter决定(容器必须实现insert接口)

更多精彩内容，请关注微信公众号悟空者说

【本文地址】

公司简介

联系我们