vector的简单实现

目录

vector的结构 

构造和析构 

 迭代器和容量相关的函数

扩容 

插入和删除

尾插和尾删 

 任意插入和任意删除

重载下标引用操作符和赋值运算符

operator=

operatro[ ]

---

vector的结构 

vector是一个类模板

	template<typename T>class vector{public:typedef T* iterator;typedef const T& const_iterator;	private:iterator _start = nullptr;iterator _end_of_sortage = nullptr;iterator _finish = nullptr;};

通过_start,_end_of_sortage,_finish这三个指针来控制vector

构造和析构 

构造

		vector() = default;//使编译器自动生成默认构造函数vector(size_t n,const T& val = T()){_start = new T[n];for (int i = 0; i < n; i++){_start[i] = val;}_finish = _end_of_sortage = _start + n;}vector(const vector<T>& v)//拷贝构造{size_t len = v.size();iterator tmp = new T[len];memcpy(tmp, v._start, sizeof(T)*len);delete[] _start;_start = tmp;_end_of_sortage = _finish = _start + len;}

注意这里的拷贝构造是深拷贝，需要先开辟空间，再将要拷贝的vector的数据，拷贝进新开辟的空间。

析构

		~vector(){delete[] _start;_finish = _end_of_sortage = nullptr;}

释放开辟的资源

 迭代器和容量相关的函数

		size_t size(){return _finish - _start;//两个指针相减结果是两指针之间元素的个数}size_t capacity(){return _end_of_sortage - _start;}size_t size()const{return _finish - _start;}size_t capacity()const{return _end_of_sortage - _start;}iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin()const{return _start;}const_iterator end()const{return _finish;}

扩容 

		void reverse(size_t n){if (n > capacity()){int oldsize = size();//记录原来的开辟空间的大小iterator tmp = new T[n];memcpy(tmp, _start, sizeof(T) * oldsize);//将原来的数据拷贝进新开辟的空间delete[] _start;_start = tmp;_finish = tmp + oldsize;_end_of_sortage = _start + n;}}

插入和删除

尾插和尾删 

		void push_back(const T& x)//尾插{//考虑是否需要扩容if (size() == capacity()){reverse(2 * capacity());}*_finish = x;_finish++;}void pop_back()//尾删{assert(size() > 0);_finish--;}

 任意插入和任意删除

		//iterator insert(iterator pos, const T& x){//看是否需要扩容if (size() == capacity()){reverse(2 * capacity());}iterator end1 = end()-1;//将pos位置及其以后位置的元素整体向后挪一位while (end1 != pos+1){*(end1+1) = *end1;end1--;}*(pos+1) = x;_end_of_sortage++;return pos+1;}iterator erase(iterator pos){iterator cur = pos;//将pos之后的所有元素整体向前挪一位while(cur!=end()-1){*cur = *(cur + 1);cur++;}_end_of_sortage--;return pos;}

注意insert和erase的返回值都是迭代器。

为什么会返回迭代器？

因为当插入或删除一个数据后，可能会导致迭代器失效的问题。

	vector<int> v = { 1,2,3,4,5,6,7 };vector<int>::iterator it = v.begin();vector<int>::iterator end = v.end();while (it != end){if (*it == 3)v.erase(it);//删除一个3这个数据就会导致end指向的位置不在是vector容器的末尾end失效cout << *it << " ";}

 解决办法就是

	while (it != v.end())//实时更新{if (*it == 3)v.erase(it);cout << *it << " ";}

重载下标引用操作符和赋值运算符

operator=

		//原始写法vector<T>& operator=(const vector<T>& v){reverse(v.capacity());memcpy(_start, v._start, sizeof(T) * v.size());_end_of_sortage = _start + v._size();//_finish = _start + v.capacity;return *this;}		//现代写法vector<T>& operator=(const vector<T> v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_sortage, v._end_of_sortage);return *this;}

operatro[ ]

		T& operator[](size_t pos){assert(pos >= 0 && pos < size());return _start[pos];}

注意对下标的检查，下标不能越界访问。

完整代码在gitee：

刷题记录: 用来调试刷题是写的代码 (gitee.com)