常规用法
一、vector基本用法及技巧
1、基本用法
1）vector常用内置函数
a.push_back();
a.pop_back();
a.front();
a.back();
a.clear();
a.erase(a.begin(), a.begin() + p)
a.size();
//b为向量，将a中的元素和b中的元素整体交换
a.swap(b);
//b为向量，向量的比较操作还有 != >= > <= <
//如果vector里面的元素类型是简单类型（内置类型），可以直接使用“==”或者“!=”进行比较
//甚至可以使用“<=” “<” “>=” ">"比较两个vector大小：按照字典序排列
a == b;
2）algorithm对vector常用函数
#include<algorithm>
//对a中的从a.begin()（包括它）到a.end()（不包括它）的元素进行从小到大排列
sort(a.begin(),a.end());
//对a中的从a.begin()（包括它）到a.end()（不包括它）的元素倒置，但不排列，如a中元素为1,3,2,4,倒置后为4,2,3,1
reverse(a.begin(),a.end());
//把a中的从a.begin()（包括它）到a.end()（不包括它）的元素复制到b中，从b.begin()+1的位置（包括它）开始复制，覆盖掉原有元素
copy(a.begin(),a.end(),b.begin()+1);
//在a中的从a.begin()（包括它）到a.end()（不包括它）的元素中查找10，若存在返回其在向量中的位置
find(a.begin(),a.end(),10);
//在a中的从a.begin()（包括它）到a.end()（不包括它）的元素中查找10的个数，返回个数
count(a.begin(), a.end(),10);
3）下标只能用来获取已经存在的元素,不能通过下标赋值
2、使用技巧（很好用！！！！）
$\color{red}{1）vector的转存作用}$
/*把map中元素转存到vector中*/
vector<PAIR> name_score_vec(mp.begin(), mp.end());
/可以通过sort将map中的value排序，非常的nice
例题：3466. 清点代码库
https://www.acwing.com/problem/content/3469/
1351.密码锁
https://www.acwing.com/problem/content/1353/
二、map和unored_map()
1、区别
unordered_map<vector<int>, int> map1; // 这种用法错误
//我们知道c++中有unordered_map和unordered_set这两个数据结构，
// 其内部实现是哈希表，这就要求作为键的类型必须是可哈希的，一般来说都是基本类型
//所以pair和vector一类的不可以
map<vector<int>, int> map2; // 用法正确
// map和set内部的实现是树（红黑树，更高级的二叉搜索树），
//既然运用到二叉搜索树就必须得有比较两个元素大小的方法，
// 所以pair<int,int>和vector<int>，可以直接作为键进行使用
unordered_map<int, vector<int>> map; // 哈希表的值可以是数组等其他复杂类型
// 可以用一个哈希表记录多种内容，而不必使用多个哈希表
2、map基本用法及技巧
1)基本用法
1> 位置与大小
mp.begin();
mp.end();
mp.size();
II> 增
//第一种
mp.insert(pair<xx, xx>);
//第二种
mp[xx] = xx;
III> 删除
mp.clear();//清空
mp.erase();
//迭代器刪除
iter = mapStudent.find("123");
mapStudent.erase(iter);
//用关键字刪除
int n = mapStudent.erase("123"); //如果刪除了會返回1，否則返回0
//用迭代器范围刪除 : 把整个map清空
mapStudent.erase(mapStudent.begin(), mapStudent.end());
IV> 查
//查找
mp.find(); //返回key位置，没有找到返回mp.end()
mp.count(); //返回key值个数
mp.lower_bound()//返回键值>=给定元素的第一个位置
V> 改
//交换
mp.swap(mp1);
2）使用技巧（很好用！！！！）
$\color{red}{I> key按照从大到小排序}$
//这里和algorithm中的sort（a, b, greater<int>()）做区别（没有括号）
map<int, int, greater<int>> mp1;
map<string, int, greater<string>> mp1;
$\color{red}{II> 重定义map内部的Compare函数}$
struct cmp
{
bool operator< (const string &k1, string &k2)
{
return k1.size() < k2.size();
}
}
map<string, int, cmp> mp;
$\color{red}{III> key是结构体排序}$
结构体中又重载运算即可
struct student
{
string name;
int math;
bool operator< (const student &t) const
{
if (math != t.math) return math < t.math;
return name < t.name;
}
}sdt;
map<sdt, int> mp;
$\color{red}{IV> 排序map中的value或者key、value都需要排序}$
/*把map中元素转存到vector中*/
vector<PAIR> name_score_vec(mp.begin(), mp.end());
/可以通过sort将map中的value排序，非常的nice
3、关于unordered_map、map的时间复杂度
搜索(查找)时间复杂度
map： 该类型的搜索时间复杂度为log(n)
unordered_map ： 搜索时间复杂度。O(1)为平均时间，最坏情况下的时间复杂度为O（n）;
插入操作的时间复杂度
map : 该操作的时间 复杂度为log(n)+再平衡时间
unordered_map : 该操作的时间复杂度与搜索的时间复杂度一样。
删除操作的时间复杂度与插入操作的时间复杂度是一样的。
4、unordered_map, map初始化:
unordered_map<char, int> swp = {{'F',0}, {'B',1}, {'L',2}, {'R',3}};
map<string, int> cow_to = {{"FR",0}, {"FL",1}, {"RR",2},{"RL",3}};
一、algorithm一些好用的函数
1)is_sorted() 函数—一个判断数组和容器是否有序的函数
//如果有序返回true,否则返回false
is_sorted(x, y) x,y为指针或迭代器,不为数组下标
if (is_sorted(a.begin(),a.end()) cout << "YES" << endl;
else cout << "NO" << endl;
2）unique(a, a + n) 返回去从后的指针（必须是有序的数组）
技巧
1、unodered_map<string, vector<int>> mp的使用
2）如何在vector中添加数据, 最好先映射一下vector再向其添加元素
map< string, vector< int > > mp;
string s;
cin >> s;
auto &vc = mp[ s ];
cin >> x;
vc.push_back( x );
例题：牛客小白月赛46 C 英语作文
https://ac.nowcoder.com/acm/contest/11223/C
string初始化
//string 复制
char sp[5];
scanf("%s", sp);
string s(sp, 2);
//string复制n个'a'
string s(n, 'a');
----------
----------
#### 2、multiset当(不严格)单调栈用，insert， begin，end, erase；
例题：
Codeforces Round #761 (Div. 2)C. Paprika and Permutation
[https://codeforces.com/contest/1617/problem/C](https://)
----------
----------
## string
#### 卧槽重大发现：
int n;
n = 10000000;
for (int i = 0; i < n; i ++ )
res += ‘1’;
int n;
n = 10000000;
for (int i = 0; i < n; i ++ )
res = res + ‘1’;
#### $\color{red}{时间复杂度不一样！！！！！}$
## set迭代器底层const
#### 当然也可以通过 const_cast 来解除 set 迭代器的底层 const：
set[HTML_REMOVED] s;
s.insert(1);
s.insert(10);
s.insert(100);
const set<int>::iterator it = s.begin();
int &cnt = const_cast<int&>(*it);//cnt为it所指对象的引用, 但cnt不具有底层const
cnt += 100;
cout << *it << endl;//输出101
cout << cnt << endl;//输出101
for(auto i : s){
cout << i << " ";//输出 101 10 100 (set类型对象s的有序性被破坏了)
}
cout << endl;
s.insert(1);
cout << *s.begin() << endl;
for(auto i : s){
cout << i << " ";//输出 1 101 10 100
}
cout << endl;
```
