文章首发于：My Blog 欢迎大佬们前来逛逛

1. 迭代器设计思维

STL的中心思想：将数据容器与算法分离开，彼此独立设计，再以一剂黏着剂将二者撮合在一起。

如何设计出这样的黏着剂呢？

//两个迭代器和一个搜索对象
template <class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T& value) {
  while (first != last && *first != value) ++first;
  return first;
}

find算法的源码揭示了 容器算法与迭代器之间的合作关系

1.1 制作List及其迭代器

来为list设计一个迭代器：

$ mylist.h

#ifndef MT_LIST
#define MT_LIST

template <typename T>
class ListNode
{
public:
	ListNode(T val, ListNode* pnext = nullptr)
		:_data(val), _next(pnext) {}
	T value()const { return this->_data; }
	ListNode* next()const { return this->_next; } //关键函数
	bool operator!=(const T& val)const { return this->_data!=val; }
public:
	T _data;
	ListNode* _next;	//next指针
};

template <typename T>
class List
{
public:
	List() :_front(nullptr), _end(nullptr), _size(0) {}
	//单链表尾插
	void insert_end(T value)
	{
		ListNode<T>* pNew = new ListNode<T>{ value };
		this->_end->_next = pNew;
		this->_end = pNew;
		this->_size++;
	}
	//单链表头插
	void insert_front(T value)
	{
		ListNode<T>* pNew = new ListNode<T>(value);
		pNew->_next = this->_front;
		this->_front = pNew;
		this->_size++;
		if (this->_size == 1)
		{
			this->_end = this->_front;
		}
	}
	//遍历链表
	void show(std::ostream& out=std::cout)
	{
		ListNode<T>* temp = this->_front;
		while (temp!=nullptr)
		{
			out << temp->value() << " ";
			temp = temp->_next;
		}
		out << "\n";
	}
	std::ostream& operator<<(std::ostream& os) {}
public:
	ListNode<T>* front()const { return this->_front; }
	ListNode<T>* end()const { return this->_end; }
private:
	ListNode<T>* _end;
	ListNode<T>* _front;
	size_t _size;
};

#endif // !MT_LIST

$ mylist-iter.h

#ifndef MY_LIST_ITER
#define MY_LIST_ITER
#include "mylist.h"
template <typename Node>
class ListIter
{
public:
	ListIter<Node>(Node* p = NULL)
		:_ptr(p) {}
	Node& operator*()const { return *_ptr; }
	Node* operator->()const { return _ptr; }
	ListIter& operator++()
	{
		//前置++
		_ptr = _ptr->next(); //! 暴露了ListNode的next函数
		return *this;
	}
	ListIter operator++(int)
	{
		//后置++
		ListIter temp = *this;
		++* this;
		return temp;
	}
	bool operator==(const ListIter& lhs)const { return _ptr == lhs._ptr; }
	bool operator!=(const ListIter& lhs)const { return _ptr != lhs._ptr; }
private:
	Node* _ptr;
};

#endif

$ main

#include <iostream>
#include <algorithm>
#include "mylist-iter.h"

template <class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T& value) {
	/*
	传入后first和last调用ListIter类的重载的!=运算符。
	但是*first得到的是ListNode<T>类型的值，因此为了比较与T类型的值还需要进行操作：
		1. 直接在外部添加针对ListNode<T>和T的!=的重载运算符
		2. 在ListNode<T>内添加重载!=的运算符
	*/
	while (first != last && *first != value) ++first;

	return first;
}

#if 0
template <typename T>
bool operator!=(const ListNode<T>& pnode, const T& val)
{
	return pnode.value() != val;
}
#endif

int main()
{
	List<int> mlist;
	for (int i = 1; i <= 5; i++)
	{
		mlist.insert_front(i);
		mlist.insert_end(i + 10);
	}
	mlist.show();

	ListIter<ListNode<int>> beg(mlist.front());
	ListIter<ListNode<int>> end;
	ListIter<ListNode<int>> Iter;
	Iter = find(beg, end, 11);
	if (Iter == end) std::cout << "没有找到!" << '\n';
	else std::cout << "找到了! " << Iter->value() << '\n';
	return 0;
}

