容器
vector
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
//容器1:vector
//vector可以随开随用,下面的操作类似于二维数组
//vector<int> vec1[100];
vector<int> vec;
int n, t;
cin>>n;
for(int i = 0; i < n; i++)
{
cin>>t;
//从尾部插入t
vec.push_back(t);
}
//正序排序
sort(vec.begin(),vec.end());
//倒序排序
//reverse(vec.begin(),vec.end());
//正序遍历
//迭代器遍历
vector<int>::iterator it;
//begin返回第一个元素的迭代器
//end返回最后一个元素的迭代器
for(it = vec.begin(); it != vec.end(); it++)
{
cout<<*it<<" ";
}
cout<<endl;
//for循环中的auto,可以遍历容器
for(auto j:vec)
{
cout<<j<<" ";
}
cout<<endl;
//vector遍历
for(int i = 0; i < vec.size(); i++)
{
cout<<vec[i]<<" ";
}
cout<<endl;
//倒序遍历
vector<int>::reverse_iterator it1;
//it1可以直接在for循环内使用auto类型
for(it1 = vec.rbegin(); it1 != vec.rend(); it1++)
{
cout<<*it1<<" ";
}
cout<<endl;
for(int i = vec.size() - 1; i >=0; i--)
{
cout<<vec[i]<<" ";
}
cout<<endl;
//按值删除vec中的元素
for(auto it = vec.begin(); it != vec.end();)
{
if(*it == 4)
{
it = vec.erase(it);
}
else
{
it++;
}
}
for(auto j:vec)
{
cout<<j<<" ";
}
cout<<endl;
//删除尾部的元素
vec.pop_back();
if(vec.size())
{
//返回第一个元素
vec.front();
//返回最后一个元素
vec.back();
}
//清空vec
vec.clear();
return 0;
}
string
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main()
{
//容器2:string
string a, b;
cin>>a;
//在容器尾部插入元素
a.push_back('xxxxxx');
//排序
sort(a.begin(), a.end());
cout<<a<<endl;
//在容器尾部删除元素
a.pop_back();
cout<<a<<endl;
//返回找到第一个b的索引
cout<<a.find('b')<<endl;
//从3开始往后截取5个字符,不会越界
cout<<a.substr(3,5)<<endl;
return 0;
}
pair
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int, int> p;
int main()
{
//容器3:pair
//关键字 关键值
//基础用法
// pair<char, string> a, b;
// char t;
// string s;
// cin>>t>>s;
// a = {t, s};
//
// cout<<a.first<<" "<<a.second;
//别名用法
p p1 = p(1, 3);
p p2 = p(2, 2);
p p3 = p(0, -2);
vector<p> vec;
vec.push_back(p1);
vec.push_back(p2);
vec.push_back(p3);
//pair排序
//pair默认是先对第一个关键字从小到大排序
//如果第一关键字相同，在对第二关键字从小到大排序
sort(vec.begin(), vec.end());
for(auto i : vec)
{
cout<<i.first<<" "<<i.second<<endl;
}
return 0;
}
stack
#include <iostream>
#include <stack>
using namespace std;
int main()
{
//容器4:stack 栈(先进后出)
stack<int> sta;
int n, t;
cin>>n;
for(int i = 0; i < n; i++)
{
cin>>t;
//入栈
sta.push(t);
}
cout<<sta.top()<<endl;
//出栈
sta.pop();
cout<<sta.top()<<endl;
//用数组模拟栈，输出后可以保留栈的数据
// int z[100];
// int n,t;
// int tt = 0;
// cin>>n;
// //模拟进栈
// for(int i = 0; i < n; i++)
// {
// cin>>t;
// z[tt++] = t;
// }
// //模拟出栈（不会真的出栈）
// for(int i = tt - 1; i >= 0; i--)
// {
// cout<<z[i]<<endl;
// }
return 0;
}
queue
#include <iostream>
#include <queue>
using namespace std;
int main()
{
//容器5:queue(先进先出)
// queue<int> q;
// int n,t;
// cin>>n;
// for(int i = 0; i < n; i++)
// {
// cin>>t;
// q.push(t);
// }
// while(q.size())
// {
// //返回队头元素和队尾元素
// cout<<q.front()<<" "<<q.back()<<endl;
// q.pop();
// }
//数组模拟queue
int z[100];
int n, t;
int hh = 0, tt = 0;
cin>>n;
for(int i = 0; i < n; i++)
{
cin>>t;
z[tt++] = t;
}
while(hh < tt)
{
cout<<z[hh++]<<endl;
}
return 0;
}
deque
#include <iostream>
#include <stack>
using namespace std;
int main()
{
//容器6:deque 双端队列
deque <int> q;
int t = 0;
q.push_back(t);
q.push_front(t);
q.pop_back();
q.pop_front();
return 0;
}
priorty_queue
#include <iostream>
#include <queue>
using namespace std;
int main()
{
//容器7:priorty_queue 优先队列(堆)
//自动排序,从大到小,类似于大根堆,vector为默认的存放容器
priority_queue<int, vector<int>, less<>> q;
//类似小根堆
priority_queue<int, vector<int>, greater<>> q1;
int n, t;
cin>>n;
for(int i = 0; i < n; i++)
{
cin>>t;
q.push(t);
}
while(q.size())
{
cout<<q.top()<<endl;
q.pop();
}
return 0;
}
set
#include <iostream>
#include <set>
using namespace std;
int main()
{
//容器8:set 红黑树实现
//不存在重复的数据
//正序排序
set<int> se;
int n,t;
cin>>n;
for(int i = 0; i < n; i++)
{
cin>>t;
//插入
se.insert(t);
}
//迭代器遍历
set<int>::iterator it;
for(it = se.begin(); it != se.end(); it++)
{
cout<<*it<<" ";
}
cout<<endl;
//for循环中的auto遍历
for(auto j : se)
{
cout<<j<<" ";
}
cout<<endl;
//倒序遍历
set<int>::reverse_iterator it1;
for(it1 = se.rbegin(); it1 != se.rend(); it1++)
{
cout<<*it1<<" ";
}
cout<<endl;
//查找3 如果查找不到会返回se.end()
//用法：可以通过j++ j--获取比j大一位或者小一位的数
auto j = se.find(3);
if(j == se.end())
{
cout<<"did not find"<<endl;
}
else
{
cout<<*j<<endl;
}
//返回>=3的第一个数(二分查找)
//要求是有序数组,不存在这个数则返回end()
j = se.lower_bound(3);
//返回>3的第一个数
j = se.upper_bound(3);
//删除指定元素
//set可以直接删除值
//vector只能通过指针删除
se.erase(3);
for(auto it = se.begin(); it != se.end();)
{
if(*it == 4)
{
it = se.erase(it);
}
else
{
it++;
}
}
for(auto j : se)
{
cout<<j<<" ";
}
//返回1出现的次数
se.count(1);
//清空set
se.clear();
return 0;
}
map
#include <iostream>
#include <map>
using namespace std;
int main()
{
//容器9:map 红黑树实现
//和set类似但是维护的是pair类型
//不存在重复的数据
//根据第一关键字正序排序
map<int,int> mp;
int n, t, s;
cin>>n;
for(int i = 0; i < n; i++)
{
cin>>t>>s;
mp[t] = s;
}
//用法:记录同一个值出现的次数
// for(int i = 0; i < n; i++)
// {
// cin>>t;
// mp[t]++;
// }
//插入 两种方法等价
//mp.insert({1,2});
//mp[1] = 2;
//正序遍历
map<int,int>::iterator it;
for(it = mp.begin(); it != mp.end(); it++)
{
cout<<(*it).first<<" "<<(*it).second<<endl;
}
for(auto j : mp)
{
cout<<j.first<<" "<<j.second<<endl;
}
//删除指定元素
//map可以直接根据对应关键字删除
mp.erase(3);
//返回1作为关键字出现的次数
mp.count(1);
return 0;
}
multiset
#include <iostream>
#include <set>
using namespace std;
int main()
{
//容器10:multiset 红黑树实现
//可以存放重复的数据
//自动进行正序排序
multiset<int> se;
int n, t;
cin>>n;
for(int i = 0; i < n; i++)
{
cin>>t;
se.insert(t);
}
//删除指定元素
se.erase(2);
for(auto it = se.begin(); it != se.end();)
{
if(*it == 3)
{
it = se.erase(it);
}
else
{
it++;
}
}
//正序遍历
for(auto j : se)
{
cout<<j<<endl;
}
return 0;
}
multimap
#include <iostream>
#include <map>
using namespace std;
int main()
{
//容器11:multimap 红黑树实现
//和set类似但是维护的是pair类型
//可以存放重复的数据
//因为数据可能重复 所以不能使用mp[t] = s这种插入方法
//根据第一关键字正序排序
multimap<int,int> mp;
int n, t, s;
cin>>n;
for(int i = 0; i < n; i++)
{
cin>>t>>s;
mp.insert({t, s});
}
//这样会删除所有的以3位关键字的元素
mp.erase(3);
//删除指定的关键值和关键字组成的元素
for(auto it = mp.begin(); it != mp.end();)
{
if((*it).first == 3 && (*it).second == 2)
{
it = mp.erase(it);
}
else
{
it++;
}
}
for(auto j : mp)
{
cout<<j.first<<" "<<j.second<<endl;
}
return 0;
}
hashmap、hashset
#include <iostream>
#include <unordered_map>
#include <unordered_set>
using namespace std;
int main()
{
//哈希表
//容器12:hashset
//容器13:hashmap
//无自动排序，有去重，支持 O(1) 时间查找元素是否存在
//map、set使用红黑树为 O(logn)
unordered_map<int, int> ump;
unordered_set<int> ums;
ump.insert({ 1, 2 });
ump[1] = 2;
ump[2] = 3;
ums.insert(3);
ums.insert(4);
for (auto j : ump)
{
cout<<j.first<<" "<<j.second<<endl;
}
cout<<endl;
for (auto j : ums)
{
cout << j << endl;
}
cout<<endl;
//查找元素是否存在，存在就返回true，否则返回false
bool t = ump.count(3);
bool g = ums.count(1);
cout<<t<<g;
return 0;
}
函数
unique
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
vector<int> vec = {3,3,4,4,5,5,6,7,7,4};
sort(vec.begin(), vec.end());
for(auto j : vec)
{
cout<<j<<" ";
}
cout<<endl;
//将重复的数字堆在数组有序数组后面
//返回重复的第一个元素
//通过erase删除后面重复的元素
vec.erase(unique(vec.begin(), vec.end()),vec.end());
for(auto j : vec)
{
cout<<j<<" ";
}
cout<<endl;
//对数组进行去重
int a[200] = {0,1,2,2,2,3,0,5,7,1};
sort(a, a+10);
int n = unique(a, a+10) - a;
for(int i = 0; i < n; i++)
{
cout<<a[i]<<" ";
}
return 0;
}
next_permutation
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
//时间复杂度比较高 最好只处理比较小的数组
//next_permutation 从小到大全排列
//如果要求排列所有情况 需要一组升序的元素
int a[] = {1,2,3,4};
do
{
for(int i = 0; i < 4; i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
}while(next_permutation(a, a+4));
cout<<"-----------------------"<<endl;
for(int i = 0; i < 4; i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
reverse(a,a+4);
for(int i = 0; i < 4; i++)
{
cout<<a[i]<<" ";
}
cout<<endl<<"-----------------------"<<endl;
//prev_permutation 从大到小全排列
do
{
for(int i = 0; i < 4; i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
}while(prev_permutation(a, a+4));
return 0;
}
lower_bound
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
//用的是二分查找的方法
//区间是前闭后开
//返回>=key的值 需要是一个有序数组
//找不到的话会返回vec.end() 或者比数组范围更大1的位置
int a[] = {1,2,3,4,5,6};
int t = lower_bound(a, a+6, 200) - a;
cout<<t<<endl;
vector<int> vec = {1,2,3,4,5,6};
int s = lower_bound(vec.begin(),vec.end(),10) - vec.begin();
cout<<s<<endl;
return 0;
}
完整代码
https://github.com/lengyueling/AlgorithmStudy
参考资料
https://www.bilibili.com/video/BV1Sa411b7L6
加油
