vector
vector 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 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 name
| 函数 |
功能 |
时间复杂度 |
| push(x) |
将x入队 |
O(logN)，N为当前优先队列中的元素个数 |
| top() |
获得队首元素（即堆顶元素）,使用前调用empty()函数 |
O(1) |
| pop() |
令队首元素（即堆顶元素）出队 |
O(logN)，N为当前优先队列中的元素个数 |
| empty() |
检测优先队列是否为空 |
O(1) |
| size() |
返回优先队列内元素的个数 |
O(1) |
priority_queue q 数字越大优先级越大
priority_queue,less> q 数字越大优先级越大
priority_queue,greater> q 数字越小优先级越大
#include
#include
#include 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 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<
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::iterator it;
set::iterator it;
set::iterator it;
int main(){
set st;
for(set::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容器）。
【算法笔记-STL以及常见问题】map mp;
如果是字符串到整型的映射，必须使用string而不能用char数组。
map mp;
map容器中元素的访问一般有两种访问方式：
- 通过下标访问；当建立映射的时候，就可以直接使用map['c'] = 20这样和普通数组一样的方式。
- 通过迭代器访问；
map::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>& prerequisites) {
int in_degree[numCourses];
vector graph[numCourses];
int nums = 0;
queue topo;
for(int i=0;
i tmp:prerequisites){
graph[tmp[0]].push_back(tmp[1]);
in_degree[tmp[1]]++;
}
for(int i=0;
i
参考书目：《算法笔记》
推荐阅读
