STL
vector(变长数组)
变长数组,支持随机访问,不支持在任意位置O(1)插入。为了保证效率,元素的增删一般应该在末尾进行
#include<vector> //头文件
vector<int> a; //相当于一个长度动态变化的int 数组
vector<int> b[233]; //相当于第一维长233,第二位长度动态变化的int数组
struct rec{…};
vector<rec> c; //自定义的结构体类型也可以保存到vector中
----------------------
vector<int> a;
a.size(); //长度(元素个数)
a.empty(); //判断是否为空,空返回1
a.clear(); //清空
vector<int>::iterator it; //迭代器、支持相加减
*it //相当于a[it]
a.begin(); //返回第一个元素的迭代器
a.end(); //返回最后一个元素后一个位置的迭代器
a.front(); //返回第一个元素
a.back(); //返回最后一个元素
a.push_back(x); //把元素x插入到vector a的尾部、O(1)
a.pop_back(); //删除vector a的最后一个元素
next_permutation(a.begin(), a.end()); //返回数组的下一个排列,若没有下一个排列就返回0
//三种遍历
for(int i = 0; i < a.size(); i++ )
for(auto it = a.begin(); it != a.end(); it++ )
for(int x : a)
queue(队列)
先进先出
头文件queue主要包括循环队列queue和优先队列priority_queue两个容器
#include<queue> //头文件
queue<int> q;
struct rec{…};
queue<rec> q;
priority_queue<int> q; // 大根堆、优先弹出最大值
priority_queue<int, vector<int>, greater<int>> q; // 小根堆、优先弹出最小值
priority_queue<pair<int, int>> q;
struct rec
{
int a, b;
bool operator< (const rec& t) const //大根堆重载小于号
{
return a < t.a;
}
};
priority_queue<rec> q;
----------------------
queue<int> a; //队头弹出、队尾插入
a.push(x); //在队尾插入元素x
a.pop(); //弹出队头元素
a.front(); //返回队头元素
a.back(); //返回队尾元素
//队列、优先队列、栈三个容器没有clear函数
//重新初始化来清空
priority_queue<int> a;
a.push(x); //插入一个数x
a.top(); //取最大值
a.pop(); //删除最大值
stack(栈)
先进后出
#include<stack>
stack<int> a;
----------------------
a.push(x); //插入一个元素
a.top(); //取出栈顶元素
a.pop(); //删除栈顶元素
deque(双端队列)
双端队列deque是一个支持在两端高效插入或删除元素的连续线性存储空间。它就像是vector和queue的结合。与vector相比,deque在头部增删元素仅需要O(1)的时间;与queue相比,deque像数组一样支持随机访问。
#include<deque>
deque<int> a;
----------------------
deque<int> a;
a.begin(); //返回队头的迭代器
a.end(); //返回队尾后一个元素的迭代器
a.front(); //返回队头元素
a.back(); //返回队尾元素
a.push_front(x); //在队头插入一个元素
a.push_back(x); //在队尾插入一个元素
a.pop_front(); //从对头出队
a.pop_back(); //从队尾出队
a.clear(); //清空
set
头文件set主要包括set和multiset两个容器,分别是“有序集合”和“有序多重集合”,即前者的元素不能重复,而后者可以包含若干个相等的元素。set和multiset的内部实现是一棵红黑树,它们支持的函数基本相同。
#include<set>
set<int> a; //不能包含重复元素
multiset<int> a; //可以包含重复元素
struct rec
{
int a, b;
bool operator< (const rec& t) const //重载小于号
{
return a < t.a;
}
}
set<rec> a;
----------------------
set<int> a;
set<int>::iterator it = a.begin();
it++; it--; //有序数列的前驱与后继
++it; --it;
a.begin(); //指向集合中最小元素的迭代器
a.end(); //指向集合中最大元素的下一个位置的迭代器
a.insert(x); //插入元素x,O(logn),在set中若x已存在则不会重复插入元素
a.find(x); //查找元素x,返回其迭代器,O(logn),若不存在则返回a.end()
if(a.find(x) == a.end()) //判断a中是否存在x
a.lower_bound(x); //查找大于等于x的元素中最小的一个,返回其迭代器,O(logn)
a.upper_bound(x); //查找大于x的元素中最小的一个,返回其迭代器,O(logn)
a.erase(it); //删除迭代器it指向的元素,O(logn)
a.erase(x); //删除所有等于x的元素,O(k + logn),k是被删除的元素个数
a.count(x); //返回等于x的元素个数,O(k + logn),k是被删除的元素个数
map
map容器是一个键值对key-value的映射,其内部实现是一棵以key为关键码的红黑树,map的key和value可以是任意类型,其中key必须定义小于号运算符。
#include<map>
map<int, int> a;
a[1] = 2;
map<string, vector<int>> a;
a["abc"] = vector<int>({1, 2, 3, 4});
cout << a["abc"][2];
pair<string, int> a;
a = {"abc", 1};
cout << a.first;
cout << a.second;
----------------------
//size/empty/clear/begin/end均与set类似
//insert/erase与set类似,但其参数均是pair<key_type, value_type>
map<string, vector<int>> a;
a.insert({"abc", {}});
a.find(x); //在变量名为a的map中查找key为x的二元组
a[key] //返回key映射的value的引用,时间复杂度为O(logn)。
unordered_set和unordered_map
#include<unordered_set>
unordered_set<int> a; //哈希表实现,不能有重复元素
unordered_multiset<int> a; //哈希表实现,可以有重复元素
#include<unordered_map>
unordered_map<int, int> a; //哈希表实现
bitset
#include<bitset>
bitset<1000> a; //长度为1000的01串
a.count(); //返回1的个数
a.set(3); //将3的位置设为1
a.reset(3); //将3的位置设为0
位运算常用方法
x >> k & 1; //求x的第k位数字
lowbit(x) = x & (-x); //求x的最后一位1的位置,如011001000会返回000001000,没有库函数,需要自己定义
常用库函数
reverse,unique,random_shuffle,sort,lower_bound/upper_bound
#include<algorithm> //头文件
----------------------
reverse(a.begin(), a.end()); //翻转一个vector,O(n)
reverse(a, a + n); //翻转一个数组,第一个参数起始位置,第二个参数终止位置的后一个位置
----------------------
//unique函数作用的数组要相同的元素在一起,将不重复的数放在数组的前面,返回值是新数组的下一个位置
unique(a, a + n);
int m = unique(a.begin(), a.end()) – a.begin(); //数组当中不同元素的数量
a.erase(unique(a.begin(), a.end()), a.end());
int m = unique(a , a + n) – a;
----------------------
#include<ctime>
srand(time(0));
random_shuffle(a.begin(), a.end()); //随机打乱数组
----------------------
sort(a.begin(), a.end()); //从小到大排序
sort(a.begin(), a.end(), greater<int>()); //从大到小排序
bool cmp(int a, int b) //判断a是否应该排在b前面,1:a排在b前面,0:a排在b后面
{
return a < b;
}
sort(a.begin(), a.end(), cmp); //自定义排序
//排序结构体
struct rec
{
int x, y;
};
bool cmp(rec a, rec b)
{
return a.x > b.x;
}
rec a[5];
sort(a, a + 5, cmp);
----------------------
lower_bound(a.begin(), a.end(), x) //返回指向第一个大于等于x的元素的位置的迭代器(指针)
upper_bound(a.begin(), a.end(), x) //返回指向第一个大于x的元素的位置的迭代器(指针)
帮大忙了!!!
一起加油!