1.什么是vector

vector 是封装动态数组的顺序容器。动态数组，顾名思义，就是内存是动态的。他可以任意修改内存大小。但正是由于他的这一特性，既是优点，也是缺点。

众所周知，C系统申请空间时所消耗的时间受申请空间的大小影响不大，最大影响是申请次数。如何理解呢，例如，int arr[1e5], int arr[1]所消耗的时间差距不大，但如果你申请1e5次arr[1]，那么消耗的时间就是int arr[1e5]的1e5倍。如果看不懂没关系，结论就是，我们要尽量减少申请空间的次数，而增大每次申请的空间大小，以此提升性价比。

当我们有了以上概念的时候，我们就能明白，vector的缺点在哪里了。由于vector是动态数组，所以最开始空间是没有申请的，当你插入一个数，他就申请一个空间，删除一个数，就把多余的空间消耗掉。毫无疑问，大家都能想到的，如果我们插入1e5个数，或者删除1e5个数，就会申请1e5个空间，因此vector在实现的时候结构体里面做了一些优化，他不是一次只申请插入数的数量的空间，而是倍增申请。例如，假如最开始假设vector只有32个数的空间，此时里面有32个数，而当你再插入一个数，他申请的不是32个空间，而是直接把vector的空间个数扩大到64个。因此，对vector而言，在数组中插入一个数，他的时间复杂度是O(n)，而如果是在末尾插入或删除，那么他的时间复杂度是均摊常数O(1)。当然，vector支持随机访问，时间复杂度也是O(1)

2.为什么使用vector

他的缺点另一方面也是他的优点，他作为容器，里面可以放任意的类型，甚至可以vector套vector，同时，尽管空间申请会消耗很多时间，但正是由于空间动态，可以方便我们操作数组里面的元素，高精的实现就可以使用vector。当然，实话实说，我也不知道为什么，我只是看别人在用，偶尔想起来了我也用⊙︿⊙

3.vector定义

1.

vector<int> a;

 定义一个vector数组a，vector数组默认是空的

2.

vector<int> b(n);

定义一个有n个元素的vector数组，由于已经放入了n个元素，而且没有定义，所以里面的值是随机的

3.

vector<int> c(n, val);

定义了有n个元素的vector数组，且给出每个元素的初值为val

4.

vector<int> h[n];

vector数组，有n个vector，就像 int a[n]

5.

vector<int> d(b);

创建一个vector数组d，d里面的值直接由b赋值

6.

vector<int> e(b.begin(), b.begin() + 3);

创建一个vector数组，里面的值由b数组下标[0,3)的值赋值

7.

int f[7]={1,2,3,4,5,9,8};
vector<int> g(f, f + 7);

一个实际应用，从数组中获值也可以

4.成员函数

1.定义修改

a.assign(b.begin(), b.begin() + 3);
a.assign(n, val);
a.assign({1, 2, 3, 4});

第一个将b的0~2个元素构成的向量赋给a

第二个将a变成n份val，val的类型可以是任意的

第三个直接改变a的值，注意，不能写成其他类型的变量，比如 a.assign(b)是不可以的

需要注意的是，三者的时间复杂度都是O(n)

2.元素访问

a.at(pos);
a[pos];

两者等价，返回下标pos的值。如果pos >= size 会抛出异常

a.data();

指向底层元素存储的指针。对于非空容器，返回的指针与首元素地址比较相等。

若 size() 为 0 ，则 data() 可能返回或不返回空指针。

a.front();
a.back();

前者返回a的第一个元素  <=> *c.begin()

后者返回a的最后一个元素 <=> *std::prev(c.end())  在空容器上调用 back 导致未定义行为

3.迭代器

a.begin();
a.end();

前者返回指向首元素的迭代器。 若 vector 为空，则返回的迭代器将等于 end() 。

后者返回指向末元素后一元素的迭代器。此元素表现为占位符；访问它导致未定义行为。

注意，后者返回的是末尾元素的下一个元素的迭代器

a.cbegin();
a.cend();

