vector
vector<typename> name
| 函数 | 性能 | 工夫复杂度 |
|---|---|---|
| push_back(x) | 在vector前面增加一个元素 | O(1) |
| pop_back() | 删除vector的尾元素 | O(1) |
| size() | 取得vector的元素个数 | O(1) |
| clear() | 清空vector中的所有元素 | O(N)，N为vector元素个数 |
| insert(it,x) | 向vector的任意迭代器it处插入一个元素x | O(N) |
| erase(it) | 删除迭代器it处的元素 | O(N) |
| erase(first,last) | 删除[first,last)内的所有元素 | O(N) |
queue
queue<typename> name
| 函数 | 性能 | 工夫复杂度 |
|---|---|---|
| push(x) | 将x进行入队 | O(1) |
| front() | 取得队首元素，应用前调用empty()函数 | O(1) |
| back() | 取得队尾元素，应用前调用empty()函数 | O(1) |
| pop() | 令队首元素出队 | O(1) |
| empty() | 检测queue是否为空 | O(1) |
| size() | 返回queue内元素的个数 | O(1) |
priority_queue
priority_queue<typename> name
| 函数 | 性能 | 工夫复杂度 |
|---|---|---|
| push(x) | 将x入队 | O(logN)，N为以后优先队列中的元素个数 |
| top() | 取得队首元素（即堆顶元素）,应用前调用empty()函数 | O(1) |
| pop() | 令队首元素（即堆顶元素）出队 | O(logN)，N为以后优先队列中的元素个数 |
| empty() | 检测优先队列是否为空 | O(1) |
| size() | 返回优先队列内元素的个数 | O(1) |
priority_queue<int> q 数字越大优先级越大
priority_queue<int ,vector<int>,less<int>> q 数字越大优先级越大
priority_queue<int,vector<int>,greater<int>> q 数字越小优先级越大
#include <iostream>#include <stdio.h>#include <queue>using namespace std;struct fruit{ string name; int price; friend bool operator < (fruit f1,fruit f2)//只能对小于号进行重载 { return f1.price>f2.price; //具体了解：如果f1.price>f2.price为true，那么就认为f1 "<" f2，所以f1应该在f2前面 //与sort函数中的cmp正好相同 }} f1,f2,f3;int main(){ priority_queue<fruit> q; f1.name = "桃子"; f1.price = 3; f2.name = "梨子"; f2.price = 4; f3.name = "苹果"; f3.price = 1; q.push(f1); q.push(f2); q.push(f3); //printf("%s %d\n",q.top().name,q.top().price); cout<<q.top().name<<" "<<q.top().price<<endl; return 0;}priority_queue的用处：解决贪婪问题；对Dijkstra算法进行优化。
stack
stack< typename > name
| 函数 | 性能 | 工夫复杂度 |
|---|---|---|
| push(x) | 将x入栈 | O(1) |
| top() | 取得栈顶元素 | O(1) |
| pop() | 弹出栈顶元素 | O(1) |
| empty() | 检测stack是否为空 | O(1) |
| size() | 返回stack内元素的个数 | O(1) |
set
set内的元素主动递增排序，且主动去除了反复元素
set迭代器拜访办法：
set<typename>::iterator it;set<int>::iterator it;set<char>::iterator it;int main(){ set<int> st; for(set<int>::iterator it=st.begin(); it!=st.end(); it++){ printf("%d",*it); } }| 函数 | 性能 | 工夫复杂度 |
|---|---|---|
| insert(x) | 将x插入set容器中，并主动递增和去重 | O(logN) |
| find(value) | 返回set中对应值为value的迭代器 | O(logN) |
| erase(it) | 删除单个元素，it为所须要删除元素的迭代器 | O(1) |
| erase(value) | 删除单个元素，value为所须要删除元素的值 | O(logN) |
| erase(first,last) | 删除一个区间内的所有元素，即删除[first,lase) | O(last-first) |
| size() | 用来取得set内元素的个数 | O(1) |
| clear() | 用来清空set中的所有元素 | O(N)，其中N为set内元素的个数 |
map
map能够将任何根本类型（包含STL容器）映射到任何根本类型（包含STL容器）。
map<typename1,typename2> mp;
如果是字符串到整型的映射，必须应用string而不能用char数组。
map<string,int> mp;
map容器中元素的拜访个别有两种拜访形式：
- 通过下标拜访；当建设映射的时候，就能够间接应用map['c'] = 20这样和一般数组一样的形式。
通过迭代器拜访；
map<typename1,typename2>::iterator it;
应用it->first来拜访键，应用it->second来拜访值。
map会以键从小到大的程序主动排序。
| 函数 | 性能 | 工夫复杂度 |
|---|---|---|
| find(key) | 返回键为key的映射的迭代器 | O(logN)，N为map中映射的个数 |
| erase(it) | 删除单个元素，it为须要删除的元素的迭代器 | O(1) |
| erase(first,last) | 删除左闭右开区间[first,last)，first和last均为迭代器 | O(last-first) |
| size() | 用来取得map中映射的对数 | O(1) |
| clear() | 用来清空map中的所有元素 | O(N)，N为map中映射的个数 |
string
"xyz">"abc"成立，因为“x">"a"
如何在一个string类型的变量前面增加删除字符
string a;a.push_back('a');a.pop_back()string类型的变量只能用双引号括起来，不能用单引号括起来：
string a = 'abc';//谬误，python能够这么干，c++不能string b = "abc";//正确class Solution {public: bool canFinish(int numCourses, vector<vector<int>>& prerequisites) { int in_degree[numCourses]; vector<int> graph[numCourses]; int nums = 0; queue<int> topo; for(int i=0; i<numCourses; i++){ in_degree[i] = 0; } for(vector<int> tmp:prerequisites){ graph[tmp[0]].push_back(tmp[1]); in_degree[tmp[1]]++; } for(int i=0; i<numCourses; i++){ if(in_degree[i]==0){ topo.push(i); } } while(!topo.empty()){ int now = topo.front(); topo.pop(); nums++; for(int i=0; i<graph[now].size(); i++){ in_degree[graph[now][i]]--; if(in_degree[graph[now][i]] == 0){ topo.push(graph[now][i]); } } } if(nums==numCourses){ return true; } return false; }};参考书目：《算法笔记》