STL
- vector 变长数组,倍增的思想
- string 字符串,substr(), c_str() 返回str对应的字符数组的头指针
- queue 队列push() front() pop() back()
- priority_queue 优先队列,push(), top(), pop()
- stack 栈 push(),top(), pop()
- deque 双端队列 队头队尾都可以插入删除,支持随机访问
- set map multiset multimap 基于平衡二叉树(红黑树),动态维护有序序列
- unordered_set unordered_map unordered_multiset unordered_multimap 基于哈希表
- bitset 压位
vector
// 初始化
vector<int> a(10); // 初始化长度为10的向量,默认元素为0
vector<int> b(10,3); // 长度为10,元素都为3
// 所有容器都有size和empty,有个变量来存,时间复杂度O(1)
a.size(); // 元素个数
a.empty(); // 是否为空
a.clear(); // 清空后元素个数为0
a.front(); // 返回第一个数
a.back(); // 返回最后一个数
a.push_back(5); // 在最后增加一个数
a.pop_back(); // 弹出最后一个数
a.begin(),a.end(); // 迭代器,第0个数a[0],最后一个数的后面一个位置a[a.size()]
b.erase(b.begin()+2,b.begin()+4); // 删除中间的元素
[] —— 可以用数组下标访问vector元素
支持比较运算,按照字典序
三种遍历方式
// 数组下标
for(int i = 0;i<a.size();i++){
cout<<a[i]<<' ';
}
// 迭代器
for(vector<int>::iterator i = a.begin();i!=a.end();i++){
cout<<*i<<" ";
}
// c++增加
for(auto x:a)cout<<x<<" ";
pair
#include
pair<int,string>p;
-
p.first ——第一个元素 -
p.second —— 第二个元素
构造
pair<int,string>pair1; // 注意没有括号
pair<int,string>pair2(1,"abc");
pair<int,string>pair3 = make_pair(22,"zzz");
pair<int,string>pair4 = {66,"No"};
pair4.first = 66; // 对first 和 second再进行修改
pair4.second = "yes";
pair4.first = 100;
比较
支持比较运算,按照字典序以first为第一关键字,second为第二关键字,先比较first,再比较second,两个均相同才相等
交换
swap(p1,p2);
扩展元素
pair<int,pair<int,int>>p; // 用pair存储三个属性
排序
我们可以直接使用sort对pair进行排序,按照first排序
sort(p,p+N,cmp);
bool cmp(pair<int,int>p1,pair<int,int>p2){
if(p1.first>p2.first){
return true;
}
else if(p1.first==p2.first && p1.second >p2.second){
return true;
}
else{
return false;
}
}
string
string str;
str.size();
str.empty();
str.clear();
str += "abc";
str +='a';
str.substr(1,2); // 获取子串(begin,len);如果长度超过子串末尾,就只输出到末尾
printf字符串
对比:
string str = "abc";
char ch[] = "hello";
printf("%s\n",str.c_str());
printf("%s\n",ch);
queue
queue<int>q;
q.push(x);
q.front();
q.back();
q.pop();
q.size();
q.empty();
// 没有clear
遍历输出队列
queue<int>q;
q.push(1);
q.push(2);
q.push(999);
while(!q.empty()){
cout<<q.front()<<" ";
q.pop();
}
priority_queue
默认大根堆
push(); // 插入一个元素
top(); // 返回堆顶元素
pop(); // 弹出堆顶元素
priority_queue<int>heap; // 定义一个大根堆
要实现小根堆:
stack
size();
empty();
// 没有clear()
push();
top();
pop();
deque 双端队列
支持再两端高效插入或删除元素的连续线性存储空间
效率低
deque<int>dq;
dq[1]; //
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
- set中不能有重复元素
- multiset 可以有重复元素
set 和 multiset: 所有操作是O(logn)
#include<set> // 包括set 和 multiset
set<int>s;
multiset<int>ms;
map+multimap
是一个键值对key-value的映射,内部是红黑树,key必须定义"小于号"运算符
- insert() 插入的数是一个pair
- erase() 输入的参数是pair或者迭代器
- find()
- [] 时间复杂度是o(logn) —— 如果不存在会新建一个二元组,value=空
- lower_bound() 返回大于等于x最小的数的迭代器
- upper_bound() 返回大于x最小的数的迭代器
map<string,int> a;
a["zzz"] = 1;
cout<<a["zzz"]<<endl;
遍历案例
//创建一个空的 map 关联式容器,该容器中存储的键值对,其中键为 string 字符串,值也为 string 字符串类型
map<string, string> mymap;
//向 mymap 容器中添加数据
mymap["http://c.biancheng.net/c/"] = "C语言教程";
mymap["http://c.biancheng.net/python/"] = "Python教程";
mymap["http://c.biancheng.net/java/"] = "Java教程";
//使用 map 容器的迭代器,遍历 mymap 容器,并输出其中存储的各个键值对
for (map<string, string>::iterator it = mymap.begin(); it != mymap.end(); ++it) {
//输出各个元素中的键和值
cout << it->first << " => " << it->second << '\n';
}
for(auto it:mymap){
cout << it.first << " => " << it.second << '\n';
}
自定义排序
map<int,string>mymap = {{11,"zbc"},{22,"abc"},{15,"hhh"}}; // 默认从小到大
map<int,string,less<int>>mymap2 = {{11,"zbc"},{22,"abc"},{15,"hhh"}}; // 从小到大
map<int,string,greater<int>>mymap3 = {{11,"zbc"},{22,"abc"},{15,"hhh"}}; // 从大到小
for(auto x:mymap){
cout<<x.first<<" "<<x.second<<endl;
}
cout<<endl;
for(auto x:mymap2){
cout<<x.first<<" "<<x.second<<endl;
}
cout<<endl;
for(auto x:mymap3){
cout<<x.first<<" "<<x.second<<endl;
}
迭代器
map 的迭代器是双向迭代器(bidirectional iterator)。这意味着,map 容器迭代器只能进行 ++p、p++、–p、p–、*p 操作,并且迭代器之间只能使用 == 或者 != 运算符进行比较。
find
int main() {
//创建并初始化 map 容器
std::map<std::string, std::string>myMap{ {"STL教程","http://c.biancheng.net/stl/"},
{"C语言教程","http://c.biancheng.net/c/"},
{"Java教程","http://c.biancheng.net/java/"} };
//查找键为 "Java教程" 的键值对
auto iter = myMap.find("Java教程");
//从 iter 开始,遍历 map 容器
for (; iter != myMap.end(); ++iter) {
cout << iter->first << " " << iter->second << endl;
}
return 0;
}
lower_bound 和 upper_bound -更多用于 multimap 容器,在 map 容器中很少用到
map<int,string>mymap = {{11,"zbc"},{22,"abc"},{15,"hhh"}};
for(map<int,string>::iterator it = mymap.lower_bound(15);it!=mymap.end();it++){ // 包含15
cout<<it->first<<" "<<it->second<<endl;
}
for(map<int,string>::iterator it = mymap.upper_bound(15);it!=mymap.end();it++){ // 不包含15
cout<<it->first<<" "<<it->second<<endl;
}
equal_range- 更多用于 multimap 容器,在 map 容器中很少用到
map<int,string,greater<int>>mymap = {{11,"zbc"},{22,"abc"},{15,"hhh"}};
pair<map<int,string>::iterator,map<int,string>::iterator>ret = mymap.equal_range(15);
for(auto x = ret.first;x!=ret.second;x++){
cout<<x->first<<" "<<x->second<<endl;
}
获取键对应值
- mymap[key] 可以返回value ——如果有就返回,没有就会创建,且value = 0
- mymap.at(key) 可以返回value ——如果有就返回,没有就会抛出异常
插入元素
-
[] -
insert
- insert(pair1)
- insert({1,"abc})
- insert(first迭代器, last迭代器); ——插入其他map的内容
返回值:pair<map<int,string>::iterator,bool> 迭代器表示插入的键值对的迭代器(如果原来存在相同的键,仍然指向原来的),bool表示是否插入成功 map<int,string>mymap;
pair<int,string>p1 = {1,"abz"};
pair<map<int,string>::iterator,bool>ret;
ret = mymap.insert(p1);
cout<<ret.first->first<<" "<<ret.first->second<<" "<<ret.second<<endl;
ret = mymap.insert({2,"zzz"});
cout<<ret.first->first<<" "<<ret.first->second<<" "<<ret.second<<endl;
ret = mymap.insert({2,"yes"});
cout<<ret.first->first<<" "<<ret.first->second<<" "<<ret.second<<endl;
for(auto x:mymap){
cout<<x.first<<" "<<x.second<<endl;
}
1 abz 1
2 zzz 1
2 zzz 0 // 插入失败,指向原来的
1 abz
2 zzz
unordered_set unordered_map unordered_multiset unordered_multimap
和上面类似,增删改查的时间复杂度是o(1)
不支持和排序相关的操作,不支持lower_bound()、upper_bound()
bitset
占用的空间是布尔数组/8
bitset<10000>s; // 大小为10000
~ & | ^
>> <<
== !=
// --- 判断相关----
[] // 取出某一位
count() // 返回有多少个1
any() // 判断是否至少有一个1
none() // 判断是否全为0
// --- 设置相关----
set() // 把所有位置变成1
set(k,v) //把第k位变成v
reset() //把所有位置变成0
flip() // 所有位取反,s = ~s
flip(k) // 把第k位取反,s[k]^=1
这几个函数很像触发器:置位、清零、反转
|