vector 容器
迭代器
vector<int> v{1, 0, 0, 8, 6};
for(vector<int>::interator it = v.begin(); it != v.end(); it ++)
cout << *it << " ";
函数
push_back(x); // 添加元素
pop_back(); // 删除尾元素
size(); // 查询 vector 长度
insert(it, x); // 插入元素
erase(); // 删除vector容器中的一个或一段元素
clear(); // 清空容器
总结
做题时能用数组就尽量用数组， vector 的时间复杂度比数组慢很多。
set 集合
介绍
\(set\)（集合）是 \(C++ STL\) 中的一种关联式容器， 它内部使用红黑树（一种自平衡二叉搜索树）去实现元素的有序存储。
访问
只能通过迭代器访问 例：
set<int> s{1, 0, 0, 8, 6};
for(set<int>::interator it = s.begin(); it != s.end(); it ++)
cout << *it << " ";
但可以利用 \(C++ 11\) 继续简化
for(auto it = s.begin(); it != s.end(); it ++)
cout << *it << " ";
或
for(auto it : s)
cout << it << " ";
函数
insert(x); // 时间复杂度 O(log_n)
find(x); // 返回 set 中对应值的迭代器， 否则返回 end()， 时间复杂度 O(log_n)
erase(first, second); // 删除容器中的元素
clear(); // 清空容器
lower_bound(x); // 找到首个大于等于给定元素的迭代器， 不存在返回 end()
upper_bound(x); // 找到首个大于给定元素的迭代器， 不存在返回 end()
size(); // 查询 set 元素个数， 时间复杂度 O(1)
empty(); // 容器是否为空
count(x); // 查找 x 的个数， 返回 0 / 1
拓展
不去重但排序的容器 ： \(multiset\)
map 容器
为什么要用 map
问 ： 我要统计一堆数中一个数的个数， 用什么！！
答 ： 用 桶数组！！
再问 ： 我要统计一堆字符串中一个字符串的个数， 用什么！！
答 ： \(map\)！！
现在懂了为什么要用 \(map\) 了吗？
特性
1. 通过键访问
map<string, int> mp;
mp["mp"] ++;
mp["10086"] ++;
mp["abc"] ++;
mp["10086"] ++;
cout << mp["10086"] << ' ' << mp["abc"];
这里程序结果输出 2 1， 可以看出 \(map\) 的键具有唯一性。
2. 通过迭代器访问
注： map 会以键的大小自动排序
map<char, int> mp;
mp['a'] ++;
mp['b'] = 10086;
mp['c'] = 114514;
for(map<char, int>::interator it = mp.begin(); it != mp.end(); it ++)
cout << it->first << " " << it->second << endl;
这里 也可以写成 ：
for(auto it = mp.begin(); it != mp.end(); it ++)
cout << it->first << " " << it->second << endl;
或
for(auto it : mp)
cout << it.first << " " << it.second << endl;