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;
}
};参考书目：《算法笔记》
发表回复