STL-需求分析

本小节主要是对要实现的各个功能梳理，理解各个设计之间的关联。（未完结）

1 list数据结构

可以毫不夸张的说，我们整个项目都是围绕list展开的。因此，我们首先得清楚要使用哪种list。

有请灵魂画手登场：
在这里插入图片描述

这是一个双向链表，每个节点包含三个信息：指向上一个节点的指针、指向下一个节点的指针、节点包含的数据。

在SGI STL中，链表被设计成双向循环链表：
在这里插入图片描述

所有可能出现的操作如下：
（1）数据结构（节点等信息）
（2）迭代器
（3）内存管理
（4）元素操作

2 关注容器：区别“链表节点”和“链表”

2.1 链表节点

当我们提到“链表节点”时，我们更多指的是如下结构：（对于一个双向循环链表的节点，需要两个指针和一个数据节点。）

template <class T>
struct __list_node{//定义一个双向链表_list_node<T> * prev;//上一个节点_list_node<T> * next;//下一个节点T data;
};

我们可以对照vector和其内部的元素来理解上述的设计。

1）因为C++本身不提供节点类型（更确切的说，list节点并不是基本数据类型，而是复合类型。）
2）相比vector存储仅需要连续的存储空间，list的创建，多了一步节点类型的定义。

2.2 链表

而当我们谈到“链表”时，我们指的不仅仅是多个“链表节点”构成数据，还包括数据存储和释放，访问等其他相应操作，包括我们提到的容器和其对迭代器提供的支持。
具体来说，“链表”相关的支持包括如下内容：
1）访问方式（迭代器实现）
2）构造与内存管理
3）元素操作（每个容器针对性实现）
这些内容联合“链表节点”，共同构成了完整的list容器。

3 关注迭代器：由容器定义具体的迭代访问方式，由迭代器文件设计通用接口

在开始学习前，请记住：迭代器设计与编译器密切相关！

3.1 函数返回值推导

迭代器的设计核心，就是提供通用接口。你或许会想，直接使用模板不就行了吗？

（1）这里提一个模板函数的例子：

#include <iostream>
#include <list>using namespace std;template<typename T>
T sum(T a, T b){return (T)(a+b);
}int main(){int a,b;a = 10;b = 20;cout << sum(a,b) <<endl;}

这样看来，函数似乎没有任何问题。

（2）那么，我们再来看另一个例子：

#include <iostream>using namespace std;template <typename T>
class A{public:T * ptr; //指向数据的指针A(T*p=0): ptr(p) {} //等价于 A(T*p=0){ptr=p;};T & operator * () const {return * ptr;} // dereference
};template <typename T>
T getValue(T ite){return * ite;
}int main(){A<int> ite(new int(10));cout << getValue(ite) << endl;}

上述代码看着没什么问题，但是实际运行的时，就会出现报错。
注意，这是因为：getValue(ite) 中，通过参数推导机制，T=A，但是*ite的类型却是 int 类型。因此，参数推导就出现了问题。

（3）但是，如果使用内嵌型别，可以解决上述问题。

#include <iostream>using namespace std;template <typename T>
class A{public:typedef T value_type;T * ptr; //指向数据的指针A(T*p=0): ptr(p) {} //等价于 A(T*p=0){ptr=p;};T & operator * () const {return * ptr;} // dereference
};template <typename T>
typename T::value_type getValue(T ite){return * ite;
}int main(){A<int> ite(new int(10));cout << getValue(ite) << endl;}

注意：typename关键字用于定义紧接其后的那个“T::value_type”，是一个型别，而不是类、变量或函数。（因为模板在被编译器具象化前，编译器对T一无所知，并不知道“T::value_type”是什么东西。）

3.2 模板偏特化

上述嵌型别的实现，需要class type。而native pointer不是class type，那怎么给这个native pointer添加类型型别呢？
实际上，我们不需要考虑修改native pointer，我们只需要利用模板的偏特化机制即可。
常见的偏特化是直接给T制定一个类型。其实不然，partial specialization是提供另一份template定义式，而其本身仍为templatized。

#include <iostream>using namespace std;template <typename T>
class A{public:A(){cout << "origin version" <<endl;}};template <typename T>
class A<T*>{public:A(){cout << "partial version" <<endl;      }
};int main(){A<int> a1;//调用原始版本，参数推导T=intA<int *> a2;//调用偏特化版本，参数推导T*表示原生指针，T代表指针指向的类型
}