STL与泛型编程
一、STL是什么
STL（Standard TemplateLibrary），即标准模板库，是一个具有工业强度的，高效的C++程序库。它被容纳于C++标准程序库（C++ Standard Library）中，是ANSI/ISO C++标准中最新的也是极具革命性的一部分。该库包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法。为广大C++程序员们提供了一个可扩展的应用框架，高度体现了软件的可复用性。
从逻辑层次来看，在STL中体现了泛型化程序设计的思想（generic programming），引入了诸多新的名词，比如像需求（requirements），概念（concept），模型（model），容器（container），算法（algorithmn），迭代子（iterator）等。与OOP（object-oriented programming）中的多态（polymorphism）一样，泛型也是一种软件的复用技术；
从实现层次看，整个STL是以一种类型参数化（type parameterized）的方式实现的，这种方式基于一个在早先C++标准中没有出现的语言特性--模板（template）。如果查阅任何一个版本的STL源代码，你就会发现，模板作为构成整个STL的基石是一件千真万确的事情。除此之外，还有许多C++的新特性为STL的实现提供了方便；
二、STL的六大组件
STL：主要包含6个parts：
** 容器（****Container****），是一种数据结构，如list，vector，和deque，以模板类的方法提供。为了访问容器中的数据，可以使用由容器类输出的迭代器（有的容器不含迭代器，如queue，stack）；
** 迭代器（****Iterator****），提供了访问容器中对象的方法。例如，可以使用一对迭代器指定list或vector中的一定范围的对象。迭代器就如同一个指针。事实上，C++的指针也是一种迭代器。但是，迭代器也可以是那些定义了operator()以及其他类似于指针的操作符地方法的类对象；
** 算法（****Algorithm****），是用来操作容器中的数据的模板函数。例如，STL用sort()来对一个vector中的数据进行排序，用find()来搜索一个list中的对象，函数本身与他们操作的数据的结构和类型无关，因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用；
** 仿函数（Functionobject，仿函数(functor)又称之为函数对象（function object），其实就是重载了()操作符的struct，没有什么特别的地方
** 迭代适配器（Adaptor）
** 空间配制器、分配器（allocator*）其中主要工作包括两部分1.对象的创建与销毁2.内存的获取与释放。
2.1 部件之间的关系
三、整个课程目录：
（***完***）* 第一课：体系结构与内核分析 在C++标准中，STL被组织为下面的17个头文件：<[algorithm](http://baike.baidu.com/item/algorithm)>、<[deque](http://baike.baidu.com/item/deque)>、<[functional](http://baike.baidu.com/item/functional)>、<[iterator](http://baike.baidu.com/item/iterator)>、<[array](http://baike.baidu.com/item/array)>、<[vector](http://baike.baidu.com/item/vector)>、<[list](http://baike.baidu.com/item/list)>、、、、、<[numeric](http://baike.baidu.com/item/numeric)>、<[queue](http://baike.baidu.com/item/queue)>、<[set](http://baike.baidu.com/item/set)>、、<[stack](http://baike.baidu.com/item/stack)>和<[utility](http://baike.baidu.com/item/utility)>。 C++标准库头文件header不包含副档名 如：#include不包含.h后缀 新式C库也不包含副档名。#include
几个重要的C++网站：
* ** cplusplus.com***
*** cppReference.com***
*** gcc.gnu.org***
程序复杂度O(n)：n需要很大，工业级的，比如几十万几百万数据量，才能体现线性复杂度。
标准库容器迭代器采用前闭后开区间[ a,b)。
不能对c.end()取内容。*c.end() //(X)
容器在内存中不一定连续。
新版本（since C++11）容器遍历：
1容器的分类和内存结构
1容器的分类和内存结构
1.1容器的分类
[图片上传中。。。（5）]
容器大致可以分为两种；Sequence containers****和****associative containers两大类
一、****Sequence
containers:**有序的容器；******
1、如数组的类实现array（在内存中顺序排放，并且长度不能动态改变。）、
2、Vector：当空间不够时，分配器会自动向后扩充空间
3、deque（读daike）：双头队列。
**1,2,3****这些容器在内存中连续******
4、list：双向链表，空间在内存中不连续
二、****associative containers****：查找效率高。******
在STL内部，set用红黑树**实现
Set/multiSet: Map/multiMap
Set和Map中数据元素不能重复
multiSet和multiMap中数据元素可以重复
1.2 容器Array的使用：
使用,很方便,用起来和STL一样;执行效率比高,几乎和
int myarray[5]效率一样。当你想要一个执行时效率高,而用不想自己管理内存的时候,就用它。Array在内存中是连续排列的。可以使用[]操作符或c.at(i)索引数组元素。包含头文件：#include
实测：类型和大小相同的Array对象可以相互赋值，且拷贝赋值之后彼此不影响。属于深拷贝。
arrayc;
array a,b;
a[0] = 1
b = a;
1.3容器Vector的使用：
Vector是一端开口的数组，每次扩充以2倍增长。
扩充：即成长，这个过程是非常缓慢的，存在内存拷贝。当当前空间Aspace不够用时，在另外一个地方重新开辟一个大小为2space的空间B，将A中元素拷贝到B，然后清理掉A。
定义自动变量pItem；
同时调用全局函数：：find()顺序查找值为target的元素地址。
通过pItem就可获得值。
在c++中，vector是一个十分有用的容器。
*1****基本操作******
(1)头文件#include.
(2)创建vector对象，vectorvec;
(3)尾部插入数字：vec.push_back(a);
(4)使用下标访问元素，cout<
(5)使用迭代器访问元素.
vector::iteratorit;
for(it=vec.begin();it!=vec.end();it++)
cout<<it<
(6)插入元素：vec.insert(vec.begin()+i,a);在第i+1个元素前面插入a;
(7)删除元素：vec.erase(vec.begin()+2);删除第3个元素
vec.erase(vec.begin()+i,vec.end()+j);删除区间[i,j-1];区间从0开始
(8)向量大小:vec.size();
(9)清空:vec.clear();
1.4容器List的使用：
STL中的list就是一双向链表，可高效地进行插入、删除元素操作。
list不支持随机访问。所以没有at(pos)和operator[]。
List本身提供sort函数。这是排序算法最好采用内部sort成员函数。
有些容器没有提供sort成员函数，如vector、array。
标准库提供的：：find()函数是
顺序查找。
1.5容器deque的使用：
deque双向队列是一种双向开口的连续线性空间，可以高效的在头尾两端插入和删除元素，deque在接口上和vector非常相似。
deque的实现比较复杂，内部会维护一个map（注意！不是STL中的map容器）即一小块连续的空间，该空间中每个元素都是指针，指向另一段（较大的）区域，这个区域称为缓冲区，缓冲区用来保存deque中的数据。因此deque在随机访问和遍历数据会比vector慢。具体的deque实现可以参考《STL源码剖析》。
Deque在内存中是分段连续的，但在使用者用起来是没有这种“分段连续”的感受，
我们在使用++操作符作用在deque对象。
下面给出deque的使用范例：
//双向队列 deque //by MoreWindows http://blog.csdn.net/morewindows #include#include#includeusing namespace std; int main() { dequeideq(20); //Create a deque ideq with 20 elements of default value 0 deque::iterator pos;
int i;
//使用assign()赋值 assign在计算机中就是赋值的意思
for (i = 0; i < 20; ++i)
ideq[i] = i;
//输出deque
printf("输出deque中数据:\n");
for (i = 0; i < 20; ++i)
printf("%d ", ideq[i]);
putchar('\n');
//在头尾加入新数据
printf("\n在头尾加入新数据...\n");
ideq.push_back(100);
ideq.push_front(i);
//输出deque
printf("\n输出deque中数据:\n");
for (pos = ideq.begin(); pos != ideq.end(); pos++)
printf("%d ", *pos);
putchar('\n');
//查找
const int FINDNUMBER = 19;
printf("\n查找%d\n", FINDNUMBER);
pos = find(ideq.begin(), ideq.end(), FINDNUMBER);
if (pos != ideq.end())
printf("find %d success\n", *pos);
else
printf("find failed\n");
//在头尾删除数据
printf("\n在头尾删除数据...\n");
ideq.pop_back();
ideq.pop_front();
//输出deque
printf("\n输出deque中数据:\n");
for (pos = ideq.begin(); pos != ideq.end(); pos++)
printf("%d ", *pos);
putchar('\n');
return 0;
}
Queue和stack的内部实现都包含一个deque。因此，queue和stack都可以看做是特殊的deque。
1.6容器set和multiset的使用（关联式容器）：
红黑树和哈希表。作为数据结构，非常适用于需要大量查找的场合。
元素就是key，key就是元素。
set和multiset会根据特定的排序准则，自动将元素进行排序。不同的是multiset****允许元素重复而set****不允许。只要是可复赋值、可拷贝、可以根据某个排序准则进行比较的型别都可以成为它们的元素。第二个参数用来定义排序准则。缺省准则less是一个仿函数。
和所有关联式容器类似，通常使用平衡二叉树完成。事实上，set和multiset通常以红黑树实作而成。
自动排序的优点是使得搜寻元素时具有良好的性能****，具有对数时间复杂度。但是造成的一个缺点就是：
不能直接改变元素值。因为这样会打乱原有的顺序。
改变元素值的方法是：先删除旧元素，再插入新元素。
存取元素只能通过迭代器，从迭代器的角度看，元素值是常数。
用STL的算法：：find()查找元素和用MultiSet自身的find（）成员函数查找速度对比：
1.7容器map和multimap的使用（关联式容器）：
每一个元素包含一个key，通过key来查找元素。
1.8容器unordered_multiset的使用（关联式容器）：
Hash table.
Hash
table篮子一定比元素多，大概是元素的2倍 。
新版本STL中用unordered_XXX代替了旧版本的hash_XXX
2 分配器
容器内部需要分配器来管理内存。