为了实现一个针对 List的迭代器，我们暴露了太多关于 List 的细节：

在制作beg和end迭代器的时候，我们暴露了 ListNode 这个一个类。
在 Find 的时候，我们暴露了 ++ 运算符的关于 ListNode类的 next操作。

ListNode作为一个内部节点，应该完全隐藏起来才对。

这时 List 的迭代器的一个雏形，通过往下的学习，我们将逐步解决这些问题。

1.2 迭代器的相应型别

在运用迭代器的时候，我们很可能会用到迭代器的相应型别，

迭代器所指之物的型别便是相应型别

获得《迭代器相应型别》的型别：

利用 function template的参数推导机制：

template <typename Iter,typename T>
void func_temp(Iter it,T t)
{
	//it: int* ; t: int
	T tmp; //tmp: int
    //func：
}

template <typename T>
void func(T val)
{
	func_temp(val, *val);//val: int* ;  *val: int
}
int main()
{
	int a = 10;
	func(&a);

	return 0;
}

把func函数全部功能全部放入func_temp中，在func_temp通过template参数推导自动获得了 型别T

这样T 就是迭代器所指之物的型别

但是迭代器的相应型别不只是所指之物的型别，相应的型别有五种，但是并非任何情况下都能使用这个template参数推导来取得。

1.3 Traits编程技巧

迭代器所指对象的型别称为该迭代器的 value type。

template参数推导无法处理作为返回值的 value type，如果解决这个问题？

template <typename T>
struct Mystu
{
	T* ptr;
	Mystu(T* ptr = NULL) :ptr(ptr) {}
	T& operator*()const { return *ptr; }
};
template <typename T>
T func2(T ite)
{
	//T的型别是 ite的型别即 Mystu<int> 但是作为返回值的类型是什么呢？
	return *ite;//解引用获得其值
}

使用内嵌类型声明：

template <typename T>
struct Mystu
{
	typedef T value_type;	//内嵌型别
	T* ptr;
	Mystu(T* ptr = NULL) :ptr(ptr) {}
	T& operator*()const { return *ptr; }
};

template <typename T>
typename T::value_type func2(T ite)
{
	//T的型别是 ite的型别即 Mystu<int> 但是作为返回值的类型是什么呢？
	return *ite;//解引用获得其值
}
int main()
{
	Mystu<int> b{ new int{10} };
	std::cout<<func2(b);

	return 0;
}

关键做法：

在类中需要对 T 参数进行typedef。
在作为返回值的地方必须使用 typename 作为修饰，然后返回T的型别

关键词typename告诉编译器这是一个 Mystu< T >::value_type的型别

但是如果不是 类类型，就无法使用上述的定义内嵌类型的形式

原生指针就不是类，因此无法定义内嵌型别。

例如：

1 2	int* c = new int{ 10 }; std::cout<<func2(c); //ERROR

你会发现，就会报错，没有匹配的函数，因为原生指针不是类，无法定义内嵌类型

但是STL提供了一种方法可以使得原生指针作为一种特殊情况被一般化。

偏特化！

萃取迭代器的类型：

//3. 萃取迭代器的类型
template <typename T>
struct iterator_traits //普通类型
{
	//如果 T 有自己的value_type 那么通过这个traits，萃取出来的value_type 就是T的value_type
	typedef typename T::value_type value_type;
};
template <typename T>
typename iterator_traits<T>::value_type func3(T ite)
{
	return *ite;
}

但是我们会发现，他不和上面的内嵌型别是一样的吗，而且返回值还写复杂了，有什么用呢？

我们再写一个针对iterator_traits的偏特化版本：

// traits的特化版本
template <typename T>
struct iterator_traits<T*>
{
	typedef T value_type;
};

这时候，你就会发现，这条语句竟然成功了，并且返回 10作为返回值：

1 2	int* c = new int{ 10 }; std::cout<<func3(c); //OK

