zhangas

Pay more attention

0%

STL容器的使用

Posted on Edited on

.empty();//空返回true 非空返回false

vector

1
2
3
4
5
6
7
8
9
10
11
12
#include<vector>
vector<int> a(n,x);//初始化n个空间为x
for(auto item: a){//遍历容器
    cout<<item<<" ";
}
a.size();//返回大小
a.empty();//判断是否为空
a.clear();//清空
a.front()/a.back()//返回头 尾元素
a.push_back()/a.pop_back()//添加 删除末尾元素
a.begin()//a[0]
a.end()//a[a.size()]

pair

比一般的结构体多实现了比较函数

1
2
3
pair<int,string> p;//把需要排序的一类元素 放到first里面
p.first()/p.second()//返回第一二个元素
pair<int,pair<int,string>>p;//三列的pair

string 字符串

1
2
3
4
5
string s;
s.size()/s/length()//返回字符串的长度
s.substr(n,m);//n起始位置 m是数组的长度 
s.c_str();//返回该字符串的指针常量 与c语言兼容(c语言无法直接输出string类型的变量)
printf("%s",s.c_str());//输出字符串s

queue 队列

1
2
3
4
5
6
7
8
9
#include<queue>
queue<int> q;
q.size();
q.empty();
q.push();//在队尾添加一个元素
q.front();//返回队头元素
q.back();//返回队尾元素
q.pop();//弹出队头元素

虽然没有clear函数 但可以通过构造新队列初始化 如下 

1
2
3
4
queue<int>q;
q=queue<int> ();
//或者
q=queue<int> {};

priority_queue 优先队列 (堆)

1
2
3
4
5
6
7
8
9
10
priority_queue<int>q;//定义默认是 大根堆(堆顶是最大的元素)
q.push();//插入元素到堆末(并进行排序)
q.top();//返回堆顶的值
q.pop();//弹出堆顶的值
priority_queue<int,vector<int>,greater<int>>q;//定义 小根堆(堆顶是最小的元素)

//小根堆的遍历方式 与大根堆的遍历方式略有不同
for(auto item:(vector<int>&)q){
    cout<<item<<" ";
}

如果是大根堆的话 定义结构体需要重载小于号

1
2
3
4
5
6
7
8
struct node{
    int a,b;
    bool operator < (const node& t) const {
        return a < t.a;
    }
};
priority_queue<node>q;
q.push({1,2});

如果是大根堆的话 定义结构体需要重载大于号

1
2
3
4
5
6
7
struct node{
    int a,b;
    bool operator > (const node& t) const{
        return a>t.a;
    }
};
priority_queue<node,vector<node>,greater<node>> q;

栈 stack

1
2
3
4
5
6
7
#include<stack>
stack<int>stk;
stk.size();//返回大小
stk.empty();//判断是否为空
stk.push();//向栈顶添加元素
stk.top();//返回栈顶的值
stk.pop();//弹出栈顶

deque 双端队列

速度比一般的数组慢上几倍

1
2
3
4
5
6
7
8
#include<deque>//双端队列具有清楚的功能
deque<int>q;
q.front();//返回队列头
q.back();//返回队列尾
q.push_front()/q.push_back()//向队列的头 尾插入元素
q.size();//返回队列的大小
q.clear();//清除双端队列
q.begin()/q.end();//支持迭代器

set/multiset map/multimap 基于平衡二叉树(红黑树) 动态维护有序序列

支持以下操作

1
2
size(),empty(),clear() 
begin(),end(); ++ -- 返回前驱和后继(前一个迭代器) 时间复杂度为o(logn)

set/multiset

set容器中元素不能重复而multiset可以

1
2
3
4
5
6
7
insert();//插入一个数
find();//查询一个数
count();//返回某一个数的个数
erase();//①输入一个数x 删除所有x O(k+logn)
        //②输入一个迭代器 删除这个迭代器
lower_bound();//返回第一个不小于x的数字
upper_bound();//返回第一个不大于x的数字

map/multimap

1
2
3
4
5
6
7
map<PII,int>mp;
mp.insert({a,b});//添加数对a->b
insert();//插入一个pair
erase();//输入的是一个pari或者是迭代器
find();
支持[]
lower_bound()/upper_bound()

无序容器 (哈希容器(也叫散列表))

unordered_set unordered_map unordered_multiset unordered_multimap

和上面操作类似 

1
2
优点: 增删改查的时间复杂度为O(1),set map容器的时间复杂度为O(logn)基于红黑树的高度
缺点: 不支持lower_bound()和upper_bound()操作   也不支持迭代器的++ --

bitset 压位运算

& 按位与 : 如果对应位都为1,那么结果就是1;如果任意一个位是0,则结果就是0
| 按位或 : 与& 的区别在于 如果对应位中任一个操作数为1 那么结果就是1(不需要两个对应位都为1)
~ 取反 : 对位求反 1变0, 0变1
^ 按位异或 : 跟 | 类似, 但有一点不同的是 如果两个操作位都为1的话，结果产生0
<<左移 >>右移
== !=
[]

1
2
3
4
5
6
7
8
9
10
11
12
bitset<N> bst;//N必须是一个整型常数
count();//返回有多少个1

any();//判断是否至少有一个1
none();//判断是否全为0

set();;//所有位置成1
set(k,v);//讲第k位变成v
reset();//把所有位置变为0

flip();//取反 等价于~
flip(k);//把第k位取反