vector 容器
迭代器 interator
vector<int> v{1, 0, 0, 8, 6};
for(vector<int>::interator it = v.begin(); it != v.end(); it ++)
cout << *it << " ";
vector 函数集合
push_back(x); // 添加元素
pop_back(); // 删除尾元素
size(); // 查询 vector 长度
insert(it, x); // 插入元素
erase(); // 删除vector容器中的一个或一段元素
clear(); // 清空容器
总结
做题时能用数组就尽量用数组， vector 的时间复杂度比数组慢很多。
set 集合
介绍
\(set\)（集合）是 \(C++ STL\) 中的一种关联式容器， 它内部使用红黑树（一种自平衡二叉搜索树）去实现元素的有序存储。
set 元素访问
只能通过迭代器访问 例：
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 << " ";
set 函数集合
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
拓展
不去重但排序的容器 ： \(muliset\)