这是因为 c作为一个普通的指针，我们传入 func3 函数之后，函数察觉到了这是一个原生指针，因此调用 iterator_traits的原生指针T* 的偏特化版本，使得可以接受一个原生指针

解决参数是 const 类型的原生指针：

1 2	const int* d = new int{ 20 }; std::cout<<func3(d); //OK but 我们返回的仍然是const int 类型的值

如果我们返回一个非 const，则可以针对const 指针再来一个偏特化版本：

// traits的特化版本 const版本
template <typename T>
struct iterator_traits<const T*>
{
	typedef T value_type;
};

这样函数的返回值就是一个非const，即去除了参数的 const属性。

traits 所扮演的特性是 特性萃取机的角色，萃取各个迭代器的相应型别，要使得特性萃取机能够有效的工作，每一个迭代器都应该以内嵌类型定义的形式定义出相应的型别。

迭代器一共有五种相应型别：

value_type
difference_type
pointer
reference
iterator_catagoly

为你的迭代器定义这五种相应型别。

1.3.1 value_type

value_type是指迭代器的所指对象的相应型别。如上节所示，value_type 是任何STL容器的设计基础。

1.3.2 deference_type

deference_type用来表示表示两个迭代器之间的距离，可以用来表示一个容器的最大容量。

count函数用来返回等于val值的个数，因此如果一个泛型算法具有计数的功能，其返回值就必须使用deference_type类型的值。

template <typename T>
struct iterator_traits
{
	typedef typename T::deference_type deference_type;
};
//count算法
template <typename Iter,typename T>
typename iterator_traits<T>::deference_type count(Iter beg, Iter end, const T& val)
{
	typename iterator_traits<T>::deference_type n = 0;
	for (; beg != end; ++beg)
	{
		if (*beg == val)n++;
	}
	return n;
}

我们刚才自己写的 List就可以来测试一下：

只需要在List 的类中加上

1	typedef ptrdiff_t difference_type

ptrdiff_t 是一个 int64类型的值，用于统计。

//原版
template <typename T>
struct iterator_traits
{
	typedef typename T::difference_type difference_type;
};
//针对原生指针的偏特化版本
template <typename T>
struct iterator_traits<T*>
{
	typedef T difference_type;
};


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

template <typename Iter, typename T>
typename iterator_traits<Iter>::difference_type _count(Iter beg, Iter end, const T& val)
{
	typename iterator_traits<Iter>::difference_type n = 0;//n: ptrdiff_t
	for (; beg != end; ++beg)
	{
		if (*beg == val)
			++n;
	}
	return n;
}

int main()
{
	List<int> p;
	for (int i = 1; i <= 10; i++)
	{
		p.insert_end(i);
	}
	p.insert_end(5);
	p.show();

	ListIter<ListNode<int>> beg(p.front());
	ListIter<ListNode<int>> end;
	ListIter<ListNode<int>> Iter;
	auto ppp =  _count(beg, end, 5);
	std::cout << ppp << std::endl;	// 2
	return 0;
}

1.3.3 reference 和 pointer

代表迭代器所指对象的引用与指针类型，实现如下：

template <typename T>
struct iterator_traits
{
	typedef typename T::pointer pointer;
	typedef typename T::reference reference;
};
template <typename T>
struct iterator_traits<T*>
{
	typedef T* pointer;
	typedef T& reference;
};
template <typename T>
struct iterator_traits<const T*>
{
	typedef const T* pointer;
	typedef const T& reference;
};

1.3.4 iterator_category

首先来看迭代器的五种类型：

Input iterator：只读迭代器
Output iterator：只写迭代器
Forward iterator：可读可写迭代器
Bidirectional iterator：双向移动迭代器
Random Access iterator：前四种迭代器都支持一种指针运算（++或者—），而此迭代器支持所有的指针运算。

这五种迭代器自上而下呈加强状态，即功能越来越强。

要对某种迭代器提供一种准确的定义，对另一种强化的迭代器提供另一种定义，这样才能使得效率最大化。

举例：如何设计 Advance函数

advance函数的含义是传入两个参数，并且将第一个参数的迭代器前进 n个位置。

如何针对指定的迭代器类型来选择合适的实现功能呢？

