标准模板STL-概述

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>头文件。