同上，区别在于只能只读，不能用作修改值。意思就是你可以通过迭代器begin和end修改数组中的值，但是cbegin不可以

a.rbegin();
a.rend();

前者返回尾元素所在迭代器

后者返回首元素的上一个元素的迭代器。此元素表现为占位符，试图访问它导致未定义行为。

可以通过rbegin访问最后一个元素

a.crbegin();
a.crend();

4.容量

a.empty();

判断a是否为空，空则返回ture,不空则返回false  <=> begin() == end()

a.size();
distance(a.begin(), a.end());

两者含义相等。返回a中元素的个数

a.max_size();

反映容器大小上的理论极限

5.修改器

a.clear();

清空a中的元素

由于vector是动态数组，所以时间复杂度是O(n)

那么这里提供一个小技巧

a = vector<int> ();

使用这种方法也可以清空vector容器，同时我专门做过详细的实验，对于同样大小的vector数组大小，当vector容器的大小在[4e2, 5e2]的时候，两者消耗的时间几乎是一样的

而当小于这个区间的时候，前者的时间更快；大于这个区间的时候，后者的时间更快

a.insert(a.begin(), val);

a.insert(a.begin(), n, val);

a.insert(a.begin(), b.begin() + 1, b.begin() + 3);

a.insert(a.begin(), {1, 2, 3});

第一个在begin前插入val

第二个begin前插入n个val

第三个在begin前插入[b.begin + 1, begin + 3)的元素

第四个在begin前插入123

a.emplace(a.begin(), val);

C++11新特性，比insert更快。在begin前插入val。用法同insert(应该还有其他用法，但我翻遍了很多资料网站，都没有找到详细且清晰的介绍，因此就不提及那些模棱两可的用法了，当insert用就行)

a.erase(a.begin());
a.erase(a.begin(), a.end());

前者删除begin位置的元素

后者删除[begin,end)内的元素

a.push_back(val);
a.emplace_back(val);

两者含义等价，在末尾插入val。后者更快。当然，还是那句话，后者的其他用法我没研究的太懂，等后面研究明白了回来补齐

a.pop_back();

删除最后一个元素。在空容器上调用 pop_back 导致未定义行为

a.resize(n, val);

重设容器大小以容纳 n 个元素。

若当前大小大于 n ，则删除尾部多余元素。

若当前大小小于 n ，则后附额外的默认插入的元素，若val写成b，则添加b的副本

a.swap(b);
swap(a, b);

两者等价，交换ab

erase(a, val);
erase_if(a, cmp);

C++20语句

前者删除vector里所有等于val的元素

后者删除vector里所有满足cmp条件的元素。cmp是自写的一个判断函数，bool类型

5.其他语句

1.

sort(arr.begin(),arr.end());
sort(arr.begin(),arr.end(), greater<int>());

排序vector数组，默认从小到大，后者从大到小

2.

arr.erase(unique(arr.begin(),arr.end()),arr.end());

删除数组里面重复的元素，语句含义是

unique是把数组里面的重复元素移至数组后面

erase把那一部分删除

需要注意的是使用之前需要先排序

3.

reverse(a.begin(),a.end());

对a中的元素倒置

4.

copy(a.begin(),a.end(),b.begin()+1);

把a中的元素复制到b中，从b.begin()+1的位置（包括它）开始复制，覆盖掉原有元素

5.

find(a.begin(),a.end(),n);

在a中的的元素中查找n，若存在返回其在向量中的位置，返回的是迭代器

6.vector访问方法

1.下标访问

int a[6]={1,2,3,4,5,6};
vector<int> b(a, a + 4);
for(int i = 0;i <= b.size() - 1; i++)
    cout<<b[i]<<endl;

 但是需要注意的是，下标只能用来访问已经获取的元素。例如

vector<int> c;
for(int i=0;i<10;++i)
    c[i] = i;

是错误的

2.迭代器访问

for(vector<int>::iterator it=b.begin();it!=b.end();it++)
    cout<<*it<<" ";

3.C++11新特性，auto访问

for(auto x : b)
    cout << x << " ";