//对于只读迭代器：Input 可读可写迭代器：Forward 都是这样的
template <typename InputIterator,typename Distance>
void advance(InputIterator Iter, Distance n)
{
	while (n--) ++Iter;
}
//对于双向迭代器：Bidirectional 
template <typename Bidirectional, typename Distance>
void advance(Bidirectional Iter, Distance n)
{
	if (n >= 0)
	{
		while (n--) ++Iter;
	}
	else
	{
		while (n++) --Iter;
	}
}
//对于随机迭代器：Random
template <typename RandomIterator, typename Distance>
void advance(RandomIterator Iter, Distance n)
{
	Iter += n;//随机迭代器支持任意的指针运算
}

我们写出了每种迭代器的最佳的选择，那么我们怎么确定一个最终的执行函数呢？

难道要设计几个函数判断其是为只读型迭代器还是双向迭代器还是随机迭代器？

但是这样每次在执行advanc的时候都执行一次选择哪个版本的判断，太影响效率了，我们最好在编译期间就能判断执行哪个版本，我们可以使用重载函数的机制来实现。

我们让这三个函数同名，并且加上第三个参数，第三个参数为迭代器类型，使得traits可以根据第三个参数的类型来推断出执行哪个函数。

因此第三个参数一定是一个类类型，我们使用以下方式来解决：

//五个标记类型
//五个标记类型
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_Iterator_tag:public Bidirectional_Iterator_tag {};


//对于只读迭代器：Input 可读可写迭代器：Forward 都是这样的
template <typename InputIterator, typename Distance>
void _advance(InputIterator Iter, Distance n,Input_Iterator_tag)
{
	while (n--) ++Iter;
}
//对于可读可写迭代器:直接调用Input
template <typename InputIterator, typename Distance>
void _advance(InputIterator Iter, Distance n, Forward_Iterator_tag)
{
	_advance(Iter,n, Input_Iterator_tag())
}
//对于双向迭代器：Bidirectional 
template <typename Bidirectional, typename Distance>
void _advance(Bidirectional Iter, Distance n,Bidirectional_Iterator_tag)
{
	if (n >= 0)
	{
		while (n--) ++Iter;
	}
	else
	{
		while (n++) --Iter;
	}
}
//对于随机迭代器：Random
template <typename RandomIterator, typename Distance>
void advance(RandomIterator Iter, Distance n,Random_Iterator_tag)
{
	Iter += n;//随机迭代器支持任意的指针运算
}

创建五种迭代器标记，他们只作为标记使用，在实际的_advance中无需参数的名称，根据是哪一个型别，编译器可以推断出使用哪一个版本。

对于最终的执行函数，我们只需要来 traits萃取迭代器的类型即可。

//iterator_category函数
template <typename Iter>
inline typename iterator_traits<Iter>::iterator_category iterator_category(const Iter&)
{
	typedef typename iterator_traits<Iter>::iteratr_category category;
	return category();
}
template <typename T>
struct iterator_traits
{
	typedef typename T::iterator_category iterator_category;
};
//原指针的偏特化
template <typename T>
struct iterator_traits<T*>
{
	typedef Random_Iterator_tag iterator_category;
};
//const指针的偏特化
template <typename T>
struct iterator_traits<const T*>
{
	typedef Random_Iterator_tag iterator_category;
};
//执行函数
template <typename InputIterator,typename Distance>
void advance(InputIterator& it, Distance n)
{
	_advance(it, n, iterator_category(it));
}

对于advance函数来说，InputIterator作为其函数参数类型的名字是合理的。

因为STL的命名规则是以函数所能接受的最低阶迭代器类型作为其迭代器参数的类型名称

1.3.5 迭代器标签

上面描述的五个迭代器的标签，不仅可以促成函数重载机制与traits萃取的功效

而且通过继承，我们不必再写多个标签的函数。

distance的函数是计算两个迭代器之间的距离：

