c++中数组的特点，vector容器的实现（增删改查各个接口的实现）

数组的特点:在内存中是连续存放的

基于这个特点我们就可以分析一下数组的优缺点

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指定数组的大小，默认值为10
	Arrary(int size = 10) :aNum(0), aCap(size){ //一开始元素个数设为0，容量大小为size
		pArr = 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;
};