1. STL
（1）先回忆数据结构
从数据结构的学习中，我知道了有顺序表，链表，哈希表，顺序树，链式数等数据结
构可以用于存放数据。
在c中，这些数据结构都需要程序员自己实现，但是在面向对象的语言中，为了节省编
程者的开发时间，都提供了自己的定义的现成可用的数据结构，这些数据结构本质上还
是数组，链表，树（红黑树），哈希表等等。
（2）一个数据结构包含哪些内容
以我们之前学习的链表这个数据结构为例，它包含如下内容。
（1）容器：链表就是一个存放数据的容器，存储结构为链式存储，存放数据时，
需要反映出被存储数据的逻辑结构
（2）遍历：向前向后索引节点就是遍历，遍历节点是能够访问数据的前提。当然对于
遍历操作来说，除了可以使用迭代器外。
（3）算法：对链表中的数据的具体操作算法，增加，删除，查找，修改，排序
实际上对于高级语言自带的数据结构做的也是这些事情，但是这些事情不需要程序员
操心，我们只要学会使用就好，有了这些现成的数据结构，我们甚至都可以省去使用
自定义数组，因为这些数据结构本身就可以替代数组的功能。某些数据结构中本身就
是数组。
（1）c++的STL模板库与java中的集合
对于哪些封装好的现成可用的数据结构在c++中叫STL，java中称为集合，实际上是一
个东西，对于这些现成的数据结构来说，同样涉及如下三个方面的内容：
（1）容器
（2）遍历：普通指针，迭代器（智能指针），在c++和java都有迭代器，实现原理也
是一样。
（3）算法：针对操作容器的算法，可以有如下3情况
（1）可以自己实现操作容器的算法，实际上这么做没有必要
（2）容器提供成员函数方式实现的算法
（3）STL模板库提供全局算法函数
对于容器和集合的学习，重点在于学习怎么使用容器，比通过提供的算法去操作容器中
的数据。
不管是c++还是java的定义的数据结构，都是用到了泛型，在c++称为模板（函数模板和
类模板）。
2. 容器/迭代器/算法
（1）STL容器：
（1）存放内容的方式
（1）存放副本：存放副本的特点是，修改副本并不会修改原对象的内容。
（2）存放指针：使用指针好处是，效率很高，比存放副本的方式效率高很多。
在java中没有存放副本的做法，存放的都是指针。
（2）STL容器分类
（1）序列容器：以线性方式组织管理存放的数据，STL提供的顺序容器有：
（1）vector<T>：以数组方式实现的数据结构，空间开辟于堆，
其大小和容量可以根据实际情况改变。
（2）deque<T>：可以在两头操作的特殊vector。
（3）list<T>：使用链表实现的数据结构。
（4）stack：栈，使用较少
（5）queue：队列，使用较少
（6）priority_queue：优先队列，使用较少
（2）关联容器：使用键值(key)与存储的内容关联起来，通过key去访问容
器的中内容。STL提供的关联容器有：
（1）map<key, T>：容器中一部分用于存放key值（key值不能重复）。
另一部分用于存放key值对应的数据，把我们把
Key和对应的数据我们称为键值对。
（2）multimap<key, T>：同map，但是key值可以重复。
（3）set<key>：数据本身就是key值，要求内容不能重复。
（4）multiset<key>：同set，但是内容可以重复。
在c++这只提供了线性容器和关联容器这两类，但是在java提供了更加丰富的容器，
（1）线性容器：vector,list,队列等
（2）非线性容器：树（tree）结构的容器
（3）关联容器：map和set
（2）STL迭代器（普通指针）
（1）什么是迭代器
迭代器就是封装好的智能指针，在学习前面的课程中，我们知道，智能指针
就是对指针做了类封装的，c和c++中的指针就是最简单的迭代器。
（2）按功能对迭代器进行分类
从功能上按照简单到复杂的顺序，迭代器分为如下及种类型，复杂类型的迭
代器兼容简单类型的迭代器。
（1）输入输出迭代器
（1）用于读写一系列的对象，输入迭代器只能进行读操作，输出
迭代只能进行写操作。
（2）只能使用一次，第二次使用需要重新创建
（3）实现的操作有：前后++，==，!=，*
（2）前向迭代器
兼容输入输出迭代器的功能，可以多次使用向前迭代器读写容器
中的对象，迭代器支持++操作（前++/后++都支持）。
（3）双向迭代器
兼容前向迭代器的功能，但同时还允许向后遍历对象。所以迭代器
还支持前后--的操作（前--/后--都支持）。
（4）随机迭代器
兼容双向迭代器的功能，但是同时允许随机访问。因为支持随机访
问，所以必须支持如下操作：
（1）iter+n和iter-n操作，iter[n]等价于*(iter+n)
（2）iter+=n和iter-=n操作
（3）迭代器相减，iter1-iter2操作
（4）迭代器比较操作，比如iter1<iter2，iter1>iter2，
iter1<=iter2，iter1>=iter2操作。
以上功能是累积的，输入输出迭代器功能最弱，随机迭代器功能最强。
（3）在迭代器中使用泛型的问题
定义迭代器对象时，需要指定访问的数据类型，比如：
std::vector<int>::iterator iter;
如果类型是泛型的话，定义迭代器是必须使用typename关键字,否者将会无法使用，比如：
typename std::vector<T>::iterator iter;
如果使用typedef给迭代器类型起别名时，如果涉及到泛型，那么同样的也需要使用
typename关键字，比如：
typedef typename std::vector<T>::iterator Iter;
Iter iter;//使用别名定义迭代器
（3）如何获取迭代器
（1）自定义迭代器，自定义迭代器可以按照自己要求实现以上4种类型中需要类型的迭代器。
（2）从容器中获取迭代器
STL容器自己提供了访问容器的迭代器。
容器： 提供的迭代器类型
vector 随机
deque 随机
list 双向
set 双向
multiset 双向
map 双向
multimap 双向
stack 不支持迭代器
queue 不支持迭代器
priority_queue 不支持迭代器
vector和deque之所以可以随机访问，因为他们本质上都是数组，我们前面讲过，数组
本身就支持随机访问。
list本质是链表，链表是不支持随机访问。
set和map专门用于存放集合类数据，也是不支持随机访问的。
栈，队列，优先队列之所以没有迭代器，因为都是在它们的头尾进行操作的，不需要遍
历和随机访问。
（3）使用容器以外迭代器
比如iostream，istream, ostream, sstream等输入输出流提供的迭代器。
（3）算法函数
（1）容器提供的成员算法函数
每种容器都提供了哪些成员算法函数，将在后面讲解，成员算法函数中，有些是直接定义的
函数，有些就是通过函数模板实现的。
容器提供的成员算法函数只针对本容器进行的。
（2）全局算法函数
（1）查找类
find()，find_end()，adjacent_find()，count(), mismatch(),
seaech(), equal()。
（2）修改类
swap(), copy(), transform(). replace(), remove(), reverse(),
rotate(), fill(), random/_shffle()。
（3）排序
sort() stable_sort(), binary_search(), merage(), min(),
max(), lexicographical_compare()。
实际上一些普通的修改，查找等操作，直接通遍历访问每个元素就可以实现，
不需要使用这些算法函数。全局算法函数大多都是通过函数模板实现的。
全局算法函数可以针对不同种类的容器进行操作，但是也有些容器是无法通过
全局算法函数无法操作的，这个时候只能通过容器的成员算法函数进行操作。
（4）STL的头文件
（1）容器头文件
<vector>（单端数组）, <deque>（双端数组）, <list>, <map>, <set>,
<queque>(双端队列)，<stack>(栈)
（2）迭代器头文件
<iterator>
但是由于容器使用到了迭代器，因此容器头文件中也有包含<iterator>头文
件，包含容器头文件时，可以不用包含迭代器头文件。
如果使用到了输入输出流提供的迭代器，需要包含输入输出流的头文件，比
如<iostream>, <istream>, <ostream>，<sstream>。
（3）全局算法涉及头文件
<algorithm>
如果涉及函数对象，还需要<functional>头文件。
网友评论