template <typename InputIterator>
typename iterator_traits<InputIterator>::difference_type  
	_distance(InputIterator beg, InputIterator end, Input_Iterator_tag)
{
	iterator_traits<InputIterator>::difference_type n = 0;
	while (beg != end)
	{
		++beg;
		++n;
	}
	return n;
}

template <typename RandomIterator>
typename iterator_traits<RandomIterator>::difference_type
	_distance(RandomIterator beg, RandomIterator end, Random_Iterator_tag)
{
	//直接计算差距
	return end - beg;
}

template <typename InputIterator>
typename iterator_traits<InputIterator>::difference_type
	distance(InputIterator beg, InputIterator end)
{
	typedef typename iterator_traits<InputIterator>::iterator_category category;
	_distance(beg, end, category());
}

只需处理两个迭代器类型即可，即InputIterator和RandomIterator

因为其他的迭代器都可由 InputIterator 完全替代，通过继承我们可以直接指定他们的默认_distance 函数就是 InputIterator的 _distance函数。

1.4 iterator模板

任何迭代器都应该提供上述五个相应型别，以利于traits的萃取。

STL提供的iterator完整如下所示：

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

现代 STL 使用using，当然typedef也是可以的。

iterator只是型别定义，不含任何成员，因此可以在后续设计的迭代器中继承它

因此就可以在自己的迭代器中：

template <typename T>
class ListIter:public iterator<T,std::forward_iterator_tag>
{
	//类内
};

只需要传入 T 以及它的迭代器型别标签即可。

简单总结：

设计迭代器的相应型别，是迭代器的责任。
设计容器的适当的迭代器，是容器本身的责任，只有容器才直到该如何设计适当的迭代器来遍历与操作自己。迭代器的行为包括取值，前进，后退，取用成员。
设计算法则无需 容器和迭代器 的帮助，只要以迭代器为接口即可。

traits编程技巧的精华：

内嵌型别的编程方法
template自动推导参数的方法。

1.5 iterator完整源代码

SGISTL库的iteraotr的结构：

五种迭代器类型
iterator类
迭代器萃取类，针对指针的偏特化
决定某个迭代器的型别（category，value_type，difference_type）
distance函数，advance函数

手写完整代码如下：

#ifndef MY_ITERATOR_H
#define MY_ITERATOR_H
#include <iostream>
/*
1. 五种迭代器类型
2. iterator类
3. 迭代器萃取类，针对指针的偏特化
4. 决定某个迭代器的型别（category，value_type，difference_type）
5. distance函数，advance函数
*/

//1. 五种迭代器类型
struct InputIterator_tag {};//读入迭代器
struct OutputIterator_tag {};//输出迭代器
struct ForwardIterator_tag {};//可读可写迭代器
struct Bidirectional_Iterator_tag {};//双向迭代器
struct RandomAccessIterator_tag {};//随机迭代器

//2. iterator类
template <typename category, typename T, typename Distance = std::ptrdiff_t,
	typename Pointer = T*, typename Reference = T&>
struct iterator
{
	using value_type = T;
	using difference_type = Distance;
	using pointer = Pointer;
	using reference = Reference;
	using iterator_category = category;
};

//3. 迭代器型别萃取类
template <typename Iter>
struct iterator_traits
{
	using value_type = typename Iter::value_type;
	using difference_type = typename Iter::difference_type;
	using pointer = typename Iter::pointer;
	using reference = typename Iter:reference;
	using iterator_category = typename Iter::iterator_category;
};

//针对指针的偏特化
template <typename T>
struct iterator_traits<T*>
{
	using value_type = T;
	using difference_type = ptrdiff_t;
	using pointer = T*;
	using reference = T&;
	using iterator_category = RandomAccessIterator_tag;
};
template <typename T>
struct iterator_traits<const T*>
{
	using value_type = T;
	using difference_type = ptrdiff_t;
	using pointer = const T*;
	using reference = const T&;
	using iterator_category = RandomAccessIterator_tag;
};

