1 vector
1.1介绍
vector为可变长的数组(动态数组)。
注意：在局部区域中（比如局部函数里面）开vector数组，是在堆空间里面开的。
在局部区域开数组是在栈空间开的，而栈空间比较小，如果开了非常长的数组就会发生爆栈。
故局部区域不可以开大长度数组，但是可以开大长度
vector。
- 头文件 ：
#include <vector> - 一位初始化 ：
指定长度和初始值的初始化vector<int> a; //定义了一个名为a的一维数组,数组存储int类型数据 vector<double> b;//定义了一个名为b的一维数组，数组存储double类型数据 vector<node> c;//定义了一个名为c的一维数组，数组存储结构体类型数据，node是结构体类型
初始化数组中的多个元素vector<int> v(n);//定义一个长度为n的数组，初始值默认为0，下标范围[0, n - 1] vector<int> v(n,1);//v[0] 到 v[n - 1]所有的元素初始值均为1 //注意：指定数组长度之后（指定长度后的数组仍可以动态变化）
拷贝初始化vector<int> a{1, 2, 3, 4, 5};//数组a中有五个元素，数组长度就为5vector<int> a(n+1,0); vector<int> b(a);//// 两个数组中的类型必须相同,a和b都是长度为n+1，初始值都为0的数组 vector<int> c = a; // 也是拷贝初始化,c和a是完全一样的数组 - 二维初始化 ：
行不变列可变vector<int> v[5];//定义可变长二维数组 //注意：行不可变（只有5行）, 而列可变,可以在指定行添加元素 //第一维固定长度为5，第二维长度可以改变
行列均可变vector<int> v[5]可以这样理解：长度为5的v数组，数组中存储的是vector<int>数据类型，而该类型就是数组形式，故v为二维数组。其中每个数组元素均为空，因为没有指定长度，所以第二维可变长。可以进行下述操作：v[1].push_back(3); v[2].push_back(7);vector<vector<int>> v;//定义一个行和列均可变的二维数组 //第一维是一个长度可变的vector<vector>数组，可以存放数量可变的vector<int> //第二维是长度可变的vector<int>
行列长度可变的二维数组的初始化应用：可以在v数组里面装入多个数组
vector<vector<int>> v; vector<int> t1{1, 2, 3, 4}; vector<int> t2{2, 3, 4, 5}; v.push_back(t1); v.push_back(t2); v.push_back({3, 4, 5, 6}) // {3, 4, 5, 6}可以作为vector的初始化,相当于一个无名vectorvector<vector<int>> v(n,vector<int>(m,0));
1.2封装函数
知道了如何定义初始化可变数组，下面就需要知道如何添加，删除，修改数据。
c指定为数组名称，含义中会注明算法复杂度。
| 代码 | 含义 |
|---|---|
c.at(x) |
访问指定位置c[x]的元素，提供范围检查,如果超过向量的有效范围，则会引发异常 |
c.front() |
返回第一个数据O(1) |
c.back() |
返回最后一个数据O(1) |
c.push_back(element) |
在尾部加一个数据element,O(1) |
c.pop_back() |
删除最后一个数据O(1) |
c.size() |
返回实际数据个数（unsigned类型）O(1) |
c.clear() |
清除所有元素O(N),N为元素个数 |
c.resize(n,v) |
调整数组大小为n，空间变多赋值为v，空间变少直接删除。若v没有赋值，默认为0 |
c.insert(it,x) |
向任意迭代器it插入一个元素x ，O(N) |
例：c.insert(c.begin() + 3,-1) |
将-1插入c[3]的位置,原本在v[3]处的数据往后移一位 |
c.insert(it,n,x) |
向任意迭代器it插入n个元素x ，O(N) |
c.insert(it,c.begin(),c.end()) |
向任意迭代器it插入可变数组c ，O(N) |
c.swap(c') |
交换数组c,c'的内容 |
c.erase(first,last) |
删除[first,last)的所有元素，O(N) |
c.begin() |
返回首元素的迭代器（通俗来说就是地址）O(1) |
c.end() |
返回最后一个元素的后一个位置的迭代器（地址）O(1) |
c.empty() |
判断是否为空，为空返回真，反之返回假O(1) |
注意：
end()返回的是最后一个元素的后一个位置的地址，不是最后一个元素的地址，所有STL容器均是如此
排序：
使用sort排序要：sort(c.begin(),c.end());
vector<int> a(n + 1);
sort(a.begin() + 1, a.end()); // 对[1, n]区间进行从小到大排序1.3访问
共三种方法：
- 下标法：和普通数组一样
注意：一维数组的下标是从0到v.size()-1，访问之外的数会出现越界错误 - 迭代器法：类似指针一样的访问 ，首先需要声明迭代器变量，和声明指针变量一样，可以根据代码进行理解（附有注释）。
vector<int> v; //定义一个v数组 vector<int>::iterator it = v.begin();//声明一个迭代器指向v的初始位置(v[0]) - 使用auto ：非常简便，但是会访问数组的所有元素（特别注意0位置元素也会访问到）
1.3.1下标访问
直接和普通数组一样进行访问即可。
vector<int> v;
//添加元素
for(int i = 0; i < 5; i++)
v.push_back(i);
//下标访问
for(int i = 0; i < 5; i++)
cout << v[i] << " ";
cout << "\n";1.3.2迭代器访问
类似指针，迭代器就是充当指针的作用。
vector<int> vi{1, 2, 3, 4, 5};
//迭代器访问
vector<int>::iterator it;
// 相当于声明了一个迭代器类型的变量it
// 通俗来说就是声明了一个指针变量- 方式一：
vector<int>::iterator it = v.begin();
for(int i = 0; i < 5; i++)
cout << *(it + i) << " ";
cout << "\n";- 方式二：
vector<int>::iterator it;
for(it = v.begin(); it != v.end();it ++)
cout << *it << " ";
//v.end()指向尾元素地址的下一个地址
// 或者
auto it = v.begin();
while (it != v.end()) {
cout << *it << "\n";
it++;
}1.3.3智能指针
只能遍历完数组，如果要指定的内容进行遍历，需要另选方法。
auto能够自动识别并获取数据类型
// 1. 输入
vector<int> a(n);
for (auto &x: a) {
cin >> x; // 可以进行输入，注意加引用
}
// 2. 输出
vector<int> v;
v.push_back(12);
v.push_back(241);
for(auto val : v) {
cout << val << " "; // 12 241
}
vector注意：
v[i]和*(v.begin() + i)等价，与指针类似。vector和string的STL容器支持*(it + i)的元素访问，其它容器可能也可以支持这种方式访问，但用的不多，可自行尝试。
2 stack
2.1介绍
栈为数据结构的一种，是STL中实现先进后出，后进先出的一种容器。
//头文件需要添加
#include<stack>
//声明
stack<int> s;
stack<string> s;
stack<node> s;//node为结构体类型2.2封装函数
| 代码 | 含义 |
|---|---|
s.push(element) |
将元素element压入栈中，增加元素，O(1) |
s.pop() |
移除栈顶元素O(1) |
s.top() |
返回栈顶元素(但不删除)O(1) |
s.empty() |
检测栈内是否为空，空为真O(1) |
s.size() |
返回栈内元素个数，O(1) |
注意没有 s.clear()! |
不提供该函数 |
2.3栈的遍历
2.3.1栈遍历
栈只能对栈顶元素进行操作，如果想要进行遍历，只能将栈中元素一个个取出来存在数组中
stack<int> st;
for (int i = 0; i < 10; ++i) st.push(i);
while (!st.empty()) {
int tp = st.top(); // 栈顶元素
st.pop();
}2.3.2数组模拟栈进行遍历
通过一个数组对栈进行模拟，一个存放下标的变量top模拟指向栈顶的指针
特点：比STL的stack速度更快，遍历元素方便
一般来说单调栈和单调队列写法均可以使用额外变量
tt或hh来进行模拟
int s[100]; // 栈 从左至右为栈底到栈顶
int tt = -1; // tt 代表栈顶指针,初始栈内无元素，tt为-1
for(int i = 0; i <= 5; ++i) {
//入栈
s[++tt] = i;
}
// 出栈
int top_element = s[tt--];
//入栈操作示意
// 0 1 2 3 4 5
// tt
//出栈后示意
// 0 1 2 3 4
// tt3 queue
3.1介绍
队列为数据结构的一种，是STL中实现先进先出，后进后出的一种容器。
//头文件
#include<queue>
//初始化定义
queue<int> q;3.2封装函数
| 代码 | 含义 |
|---|---|
q.front() |
返回队首元素O(1) |
q.back() |
返回队尾元素O(1) |
q.push(element) |
队尾添加一个元素elementO(1) |
q.size() |
返回队列中元素个数，返回值类型unsigned intO(1) |
q.empty() |
检测队列是否为空，空为真O(1) |
注意没有 q.clear()! |
不提供该函数 |
3.3队列模拟
使用数组q[]模拟队列
hh表示队首元素的下标，初始值为0
tt表示队尾元素的下标，初始值为-1,表示刚开始队列为空
一般来说单调栈和单调队列写法均可以使用额外变量
tt或hh来进行模拟
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int q[N];
int main(){
int hh=0,tt=-1;
// 入队
q[++tt]=1;
q[++tt]=2;
// 将所有元素出队
while(hh<=tt>){
cout << q[hh++] << ' ';
}
return 0;
}4 deque
4.1介绍
首尾都可以插入和删除的队列为双端队列。
//添加头文件
#include<deque>
//初始化定义
deque<int> dq;4.2封装函数
注意双端队列的常数比较大
| 代码 | 含义 |
|---|---|
dq.push_back(element)/push_front(element) |
把element插入队尾后/队首O(1) |
dq.back()/dq.front() |
返回队尾/队首元素O(1) |
dq.pop_back()/dq.pop_front() |
删除队尾/队首元素O(1) |
dq.erase(iterator it) |
删除双端队列中的某一个元素 |
dq.erase(iterator first,iterator last) |
删除双端队列中[first,last)中的元素 |
dq.size() |
返回deque中元素个数O(1) |
dq.empty() |
检测队列是否为空，空为真O(1) |
dq.clear() |
清空deque |
4.3注意点
deque可以进行排序
//从小到大
sort(q.begin(), q.end())
//从大到小排序
sort(q.begin(), q.end(), greater<int>());//deque里面的类型需要是int型,保证deque的数据类型和greater的数据类型一致
sort(q.begin(), q.end(), greater());//高版本C++才可以用5 priority_queue
5.1介绍
优先队列是在正常队列的基础上加了优先级，保证每次的队首元素都是优先级最高的。
可以实现每次从优先队列中取出的元素都是队列中优先级最高的一个。
它的底层是通过堆来实现的。
//头文件
#include<queue>
//初始化定义
priority_queue<int> q;5.2封装函数
| 代码 | 含义 |
|---|---|
q.top() |
返回队首元素O(1) |
q.push(element) |
将element压入队列O(logN) |
q.pop() |
堆顶（队首）元素出队O(logN) |
q.size() |
返回队列中元素个数O(1) |
q.empty() |
检测队列是否为空，空为真O(1) |
注意没有 q.clear()! |
不提供该函数 |
优先队列只能通过top()访问队首元素(优先级最高的元素) |
5.3设置优先级
5.3.1基本数据类型的优先级
priority_queue<int> pq;// 默认大根堆，即每次取出的元素是队列中的最大值
priority_queue<int, vector<int>,less<int> > q2;// 大根堆每次取出的元素是队列中的最大值，同第一行
priority_queue<int, vector<int>,greater<int> > q3// 小根堆，每次取出的元素是队列中的最小值参数解释：
-
第一个参数：就是优先级队列中储存的数据类型
-
第二个参数：
vector<int>是用来承载底层数据结构堆的容器，若优先队列中储存的数据类型是double，就要填vector<double>
总之存的是什么类型的数据，就相应的填写对应类型。同时也要改动第三个参数里面的对应类型。 -
第三个参数：
less<int>表示数字大的优先级高，堆顶为最大的数字
greater<int>表示数字小的优先级高,堆顶为最小的数字
int代表的是数据类型，也要填优先队列中存储的数据类型
下面介绍基础数据类型优先级设置的写法：
1.基础写法(非常实用)：
priority_queue<int> q1; // 默认大根堆, 即每次取出的元素是队列中的最大值
priority_queue<int, vector<int>, less<int> > q2; // 大根堆, 每次取出的元素是队列中的最大值，同第一行
priority_queue<int, vector<int>, greater<int> > q3; // 小根堆, 每次取出的元素是队列中的最小值2.自定义排序(不常见，比较麻烦)：
struct cmp1{
bool operator()(const int x,const int y){
return x<y;
}
};
struct cmp2{
bool operator()(int x, int y){
return x>y;
}
};
priority_queue<int,vector<int>,cmp1> q1;//大根堆
priority_queue<int,vector<int>,cmp2> q2;//小根堆5.3.2高级数据类型(结构体)优先级
即优先队列中存储结构体类型，必须要设置优先级，即结构体的比较运算（因为优先队列的堆中要比较大小，才能将对应最大或者最小元素移到堆顶）。
优先级设置可以定义在结构体内进行小于号重载，也可以定义在结构体外。
//要排序的结构体（存储在优先队列里面的）
struct Point {
int x, y;
};- 版本一：自定义全局比较规则
//定义的比较结构体
//注意：cmp是个结构体
struct cmp {//自定义堆的排序规则
bool operator () (const Point &a,const Point &b) {
return a.x < b.x;
}
};
//初始化定义，
priority_queue<Point, vector<Point>, cmp> q; // x大的在堆顶- 版本二：直接在结构体内定义
因为是在结构体内部自定义的规则，一旦需要比较结构体，自动调用结构体内部重载运算符规则。
比较美观，易查找
结构体内部有两种方式：
方式一：（更清晰）
struct node{
int x,y;
friend bool operator < (const node &a,const node &b){
return a.x < b.x;// 按照x从小到大排序，大根堆
}
};方式二：
struct node{
int x,y;
bool operator < (const node &a) const {
return x < a.x;//按照x从小到大排序，大根堆
}
};优先队列的定义
priority_queue<node> q;注意：优先队列自定义排序规则和sort()函数定义cmp函数很相似，但最后返回的情况是相反的。即相同的符号，最后定义的排列顺序是完全相反的。
所以只需要记住sort的排序规则和优先队列的规则是相反的或者堆顶位于最后一个元素就可以了。
当理解了堆的原理就会发现，堆调整时比较顺序是孩子和父亲节点进行比较，如果是
>，那么孩子节点要大于父亲节点，堆顶自然是最小值。
5.4储存特殊类型的优先级
5.4.1储存pair类型
- 排序规则：
默认先对pair的first进行降序排序，然后再对second降序排序
对first先排序，大的排在前面，如果fiest元素相同，再对second元素排序，大的排在前面。
pair请参考下文
#include<bits/stdc++.h>
using namespace std;
int main() {
priority_queue<pair<int, int> >q;
q.push({7, 8});
q.push({7, 9});
q.push(make_pair(8, 7));
while(!q.empty()) {
cout << q.top().first << " " << q.top().second << "\n";
q.pop();
}
return 0;
}输出结果：
8 7
7 9
7 8
6 map
6.1介绍
映射类似与函数的对应关系，每一个x对应一个y，而map是每一个键对应一个值，会python的朋友学习后就会知道这和python的字典非常类似。
比如说：学习 对应 看书，学习 是键，看书 是值。
学习->看书
玩耍 对应 打游戏，玩耍 是键，打游戏 是值。
玩耍->打游戏
//头文件
#include<map>
//初始化定义
map<string,string> mp;
map<string,int> mp;
map<int,node> mp;//node是结构体map特性：map会按照键的顺序从小到大自动排序，建的类型必须可以比较大小
6.2封装函数
6.2.1封装函数
| 代码 | 含义 |
|---|---|
mp.find(key) |
返回键为key的映射的迭代器O(logN) 注意：用find函数来定位数据出现位置，它返回一个迭代器。当数据存在时，返回数据所在位置的迭代器，数据不存在时，返回mp.end() |
mp.erase(it) |
删除迭代器对应的键和值O(1) |
mp.erase(key) |
删除映射的键和值O(logN) |
mp.erase(first,last) |
删除[first,last)左闭右开迭代器对应的键和值O(last-first) |
mp.size() |
返回映射的对数O(1) |
mp.clear() |
清空map中所有的元素O(N) |
mp.insert() |
插入元素，插入时要构成键值对 |
mp.empty() |
如果map为空，返回true，否则返回false |
mp.begin() |
返回指向map第一个元素的迭代器(地址) |
mp.end() |
返回指向map最后一个元素的下一个地址的迭代器 |
mp.rbegin() |
返回指向最后一个元素的逆向迭代器(地址) |
mp.rend() |
返回指向map第一个元素前面(上一个地址)的逆向迭代器 |
mp.count(key) |
查看元素是否存在，因为map中键是唯一的，所以存在返回1，不存在返回0 |
mp.lower_bound(key) |
返回一个迭代器，指向键值>=key的第一个元素 |
mp.upper_bound(key) |
返回一个迭代器，指向键值>key的第一个元素 |
6.2.2注意点
下面说明部分封装函数的注意点
注意：
- 查找元素是否存在时，可以使用
①mp.find()②mp.count()③mp[key]
但是第三种情况，如果不存在对应的key时，会自动创建一个键值对<key,0>（产生一个额外的键值对空间）
所以为了不增加额外的空间负担和避免对下一次查找造成干扰，最好使用前两种方法- 使用逆向迭代器时，遍历也是
it++，删除元素需要使用到mp.base()函数，一般不用来插入元素
6.2.3迭代器进行正反向遍历
mp.begin()和mp.end()用法：
用于正向遍历map
map<int,int> mp;
mp[1] = 2;
mp[2] = 3;
mp[3] = 4;
for(auto it=mp.begin();it!=mp.end();it++){
cout << it->first << " " << it->second << "\n";
}
/*
结果：
1 2
2 3
3 4
*/ mp.rbegin()和mp.rend()
用于逆向遍历map
map<int,int> mp;
mp[1] = 2;
mp[2] = 3;
mp[3] = 4;
for(auto it=mp.rbegin();it!=mp.rend();it++){
cout << it->first << " " << it->second << "\n";
}
/*
结果：
3 4
2 3
1 2
*/ 6.2.4二分查找
二分查找 lower_bound() upper_bound()
map的二分查找以第一个元素（即键为准），对键进行二分查找
返回值为map迭代器类型
#include<bits/stdc++.h>
using namespace std;
int main() {
map<int, int> m{{1, 2}, {2, 2}, {1, 2}, {8, 2}, {6, 2}};//有序
map<int, int>::iterator it1 = m.lower_bound(2);
cout << it1->first << "\n";//it1->first=2
map<int, int>::iterator it2 = m.upper_bound(2);
cout << it2->first << "\n";//it2->first=6
return 0;
}6.3添加元素
//先声明
map<string,string> mp;- 方式一：
mp["学习"] = "看书"；
mp["玩耍"] = "打游戏"；- 方式二：
mp.insert(make_pair("vegetable"，"蔬菜"))；- 方式三：
mp.insert(pair<string,string>("fruit"，"水果"));- 方式四：
mp.insert({"water","水"});6.4元素访问
- 方式一：迭代器访问
map<string,string>::iterator it; for(it = mp.begin(); it != mp.end(); it++) {
// it是结构体指针访问所以要用 -> 访问
cout << it->first << " " << it->second << "\n";
// 键 值
//*it是结构体变量 访问要用 . 访问
//cout<<(*it).first<<" "<<(*it).second;
}- 方式二：智能指针访问
for(auto ed : mp)
cout << ed.first << ' ' << ed.second << endl;//键，值- 方式三：对指定单个元素访问
map<char,int>::iterator it = mp.find('a');
cout << it.first << ' ' << it.second << endl;6.5与unordered_map的比较
6.5.1封装函数
| 代码 | 含义 |
|---|---|
ump.find(key) |
返回键为key的映射的迭代器O(1) 注意：用find函数来定位数据出现位置，它返回一个迭代器。当数据存在时，返回数据所在位置的迭代器，数据不存在时，返回ump.end() |
ump.erase(it) |
删除迭代器对应的键和值O(1) |
ump.erase(key) |
删除映射的键和值O(N) |
ump.erase(first,last) |
删除[first,last)左闭右开迭代器对应的键和值O(last-first) |
ump.size() |
返回映射的对数O(1) |
ump.clear() |
清空unordered_map中所有的元素O(N) |
ump.insert()/ump.emplace() |
插入元素，插入时要构成键值对 |
ump.empty() |
如果unordered_map为空，返回true，否则返回false |
ump.begin() |
返回指向unordered_map第一个元素的迭代器(地址) |
ump.end() |
返回指向unordered_map最后一个元素的下一个地址的迭代器 |
ump.count(key) |
查看元素是否存在，因为unordered_map中键是唯一的，所以存在返回1，不存在返回0 |
注意：
头文件#include<unordered_map>ump.insert()
- 如果插入的键已经存在于
unordered_map中，insert()不会添加新的键值对，而是保持原有的键值对不变。如果你希望更新已存在键对应的值，你可以使用operator[]或者at()函数。insert()返回一个 std::pair 对象，其 first 成员指向一个指向插入的元素的迭代器，second 成员表示插入是否成功。如果插入成功，second 将为 true；如果插入失败，second 将为 false//方法一： ump.emplace(std::pair<int, std::string>(1, "one")); //方法二： ump.insert(std::unordered_map<int, std::string>::value_type(1, "one")); //方法三： ump.insert({1, "one"});//有花括号ump.emplace()
emplace()接受参数作为键值对的构造函数的参数。它会在 std::unordered_map 中构造新的元素，而不需要进行拷贝或移动操作。如果指定的键已经存在，它将会失败。如果键不存在，则会插入成功。emplace()返回一个 std::pair 对象，与insert()类似，但它的 first 成员指向一个指向新插入元素的迭代器。//方法一： ump.emplace(std::pair<int, std::string>(1, "one")); //方法二： myMap.emplace(std::unordered_map<int, std::string>::value_type(1, "one")); //方法三： myMap.emplace(1, "one");//没有花括号遍历问题
对于unordered_map或者unordered_set容器，其遍历顺序与创建该容器时输入元素的顺序是不一定一致的，遍历是按照哈希表从前往后依次遍历的
6.5.2内部实现原理
map：内部使用红黑树实现，具有自动排序(按键从小到大)功能。
unordered_map：内部使用哈希表实现，内部元素无序杂乱。
6.5.3效率比较
map：
- 优点：内部使用红黑树实现，内部元素具有有序性查询删除等操作复杂度为O(logN)
- 缺点：占用空间，红黑树里每个节点需要保存父子节点和红黑性质等信息，空间占用较大
unordered_map： - 优点：内部使用哈希表实现，查找速度非常快(适用于大量的查询操作)
- 缺点：建立哈希表比较耗时
两者封装函数的使用方法基本一样，差别不大。
注意：
- 使用内部元素越来越多，两种容器的插入删除查询操作的时间都会逐渐变大，效率逐渐变低
- 使用
[]查找元素时，如果元素不存在，两种容器都是创建一个空的元素；如果存在，会正常索引对应的值。所以如果查询过多的不存在的元素值，容器内部会创建大量的空的键值对，后续查询创建删除效率会大大降低。- 查询容器内部元素的最优方法是：先判断存在与否，再索引对应值（适用于这两种容器）
//以map为例 map<int,int> mp; int x = 999999999; if(mp.count(x)) // 此处判断是否存在x这个键 cout << mp[x] << '\n' // 只有存在才会索引对应的值，避免不存在x时多余空元素的创建
另外：
还有一种映射：
multimap
键可以重复出现，即一个键对应多个值
用法于map类似，也是红黑树实现，如要了解，可以自行搜索
7 set
7.1 介绍
set容器的元素不会重复,当插入一个集合中已有的元素时,并不会插入就去,而且set容器里的元素会自动从小到大排序,即: set里面的元素不重复且有序
//头文件
#include<set>
//初始化定义
set<int> s;7.2封装函数
| 代码 | 含义 |
|---|---|
s.begin() |
返回set容器的第一个元素的地址(迭代器)O(1) |
s.end() |
返回set容器的最后一个元素的下一个地址(迭代器)O(1) |
s.rbegin() |
返回逆序迭代器,指向容器元素最后一个位置O(1) |
s.rend() |
返回逆序迭代器,指向容器第一个元素前面的位置O(1) |
s.clear() |
删除set容器中的所有的元素,返回unsigned int类型O(N) |
s.empty() |
判断set容器是否为空O(1) |
s.insert(k) |
插入一个元素k |
s.size() |
返回当前set容器中的元素个数O(1) |
s.erase(iterator) |
删除定位器iterator指向的值 |
s.erase(first,last) |
删除定位器[first,last)之间的值 |
s.erase(key) |
删除键值key的值 |
s.find(element) |
查找set中的某一元素，有则返回该元素对应的迭代器，无则返回结束迭代器 |
s.count(element) |
查找set中的元素出现的个数，由于set中元素唯一，此函数相当于查询element是否出现 |
s.lower_bound(k) |
返回大于等于k的第一个元素的迭代器 |
s.upper_bound(k) |
返回大于k的第一个元素的迭代器 |
7.3访问
- 迭代器访问
for(set<int>::iterator it = s.begin(); it != s.end(); it++)
cout << *it << " ";- 智能指针
for(auto i : s)
cout << i << endl;7.4重载<运算符
- 基础数据类型
方式一:改变set排序规则,set中默认使用less比较器,即从小到大排序(常用)
set<int> s1; // 默认从小到大排序
set<int, greater<int> > s2; // 从大到小排序方式二:重载运算符
//重载 < 运算符
struct cmp {
bool operator () (const int& u, const int& v) const {
// return + 返回条件
return u > v;
}
};
set<int, cmp> s;
for(int i = 1; i <= 10; i++)
s.insert(i);
for(auto i : s)
cout << i << " ";
// 10 9 8 7 6 5 4 3 2 1方式三:初始化时使用匿名函数定义比较规则
set<int, function<bool(int, int)>> s([&](int i, int j){
return i > j; // 从大到小
});
for(int i = 1; i <= 10; i++)
s.insert(i);
for(auto x : s)
cout << x << " ";- 高级数据结构类型(结构体)
直接重载结构体运算符即可,让结构体可以比较
struct Point {
int x, y;
bool operator < (const Point &p) const {
// 按照点的横坐标从小到大排序,如果横坐标相同,纵坐标从小到大
if(x == p.x)
return y < p.y;
return x < p.x;
}
};
set<Point> s;
for(int i = 1; i <= 5; i++) {
int x, y;
cin >> x >> y;
s.insert({x, y});
}
/* 输入
5 4
5 2
3 7
3 5
4 8
*/
for(auto i : s)
cout << i.x << " " << i.y << "\n";
/* 输出
3 5
3 7
4 8
5 2
5 4
*/7.5其它set
multiset:元素可以重复,且元素有序(元素相等时,先插入的排在前面)
unordered_set:元素无序且只能出现一次
unordered_multiset:元素无序可以多次出现
8 pair
8.1介绍
pair只含有两个元素,可以看作是只有两个元素的结构体
应用:
- 替代二元结构体
- 支持比较操作符，可以使用
==、!=、<、<=、>、>=来比较两个pair对象的大小关系。按字典序进行比较，先比较第一个元素，如果相等再比较第二个元素。(可以应用于优先队列,set等) - 作为
map键值对进行插入(代码如下)
map<string,int>mp;
mp.insert(pair<string,int>("xingmaqi",1));
// mp.insert(make_pair("xingmaqi", 1));
// mp.insert({"xingmaqi", 1});//头文件
#include<utility>
//1.初始化定义
pair<string,int> p("wangyaqi",1);//带初始值的
pair<string,int> p;//不带初始值的
//2.赋值
p = {"wang", 18};
p = make_pair("wang", 18);
p = pair<string, int>("wang", 18);8.2访问
//定义结构体数组
pair<int,int> p[20];
for(int i = 0; i < 20; i++) {
//和结构体类似，first代表第一个元素，second代表第二个元素
cout << p[i].first << " " << p[i].second;
}9 string
9.1介绍
string是一个字符串类,和char型字符串类似
可以把string理解为一个字符串类型,像int一样可以定义
9.2定义及初始化
//头文件
#include<string>
//1.
string str1; //生成空字符串
//2.
string str2("123456789"); //生成"1234456789"的复制品
//3.
string str3("12345", 0, 3);//结果为"123" ，从0位置开始，长度为3
//4.
string str4("123456", 5); //结果为"12345" ，长度为5
//5.
string str5(5, '2'); //结果为"22222" ,构造5个字符'2'连接而成的字符串
//6.
string str6(str2, 2); //结果为"3456789"，截取第三个元素（2对应第三位）到最后
简单使用
- 访问单个字符:
#include<iostream>
#include<string>
using namespace std;
int main() {
string s = "king mc ws!!!";
for(int i = 0; i < s.size(); i++)
cout << s[i] << " ";
return 0;
}string数组使用:
#include<iostream>
#include<string>
using namespace std;
int main() {
string s[10];
for(int i = 1; i < 10; i++) {
s[i] = "loading... " ;
cout << s[i] << i << "\n";
}
return 0;
}结果:
loading... 1
loading... 2
loading... 3
loading... 4
loading... 5
loading... 6
loading... 7
loading... 8
loading... 99.3string特性
- 支持比较运算符
string字符串支持常见的比较操作符>,>=,<,<=,==,!=，支持string与C-string的比较（如str<"hello"）。
在使用>,>=,<,<=这些操作符的时候是根据“当前字符特性”将字符按字典顺序进行逐一得 比较。字典排序靠前的字符小， 比较的顺序是从前向后比较，遇到不相等的字符就按这个位置上的两个字符的比较结果确定两个字符串的大小（前面减后面）。
同时，string ("aaaa") <string("aaaaa")。
- 支持
+运算符,代表拼接字符串
string字符串可以拼接,通过"+"运算符进行拼接
string s1 = "123";
string s2 = "456";
string s = s1 + s2;
cout << s; //1234569.4读入详解
读入字符串,遇空格,回车结束
string s;
cin >> s;读入一行字符串(包含空格),遇回车结束
string s;
getline(cin,s);注意:getline(cin,s)会获取前一个输入的换行符,需要在前面添加读取换行符的语句.如:getchar()或cin.get()
错误读取:
int n;
string s;
cin >> n;
getline(cin, s); //此时读取相当于读取了前一个回车字符正确读取
int n;
string s;
cin >> n;
getchar(); //cin.get()
getline(cin, s);//可正确读入下一行的输入
cin与getline()混用
cin输入完后,回车,cin遇到回车符结束输入,但回车还在输入流中,cin并不会清除,导致getline()读取回车,结束读入.
需要在cin后面加上cin.ignore();主动删除输入流中的换行符(不常用)
cin和cout解锁
代码(写在main函数开头):
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);为什么要进行
cin和cout的解锁，原因是：
在一些题目中，读入的数据量很大，往往超过了1e5（105）的数据量,而cin和cout的读入输出的速度很慢（是因为cin和cout为了兼容C语言的读入输出在性能上做了妥协），远不如scanf和printf的速度，具体原因可以搜索相关的博客进行了解。
所以对cin和cout进行解锁使cin和cout的速度几乎接近scanf和printf，避免输入输出超时。
注意: cin,cout解锁使用时，不能与 scanf,getchar, printf,cin.getline()混用，一定要注意，会出错。
string与C语言字符串（C-string）的区别:
- string
是C++的一个类,专门实现字符串的相关操作,具有丰富的操作方法,数据类型为string,字符串的结尾是由类内部管理的，并且不需要显示地添加空字符\0。- C-string
C语言中的字符串，用char数组实现，类型为const char *,需要程序员手动确保字符串结尾以\0结束
一般来说string向char数组转换会出现一些问题，所以为了能够实现转换，string有一个方法c_str()实现string向char数组的转换。
string s = "king ws qs";
const char* s2 = s.c_str(); // 获取指向 C 字符串的指针(不可s2进行修改)
char* s2 = const_cast<char*>(s.data()); // 获取指向字符串的可修改的字符数组**注意:**这两种方法都是将字符串s的地址赋值给s2,若使用方法二对s2进行修改,对原本的字符串s和其它引用该地址的变量也会造成影响.
9.5函数方法
- 获取字符串长度
| 代码 | 含义 |
|---|---|
s.size()和s.length() |
返回string对象的字符个数,他们执行效果相同 |
s.max_size() |
返回string对象最多包含的字符数，超出会抛出length_error异常 |
s.capacity() |
重新分配内存之前，string对象能包含的最大字符数 |
- 插入
