数组的特点:在内存中是连续存放的
基于这个特点我们就可以分析一下数组的优缺点
1.优点
下标访问(随机访问)时间复杂度是O(1)。注意是下标访问，不是for循环查询某个元素
末尾位置增加删除元素时间复杂度是O(1)。末尾位置不用进行增减不会对数据进行移动，所以对数组末尾的操作很方便
访问元素前后相邻位置的元素非常方便。只需对下标进行加减操作就能轻松访问
2.缺点
非末尾位置增加删除元素需要进行大量的数据移动
3.搜索的时间复杂度
无序数组-线性搜索O(n)
有序数组-二分搜索O(logn)
数组扩容消耗比较大
vector容器的实现
vector的底层数据结构就是一个动态数组，既然是动态的了那么我们就要在堆上new一个数组内容了
实现一个数组需要三个参数，一是指向堆中动态数组的地址的指针 int *pArr，二是这个动态数组的大小（容量）aCap，三是这个动态数组里面实际上存放了多少个数据 aNum，比如你设置了100个数据的空间，但是里面只存放了20个数据,那么aCap就是100，aNum就是20了
代码：
#include <windows.h>
#include <iostream>class Arrary {
public://构造函数用来初始化数组的值,可以传入size指定数组的大小，默认值为10Arrary(int size = 10) :aNum(0), aCap(size){ //一开始元素个数设为0，容量大小为sizepArr = new int[aCap];}~Arrary() {delete[]pArr;pArr = nullptr;}
public://末尾增加元素void push_back(int val) {//首先要判断一下内存空间够不够，不够就要扩容if (aNum = aCap) {expand(2 * aCap); }pArr[aNum++] = val; //aNum++是先用再加，效果和pArr[aNum] = val; aNum++ 一样}//末尾删除元素void pop_back() {if (aNum == 0) return;aNum--;}//指定位置添加元素void insert(int pos, int val) {//首先要判断插入位置是否有效if (pos < 0 || pos > aNum) return;//然后如果插入的时候容量不够，就要扩充if (aCap == aNum) {expand(aCap * 2);}for (int i = aNum; i > pos; i--) {pArr[i] = pArr[i--]; }pArr[pos] = val;aNum++;}//按位置删除元素void earse(int pos) {if (pos < 0 || pos >= aNum) {return;}for (int i = pos; i < aNum-1; i++) {pArr[i] = pArr[i++];}aNum--;}//元素查询int find(int val) {for (int i = 0; i < aNum; i++) {if (pArr[i] == val) return i;}return -1; }private:void expand(int size) {//扩容的思想是在堆空间定义一块新的内存，这块内存是旧的内存空间的俩倍，再把旧的内存元素复制过来int *p = new int[size];memcpy(p, pArr, sizeof(int) * aCap); delete[] pArr;pArr = p;aCap = size;}private:int* pArr;int aCap;int aNum;
};
