vector的总结

2021-01-12

vector总结

vector是不定长数组，具有静态数组的稳定性和动态分配内存的灵活性，在赛场上不失为指针之外牺牲部分时间的保险之举。

本文先介绍一些vector常用的函数（部分借鉴一篇博客中的内容链接），并以此为铺垫，介绍本人在解题过程中对vector用途的一些总结。

vector中迭代器的声明：vector::iterator it;

迭代器的使用方法与指针几乎完全一样，vector中绝大多数带参数的函数参数都有迭代器，很多函数的返回值也是迭代器。

常用函数：

1.begin,end：
a.begin()返回指向a中第一个元素的迭代器，a.end()返回指向a中最后一个元素的位置的下一个位置的迭代器。begin和end可以用来遍历，当然for(int i=0;i<a.size();i++)也可以实现，效率完全相同，但在运行一些输入参数为迭代器的函数时，vector的下标就无法解决了。

2.size,capacity：
a.size()返回a中非空元素个数，a.capacity()返回a所占内存可容纳元素的个数。

3.clear,resize：
a.clear()是void类型，表示将a中所有元素置空，但不改变a所占内存，即size变为0，capacity不变。

a.resize(x)也是void类型，表示将a的size变为x，capacity变为max(capacity,x)。（好奇怪的操作……）

4.push_back：
a.pushback(x)是void类型，表示将x插入到a的尾部，size+1。

值得注意的是，a的capacity并不是push_back一次就+1，而是当capacity不够用的时候增大为原来的两倍。即capacity的值只可能是0或2的幂次。在某些极限情况下vector所占内存可以达到预计内存的近似两倍，在做题时要额外注意MLE的风险。

5.insert：
insert共有三种用法：

a.insert(it,val)：函数表示在迭代器it指向位置之前插入值为val的元素，返回指向插入元素的迭代器。
a.insert(it,num,val)：该函数是void类型，表示在迭代器it指向位置之前插入num个值为val的元素。
a.insert(it,l,r)：该函数是void类型，表示在迭代器it指向位置之前插入从迭代器l指向位置到迭代器r指向位置的前一个位置的元素（即插入某个容器中[l,r)的元素）。
(可以实现两段vector的合并：
vector vec_1.insert(vec_1.end(), vec_2.begin(), vec_2.end()) )

6.erase：
erase共有两种用法，与insert的第一种和第三种类似。

a.erase(it)：函数表示删除迭代器it指向的元素，返回指向被删元素的前一个元素的迭代器。
a.erase(l,r)：函数表示删除从迭代器l指向位置到迭代器r指向位置的前一个位置的元素（即删除a中[l,r)的元素）。

insert的操作3和erase的操作2结合起来使用，可以实现区间的插入，删除，交换。

7.lower_bound,upper_bound：

lower_bound(l,r,x)中l,r为迭代器，函数返回指向容器[l,r)中第一个大于等于x的元素的迭代器。
upper_bound(l,r,x)中l,r为迭代器，函数返回指向容器[l,r)中第一个大于x的元素的迭代器。