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
|
1 2 3 4 5 6 7 8 |
stack<int>st;//栈st，用于存放int型数据 st.push(3);//将3入栈 st.push(2);//将2入栈 st.pop();//栈顶2出栈 int Top = st.top();//获取栈顶元素,即3 int Size = st.size();//求栈中的元素个数 bool isEmpty = st.empty(); //栈中元素是否为空，1表示空，0表示非空 stack<T>st; // T是存放数据的类型，可以是int, double等，也可以是自定义的结构体类型 |
2.Queue
|
1 2 3 4 5 6 7 8 |
queue<int>que;//队列que,存放int型数据 que.push(3);//将3入队列 que.push(2);//将2入队列 que.pop();//队首3出队列 int Front = que.front();//获取队首元素 int Size = que.size();//队列中元素个数 bool isEmpty = que.empty(); //是否为空 queue<T>que; // T是存放数据的类型，可以是int, double等，也可以是自定义的结构体类型. |
3.Priority Queue
|
1 2 3 4 5 6 7 8 9 10 11 12 |
const int len = 5; int a[len] = {3, 5, 9, 6, 2}; priority_queue<int> q; for(int i = 0; i < len; ++ i) { q.push(a[i]); } for(int i = 0; i < len; ++ i) { cout<< q.top() <<endl; q.pop(); } |
输出的元素依次为 9 6 5 3 2
如果要按照从小到大排列，把priority_queue<int>q;这条语句换成
priority_queue<int,vector<int>,greater<int>>q;就可以实现。
另外我们可以根据需求，自己定义优先级，对’<’符号进行重载，使得队列中的元素按照一定的顺序排列，假设我们定义一个操作系统中作业的结构体，里面有两个元素，一个是作业名char name[5]; 一个是到达时间intarriveTime; 把作业对象放到优先队列里面，要求在优先队列按作业到达时间从小到大排列，即到达时间最小的作业在队首。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
struct Job //定义作业结构体 { char name[5];//作业名 int arriveTime;//到达时间 bool operator < (const Job another)const{//如果当前作业到达时间大于另一个，则当前作业优先级小 if(arriveTime > another.arriveTime) return true; return false; } }job[3]; int main() { strcpy(job[0].name, "no1"); strcpy(job[1].name, "no2"); strcpy(job[2].name, "no3"); job[0].arriveTime = 2; job[1].arriveTime = 1; job[2].arriveTime = 3; priority_queue<Job> que; que.push(job[0]); que.push(job[1]); que.push(job[2]); for(int i = 0; i < 3; ++ i) { Job tempJob = que.top(); que.pop(); cout<< tempJob.name <<" "<<tempJob.arriveTime<<endl; } return 0; } |
输出为：
no2 1
no1 2
no3 3
实现了优先队列中的作业按照到达时间排序
4.Vector
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
vector<int>vec; vec.push_back(2);//尾部插入数字2,即 vec[0]=2 vec.push_back(4);//尾部插入数字4,即 vec[1]=4 int Size = vec.size();//容器中存放数字的个数 cout<< vec[1] <<endl;//访问第二个数字，即4 for(int i = 0; i < vec.size(); ++ i)//按照下标遍历元素,此时vec[0]=2 vec[1]=4 { cout<< vec[i] << " "; } cout<<endl; vector<int>::iterator it;//按照迭代器遍历元素 for(it = vec.begin(); it != vec.end(); ++ it) { cout<< *it <<" "; } cout<<endl; vec.insert(vec.begin() + 1, 6);//在第二个位置上插入元素6，即vec[1]=6 vec.erase(vec.begin() + 1);//删除第二个位置上的元素 vec.clear();//把容器中的元素全部清除 //其它 vector<int>v; v.erase(v.begin() + 2);//删除第2个元素，从0开始计数 v.erase(v.begin() + 1, v.begin() + 5);//删除第1到第5个元素 sort(v.begin(), v.end());//元素排序 //sort(v.begin(), v.end(), cmp);//自定义排序规则，cmp函数自定义 reverse(v.begin(), v.end()); |
外也可以定义二维动态数组即vector<int>vec[2];也就是两个容器，用它可以很方便的保存有向图的邻接表,即vec[i]中存放的是与第i个顶点相邻的顶点（从顶点i出发），.其操作只要把上述代码中的vec改成vec[i] 就可以。
5.Set
set这种容器里面存放元素是唯一的，即不可能两个相同的数都存在set里面，set的效率比较高，起内部采用了高效的平衡检索二叉树：红黑树。插入的元素按从小到大自动排好序，第一个元素为最小值。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
set<int>st;//容器中存放int型数据 st.insert(2);//插入元素2 st.insert(1); st.insert(3); st.insert(8); int Size = st.size();//容器中元素个数 bool isEmpty = st.empty();//元素是否为空 int has1 = st.count(1);//1这个元素是否在set中 st.count()不是1就是0 int has2 = st.count(6);//6这个元素是否在set中，has1值为1 has2值为0 st.erase(1);//在容器中删除1这个元素 bool inSet = (st.find(-2)!= st.end());//-2这个元素是否在set中 cout<<*st.lower_bound(1)<<endl;//返回set中第一个大于等于1的数 cout<<*st.upper_bound(1)<<endl;//返回set中第一个大于1的数 set<int>:: iterator it;//遍历set容器，输出 1 2 3 for(it = st.begin(); it != st.end(); ++ it) { cout<< *it <<" "; } cout<<endl; st.clear();//清空set中的元素 //其它 set<int>st; //反向遍历，从大到小 set<int>::reverse_iterator rit;//定义反向迭代器 for(rit = st.rbegin(); rit != st.rend(); rit ++) { cout << *rit << endl; } |
multiset里面的值可以重复
|
1 2 3 4 5 6 7 8 9 10 11 12 |
multiset<int> ms; int n = ms.erase(3); //删除里面所有的3，返回删除元素总个数 multiset<int>::iterator it; it = ms.find(3); if(it != ms.end())//找到了3这个元素 { cout << *it <<endl; } else { cout<< "not find it"<<endl; } |
6.Map
map是一种映射关系，一对一，第一个为关键字（first），第二个为键值(second)，关键字唯一，map中的元素按关键字有序. 实际应用中要考虑好关键字和键值代表的意义，灵活运用。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
map<string, int> mp; //关键字为string类型，键值为int 类型，我们可以用来表示某一个符 //串str出现的次数,int型键值默认为0 cout<< mp[“hello”] <<endl; //输出”hello”这个字符串出现的次数，这里原来map是空的，但 //但是我们输出了一下以后，mp的元素个数自动变成了1，但是”hello”对应的键值仍然为0 mp.clear();//清空元素 mp.insert(make_pair("hello",1));//插入键值对，代表初始的时候"hello"出现的次数为1 mp.insert(make_pair("world",3));//插入键值对，初始的时候"world"出现的次数为3 mp.insert(make_pair("apple",1));//插入键值对，初始的时候"apple”出现的次数为1 cout<<mp.size()<<endl;//map中的元素个数，这里输出3 map<string, int>:: iterator it;//遍历map for(it = mp.begin(); it!= mp.end(); ++ it) { cout<<it->first<<" "<<it->second<<endl; } |
输出如下：
apple 1
hello 1
world 3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
cout<< mp[“hello”]<<end;//查看”hello”出现的次数 mp[“hello”] ++ ;//”hello”出现的次数+1 bool inMap = mp.count(“hello”); //”hello”是否在map中，返回0或1 inMap = (mp.find("hello") != mp.end()); //”hello”是否在map中，返回0或1 for(it = mp.begin(); it != mp.end(); ++ it)//查找到”hello”,然后删除该元素 { if(it->first == "hello") { mp.erase(it); break; } } |
|
1 2 3 4 5 6 7 8 9 |
//map-----------键值-->映照数据 map<int> mp; mp.erase(2);//删除键值为2的元素 map<int>::iterator it; it = mp.find(2);//查找键值 if(it != mp.end())//找到了 { cout << (*it).first << (*it).second <<endl; } |
7.头文件#include<algorithm>
使用sort可以很方便的对数组进行进行排序,它可以传两个或三个参数。第一个参数是要排序的区间首地址，第二个参数是区间尾地址的下一个地址，也就是排序的区间为[a,b),比如有一个数组 int a[5], 使得a[0] 到a[4]从小到大有序，只要写 sort(a, a + 5)就可以了，通用sort(a, a+ n);// n为元素个数。sort内部采用的是快速排序，一般情况下效率很高。
|
1 2 3 4 5 |
const int n = 3; int arr[n] = {1, 3, 2}; sort(arr,arr+n); for(int i = 0; i < n; ++ i) cout<< arr[i] <<endl; |
另外，我们也可以按照自己的需求进行元素排序，元素可以是结构体，这里就用到了第三个参数，比较函数，告诉计算机按照什么顺序进行排序。
比如：按照从大到小排序。
|
1 2 3 4 5 6 |
bool cmp(int a, int b)//定义比较函数，从大到小 { if(a >= b) return true; return false; } |
主函数中： sort(arr, arr+n,cmp);
再比如下面结构体，要按照学生的年龄从小到大排序.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
struct Student { int age; //年龄 string name;//姓名 }student[3]; bool cmp(Student a, Student b) { if(a.age <= b.age) return true; return false; } student[0].name = "aa";student[0].age = 15; student[1].name = "bb";student[1].age = 10; student[2].name = "cc";student[2].age = 8; sort(student, student+3, cmp); for(int i = 0; i < 3; ++ i) cout<< student[i].name <<" "<<student[i].age<<endl; |
输出：
cc 8
bb 10
aa 15
8.cmath
|
1 2 3 |
cout<< log2(8) <<endl; //输出3 , 因为2的3次方为8 cout<< log10(100) <<endl; //输出2，因为10的2次方为100 cout<< log(20) <<endl; //计算 ln(20)的值 |
补充
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
//重载'<'操作符，自定义排序规则，在map中 bool operator < (const Info &a) const { //按score从小到大排序 return a.score < score; } }; map<Info, int> mmp; //multimap------------允许键值相同的存在 multimap<string, double>m; m.insert(pair<string, double> ("jack", 20.4)); m.insert(pair<string, double> ("jack", 34.1)); m.erase("jack");//删除键值等于"jack"的元素 //find()函数只返回重复键值中的第一个元素的迭代器位置 //deque-------------双端队列 push_back()方法在尾部插入元素，不断扩张队列 push_front()和insert()在首部和中间位置插入元素，只是将原位置上的元素值覆盖，不会增加新元素 deque<int> d; d.push_back(1); d.push_back(2); d.push_back(3); d.insert(d.begin() + 1, 88); cout << d[0] << d[1] << d[2] <<endl; //输出 1 88 3 d.pop_front();//头部删除元素 d.pop_back();//尾部删除元素 d.erase(d.begin() + 1); //list--------------链表 list<int> l; l.push_back(2); l.push_back(1); l.push_back(5);//链表尾部插入元素，链表自动扩张 l.push_front(8);//链表头部插入元素，链表自动扩张 list<int>::iterator it; it = l.begin(); it ++;//注意链表的迭代器只能进行 ++ 或者 -- ，不能 + n l.insert(it, 20); for(it = l.begin(); it != l.end(); it ++) { cout << *it <<endl; //输出 8 20 2 1 5 } l.remove(2);//值为2的节点都删除 l.pop_front();//删除首部元素 l.pop_back();//删除尾部元素 l.sort();//排序 l.unique();//剔除重复元素， 3 8 1 1 1 3 1 ----> 3 8 1 3 1 //bitset 位集合容器 bitset<10>b; //能容纳10个元素，也就是10位，默认都为0 //赋值 b[1] = 1; b[6] = 1; b[9] = 1; //第0位是最低位，第9位是最高位 for(int i = b.size() - 1; i >= 0; i --) { cout << b[i] << " "; //输出 1001000010 } b.set();//全部重置为1 b.set(1, 1);//将第1位置为1 b.set(6, 1); b.set(9, 1); b.reset(9);//将第9位置为0 cout << b <<endl;// 和上面效果相同，也是输出1001000010 |
