C++STD库
1.vector
// vector 的常用方式
//vector 与数组的区别是,vector的存储量是随开随用的
#include <bits/stdc++.h>
using namespace std;
int main()
{
vector<int> vec;//定义一个vertor(类似于数组)
int n;
int x;
cin >> n;
for(int i = 0; i < n; i++)
{
cin >> x;
vec.push_back(x);
}//将x存入vertor里
vec.pop_back();//可以删除最后一个元素.
std::vector<int>::iterator it;//定义一个迭代器(指针)it
//auto it = vec.begin();//也可以使用auto自动识别迭代器
//本质是指针
for(auto it = vec.begin();it != vec.end();it++)//it++,是指针指向数组(vec)的下一个数(it--反之)和数组的++或者--有区别
{
printf("%d ",*it);
}//自动识别输出,逆向输出使用rbegin(),rend()即可
for(it = vec.begin(); it != vec.end(); it++)
{
printf("%d ",*it);
}//使用迭代器输出
for(int i = 0;i < vec.size();i++)//vec.size()是返回vector里元素的个数
{
printf("%d ",vec[i]);
}//使用数组输出;
for(int i = vec.size() - 1;i >= 0;i--)
{
printf("%d ",vec[i])
}//数组逆向输出
for(auto i : vec)//auto 是自动排判别
{
printf("%d ",i);
}//使用auto取vec里的值,然后输出
/其他常用方法
//排序
//sort(vec.begin(),vec.end());//对vertor正向排序
//reverse(vec.begin(),vec.end());//sort后可reverse逆向排序
//清空
vec.clear();//清空vector里的元素(仅适应于一维)
vector<int> vec[100];//类似于二维数组int vec[100][100];
for(int i = 1;i < n;i++)
{
vec[i].clear();
}//二维清空
//删除
for(auto it = vec.begin();it != vec.end();)
{
if(*it == 4)
it = vec.erase(it);//删除指定元素
else
it++;
}//使用指针(迭代器)删除
//注释 : 因为我们要删除本质是指向的数,使用删除后要将当前指向的指针重新指向下一个数
//保证其连续性
for(auto i: vec)
{
printf("%d ",i);
}
//其他不常用方法
vec.front();//返回他的第一个数
vec.back();//返回最后一个数
return 0;
}
2.string(字符串类型)
#include <bits/stdc++.h>
using namespace std;
int main()
{
string a,b;//定义一个string类型
cin >> a >> b;
a += b;//字符串类型拼接 a = "aaa" + b = "bbb";
//查找
s.find('b');//找出某个字符串第一次出现的位置
//排序
//sort(a.begin() , a.end());
//添加控制
string a="";
a.push_back('b');//在字符串最后插入一个字符
a.push_back('1');
a.push_back('2');
a.push_back('3');
cout<<a[0]<<' '<<a[1]<<' '<<a[2];//输出1 2 3
//删除控制
a.pop_back();//删除字符串最后一个元素
b.pop_back();
cout << a <<"\n"<< b << endl;
//找东西(定位)
cout << a.find('b') << endl;//找出某个字符串第一次出现的位置并返回其下标
cout << b.find('b') << endl;
//截取字符串
//a = "abcdddddd";
//a.substr(begin,end);//开始的数组下标到结束的数组下标
a.substr(0,3);//abc
a.substr(3,3);//ddd
a.substr(3,10);//dddddd => a.substr(3)
//注意 : 结束的数组下标即使超过字符串最大容量其返回值也不会数组越界,会截取可截取的所有元素
return 0;
}
3.pair(双胞胎类型)
#include <bits/stdc++.h>
using namespace std;
int main()
{
//定义双胞胎类型
pair<int,int>pll;
pair<int,int>a,b;
typedef pair<int ,int>pll;
pll a,b;
//输入方式
cin >> a.first >> b.second;
cin >> pll;
//其他输入方式
int x;int y;
cin >> x >> y;
pll = {x,y};
return 0;
}
4.栈
//特点:先放后出
#include <bits/stdc++.h>
using namespace std;
int main()
{
stack <int> sta;//定义
int n,t;
cin >> n;
for(int i = 0;i < n;i++)
{
cin >> t;
std.push(t);//入栈
}
//其他用法
sta.size();//返回元素个数
sta.empty();//判断空栈
sta.top();//弹出最顶部
sta.pop();//删除最顶部
//删除全部
while(sta.size())
{
cout << sta.top();
sta.pop();
}
return 0;
}
5.队列
//特点:先进先出
#include <bits/stdc++.h>
using namespace std;
int main()
{
queue<int> q;//定义
int n,t;
cin >> n;
for(int i = 0;i < n;i++)
{
cin >> t;
q.push(t);
}
//其他操作
while(q.size())
{
int x = q.front();//返回当前队列头
q.pop();//必须删除才能取下一个
cout << x << endl;
q.bcak();//返回最后一个元素
}//输出
//数组模拟
int n,t;
int tt = 0;//队头(数组最右端)
int hh = 0;//队尾(数组最左端)
int z[1001];
for(int i = 0;i < n;i++)
{
cin >> t;
z[tt++] = t;
}
while(hh < tt)
{
int y = z[hh++];
cout << y << endl;
}//输出
return 0;
}
6.双端队列
#include <bits/stdc++.h>
using namespace std;
int main()
{
deque<int> q;
//放置
q.push_back(t);//放置尾部
q.push_front(t);//放置头部
//删除
q.pop_back();//删尾
q.pop_front;//删尾
//输出
while(q.size())
{
int x = q.front();
int y = q.back();
q.pop_back();
q.pop_front();
cout << x;
}
return 0;
}
7.堆
// 特点 : 1.自动排序内部数,小到大或大到小
// 2.二叉数结构
// 3.nlogn(排序)
// 4.logn(查找)
#include <bits/stdc++.h>
using namespace std;
int main()
{
//定义
priority_queue<int, vector<int>, greater<int>> q1; //greater是小根堆,用vector装载内部元素(小到大排序)
priority_queue<int, vector<int>, less<int>> q2; //less是大根堆(大到小排序)
q1.push(1);
q2.push(2);
//输入
int n,t;
cin >> n;
for(int i = 0;i < n;i++)
{
cin >> t;
q.push(t);
}
//输出
while(q.size())
{
int x = q.top();
q.pop();
cout << x;
}
//其他用法
q.top();//取最顶部(最小值)
q.pop();//删除最顶部
return 0;
}
8.set
// 特点 : 1.红黑树结构,可以输出后自动排序去重
#include <bits/stdc++.h>
using namespace std;
int main()
{
set<int> se;
int n,t;
cin >> n;
for(int i = 0;i < n;i++)
{
cin >> t;
se.insert(t);//存入
}
//指针输出
std::set<int>::iterator it;
for(it = begin();it != end();it++)
{
cout << *it;
}//输出后自动排序且去重复
//auto输出
for(auto j : se)
{
cout << j;
}//输出后自动排序且去重复
//查找
auto j = se.find(3);//假设查找3
cout << *j;//如果存在则输出其指向的指针,不存在则报错(返回边界end())
if(j != end())
cout << "找到了";
//二分查找
auto i = se.lower_bound(3);//二分查找函数
i++;
i--;
//其返回值为指针,i与i左右相邻的数
cout << *i;
//其他用法
se.clear();//清空
//指针删除
auto i = se.find(3);//先找到其,返回其指针
i++;//指针向后遍历(删去3后面的数)
i--;//指针向前遍历(删去3前面的数)
if(i != se.end())
i = se.erase(i);
for(auto i : se)
cout << i << ' ';
//若没有要找的3,则只排序去重不删除。如果i++或者i--操作后没有要找的3,则删除数组对应的下标
return 0;
}
9.map
// 特点 : 1.红黑树结构,可以输出后自动排序去重
// 2.map里的操作只针对于关键字
#include <bits/stdc++.h>
using namespace std;
int main()
{
//关键字 关键值
map<int,int> mp;
//输入
mp.insert({ 1,2 });//插入一个 1 关键字,并给这个关键字的关键值赋值 2
mp.insert({ 1,1 });//因为 1 关键字已经存在,所以把关键值修改成 1
int n,t,s;
cin >> n >> t;
for(int i = 0;i < n;i++)
{
cin >> t >> s;
mp[t] = s;
mp[t]++;
}
//输出
for(auto j : mp)
cout << j.first << j.second;
for (auto it = mp.begin(); it != mp.end(); it++)
cout << (*it).first << ' ' << (*it).second << endl;
for (auto it = se.rbegin(); it != se.rend(); it++)//反向遍历
cout << *it << endl;
//删除
mp.erase(3);//删除某个指定的关键字
//如果是遍历删除 map 内特定的第 x 个数,跟 vector 删除一样要注意指针衔接
int k = 0;
for (auto it = mp.begin(); it != mp.end();k++)
{
if (k == x)
it = mp.erase(it);
else
it++;
}
//查找
mp.find();//找到某个数,返回指针
mp.cout();//计数某个数出现的次数,返回数值
auto j = mp.find(3);//查找 3 关键字在 map 内的下标
//如果不存在则 j == mp.end()
if (j != mp.end())
cout << (*j).first;//返回其关键字的指针
//二分查找
auto g = mp.lower_bound(3);//查找 map 内第一个大于等于 3 的数的下标
//如果不存在则 g == mp.end()
if (g != mp.end())
cout << (*g).first;
//其他
mp.clear();//清空
mp.size();
return 0;
}
lower_bound(二分函数)
//特点 : 1.找大于等于某数的第一个数,查找的数组必须有序
// 2.并返回其数组下标
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n = 7;//7个数
int a[] = { 2,4,6,7,9,12,111 };//范围:0 ~ 6
int t = lower_bound(a, a + n, 8) - a;//数组中大于等于8的第一个数
printf("%d",t);//返回其下标
if (t != n)//找不到会返回边界,边界是 7
cout << a[t] << endl;
int b[] = { 0,2,4,6,7,9,12,111 };//范围:1 ~ 7
t = lower_bound(b + 1, b + n + 1, 8) - b;
if (t != n + 1)//找不到会返回边界,边界是 8
cout << b[t] << endl;
return 0;
}
unique(去重函数)
//特点 :1.unique本身的功能是将排序后的数组内的所有重复元素在 O(n) 时间内堆积到数组末端
// 2. 同时它会返回一个指针/下标(区别于你传入的是容器还是数组) —— 堆积的第一个重复元素的位置
#include <bits/stdc++.h>
using namespace std;
int main()
{
vector<int> vec = { 1,3,4,5,1,1,9 };
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());//我们再利用vector的区间删除功能就能完成去重的过程
for (auto j : vec)
cout << j << ' ';
int a[10] = { 1,2,3,8,7,5,3,1,2,4 };
int n = 10;
sort(a, a + n);//排序
for(i, 0, n - 1)
cout << a[i] << ' ';
cout << endl;
n = unique(a, a + n) - a;//n 之后的元素似乎会有变动,但不影响去重本身的正确性
forr(i, 0, n - 1)
cout << a[i] << ' ';
return 0;
}