//4. 决定某个迭代器的类型（category，value_type，difference_type）
//4.1 category
template <typename Iter>
inline typename iterator_traits<Iter>::iterator_category
	iterator_category(const Iter& it)
{
	using category = typename iterator_traits<Iter>::iterator_category;
	return category();
}
//决定某个迭代器的difference_type
template <typename Iter>
inline typename iterator_traits<Iter>::difference_type*
	difference_type(const Iter& it)
{
	return static_cast<typename iterator_traits<Iter>::difference_type*>(0);
}
//决定某个迭代器的value_type
template <typename Iter>
inline typename iterator_traits<Iter>::value_type*
	value_type(const Iter& it)
{
	return static_cast<typename iterator_traits<Iter>::value_type*>(0);
}

//5. distance函数，advance函数
template <typename InputIterator>
typename iterator_traits<InputIterator>::difference_type
	_distance(InputIterator begin, InputIterator end,InputIterator_tag)
{
	typename iterator_traits<InputIterator>::difference_type n = 0;
	while (begin != end)
	{
		begin++;
		n++;
	}
	return n;
}
template <typename RandomIterator>
typename iterator_traits<RandomIterator>::difference_type
	_distance(RandomIterator begin,RandomIterator end,RandomAccessIterator_tag)
{
	return end - begin;
}
//distance主函数
template <typename InputIterator>
typename iterator_traits<InputIterator>::difference_type
	distance(InputIterator begin, InputIterator end)
{
	//using category = typename iterator_traits<InputIterator>::iterator_category;
	return _distance(begin, end, iterator_category());
}
//-----------------------------------------
//advance函数
template <typename InputIterator,typename Distance>
void _advance(InputIterator it,Distance n,InputIterator_tag)
{
	while (n--) ++it;
}
template <typename BidirectionalIterator,typename Distance>
void _advance(BidirectionalIterator it,Distance n,Bidirectional_Iterator_tag)
{
	if (n >= 0)
	{
		while (n--) ++it;
	}
	else
	{
		while (n++) --it;
	}
}
template <typename RandomIterator,typename Distance>
void _advance(RandomIterator it, Distance n,RandomAccessIterator_tag)
{
	it += n;
}
template <typename InputIterator,typename Distance>
void advance(InputIterator it, Distance n)
{
	_advance(it, n, iterator_category(it));
}

#endif // !MY_ITERATOR_H

1.6 __type_traits

iterator_traits负责萃取迭代器的特性，__type_traits负责萃取型别的特性。

ctor：构造函数

dtor：析构函数

copy ctor：拷贝构造函数

assignment：赋值运算符

trivial：无意义的：

trivial ctor：没有构造函数

trivial dtor：没有析构函数

trivial copy ctor：没有拷贝构造函数

trivial assignment：没有赋值运算符

non-trivial：有意义的

non-trivial ctor：显式定义了构造函数

non-trivial dtor：显式定义了析构函数

non-trivial copy ctor：显式定义了拷贝构造函数

non-trivial assignment：显式定义了赋值运算符

POD：具有trivial ctor，trivial dtor，trivial copy ctor，trivial assignment属性，即全部都是没有显式定义的。

什么是型别特性？

这个类是否具备有意义的（即显式定义了） non-trivial 的构造/析构/拷贝构造/赋值运算等操作，如果是trivia的（即没有显式定义），则我们就无需对ctor，dtor等进行操作，直接采用最有效率的内存操作，如memcpy，malloc等，对于大规模而频繁操作的容器具有很大的提升。

__type_traits提供了一种操作，针对不同的型别，允许在编译的时候就知道函数派送决定。如果我们知道了我们的类是否有一个 trivial ctor ，并且正好需要对这个类执行拷贝操作，则我们直接可以对内存操作。

__type_traits为像 iterator_traits一样，因此我们应该对它进行这样的操作。

__type_traits<T>::has_trivial_default_constructor;
__type_traits<T>::has_trivia_copy_constructor;
__type_traits<T>::has_trivial_assignment_operator;
__type_traits<T>::has_trivial_destructor;
__type_traits<T>::i_POD_type;

但是我们希望对 __type_traits的操作响应不是 真或者假，而是某一个类的对象，因为我们需要对这个响应的对象进行参数推导。而编译器只有面对class object这样的对象才具有参数推导的功能。

