共计 3177 个字符，预计需要花费 8 分钟才能阅读完成。
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;
}
};参考书目：《算法笔记》