STL容器：
一、#include
英文翻译：vector ：向量
vector是变长数组(动态变化)，支持随机访问，不支持在任意位置O(1)插入。为了保证效率，元素的增删一般应该在末尾进行。
声明
#include 头文件
vectora; 相当于一个长度动态变化的int数组
vectorb[233]; 相当于第一维长233，第二位长度动态变化的int数组
struct rec{…};
vectorc; 自定义的结构体类型也可以保存在vector中
size/empty
size函数返回vector的实际长度（包含的元素个数），empty函数返回一个bool类型，表明vector是否为空。二者的时间复杂度都是O(1)。
所有的STL容器都支持这两个方法，含义也相同。
clear
clear函数把vector清空。
front/back
front函数返回vector的第一个元素，等价于*a.begin() 和 a[0]。
back函数返回vector的最后一个元素，等价于*==a.end() 和 a[a.size() – 1]。
push_back() 和pop_back()
a.push_back(x) 把元素x插入到vector a的尾部。
b.pop_back()删除vector a的最后一个元素。
#include<iostream> #include<vector> using namespace std; int main() { vector<int> a; //相当于一个长度动态变化的int数组 vector<int> b[233]; //相当于第一维长233，第二位长度动态变化的int数组 a.size(); //函数返回vector的实际长度（包含的元素个数） a.empty(); //函数返回一个bool类型，表明vector是否为空。 a.clear(); //clear函数把vector清空 struct rec{ int a; double b; }; vector<rec> c; //自定义的结构体类型也可以保存在vector中 vector<int> d({1,2,3}); cout<<d.front()<<" "<<d[0]<<" "<<endl; cout<<d.back()<<" "<<d[d.size()-1]<<" "<<endl; d.push_back(4); for(auto x:d)cout<<x<<" ";//把元素x插入到vector a的尾部。 cout<<endl; d.pop_back(); for(auto x:d)cout<<x<<" ";//删除vector a的最后一个元素。 cout<<endl; return 0; }
二、#include
英文翻译：queue ：队列
头文件queue主要包括循环队列(先进先出)
queue和优先队列priority_queue两个容器。
声明
queueq;//队列
structrec{…}; queue q; //结构体rec中必须定义小于号
priority_queueq; // 大根堆
priority_queue, greater q; //小根堆
priority_queue>q; //小根堆
循环队列 queue
push从队尾插入
pop从队头弹出
front返回队头元素
back返回队尾元素
优先队列 priority_queue（堆）
**默认为大根堆
push把元素插入堆
pop删除堆顶元素
top 查询堆顶元素（最大值）
#include<iostream> #include<queue> using namespace std; int main() { queue<int> q;//队列 queue<double> q1; struct rec{ int a,b; bool operator< (const rec& t)const { return a<t.a; } }; queue<rec> q2; //结构体rec中必须定义小于号 priority_queue<int> q3; // 大根堆 priority_queue<int, vector<int>, greater<int>>q4; // 小根堆 priority_queue<pair<int, int>>q5; queue<int> s;//队列 s.push(1); //从队尾插入 s.pop(); //从队头弹出 s.front(); //返回队头元素 s.back(); //返回队尾元素 priority_queue<int> s1; s1.push(1); //把元素插入堆 s1.pop(); //删除堆顶元素 s1.top(); //查询堆顶元素（最大值） s1.push(-x); //按小根堆插入 return 0; }
三、#include
英文翻译：stack ：堆栈
头文件stack包含栈。声明和前面的容器类似。
push 向栈顶插入
pop 弹出栈顶元素
#include<iostream> #include<stack> using namespace std; int main() { stack<int>stk; stk.push(1);//向栈顶插入元素 stk.pop(); //弹出栈顶元素 stk.top(); //查询栈顶元素（最大值） return 0; }
四、#include
双端队列deque是一个支持在两端高效插入或删除元素的连续线性存储空间。它就像是vector和queue的结合。与vector相比，deque在头部增删元素仅需要O(1)的时间；与queue相比，deque像数组一样支持随机访问。
[] 随机访问
front/back 队头/队尾元素
push_back 从队尾入队
push_front 从队头入队
pop_back 从队尾出队
pop_front 从队头出队
clear 清空队列
#include<iostream> #include<deque> using namespace std; int main() { deque<int>a; a[0]; //随机访问 a.front(); a.back();//队头/队尾元素 a.push_back(1); //从队尾入队 a.push_front(2); //从队头入队 a.pop_back(); //从队尾出队 a.pop_front(); //从队头出队 a.clear(); //清空队列 return 0; }
五、#include
英文翻译： set ：集
头文件set主要包括set和multiset两个容器，分别是“有序集合”和“有序多重集合”，即前者的元素不能重复，而后者可以包含若干个相等的元素。set和multiset的内部实现是一棵红黑树，它们支持的函数基本相同。
声明
set s;
struct rec{…}; set s; //结构体rec中必须定义小于号
multiset s;
size/empty/clear
与vector类似
insert
s.insert(x)把一个元素x插入到集合s中，时间复杂度为O(logn)。
在set中，若元素已存在，则不会重复插入该元素，对集合的状态无影响。
find
s.find(x) 在集合s中查找等于x的元素，并返回指向该元素的迭代器。
若不存在，则返回s.end()。时间复杂度为O(logn)。
lower_bound/upper_bound
这两个函数的用法与find类似，但查找的条件略有不同，时间复杂度为 O(logn)。
s.lower_bound(x) 查找大于等于x的元素中最小的一个，并返回指向该元素的迭代器。
s.upper_bound(x) 查找大于x的元素中最小的一个，并返回指向该元素的迭代器。
count
s.count(x)返回集合s中等于x的元素个数，时间复杂度为 O(k +logn)，其中k为元素x的个数。
#include<iostream> #include<set> using namespace std; int main() { set<int>a;//元素不能重复 multiset<int>b;//元素可以重复 int x; a.insert(x);//把一个元素x插入到集合x中 if(a.find(x)==a.end())//判断x是否存在于x中 a.lower_bound(x);//查找大于等于x的元素中最小的一个 a.upper_bound(x);//查找大于x的元素中最小的一个 b.count(x);//返回集合b中等于x的元素个数 return 0; }
六、#include
#include
英文翻译： map：地图
map容器是一个键值对key-value的映射，其内部实现是一棵以key为关键码的红黑树。Map的key和value可以是任意类型，其中key必须定义小于号运算符。
声明
map name;
例如：
map vis;
map hash;
map, vector> test;
size/empty/clear/begin/end
均与set类似。
Insert/erase
与set类似，但其参数均是pair。
find
h.find(x)在变量名为h的map中查找key为x的二元组。
[]操作符
h[key]返回key映射的value的引用，时间复杂度为O(logn)。
[]操作符是map最吸引人的地方。我们可以很方便地通过h[key]来得到key对应的value，还可以对h[key]进行赋值操作，改变key对应的value。
#include<iostream> #include<map> #include<vector> using namespace std; int main() { //相当于数组 map<int,int>a; a[10000]=8; cout<<a[10000]<<endl; //和数组的区别(可以随便定义数组类型，包括下标) map<string,int>b; b["zyq"]=9; cout<<b["zyq"]<<endl; map<string,vector<int>>c; c["zyq"]=vector<int>({1,2,3,4,5,6}); cout<<c["zyq"][2]<<endl; c.insert({"b",{10}}); cout<<(c.find("b")==c.end())<<endl;//输出0为存在，输出1为不存在 return 0; }
map和unordered_map的区别
一.头文件不同，分别是：
#include
#include
二.其实现不同
map：其实现是使用了红黑树
unordered_map:其实现使用的是哈希表
三.特点
map:
1.元素有序，并且具有自动排序的功能（因为红黑树具有自动排序的功能）
2.元素按照二叉搜索树存储的，也就是说，其左子树上所有节点的键值都小于根节点的键值，右子树所有节点的键值都大于根节点的键值，使用中序遍历可将键值按照从小到大遍历出来
3.空间占用率高，因为map内部实现了红黑树，虽然提高了运行效率，但是因为每一个节点都需要额外保存父节点、孩子节点和红/黑性质，使得每一个节点都占用大量的空间
4.适用情况:对顺序有要求的情况下，如排序等
unordered_map:
- 元素无序。
- 查找速度非常的快。
- 哈希表的建立比较耗费时间
- 适用情况:对于查找问题
- 对于unordered_map或者unordered_set容器，其遍历顺序与创建该容器时输入元素的顺序是不一定一致的，遍历是按照哈希表从前往后依次遍历的
七、#include
1.size/empty/clear/begin/end
string均可以用
2.substr();
返回字符串长度
#include<bits/stdc++.h> using namespace std; int main() { string a="abnd"; a+="hdush";//a="abndhdush" a+='z';//a="abndhdushz" //从第1个(起始点在0)位置开始，输出3个字符 cout<<a.substr(1,3);//bnd cout<<endl; //输出从4开始的整个子串 cout<<a.substr(4);//hdushz return 0; }
八、位运算
& 与
| 或
~ 非
^ 异或
>> 右移
<< 左移
常用操作：
- 求x的第k位数字 x >> k & 1
- lowbit(x) = x & -x，返回x的最后一位1
九、总结：
vector, 变长数组，倍增的思想 size() 返回元素个数 empty() 返回是否为空 clear() 清空 front()/back() push_back()/pop_back() begin()/end() [] 支持比较运算，按字典序 pair<int, int> first, 第一个元素 second, 第二个元素 支持比较运算，以first为第一关键字，以second为第二关键字（字典序） string，字符串 size()/length() 返回字符串长度 empty() clear() substr(起始下标，(子串长度)) 返回子串 c_str() 返回字符串所在字符数组的起始地址 queue, 队列 size() empty() push() 向队尾插入一个元素 front() 返回队头元素 back() 返回队尾元素 pop() 弹出队头元素 priority_queue, 优先队列，默认是大根堆 size() empty() push() 插入一个元素 top() 返回堆顶元素 pop() 弹出堆顶元素 定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q; 也可以使用push(-x) 变成一个小根堆 stack, 栈 size() empty() push() 向栈顶插入一个元素 top() 返回栈顶元素 pop() 弹出栈顶元素 deque, 双端队列 size() empty() clear() front()/back() push_back()/pop_back() push_front()/pop_front() begin()/end() [] set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列 size() empty() clear() begin()/end() ++, -- 返回前驱和后继，时间复杂度 O(logn) set/multiset insert() 插入一个数 find() 查找一个数 count() 返回某一个数的个数 erase() (1) 输入是一个数x，删除所有x O(k + logn) (2) 输入一个迭代器，删除这个迭代器 lower_bound()/upper_bound() lower_bound(x) 返回大于等于x的最小的数的迭代器 upper_bound(x) 返回大于x的最小的数的迭代器 map/multimap insert() 插入的数是一个pair erase() 输入的参数是pair或者迭代器 find() [] 注意multimap不支持此操作。 时间复杂度是 O(logn) lower_bound()/upper_bound() unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表 和上面类似，增删改查的时间复杂度是 O(1) 不支持 lower_bound()/upper_bound()， 迭代器的++，-- bitset, 圧位 bitset<10000> s; ~, &, |, ^ >>, << ==, != [] count() 返回有多少个1 any() 判断是否至少有一个1 none() 判断是否全为0 set() 把所有位置成1 set(k, v) 将第k位变成v reset() 把所有位变成0 flip() 等价于~ flip(k) 把第k位取反
常用库函数
C++帮我们实现好了很多有用的函数，我们要避免重复造轮子
#include算法库
reverse 翻转（十星重要度）
翻转一个vector：
reverse(a.begin(), a.end());
翻转一个数组，元素存放在下标1~n：
reverse(a + 1, a + 1 + n);
cout<<"*****vector翻转*******"<<endl; vector<int> a({1,2,3,4,5}); reverse(a.begin(),a.end()); for(int x:a)cout<<x<<" "; cout<<endl; cout<<"*****数组翻转**********"<<endl; int b[]={1,2,3,4,5}; reverse(b,b+5); for(int y:b)cout<<y<<" "; cout<<endl;
unique 去重
返回去重之后的尾迭代器（或指针），仍然为前闭后开，即这个迭代器是去重之后末尾元素的下一个位置。该函数常用于离散化，利用迭代器（或指针）的减法，可计算出去重后的元素个数。
把一个vector去重：
int m = unique(a.begin(), a.end()) – a.begin();
把一个数组去重，元素存放在下标1~n：
int m = unique(a + 1, a + 1 + n) – (a + 1);
cout<<"*****vector去重**********"<<endl; vector<int> a1({1,1,2,2,3,3,4,5,8,8,8,8,8,8}); int n=unique(a1.begin(),a1.end())-a1.begin(); cout<<"去掉重复数剩余："<<n<<endl; for(int i=0;i<n;i++)cout<<a1[i]<<" "; cout<<endl; cout<<"*****数组去重**********"<<endl; int b1[]={1,1,2,2,3,3,4,5,8,8,8,8,8,8}; int m=unique(b1,b1+14)-b1; cout<<"去掉重复数剩余："<<m<<endl; for(int i=0;i<m;i++)cout<<b1[i]<<" "; cout<<endl;
random_shuffle 随机打乱
用法与reverse相同
cout<<"*****生成随机数*********"<<endl; vector<int> c({1,1,2,8,5,8}); srand((time(0)));//需要生成随机数 random_shuffle(c.begin(),c.end()); for(int q:c)cout<<q<<" "; cout<<endl;
sort（十星重要度）
对两个迭代器（或指针）指定的部分进行快速排序。可以在第三个参数传入定义大小比较的函数，或者重载“小于号”运算符。
把一个int数组（元素存放在下标1~n）从大到小排序，传入比较函数：
int a[MAX_SIZE]; bool cmp(int a, int b) {return a > b; } sort(a + 1, a + 1 + n, cmp);
把自定义的结构体vector排序，重载“小于号”运算符：
方法一：
struct rec{ int id, x, y; } vector a; bool operator <(const rec &a, const rec &b) { return a.x < b.x ||a.x == b.x && a.y < b.y; } sort(a.begin(), a.end());
方法二：（推荐）
struct rep { int x,y; }r[5]; //结构体的比较函数 bool cmp1(rep a,rep b) //自己决定如何排序 { return a.x }
//定义的结构体 struct rep { int x,y; }r[5]; //结构体的比较函数 bool cmp1(rep a,rep b) //自己决定如何排序 { return a.x<a.y;//这里决定sort排序是升序还是降序 } //数组的比较函数 bool cmp(int a,int b) //自己决定如何排序 { return a>b;//这里决定sort排序是升序还是降序 }
cout<<"*****随机数排序*********"<<endl; sort(c.begin(),c.end(),cmp); for(int q1:c)cout<<q1<<" "; cout<<endl; cout<<"*****结构体排序*********"<<endl; for(int i=0;i<5;i++) { r[i].x=-i; r[i].y=i; } cout<<"排序前结构体"<<endl; for(int i=0;i<5;i++)printf("(%d,%d) ",r[i].x,r[i].y); cout<<endl; sort(r,r+5,cmp1); cout<<"排序后结构体"<<endl; for(int i=0;i<5;i++)printf("(%d,%d) ",r[i].x,r[i].y);
lower_bound/upper_bound 二分
lower_bound 的第三个参数传入一个元素x，在两个迭代器（指针）指定的部分上执行二分查找，返回指向第一个大于等于x的元素的位置的迭代器（指针）。
upper_bound 的用法和lower_bound大致相同，唯一的区别是查找第一个大于x的元素。当然，两个迭代器（指针）指定的部分应该是提前排好序的。
在有序int数组（元素存放在下标1~n）中查找大于等于x的最小整数的下标：
int I = lower_bound(a + 1, a + 1 + n,. x) – a;
在有序vector 中查找小于等于x的最大整数（假设一定存在）：
int y = *--upper_bound(a.begin(), a.end(), x);
cout<<"********二分查找*********"<<endl; cout<<"大于等于x的最小整数:"<<endl; int x[]={1,2,3,4,5,6,9,10}; int* p=lower_bound(x,x+7,6); cout<<"查找到的值为："<<*p<<endl; int l=*p=lower_bound(x,x+7,10)-x; cout<<"大于等于x的最小整数下标:"<<l<<endl<<endl; cout<<"小于等于x的最大整数"<<endl; int* q=upper_bound(x,x+7,4); cout<<"查找到的值为："<<*q<<endl; int t=*p=upper_bound(x,x+7,4)-x; cout<<"小于等于x的最大整数下标:"<<t<<endl;
全部代码段
#include<iostream> #include<algorithm> #include<vector> #include<ctime> #include<cstdio> using namespace std; struct rep { int x,y; }r[5]; //结构体的比较函数 bool cmp1(rep a,rep b) //自己决定如何排序 { return a.x<a.y;//这里决定sort排序是升序还是降序 } //数组的比较函数 bool cmp(int a,int b) //自己决定如何排序 { return a>b;//这里决定sort排序是升序还是降序 } int main() { cout<<"*****vector翻转*******"<<endl; vector<int> a({1,2,3,4,5}); reverse(a.begin(),a.end()); for(int x:a)cout<<x<<" "; cout<<endl; cout<<"*****数组翻转**********"<<endl; int b[]={1,2,3,4,5}; reverse(b,b+5); for(int y:b)cout<<y<<" "; cout<<endl; cout<<"*****vector去重**********"<<endl; vector<int> a1({1,1,2,2,3,3,4,5,8,8,8,8,8,8}); int n=unique(a1.begin(),a1.end())-a1.begin(); cout<<"去掉重复数剩余："<<n<<endl; for(int i=0;i<n;i++)cout<<a1[i]<<" "; cout<<endl; cout<<"*****数组去重**********"<<endl; int b1[]={1,1,2,2,3,3,4,5,8,8,8,8,8,8}; int m=unique(b1,b1+14)-b1; cout<<"去掉重复数剩余："<<m<<endl; for(int i=0;i<m;i++)cout<<b1[i]<<" "; cout<<endl; cout<<"*****生成随机数*********"<<endl; vector<int> c({1,1,2,8,5,8}); srand((time(0)));//需要生成随机数 random_shuffle(c.begin(),c.end()); for(int q:c)cout<<q<<" "; cout<<endl; cout<<"*****随机数排序*********"<<endl; sort(c.begin(),c.end(),cmp); for(int q1:c)cout<<q1<<" "; cout<<endl; cout<<"*****结构体排序*********"<<endl; for(int i=0;i<5;i++) { r[i].x=-i; r[i].y=i; } cout<<"排序前结构体"<<endl; for(int i=0;i<5;i++)printf("(%d,%d) ",r[i].x,r[i].y); cout<<endl; sort(r,r+5,cmp1); cout<<"排序后结构体"<<endl; for(int i=0;i<5;i++)printf("(%d,%d) ",r[i].x,r[i].y); cout<<endl; cout<<"********二分查找*********"<<endl; cout<<"大于等于x的最小整数:"<<endl; int x[]={1,2,3,4,5,6,9,10}; int* p=lower_bound(x,x+7,6); cout<<"查找到的值为："<<*p<<endl; int l=*p=lower_bound(x,x+7,10)-x; cout<<"大于等于x的最小整数下标:"<<l<<endl<<endl; cout<<"小于等于x的最大整数"<<endl; int* q=upper_bound(x,x+7,4); cout<<"查找到的值为："<<*q<<endl; int t=*p=upper_bound(x,x+7,4)-x; cout<<"小于等于x的最大整数下标:"<<t<<endl; return 0; }
