CPP模版库使用
前言
本来想写算法题一直用go，但是无奈找工作的在线OJ大部分都不支持GO吧？反正常青树就俩，C++和JAVA，第二常见的就是python和js了，其他的基本上没有了。
所以为了不让我的C++生疏，我决定写算法题的时候还是要带上C++，和GO轮流来吧，这样子两个都熟悉熟悉。而且CPP的库我都忘光怎么使用了，因此写这篇，主要是如何使用，原理可能一带而过一下吧。
两个参考链接：
https://en.cppreference.com/w/
http://www.cplusplus.com/reference/
map
参考链接：https://www.cnblogs.com/fnlingnzb-learner/p/5833051.html
1、简介
map是STL的一个关联容器，每个key只能出现一次，第二次为value。map内部自建一颗红黑树，对数据有自动排序的功能，所以在map内部所有的数据都是有序的。
它的特点是增加和删除节点对迭代器的影响很小，除了那个操作节点，对其他的节点都没有什么影响。对于迭代器来说，可以修改实值，而不能修改key。
自动建立Key － value的对应。key 和 value可以是任意你需要的类型。
2、功能
根据key值快速查找记录，查找的复杂度基本是Log(N)，如果有1000个记录，最多查找10次，1,000,000个记录，最多查找20次。
快速插入Key -Value 记录。
快速删除记录
根据Key 修改value记录。
遍历所有记录。
3、使用
开头需要引入map
#include <map>
构造函数我们用最简单的方法
map<int, string> mapStudent;
为了使用方便，可以对模板类进行一下类型定义，
typedef map<int,CString> UDT_MAP_INT_CSTRING;
UDT_MAP_INT_CSTRING enumMap;
插入
插入一共有三种方式，有两种是insert，还有一种是根据下标。区别就是insert操作如果有key值，那么插入数据是不行的，但是用数组下标的方式，就可以插入或者更新key对应的value。
遍历
常用这种方式，或者通过迭代器
for (const auto& m : map1) {
cout << m.first << m.second << endl;
}
查找
不建议用下标的方式直接获取，因为不存在的会返回0，不太行
建议用find
删除
移除某个map中某个条目用erase（）
该成员方法的定义如下：
iterator erase（iterator it);//通过一个条目对象删除
iterator erase（iterator first，iterator last）//删除一个范围
size_type erase(const Key&key);//通过关键字删除
clear()就相当于enumMap.erase(enumMap.begin(),enumMap.end());
基本操作函数
begin() 返回指向map头部的迭代器
clear(） 删除所有元素
count() 返回指定元素出现的次数
empty() 如果map为空则返回true
end() 返回指向map末尾的迭代器
equal_range() 返回特殊条目的迭代器对
erase() 删除一个元素
find() 查找一个元素
get_allocator() 返回map的配置器
insert() 插入元素
key_comp() 返回比较元素key的函数
lower_bound() 返回键值>=给定元素的第一个位置
max_size() 返回可以容纳的最大元素个数
rbegin() 返回一个指向map尾部的逆向迭代器
rend() 返回一个指向map头部的逆向迭代器
size() 返回map中元素的个数
swap() 交换两个map
upper_bound() 返回键值>给定元素的第一个位置
value_comp() 返回比较元素value的函数
示例
#include <iostream>
#include <map>
#include <string>
using namespace std;
// 遍历二,C++17 的特性
// void print_map(const map<string, int>& m) {
// for (const auto& [key, value] : m) {
// cout << key << " = " << value << "; " << endl;
// }
// }
int main() {
// 初始化1
map<int, int> map1 = {{0, 0}, {1, 2}, {2, 3}};
// 遍历1
for (const auto& m : map1) {
cout << m.first << m.second << endl;
}
// 插入数据1，通过下标的方式
map1[4] = 5;
// 插入数据2，通过insert插入pair
map1.insert(pair<int, int>(3, 4));
// 插入数据3，通过插入value_type
map1.insert(map<int, int>::value_type(5, 6));
/* 遍历2，通过迭代器
iter = _map.begin();
while(iter != _map.end()) {
cout << iter->first << " : " << iter->second << endl;
iter++;
}
*/
map<int, int>::iterator iter;
for (iter = map1.begin(); iter != map1.end(); iter++) {
cout << iter->first << ' ' << iter->second << endl;
}
// 存在key值的情况下，再insert就会失败，可以返回pair，第一个是迭代器，第二个为是否插入成功
pair<map<int, int>::iterator, bool> Insert_Pair;
Insert_Pair = map1.insert(map<int, int>::value_type(5, 6));
cout << "Insert_Pair: " << Insert_Pair.second << endl;
// map的大小
int nSize = map1.size();
cout << "size：" << nSize << endl;
// 反向迭代器
map<int, int>::reverse_iterator iter2;
for (iter2 = map1.rbegin(); iter2 != map1.rend(); iter2++) {
cout << iter2->first << " " << iter2->second << endl;
}
//判断key是否存在，返回的是布尔值
cout << "count（1）是否存在：" << map1.count(10) << endl;
// find查找，如果有，则返回所在位置的迭代器，否则返回end位置的迭代器
iter = map1.find(10);
if (iter != map1.end())
cout << "Find, the value is " << iter->second << endl;
else
cout << "Do not Find" << endl;
cout << map1[100] << endl;
// 删除元素
iter = map1.find(1);
map1.erase(iter);
//如果要删除1，用关键字删除
int n = map1.erase(1); //如果删除了会返回1，否则返回0
//用迭代器，成片的删除,一下代码把整个map清空
map1.erase(map1.begin(), map1.end());
//
cout <<"map是否为空；"<< map1.empty() << endl;
return 0;
}
unordered_map
参考链接：https://blog.csdn.net/qq_21997625/article/details/84672775
与map用起来扎不多吧，但是有些不同
1、引入的头文件不同
#include < unordered_map >
2、内部实现机理不同
unordered_map是通过哈希表（散列表），查找的时间复杂度可达O(1)，元素的排序是无序的。
3、优缺点对比
map：
优点：有序性，因此效率非常的高
缺点： 空间占用率高，因为map内部实现了红黑树，虽然提高了运行效率，但是因为每一个节点都需要额外保存父节点、孩子节点和红/黑性质，使得每一个节点都占用大量的空间
适用处：对于那些有顺序要求的问题，用map会更高效一些
unordered_map：
优点： 因为内部实现了哈希表，因此其查找速度非常的快
缺点： 哈希表的建立比较耗费时间
适用处：对于查找问题，unordered_map会更加高效一些，因此遇到查找问题，常会考虑一下用unordered_map
vector
参考链接：https://www.runoob.com/w3cnote/cpp-vector-container-analysis.html
1、简介
向量（Vector）是一个封装了动态大小数组的顺序容器（Sequence Container）。跟任意其它类型容器一样，它能够存放各种类型的对象。可以简单的认为，向量是一个能够存放任意类型的动态数组。
2、特性
初始化默认内存容量是0，有第一个元素时开辟一个元素大小，接下来的扩容以2倍的大小自动增长。（VS下是1.5倍）
1.顺序序列
顺序容器中的元素按照严格的线性顺序排序。可以通过元素在序列中的位置访问对应的元素。
2.动态数组
支持对序列中的任意元素进行快速直接访问，甚至可以通过指针算述进行该操作。提供了在序列末尾相对快速地添加/删除元素的操作。
3.能够感知内存分配器的（Allocator-aware）
容器使用一个内存分配器对象来动态地处理它的存储需求。
3、功能
1.构造函数
- vector():创建一个空vector
- vector(int nSize):创建一个vector,元素个数为nSize
- vector(int nSize,const t& t):创建一个vector，元素个数为nSize,且值均为t
- vector(const vector&):复制构造函数
- vector(begin,end):复制[begin,end)区间内另一个数组的元素到vector中
2.增加函数
- void push_back(const T& x):向量尾部增加一个元素X
- iterator insert(iterator it,const T& x):向量中迭代器指向元素前增加一个元素x
- iterator insert(iterator it,int n,const T& x):向量中迭代器指向元素前增加n个相同的元素x
- iterator insert(iterator it,const_iterator first,const_iterator last):向量中迭代器指向元素前插入另一个相同类型向量的[first,last)间的数据
3.删除函数
- iterator erase(iterator it):删除向量中迭代器指向元素
- iterator erase(iterator first,iterator last):删除向量中[first,last)中元素
- void pop_back():删除向量中最后一个元素
- void clear():清空向量中所有元素
4.遍历函数
- reference at(int pos):返回pos位置元素的引用
- reference front():返回首元素的引用
- reference back():返回尾元素的引用
- iterator begin():返回向量头指针，指向第一个元素
- iterator end():返回向量尾指针，指向向量最后一个元素的下一个位置
- reverse_iterator rbegin():反向迭代器，指向最后一个元素
- reverse_iterator rend():反向迭代器，指向第一个元素之前的位置
5.判断函数
- bool empty() const:判断向量是否为空，若为空，则向量中无元素
6.大小函数
- int size() const:返回向量中元素的个数
- int capacity() const:返回当前向量所能容纳的最大元素值
- int max_size() const:返回最大可允许的vector元素数量值
7.其他函数
- void swap(vector&):交换两个同类型向量的数据
- void assign(int n,const T& x):设置向量中前n个元素的值为x，（会重新分配地址，草了）
- void assign(const_iterator first,const_iterator last):向量中[first,last)中元素设置成当前向量元素
8.看着清楚
1.push_back 在数组的最后添加一个数据
2.pop_back 去掉数组的最后一个数据
3.at 得到编号位置的数据
4.begin 得到数组头的指针
5.end 得到数组的最后一个单元+1的指针
6.front 得到数组头的引用
7.back 得到数组的最后一个单元的引用
8.max_size 得到vector最大可以是多大
9.capacity 当前vector分配的大小
10.size 当前使用数据的大小
11.resize 改变当前使用数据的大小，如果它比当前使用的大，者填充默认值
12.reserve 改变当前vecotr所分配空间的大小
13.erase 删除指针指向的数据项
14.clear 清空当前的vector
15.rbegin 将vector反转后的开始指针返回(其实就是原来的end-1)
16.rend 将vector反转构的结束指针返回(其实就是原来的begin-1)
17.empty 判断vector是否为空
18.swap 与另一个vector交换数据
4、使用
头文件导入#include <vector>
初始化
#include <iostream>
#include <vector>
using namespace std;
int main() {
// 1、默认初始化，为空，size为0，capacity也为0
vector<int> v1;
// 2、拷贝初始化，具有相同的容量和元素
vector<int> v2 = v1;
// 2.1、复制构造函数拷贝
vector<int> v2_1(v1);
// 3、列表中元素的拷贝
vector<int> v3 = {1, 2, 3, 4, 5, 6, 7};
// 4、指定元素中的拷贝
vector<int> v4(v3.begin() + 2, v3.end() - 1);
// 4.1 拷贝数组的元素
int a[4] = {1, 2, 3, 4};
vector<int> v4_1(a + 1, a + 3);
// 5、指定vector的长度，元素进行缺省初始化
vector<int> v5(7);
// 6、指定长度和元素的初始化值
vector<int> v6(7, 3);
return 0;
}
二维数组初始化，和上面的类似
int N = 5, M = 6;
vector<vector<int> > obj(N, vector<int>(M, 0)); //定义二维动态数组5行6列
遍历
一维数组
// 1、下标遍历
vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8, 9};
for (int i = 0; i < vec.size(); i++) {
cout << vec[i] << " ";
}
cout << endl;
// 2、C++11的遍历方式
for (int &v : vec) {
cout << v << " ";
}
cout << endl;
// 3、迭代器遍历
vector<int>::iterator it;
for (it = vec.begin(); it != vec.end(); it++) {
cout << *it << " ";
}
cout << endl;
二维数组遍历
// 1、二维数组通过下标遍历
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cout << obj[i][j] << " ";
}
cout << endl;
}
// 2、通过C++11的特性遍历
for (auto &i : obj) {
for (int &j : i) {
cout << j << " ";
}
cout << endl;
}
// 3、通过迭代器遍历
vector<vector<int>>::iterator it1;
vector<int>::iterator it2;
for (it1 = obj.begin(); it1 != obj.end(); it1++) {
for (it2 = (*it1).begin(); it2 != (*it1).end(); it2++) {
cout << (*it2) << " ";
}
cout << endl;
}
cout << endl;
5、问题
自己想到一个问题，vector都有push_back()和pop_back()两个操作，为什么不能当做栈来使用，果然知乎大神已经答过了，https://www.zhihu.com/question/378846608/answer/1074026357
std::vector是容器，而std::stack是容器适配器。
std::stack只提供和堆栈相关的接口，其中主要是push()、emplace()、pop()、top()和empty()。使用std::stack时只需关心这些接口，而非内在用了哪个具体容器。改变容器类型也不需要修改调用方的代码。这个设计应该可说是乎合 SOLID 中的 I ──接口隔离原则（interface segregation principle）。
std::stack可适配的标准容器有std::vector、std::list、std::deque，而std::deque是缺省的，因为它提供O(1)的push_back()，而std::vector::push_back()是均摊（amortized） O(1) 。
这里有两个概念：容器和容器适配器。
STL的顺序容器，分别是
- vector 向量容器，底层是由数组实现的。
- list 双向链表容器，底层由双向链表实现（含尾节点（为了保证迭代器的通用性））
- deque 双端队列容器，底层用双端队列实现 【可以下标操作】
STL的关联容器分别是
- set单重集合
- msp 映射表
- 散列表 hashtable （unordered_map?）
容器适配器
- 栈stack，底层使用deque，将一端封闭，实现后进先出的行为。
- 队列queue，底层默认使用deque的数据结构，封闭低端的出口和顶端的入口，实现先进先出
- 带权的队列qriority_queue，默认情况下qriority_queue底层使用max_heap（以vector）实现，可以满足以“权值高低自动排序”的特性。
queue
queue是容器适配器，和容器用起来有点不一样，不能直接初始化。
只能访问 queue<T> 容器适配器的第一个和最后一个元素。只能在容器的末尾添加新元素，只能从头部移除元素。
- front()：返回 queue 中第一个元素的引用。如果 queue 是常量，就返回一个常引用；如果 queue 为空，返回值是未定义的。
- back()：返回 queue 中最后一个元素的引用。如果 queue 是常量，就返回一个常引用；如果 queue 为空，返回值是未定义的。
- push(const T& obj)：在 queue 的尾部添加一个元素的副本。这是通过调用底层容器的成员函数 push_back() 来完成的。
- push(T&& obj)：以移动的方式在 queue 的尾部添加元素。这是通过调用底层容器的具有右值引用参数的成员函数 push_back() 来完成的。
- pop()：删除 queue 中的第一个元素。
- size()：返回 queue 中元素的个数。
- empty()：如果 queue 中没有元素的话，返回 true。
- emplace()：用传给 emplace() 的参数调用 T 的构造函数，在 queue 的尾部生成对象。
- swap(queue
&other_q)：将当前 queue 中的元素和参数 queue 中的元素交换。它们需要包含相同类型的元素。也可以调用全局函数模板 swap() 来完成同样的操作。
queue 也没有迭代器。访问元素的唯一方式是遍历容器内容，并移除访问过的每一个元素。
#include <iostream>
#include <queue>
using namespace std;
int main() {
deque<double> values{1.5, 2.5, 3.5, 4.5};
// 复制其底层deque的值
queue<double> numbers(values);
queue<pair<int, int>> que;
// push添加操作，拷贝构造好的
que.push(make_pair(1, 2));
// que.push(pair<int, int>(1, 2));
// 直接调用构造函数，直接构造一个，节省内存空间
que.emplace(3, 4);
// 大小
cout << "size: " << que.size() << endl;
// 取出最后一个值
cout << "新添加的值：" << que.back().first << " " << que.back().second
<< endl;
// 访问元素只能遍历一遍
while (!que.empty()) {
cout << que.front().first << " " << que.front().second << endl;
// 弹出第一个
que.pop();
}
return 0;
}