C++ vector

STL是一个非常强大的工具。用了STL，才知道你用的是C++
我们来看看STL怎么个事——

vector

vector是啥？向量？彳亍。更精确的说，是可变数组——
（以下简称数组）

创建数组、分配数组大小

让我们先来看一段代码~

#include<iostream>
#include<vector>  

using namespace std;  

int main(){

    vector <int> v;
    cout << v.size() << endl;
	
    v.resize(10);
    cout << v.size() << endl;

    return 0;
}

~~这啥东西啊我怎么忽然就看不懂了~~
这段代码的输出是

1
2

0
10

先看代码的第2行，使用vector之前，需要先导入vector库，即需要#include<vector>

how to创建数组？？

我们只需要通过第8行中vector <int> v就可以创建一个int类型的数组了！
那这个数组的大小的是多大呢，我们可以通过调用v.size()并且输出看一下，这个方法会返回数组v的大小。

于是乎我们看到了，输出结果第一行是0，也就是说咱创建的数组长度是0。

长度是0像话吗。咱们肯定需要更改一下这个数组的长度，这时只要通过使用
v.resize(length)
既可以重新分配数组的大小了，再输出，我们就看到原数组的大小改变了。

创建数组还有三种方式，分别是

1
2
3

vector <int> v(10, 2);
vector <int> u(10);
vector <int> v = {1, 2, 3, 4, 5, 6};

这两种方式与第一种方式的参数数量不同。
vector <int> v(10, 2);作用就是创建一个长度为10的数组v，并且初始化数组中每个元素都是2。
也就是说省去了resize的过程，并且顺便初始化了整个数组。

而vector <int> u(10)，其实等价于vector <int> u(10)
即把数组u中每个元素都初始化成0。

至于vector<int> v = {1, 2, 3, 4, 5, 6}，也就是和C语言一样手动初始化数组

另外 v.resize(n, val)实际也有两个参数
当缺少参数val时，只更改数组大小（如果之前小，新的就补0，之前大就删掉
当加上参数val时，则新加的元素会自动初始化成val，但是如果之前的长度比更改后的长度n长，那么参数val就会被忽略。

更改数组元素

这里用法与C语言相同，如使用v[0] = 10就可以直接更改了。

末尾添加新的元素

通过使用

1	v.push_back(data);

就可以在v后追加元素
例如

#include<iostream>
#include<vector>  

using namespace std;  

int main(){

    vector <int> v(10, 2);
	   
    v.push_back(11);
    
    for(int i = 0; i < 11; i++){
	    cout << v[i] << ' ';
    }

    return 0;
}

输出的结果是

1	0 0 0 0 0 0 0 0 0 0 11

我们发现，前十个初始化成0的元素并没有被改变，而是多出了第11个元素。
也就是说，pushback(data)会把data这个值放在原来的数组后面，也就是更改了数组长度。
此时再使用

1	cout << v.size();

会发现数组的长度变成了11。

迭代器

我们看一段代码

#include<iostream>
#include<vector>  

using namespace std;   

int main(){

    vector <int> v(6, 2);
    v.push_back(11);
    v.push_back(12);

    for(auto p = v.begin(); p != v.end(); p++){
        cout << *p << " ";
    }
    
    return 0;
}

输出的结果是

1	2 2 2 2 2 2 11 12

看到这个for循环和输出我们就猜到了，这个迭代器的作用说白了就是遍历。

auto p = v.begin()，也就是让迭代器p指向v的第一个元素。
为什么说指向？也就是说vector这里的p就是一个指针。
略微不同之处是，我们不用关心它的类型，即使用auto p就可以创建迭代器了。

p != v.end() 也就是p还不等于的end处。注意，这里的p.end()不是最后一个元素喔，是最后一个元素的==下一个元素==。

也就是说！

1 2	2 2 2 2 2 2 11 12 ^ p.end()在这里！

这也保证了v.size() = v.end() - v.begin();

一些底层逻辑

不关心的可以跳过（

<vector>的底层逻辑，其实就是数组，占用一块连续的内存，其内部维护了三块指针，分别是

T* _begin;   // 指向数据开头
T* _end;     // 指向最后一个有效元素的后面
T* _capEnd;  // 指向已分配空间的末尾

对应示意图

1 2	\| 元素1 \| 元素2 \| 元素3 \| 空 \| 空 \| 空 \| ^begin ^end ^capEnd

这样有

size() = _end - _begin
capacity() = _capEnd - begin

这里出现了一个新的函数，v.capacity()，表示vector最多能容纳多少个元素，而不用再次分配内存。也就是说，v.size()只是数组的长度，而不是内存的长度。而真正的内存长度会由_begin和_capEnd两个指针共同决定。

初始化数组和使用resize()更改数组长度时，会根据长度自动分配数组占用内存。此时size和capacity相等。

当使用v.push_back(num)后，会检测当前数组占用的内存是否都被利用了，如果没有，即end!=capEnd，此时不需要更改内存大小，直接后移end指针即可。

但如果end == capEnd，此时内存不够，就需要扩容了。
但我们知道数组占用的内存是连续的，扩容的话必须再找另外一块更大的连续的内存了。
所以此时，会重新分配一块更大的空间，并且把原来的数据全部拷贝过去，再释放旧内存。

但是为了避免多次v.push_back()扩容反复拷贝浪费时间，这里采用指数级增长，即让新的capacity是原来的两倍，降低拷贝次数，节省时间。

而为了减少频繁扩容带来的开销，可以手动提前“预留空间”
与v.resize()类似，即使用
v.reserve(1000); 就可以手动更改预留内存空间。