STL－－容器、迭代器、算法

转自：https://blog.csdn.net/sim_szm/article/details/8980879 

容器：可容纳各种数据类型的数据结构
迭代器：可依次存取容器中元素的东西
算法：用来操作容器中的元素的函数模板

一、容器

常见的容器有vector、deque、string、list、set、map、stack、queue、priority_queue

前三种支持随机访问迭代器，即支持随机存取，任何一个STL算法都可与其搭配使用，中间三种支持双向迭代器，而后三种则不支持任何迭代器。

二、迭代器

迭代器定义了常用的操作集，但有些迭代器具有比其他迭代器更强大的功能。例如ostream_iterator只支持自曾、解引用和复制运算，而vector容器提供的迭代器除了这些运算，还支持自减、关系和算数运算。因此，迭代器可根据所提供的操作集进行分类。类似地,还可根据算法要求它的迭代器提供什么类型的操作,对算法分类。有一些算法,例如 find,只要求迭代器提供读取所指向内容和自增的功能。另一些算法,,比如 sort,则要求其迭代器有读、写和随机访问元素的能力。算法要求的迭代器操作分为五个类别,分别对应下表列出的五种迭代器：

1.输入迭代器可用于读取容器中的元素,但是不保证能支持容器的写入操作。输入迭代器必须至少提供下列支持。
o 相等和不等操作符(==,!=),比较两个迭代器。
o 前置和后置的自增运算(++)使迭代器向前递进指向下一个元素。
o 用于读取元素的解引用操作符(*),此操作符只能出现在赋值运
算的右操作数上。
o 箭头操作符(->),这是 (*it).member 的同义语,也就是说,对迭代器进行解引用来获取其所关联的对象的成员。输入迭代器只能顺序使用;一旦输入迭代器自增了,就无法再用它检查之前的元素。要求在这个层次上提供支持的泛型算法包括 find 和accumulate。标准库 istream_iterator 类型输入迭代器。

2.输出迭代器 可视为与输入迭代器功能互补的迭代器;输出迭代器可用于向容器写入元素,但是不保证能支持读取容器内容。输出迭代器要求:
o 前置和后置的自增运算(++),使迭代器向前递进指向下一个元素。
o解引用操作符(*),引操作符只能出现在赋值运算的左操作数上。给解引用的输出迭代器赋值,将对该迭代器所指向的元素做写入操作。输出迭代器可以要求每个迭代器的值必须

正好写入一次。使用输出迭代器时,对于指定的迭代器值应该使用一次 * 运算,而且只能用一次。输出迭代器一般用作算法的第三个实参,标记起始写入的位置。例如,copy 算法使用一个输出迭代器作为它的第三个实参,将输入范围内的元素复制到输出迭代器指定的目标位置。标准库 ostream_iterator 类型输出迭代器。

3.前向迭代器 用于读写指定的容器。这类迭代器只会以一个方向遍历序列。前向迭代器支持输入迭代器和输出迭代器提供的所有操作,除此之外,还支持对同一个元素的多次读写。可复制前向迭代器来记录序列中的一个位置,以便将来返回此处。需要前向迭代器的泛型算法包括 replace。

4.双向迭代器 从两个方向读写容器。除了提供前向迭代器的全部操作之外,双向迭代器还提供前置和后置的自减运算(--)。需要使用双向迭代器的泛型算法包括 reverse。所有标准库容器提供的迭代器都至少达到双向迭代器的要求。
5.随机访问迭代器 提供在常量时间内访问容器任意位置的功能。这种迭代器除了支持双向迭代器的所有功能之外,还支持下面的操作:
o 关系操作符 <、<=、> 和 >=,比较两个迭代器的相对位置。
o 迭代器与整型数值 n 之间的加法和减法操作符 +、+=、- 和 -=,结果是迭代器在容器中向前(或退回)n 个元素。
o 两个迭代器之间的减法操作符(--),得到两个迭代器间的距离。
o 下标操作符 iter[n],这是 *(iter + n) 的同义词。需要随机访问迭代器的泛型算法包括 sort 算法。vector、deque 和string 迭代器是随机访问迭代器,用作访问内置数组元素的指针也是随机访问迭代器。除了输出迭代器,其他类别的迭代器形成了一个层次结构:需要低级类别迭代器的地方,可使用任意一种更高级的迭代器。对于需要输入迭代器的算法,可传递前向、双向或随机访问迭代器调用该算法。调用需要随机访问迭代器的算法时,必须传递随机访问迭代器。map、set 和 list 类型提供双向迭代器,而 string、vector 和 deque 容器上定义的迭代器都是随机访问迭代器都是随机访问迭代器,用作访问内置数组元素的指针也是随机访问迭代器。istream_iterator 是输入迭代器,而ostream_iterator 则是输出迭代器。

常见的五种使用方式：

1.iterator //正向
2.const_iterator //常量正向
3.reverse_iterator //反向
4.const_reverse_iterator //常量反向
5.容器名.begin() 容器名.end() //配套正向迭代器，分别表示首地址，和尾地址后一个单位（与类型有关）的地址。
相对的.rbegin() .rend() //配套反向迭代器，分别表示尾地址，和首地址前一个单位（与类型有关）的地址。

区别：
正向与反向的区别在于遍历的方向
常量与非常量区别类似于常量指针，就是指向常量的指针，指向值是无法修改的。

使用方法如：容器类型<数据类型>::iterator itbegin = 容器名.begin()
//这样，itbegin相当于一个指针变量，指向该容器首地址

三、算法

　　在 STL 中，算法就是函数模板。STL 中的算法大多数是用来对容器进行操作的，如排序、 查找等。大部分算法都是在头文件 <algorithm> 中定义的，还有些算法用于数值处理，定义在头文件 <numeric> 中。