C++STL泛型编程容器库

STL = Standard Template Library,标准模板库,惠普实验室开发的一系列软件的统称。它是由Alexander Stepanov、Meng Lee和David R Musser在惠普实验室工作时所开发出来的。从根本上说,STL是一些“容器”的集合,这些“容器”有list,vector,set,map等,STL也是算法和其他一些组件的集合。这里的“容器”和算法的集合指的是世界上很多聪明人很多年的杰作。STL的目的是标准化组件,这样就不用重新开发,可以使用现成的组件。STL现在是C++的一部分,因此不用额外安装什么。

序列式容器
向量(vector) 连续存储的元素<vector>
列表(list) 由节点组成的双向链表,每个结点包含着一个元素<list>
双端队列(deque) 连续存储的指向不同元素的指针所组成的数组<deque>
适配器容器
栈(stack) 后进先出的值的排列 <stack>
队列(queue) 先进先出的值的排列 <queue>
优先队列(priority_queue) 元素的次序是由作用于所存储的值对上的某种谓词决定的的一种队列 <queue>
关联式容器
集合(set) 由节点组成的红黑树,每个节点都包含着一个元素,节点之间以某种作用于元素对的谓词排列,没有两个不同的元素能够拥有相同的次序 <set>
多重集合(multiset) 允许存在两个次序相等的元素的集合 <set>
映射(map) 由{键,值}对组成的集合,以某种作用于键对上的谓词排列 <map>
多重映射(multimap) 允许键对有相等的次序的映射 <map>

1. Stack

2.Queue

3.Priority Queue

输出的元素依次为 9 6 5 3 2

如果要按照从小到大排列,把priority_queue<int>q;这条语句换成
priority_queue<int,vector<int>,greater<int>>q;就可以实现。

另外我们可以根据需求,自己定义优先级,对’<’符号进行重载,使得队列中的元素按照一定的顺序排列,假设我们定义一个操作系统中作业的结构体,里面有两个元素,一个是作业名char name[5]; 一个是到达时间intarriveTime; 把作业对象放到优先队列里面,要求在优先队列按作业到达时间从小到大排列,即到达时间最小的作业在队首。

输出为:
no2 1
no1 2
no3 3
实现了优先队列中的作业按照到达时间排序

4.Vector

外也可以定义二维动态数组即vector<int>vec[2];也就是两个容器,用它可以很方便的保存有向图的邻接表,即vec[i]中存放的是与第i个顶点相邻的顶点(从顶点i出发),.其操作只要把上述代码中的vec改成vec[i] 就可以。

5.Set

set这种容器里面存放元素是唯一的,即不可能两个相同的数都存在set里面,set的效率比较高,起内部采用了高效的平衡检索二叉树:红黑树。插入的元素按从小到大自动排好序,第一个元素为最小值。

multiset里面的值可以重复

 

6.Map

map是一种映射关系,一对一,第一个为关键字(first),第二个为键值(second),关键字唯一,map中的元素按关键字有序. 实际应用中要考虑好关键字和键值代表的意义,灵活运用。

输出如下:
apple 1
hello 1
world 3

 

7.头文件#include<algorithm>

使用sort可以很方便的对数组进行进行排序,它可以传两个或三个参数。第一个参数是要排序的区间首地址,第二个参数是区间尾地址的下一个地址,也就是排序的区间为[a,b),比如有一个数组 int a[5], 使得a[0] 到a[4]从小到大有序,只要写 sort(a, a + 5)就可以了,通用sort(a, a+ n);// n为元素个数。sort内部采用的是快速排序,一般情况下效率很高。

另外,我们也可以按照自己的需求进行元素排序,元素可以是结构体,这里就用到了第三个参数,比较函数,告诉计算机按照什么顺序进行排序。
比如:按照从大到小排序。

主函数中: sort(arr, arr+n,cmp);
再比如下面结构体,要按照学生的年龄从小到大排序.

输出:
cc 8
bb 10
aa 15

8.cmath

补充

 

留下评论

您的电子邮箱地址不会被公开。 必填项已用*标注