STL

STL基本概念

泛型程序设计

C++语言的核心优势之一就是便于软件的重用。
C++中的两个方面体现重用：
1.面向对象的思想：继承和多态，标准类库
2.泛型程序设计的思想：模板机制，以及标准模板库STL。

泛型程序设计，简单的说，就是使用模板的程序设计法。
将一些常用的数据结构（比如链表，数组，二叉树）和算法（比如排序、查找）写成模板，以后不论数据结构里放的是什么对象，算法针对什么样的对象，则都不必重新实现数据结构，重新编写算法。
标准模板库就是一些常用数据结构和算法的模板的集合。
有了STL，不必再写大多的标准数据结构和算法，并且获得非常高的性能。

STL中的概念

容器:可容纳各种数据类型的通用数据结构，是类模板
迭代器：可用于依次存取容器中元素，类似于指针
算法: 用来操作容器中的元素的函数模板，如sort()对一个vector中的数据进行排序；find()来搜索一个List中的对象
算法本身与他们操作的数据的类型无关，因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用。
如： int array[100];
该数组就是容器，而int *类型的指针变量就可以作为迭代器，sort算法可以作用于该容器上，对其进行排序:
sort(array,array+70);

容器概述

可以用于存放各种类型的数据（基本类型的变量，对象等）的数据结构，都是类模板，分为三种：
1)顺序容器:vector,deque,list
2)关联容器:set,mlutiset,map
3)容器适配器：stack,queue,priority_queue

对象被插入容器时，被插入的是对象的一个复制品。许多算法，比如排序，查找，要求对容器中的元素进行比较，有的容器本身就是排序的，所以，放入容器的对象所属的类，往往还应该重载==和<运算符。

顺序容器简介

容器并非排序的，元素的插入位置同元素的值无关。有vector,deque,list三种
vector：动态数组。元素在内存连续存放。随机存取任何元素都能在常数时间完成。在尾端增删元素具有较佳的性能。
dequeue:双向队列。元素在内存连续存放。随机存取任何元素都能在常数时间完成（但次于vector)。在两端增删元素具有较好的性能。
list:双向链表。元素在内存不连续存放。在任何位置增删元素都能在常数时间完成，不支持随机存取。

关联容器简介

元素是排序的，插入任何元素，都按相应的排序规则来确定其位置，在查找时具有非常好的性能。通常以平衡二叉树方式实现，插入和检索的时间都是O(log(N))。
set/mulitiset 头文件 set即集合。set中不允许相同元素，multiset中允许存在相同的元素。
map/multimap 头文件

容器适配器

stack: 头文件 栈，是项的有限序列，并满足序列中被删除、检索和修改的项只能是最近插入序列的项（栈顶的项）。后进先出。
queue: 头文件 队列，插入只可以在尾部进行，删除、检索和修改只允许从头部进行。先进先出。
priority_queue头文件 优先级队列。最高优先级元素总是第一个出列。

迭代器

用于指向顺序容器和关联容器中的元素，用法和指针类似，有const和非const两种，通过迭代器可以读取它指向的元素，通过非const迭代器还能修改其指向的元素。
定义一个容器类迭代器的方法可以是:容器类名::iterator；访问一个迭代器指向的元素:*迭代器变量名。
迭代器上可以执行++操作，以使其指向容器中的下一个元素。如果迭代器到达了容器中的最后一个元素的后面，此时再使用它，就会出错，类似于使用NULL或未初始化的指针一样。

int main(){
    vector<int> v;//一个存放int元素的数组，一开始里面没有元素。
    v.push_back(1);
    v.push_back(2);
    vector<int>::const_iterator i;//常量迭代器
    for(i = v.begin();i!=v.end();++i)
        cout << * i << ",";
    vector<int>::reverse_iterator r;//反向迭代器
    for(r = v.rbegin();r!=v.rend();r++)
        cout << * r << ",";
    vector<int>::iterator j;//非常量迭代器
    for(j = v.begin();j!=v.end();j++)
        * j = 100;
}

双向迭代器

若p和p1都是双向迭代器，则可对p、p1进行以下操作:
++p,p++ 使p指向下一个元素；*p，取p指向的元素；p=p1，赋值；p==p1,p!=p1判断是否相等，不等。

随机访问迭代器

vector,deque是随机访问迭代器
lisr,set,map是双向迭代器
stack，queue,不支持迭代器

算法简介

