供自己用的 记录算法基础课的stl笔记
vector 变长数组,倍增的思想
size() 返回元素个数
empty()返回是否为空
clear()清空
front()/back()//返回第一个数,返回最后一个数字
push_back()/pop_back()在最后面加一个数/删除最后的一个数
begin()/end()
vector支持随机寻址
pair< int , int >p;
p.first是第一个元素
p.second是第二个元素
string 字符串
substr()
c_str()
size()/length()
empty()
clear()
queue,队列[kjuː]
size()
empty()
push()向队尾插入一个元素
front()返回队头元素
back()返回队尾元素
pop()弹出队头元素
priority_queue 优先队列
push()插入一个元素
top()返回堆顶元素
pop()弹出堆顶元素
priority_queue<int,vector<int>,greater<int>>heap;
stack 栈
size()
empty()
push()向栈顶插入一个元素
top()返回栈顶元素
pop()弹出栈顶元素
deque双端队列 队头队尾都可以插入删除
size()
empty()
clear()
front()返回第一个元素
back()返回最后一个元素
push_back()/pop_back()
push_front()/pop_front()
begin()/end()
缺点:比别的容器慢好几倍
set,map,multiset,multimap,基于平衡二叉树(红黑树),动态维护有序序列
size()
empty()
clear()
begin()/end() ++,
set/multiset
insert()插入一个数
find()查找一个数 ,如果查不到 返回end()迭代器
count()返回某一个数的个数
//set里只有0/1的情况
//multiset可以有多个
erase()
(1)输入是一个数x,删除所有x ,复杂度O(k+logn) (k是x的个数)
(2)输入一个迭代器,删除这个迭代器
set最核心的部分
lower_bound()/upper_bound()
lower_bound()返回大于等于x的最小的数的迭代器
upper_bound返回大于x的最小的数的迭代器
map/multimap
insert()//插入的数是一个pair
erase()//输入的参数是pair或者迭代器
find()
//map最nb的部分hh
[] 时间复杂度是O(logn)
//用法见下面的代码
lower_bound()/upper_bound()
unordered_set,unordered_map,unordered_multiset,unordered_multimap、哈希表
和上面类似,好处是增删查改的时间复杂度为O(1)(上面的几个的为O(logn)
但缺点是不支持 lower_bound()/upper_bound()
也不支持迭代器的++,
bitset,压位
bitset<1000>S;
~,&,|,^
<<, >>
[]
count()返回有多少个1
any()判断是否至少有一个1
more()判断是否全为0
set()把所有位置成1
set(k,v)将第k位变成v
reset()把所有位变成0
flip()等价于~
flip(k)把第k位取反
vector
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace st;
int main(){
vecotr<int> a(10,-3);
vector<int>a(10);
vector<int>a[10];
a.size();
a.empty();
for(int i=0;i<10;i++)a.push_back(i);
for(int i=0;i<a.size();i++)cout<<a[i]<<endl;
cout<<endl;
for(vector<int>::iterator i=a.begin();i!=a.end();i++)cout<<*i<<' ';
cout<<endl;
for(auto x:a)cout<<x<<' ';
vector<int>a(4,3),b(3,4);
if(a<b)puts("a<b");
}
pair< int, int>
pair<int ,string>p;
p.first是第一个元素
p.second是第二个元素
p={20,"anc"};
pair<int,pair<int,int>>
string
string a="yxc";
a+="def";
a+='c';
cout<<a<<endl;
cout<<a.substr()<<endl;
printf("%s\n",a.c+str());
priority_queue
priority_queue<int>heap;
heap.push(-x);
priority_queue<int,vector<int>,greater<int>>heap;
set multiset
set<int>S;
multiset<int>MS;
map/multimap
map<string,int> a;
a["yxc"]=1;
cout<<a["yxc"]<<endl;