算法常用STL整理
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法常用STL整理,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2780字,纯文字阅读大概需要4分钟。
内容图文
![算法常用STL整理](/upload/InfoBanner/zyjiaocheng/623/101c88c649174f8786375e3eaa99f269.jpg)
算法常用STL
vector
头文件:#include<vector>
vector是一个可变长度的数组,支持随机访问,不支持任意位置的O(1)插入,末尾可以进行O(1)插入。
- vector的定义
struct student{
int sid;
string name;
int age;
int cid;
// ...
}
vector<int> a;
vector<int> b[233]; //b[i] 是一个size=0 的vector
// 每一个vector的size为0.
vector<student> students;
- 初始化
vector<int> a({1,2,3});
vector<int> a = {1,2,3};
vector<int> abc(10); // 10 个 val = 0
vector<int> abc(10,1); // 10 个 val = 1
// 通过数组初始化
int a[5] = {1,2,3,4,5};
vector<int> b(a,a+5);
// 通过同类型vector初始化
vector<int> a(5,1);
vector<int> b(a);
vector<int> b(a.begin()+1,a.end()-1);
vector<int> b = a;
// insert初始化
vector<int> b;
b.insert(b.begin(),a.bein(),a.begin()+3); // 将a[0]-a[3]给b,b.size() -> 3, a是同类型的vector
b.insert(b.begin(),a,a+6); // a是数组
b.insert(b.begin(),6,6); // 插入6个6;
// copy 初始化
vector<int> a(5,1); // 5个1
int a1[5] = {2,2,2,2,2};
vector<int> b(10);
/*将a中元素全部拷贝到b开始的位置中,注意拷贝的区间为a.begin() ~ a.end()的左闭右开的区间*/
copy(a.begin(), a.end(), b.begin());
//拷贝区间也可以是数组地址构成的区间
copy(a1, a1+5, b.begin() + 5);
- 常用函数
vector<int> a;
a.size();
a.empty();
a.clear();
// 迭代器
vector<int>::iterator it = a.begin();
// *it = a[0];
// *(it+2) = a[2];
*it; //去迭代器的值
a.end(); // a的最后一个位置的下一个位置。
*a.begin(); // 就是a[0]
// [begin,end)
a.front(); // == a[0] == *a.begin();
a.back(); // == a[a.size() - 1];
a.push_back();
a.pop_back();
- 遍历
for(int i = 0; i < a.size(); i ++) //..
for(vector<int>::iterator it = a.begin(); it != a.end(); it ++) // .. it != a.end(); 可以写成 it < a.end();
for(auto it = a.begin(); it != a.end(); it ++) //...
for(int x : a) //..
for(auto x : a) //..
vector采用倍增方法,假设需要插入n个元素,那么一共需要拷贝\(\frac{n}{2}+\frac{n}{4}+\frac{n}{8}+... = (\frac{1}{2}+\frac{1}{4}+\frac{1}{8}) * n < n\) 所以平均来看,效率并不差。
删除是\(O(N)\)的复杂度。
queue
文件头:#include<queue>
头文件queue中包含了循环队列queue
和优先队列priority_queue
queue
是先进先出,priority_queue
保证每次pop
的都是max—val,默认是大根堆。
- 定义
queue<int > a;
priority_queue<int> a;//大根堆
priority_queue<int,vector<int>,greater<int>> b;//小根堆
priority_queue<pair<int,int>>;
// 自定义结构体作为优先队列的类型需要重载 < (小根堆需要重载大于号)
struct Rec{
int a,b;
bool operator< (const Rec& t) const {
return a > t.a;
}
}
- 常见方法
//循环队列
q.push(1); //对头插入
q.pop();// 弹出队尾
q.front();// 队头
q.back(); // 队尾
// 优先队列
a.push(1) // 自动调整顺序
a.top(); // 获取max-val
a.pop(); // 删除max-val
/*
没有clear();
queue, priority_queue, stack 没有clear()函数。
*/
if want clear do follow
a = queue<int>(); //re-init
stack
头文件: #include<stack>
先进后出FILO
- 使用
stack<int> stk;
stk.push(1);
stk.top();
stk.pop();
deque
deque 是双端队列,无限制的队列,队尾对头都可以插入和弹出操作。
内容总结
以上是互联网集市为您收集整理的算法常用STL整理全部内容,希望文章能够帮你解决算法常用STL整理所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。