算法就是一个个函数模板，大多数在中定义。
STL中提供能在各种容器中通用的算法，比如查找，排序等
算法通过迭代器来操纵容器中的元素。许多算法可以对容器中的一个局部区间进行操作，因此需要两个参数，一个是起始元素的迭代器，一个是终止元素的后面的一个迭代器。比如，排序和查找。
有的算法返回的是一个迭代器。比如find()算法，在容器中查找一个元素，并返回一个指向该元素的迭代器。
算法可以处理容器，也可以处理普通数组。
示例：

templete <class InIt,class T>
Init find(Init first,Init last,const T& val)

first和last这两个参数都是容器的迭代器，它们给出了容器中的查找区间起点和终点[first,last]。区间的起点是位于查找范围之中的，而终点不是。find在[first,last)中查找等于val的元素。
用==运算符判断相等。
函数返回值是一个迭代器。如果找到，则该迭代器指向被找到的元素。如果找不到，则该迭代器等于last。

STL中的“大”、“小”和“相等”

关联容器内部的元素是从小到大排序的
有些算法要求其操作的区间是从小到大排序的，称为“有序区间算法”，例如binary_search，有些算法会对区间进行从小到大的排序，称为“排序算法”，例如sort。还有一些其他算法会用到大小的概念

vector和deque

#include <iostream>
#include <vector>
using namespace std;
templete<class T>
void PrintVector(T s,T e){
    for(;s!=e;++s)
        cout << *s<< " ";
}

int main(){
    int a[5] = {1,2,3,4,5};
    vector<int> v(a,a+5); //将数组a的内容放入v
    cout << "1) "<<v.end()-v.begin()<<endl;
    //两个随机迭代器可以相减，输出1） 5
    cout << "2) "; PrintVector(v.begin(),v.end());
    //2) 1 2 3 4 5
    v.insert(v.begin()+2,13);//在begin()+2位置上插入13
    cout<<"3)"; PrintVector(v.begin(),v.end());
    //3） 1 2 13 3 4 5
    v.earase(v.behin()+2);//删除位于begin()+2的元素
    cout << "4)"; PrintVector(v.begin(),v.end());
    //4) 1 2 3 4 5cout
    vector<int> v2(4,100);//v2有四个元素，都是100
    v2.insert(v2.begin(),v.begin()+1,v.begin()+3);
    //将v的一段插入v2的开头
    cout<< "5) c2:"; PrintVector(v2.begin(),v2.end()); 
    //5）v2: 2 3 100 100 100 100
    v.erase(v.begin() + 1, v.begin() + 3);
    //删除v上的一个区间，即2,3
    cout << "6)";v.erase(v.begin() + 1, v.begin() + 3);
    //6) 1 4 5
    return 0;
}

用vector实现二维数组

#include <iostream>
#include <vector>
using namespace std;
int main(){
    vector<vector<int>>v(3);
    //v有3个元素，每个元素都是vector<int>容器
    for(int i = 0;i < v.size();++i)
        for(int j = 0;j < 4;++j)
            v[i].push_back(j);
    for(int i = 0;i < v.size();++i){
        for(int j = 0;j < v[i].size();++j)
            cout << v[i][j] << " ";
        cout << endl;
    }
    return 0;
}

deque

所有适用于vector的操作都适用于deque
deque还有push_front(将元素插入到前面)和pop_front(删除最前面的元素)操作，复杂度是O(1)

双向链表(list)

list容器，在任意位置进行插入和删除，不支持随机存取。除了具有所有顺序容器都有的成员函数以外，还支持8个成员函数。
push_front:在前面插入
pop_front:删除前面的元素
sort:排序（list不支持STL的算法sort）
remove:删除和指定值相等的所有元素
unique:删除所有和前一个元素相同的元素
merge:合并两个链表，并清空被合并的那个
reverse:颠倒链表

函数对象

是个对象，但是用起来看上去像函数调用，实际上也执行了函数调用。

class CMyAverage{
public:
    double operator()(int a1,int a2,int a3){
    //重载（）运算符
        return (double)(a1+a2+a3)/3;
    }
};
CMyAverage average; //函数对象
cout << average(3,2,3);  //average.operator(3,2,3) 用起来看上去是函数调用，输出2.6667

函数对象的应用

STL里有以下模板

templete<class InIt, class T,class Pred>
T accumulate(InIt first,InIt last,T val,Pred pr);

pr就是个函数对象。对[first,last)中的每个迭代器I，执行val = pr(val,* I)，返回最终的val。pr也可以是个函数。