常用数据结构的常用函数总结（leetcode）
在刷题的过程中，梳理了一下leetcode中常用的函数，从数组、字符串、哈希表、链表以及栈与队列方面，分别总结整理。
一、数组
在c++中，是经常使用vector这个容器，vector相较于数组有一些好处，这里的长度不固定，可以随时增加。在c++ primer里提到，在实际的编程中，我们作为程序员应该避免用到低级数组和指针，而更应该多用高级的vector和迭代器。
（1）常用函数：（经常用到迭代器iterator）
- vector.assign(): 对vector中的元素赋值
- vector.size(): 获取vector元素数量
- vector.push_back():在vector最后添加一个元素
- vector.clear(): 清空所有元素
- vector.insert(): 插入元素到vector（涉及到排序时会用到）
- vector.reverse(): 元素翻转
（2）vector初始化的方式：
#include
using namespace std;//一维初始化
vector abc(10,1); //初始化10个默认值为1的元素vector b(10);
copy(abc.begin(), abc.end(), b.begin()); //复制abc从头到尾到b开始的位置//二维初始化
vector> (4, vector(4,0)); //构建4*4的二维vector （3）迭代器iterator的使用：
iteretor类似于指针。
#include
#includeusing namespace std;int main()
{vector vec(5, 1);int i = 1;//更新vector元素为1 - 5for(vector::iterator iter = vec.begin(); iter != vec.end(); iter++){*iter = i++;}//常量迭代器，不能更改指向的值for(vector::const_iterator iter = vec.begin(); iter != vec.end(); iter++){cout<<*iter< 二、字符串
对于字符串，常用的函数需要了解一下，字符串在处理一些问题时有妙用，例如对于数值的个十百...位处理时，转换成字符串处理更加的方便。对于字符串的操作，在leetcode上是非常常见的。
（1）常用的函数
- size(): 返回字符串的长度
- resize(): 重新设置字符串的大小
- assign(): 为字符串赋新值
- append(): 在字符串的末尾添加文本
- reverse(): 字符串翻转
- swap(): 交换两个字符串的内容（一般是用于字符串内两元素的交换）
- c_str(): 将字符串以c字符数组的形式返回
- substr(): 复制字符串中的子字符串（挺常用的）
（2）字符串string的初始构造
string strs; //构造一个空的字符串
string s(str); //构造一个字符串str的复制品
string s(num, '.'); //生成一个字符串，包含num个'.'字符
string s(strs, beg, end); //以区间[beg, end]内的字符作为字符串s的初值
（3）vector和string之间的互转
std::vector vec;
std::string str(vec.begin(), vec.end()); 三、哈希表
当我们遇到要快速判断一个元素是否出现在集合里的时候，就先想着用哈希表。一般哈希表都是用来判断一个元素是否出现集合里（一个元素有多少个）。
哈希常见的结构有数组、set（集合）以及map（映射）。
set是一种关联式容器，所得元素的只有key没有value，value就是key。
map也是关联式容器，map的值不作为键，键和值是分开的，所有元素都是键+值存在。所有元素都是通过键进行排序
注：set一般只能判断元素有没有，multiset可以用来存放重复的数据，并且可以用count计算重复元素的个数，但是相较于map来讲，操作较为复杂。
map可以用来寻找元素有没有的同时，value对应映射值（哈希函数后，例如元素的数量之类的）。
（1）常用的函数
- find(): 查找元素
- empty(): 为空时返回真
- insert(): 插入元素
（2）set、map的具体使用
①以寻找两个数据集的交集为例，找到交集元素（set）
#include
#include
#include int main(){//以寻找两个数据集的交集为例，找到交集元素（set）std::vector nums1 = {1,2,3,4,5,6,7,8,9};std::vector nums2 = {2,2,4,5};//构建std::unordered_set set(nums1.begin(), nums1.end());std::unordered_set result; //有一个特性：元素不重复//查询判断for(int i = 0; i < nums2.size(); i++){auto item1 = set.find(nums2[i]); //查询if(item1 != set.end()) result.insert(nums2[i]); //判断如果查询到元素则将元素填入到result}//输出std::vector result_vec(result.begin(), result.end());for (auto it = result_vec.begin(); it != result_vec.end(); it++){std::cout<<*it< ② map的使用，经常的操作---插入、查询
//构建map m;//插入、赋值m.insert(pair(1, 1));m.insert(pair(2, 2));m[3] = 3;//输出for(auto iter = m.begin(); iter != m.end(); iter++){cout<first<<" "<second< 四、链表
链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个数据域一个指针域，最后一个节点的指针域指向null。
（1）链表的数据结构
struct ListNode {int val; // 节点上存储的元素ListNode *next; // 指向下一个节点的指针ListNode(int x) : val(x), next(NULL) {} // 节点的构造函数
};（2）常用的函数
- back()：返回最后一个元素
- front()：返回第一个元素
- 迭代器的应用：begin()：返回一个元素的迭代器 end()：返回最后一个元素的迭代器
- empty()：判断元素是否为空
- insert()：插入一个元素到list中
- pop_back()：删除最后一个元素
- push_back()：在list末尾添加一个元素
五、栈与队列
基础概念：
（1）栈先进后出，队列先进先出。我们常用的SGI STL（Linux的c++编译器GCC采用） ，如果没有指定底层实现的话，默认是以deque（双向队列）为缺省情况下的底层结构。除此之外，可以指定底层结构为vector或者list。
（2）STL 队列和栈都不归为容器，而被归类为container adapter。不提供走访功能，也不提供迭代器(iterator)。
（3）栈和队列的底层实现可以是vector、deque以及list（链表）。可以在初始定义的时候，指定底层是vector或者list。例：
std::stack > one; // 使用vector为底层容器的栈
std::queue> two; // 定义以list为底层容器的队列 栈常用的函数： stack
- empty()：判断是否为空，空返回true
- pop()： 移除栈顶元素
- push()： 添加栈顶元素
- size()： 返回栈中元素数目
- top()： 返回栈顶元素
队列常用的函数：queue
- empty()：判断是否为空，空返回true
- clear(): 清空队列
- pop()： 删除第一个元素元素
- push()： 在末尾加入一个元素
- size()： 返回队列中元素数目
- back()： 返回最后一个元素
- front(): 返回第一个元素
双向队列常用的函数：deque
- pop_back(): 删除尾部的元素
- pop_front(): 删除头部的元素
- push_back(): 删除尾部的元素
- push_front(): 删除头部的元素