因此，上述的式子应该返回这样的响应对象：

1 2	struct __true_type {}; struct __false_type {};

空白的类成员，既能够标识真假，又能够起到参数推导的作用。

因此为了达成这样的操作，__type_traits的内部应该是这样的：

template <typename type>
struct __type_traits
{
	using has_trivial_default_constructor = __false_type;
	using has_trivial_copy_constructor = __false_type;
	using has_trivial_assignment_operator = __false_type;
	using has_trivial_destructor = __false_type;
	using is_POD_type = __false_type;
};

我们首先定义出最保守的值。最保守的就是对所有型别都必定有效的保守值

__type_traits可以接受任意型别的参数。

然后再设计针对每一种标量类型的特化版本

包括 char， unsigned char，int，float，double，long long 等类型


struct __type_traits<char>
{
	using has_trivial_default_constructor = __true_type;
	using has_trivial_copy_constructor = __true_type;
	using has_trivial_assignment_operator = __true_type;
	using has_trivial_destructor = __true_type;
	using is_POD_type = __true_type;
};
	

struct __type_traits<signed char>
{
	using has_trivial_default_constructor = __true_type;
	using has_trivial_copy_constructor = __true_type;
	using has_trivial_assignment_operator = __true_type;
	using has_trivial_destructor = __true_type;
	using is_POD_type = __true_type;
};

....................
    
//针对任意原生指针类型的偏特化版本
template <typename T>
struct __type_traits<T*>
{
	using has_trivial_default_constructor = __true_type;
	using has_trivial_copy_constructor = __true_type;
	using has_trivial_assignment_operator = __true_type;
	using has_trivial_destructor = __true_type;
	using is_POD_type = __true_type;
};

以下是__type_traits的应用举例：（从下往上看 uninitialized_fill_n 是要执行的函数）


template <typename ForwardIterator, typename Size, typename T>
ForwardIterator __uninitialized_fill_n_anx(ForwardIterator first, Size n,
	const T& x, __false_type)
{
	//__false_type : 不是POD类型，进行普通的构造
	ForwardIterator cur = first;
	for (; n > 0; n--, ++cur)
	{
		construct(&*cur, x);
	}
	return cur;
}

template <typename ForwardIterator, typename Size, typename T>
ForwardIterator __uninitialized_fill_n_anx(ForwardIterator first, Size n,
	const T& x, __true_type)
{
	//__true_type：是POD类型，可以进行快速的操作，操作内存
	return std::fill_n(first, n, x);
}


template <typename ForwardIterator,typename Size,typename T,typename T1>
ForwardIterator __uninitialized_fill_n(ForwardIterator first, Size n, const T& x, const T1&)
{
	//T1为萃取出的迭代器所指的元素类型
	typename __type_traits<T1>::is_POD_type is_pod;
	return 
}

//从 first处开始构造n个元素
template <typename ForwardIterator,typename Size,typename T>
ForwardIterator uninitialized_fill_n(ForwardIterator first, Size n, const T& x)
{
	//value_type利用 iterator_traits 萃取出迭代器所指的元素类型
	return __uninitialized_fill_n(first, n, x, value_type(first));
}

过程：

首先执行uninitialized_fill_n，传入三个参数，标识从first开始构造 n个 x
利用iterator_traits 的 value_type（参见上节）推断出迭代器所指对象的元素类型
在uninitialized_fill_n 中 T1 得到此参数类型，再利用 type_trait的类型推导，得出这个类型是 _true_type 还是 \false_type
如果是__true_type，则是POD类型，直接进行内存操作
如果是__false_type，则不是POD类型，则只能按照其构造函数对其进行构造

如果这个class内含指针成员，并且对他进行动态内存分配，则它就是个非 POD的，需要实现出自己的 non-trivial 操作

在以后，针对每一个标量型别，我们都可以利用 _type_traits 选择最高效的操作：

_true_type：是trivial的，执行对内存的快速操作。
_false_type：不是trivial的，执行对象的构造，调用相应的函数。

HugeYlh

STL源码学习（2） - 迭代器概念与traits编程技法