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

​ 其中value_type的主要目的是用来声明变量，而声名一个无法被赋值的变量没什么用，所以iterator(即使是const iterator)的value_type不应加上const。