C++标准模板库STL

1、C++中有两个方面体现重用：

（1）面向对象的思想：继承和多态，标准类库。

（2）泛型程序设计(generic programming) 的思想： 模板机制，以及标准模板库 STL。

将一些常用的数据结构（比如链表，数组，二叉树）和算法（比如排序，查找）写成模板，标准模板库 (Standard Template Library) 就是一些常用数据结构和算法的模板的集合。

2、概念

容器：可容纳各种数据类型的通用数据结构，是类模板。

迭代器：可用于一次存取容器中元素，类似于指针。

算法：用来操作容器中元素的函数模板。sort()排序vector数据；find()搜索list中对象等。

int array[100]; 该数组就是容器，而 int * 类型的指针变量就可以作为迭代器，sort 算法可以作用于该容器上，对其进行排序： sort(array,array+70); //将前70个元素排序

3、容器：可以用于存放各种类型的数据（基本类型的变量，对象等）的数据结构，都是类模版，分为三种。

1）顺序容器 vector, deque,list

2）关联容器 set, multiset, map, multimap

3）容器适配器 stack, queue, priority_queue

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

容器并非排序的，元素的插入位置同元素的值无关。

（1）vector 头文件 <vector>

动态数组。元素在内存连续存放。随机存取任何元素都能在常数时间完成。在尾端增删元素具有较佳性能（大部分情况是常数时间）。

（2）deque 头文件<deque>

双向队列。元素在内存连续存放。随机存取任何元素都能在常数时间完成（仅次于vector）。在首尾两端增删元素具有较佳性能（大部分情况是常数时间）。

（3）list 头文件<list>

双向链表。元素在内存不连续存放。在任何位置增删元素都能在常数时间完成。不支持随机存取。

（4）关联容器

元素是排序的。插入任何元素，都按相应的排序规则来确定其位置。在查找时具有非常好的性能。

通常以平衡二叉树方式实现，插入和检索的时间都是O(log(N))

1）set/multiset 头文件<set>

set 即集合。set中不允许相同元素，multiset中允许存在相同的元素。

2）map/multimap 头文件<map>

map与set的不同在于map中存放的元素有且仅有两个成员变量，一个名为first,另一个名为second, map根据first值对元素进行从小到大排序， 并可快速地根据first来检索元素。 map同multimap的不同在于是否允许相同first值的元素。

（5）容器适配器

stack 头文件<stack>

栈，是项的有限序列，并满足序列中被删除、检索和修改的项只能是最近插入序列的项（栈顶的项）。后进先出。

queue 头文件<queue>

队列，插入只可以在尾部进行， 删除、检索和修改只允许从头部进行。先进先出。

priority_queue 头文件<queue>

优先级队列。最高优先级元素总是第一个出列，优先级自己定义。

（6）顺序容器和关联容器都有的成员函数：

begin 返回指向容器中第一个元素的迭代器

end 返回指向容器中最后一个元素后面的位置的迭代器

rbegin 返回指向容器中最后一个元素的迭代器

rend 返回指向容器中第一个元素前面的位置的迭代器

erase 从容器中删除一个或几个元素

clear 从容器中删除所有元素

（7）顺序容器常用的成员函数：

front 返回容器中第一个元素的引用

back 返回容器中最后一个元素的引用

push_back 在容器末尾增加新元素

pop_back 删除容器末尾的元素

erase 删除迭代器指向的元素(可能会使该迭代器失效），或删除一个区间，返回被删除元素后面的那个元素的迭代器

（8）迭代器

用于指向顺序容器和关联容器中的元素；迭代器用法和指针类似，有const和非const两种；通过迭代器可以读取它指向的元素；通过非const迭代器还能修改其指向的元素。

容器类名::iterator 变量名；
容器类名::const_iterator 变量名；

迭代器定义

访问一个迭代器指向的元素：*迭代器变量名

迭代器上可以执行 ++ 操作, 以使其指向容器中的下一个元素。如果迭代器到达了容器中的最后一个元素的后面，此时再使用++，就会出错，类似于使用NULL或未初始化的指针一样。

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

迭代器实例

输出结果：

1,2,3,4，

4,3,2,1， 

100,100,100,100，

1）双向迭代器

若p和p1都是双向迭代器，则可对p、p1可进行以下操作：

++p, p++ 使p指向容器中下一个元素

--p, p-- 使p指向容器中上一个元素

* p 取p指向的元素

p = p1 赋值

p == p1 , p!= p1 判断是否相等、不等

2）随机访问迭代器

若p和p1都是随机访问迭代器，则可对p、p1可进行以下操作：

双向迭代器的所有操作

p += i 将p向后移动i个元素

p -= i 将p向向前移动i个元素

p + i 值为: 指向 p 后面的第i个元素的迭代器

p - i 值为: 指向 p 前面的第i个元素的迭代器

p[i] 值为: p后面的第i个元素的引用

p < p1, p <= p1, p > p1, p>= p1 ：p < p1是指p指向的元素在p1指向元素的前面

3）不同容器的迭代器类别

vector 随机访问

deque 随机访问

list 双向

set/multiset 双向

map/multimap 双向

stack 不支持迭代器

queue 不支持迭代器

priority_queue 不支持迭代器

Note：有的算法，例如sort， binary_search需要通过随机访问迭代器来访问容器中的元素，那么list以及关联容器就不支持该算法！

（9）算法

算法就是一个个函数模板，大多数定义在<algorithm>。

算法通过迭代器来操纵容器中的元素。许多算法可以对容器中的一个局部区间进行操作，因此需要两个参数，一个是起始元素的迭代器， 一个是终止元素的后面一个元素的迭代器，比如排序和查找。

算法可以处理容器，也可以处理普通数组。

C++标准模板库STL

原文：https://www.cnblogs.com/zhuzhudong/p/10847380.html