STL_List与萃取

List

参考文章: https://blog.csdn.net/weixin_45389639/article/details/121618243

List源码

在这里插入图片描述

List中节点的定义：
list是双向列表，所以其中节点需要包含指向前一节点和后一节点的指针， data是节点中存储的数据类型

template <class _Tp>
struct _List_node {typedef void* _Void_pointer;_Void_pointer _M_next;_Void_pointer _M_prev;_Tp _M_data;
};

List列表的定义

template<class T,class Alloc=alloc>
class list
{
protected:typedef __list_node<T> list_node;
public:typedef list_node* link_type;typedef __list_iterator<T,T&,T*>iterator;
protected:link_type node;
...
}

list(双向链表),在GNU2.9源码中，list类中维护了node这个属性，这个属性就是一个包含两个指针prev、next和当前data的结构体。基于容器都要满足前闭后开的原则，在list的头部会添加一个灰部地带，begin()获得灰部地带下一个节点，end()获得灰部地带。

在这里插入图片描述

List迭代器

list_iterator其中定义了5种参数，这五种参数是为了Iterator traits做准备
在STL的算法中，需要传入容器的迭代器，然后根据推断判断出迭代器的类型。

bidirectional_iterator_tag :指明迭代器类别，双向列表指针迭代器、单向列表指针迭代器、任意方向链表指针迭代器
T(value_type):迭代器指向的数据类型
ptrdiff_t(difference_type) 两个迭代器之间的距离，用什么type表现
ptr(pointer) 后两个，在此版本中没有使用
Ref(reference)

迭代器源码

// __list_iterator源码
template<class T,class Ref,class Ptr>
struct __list_iterator
{typedef __list_iterator<T,Ref,Ptr> self;typedef bidirectional_iterator_tag iterator_category;typedef T value_type;typedef Ptr pointer;typedef Ref reference;typedef __list_node<T>* link_type;typedef ptrdiff_t difference_type;link_type node;reference operator*()const{return *(node).data;}pointer operator->()const{return &(operator*());}self& operator++(){node = (link_type)(*node).next;return *this;}self operator++(int){self temp = *this;++*this;return temp;}...
};

迭代器萃取机Iterator traits

template<typename _ForwardIterator>
inline void rotate(_ForwardIterator __first,_ForwardIterator __middle,_ForwardIterator __last){...std::__rotate(__first,__middle,__last,std::__iterator_category(__first));
}template<typename _Iter>
inline typename iterator_traits<_Iter>::iterator_category __iterator_category(const _Iter&){return typename iterator_traits<_Iter>::iterator_category();
}

迭代器是算法和容器的桥梁
算法执行，需要获取迭代器包含的5种类型的参数
如上述所示为算法rotate的部分代码，可知算法内部还需要做Iterator类型获取操作
在这里插入图片描述

同时为了考虑兼容性的问题，就在迭代器和算法之间加了一中间层"萃取机"(traits),同时也是为了用它来辨别iterator是class类型还是non-class(指针)类型

那么问题来了，traits是如何分辨class和non-class类型的iterator呢?答案是partial specialization(模板的偏特化)。

// iterator为class类型，直接取默认泛型
template<class I>
struct iterator_traits {typedef typename I::iterator_category 	iterator_category;typedef typename I::value_type 			value_type;typedef typename I::difference_type 	difference_type;typedef typename I::pointer 			pointer;typedef typename I::reference 			reference;
};// iterator为指针
template<class T>
struct iterator_traits<T *> {typedef random_access_iterator_tag 		iterator_category;typedef T 								value_type;typedef ptrdiff_t 						difference_type;typedef T*								pointer;typedef T&								reference;
};// iterator为常量指针
template<class T>
struct iterator_traits<const T *> {typedef random_access_iterator_tag 		iterator_category;typedef T 								value_type;	typedef ptrdiff_t 						difference_type;typedef const T*						pointer;typedef const T&						reference;
};