【C++】模拟实现vector的核心框架接口

深藏阁楼爱情的钟 2023-07-15 15:16 2阅读 0赞

## vector介绍 ##

1.  vector是表示可变大小数组的序列容器。
2.  就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组,它的大小是可以动态改变的，而且它的大小会被容器自动处理。
3.  本质讲，vector使 用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。
4.  vector分配空间策略: vector会分配一些额外的空间以适应可能的增长 ，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
5.  因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。
6.  与其它动态序列容器相比(deques, lists and forward\_ lists)， vector在访问元素的时候更加高效, 在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起lists和 forward\_ists统一 的迭代器和引用更好。

## 完整代码 ##

#include<iostream>
    #include<algorithm>
    #include<assert.h>
    #include<string>
    using namespace std;
    
    namespace zd
    { 
    	template<class T>
    	class Vector
    	{ 
    	public:
    		//Vector的迭代器是一个原生指针
    		typedef T* Iterator;
    		typedef const T* constIterator;
    
    		Iterator begin()
    		{ 
    			return _start;
    		}
    
    		Iterator end()
    		{ 
    			return _finish;
    		}
    
    		constIterator CBegin() const
    		{ 
    			return _start;
    		}
    
    		constIterator CEnd() const
    		{ 
    			return _finish;
    		}
    
    		size_t Size()
    		{ 
    			return _finish - _start;
    		}
    
    		size_t Capacity()
    		{ 
    			return _endOfStorage - _start;
    		}
    
    		size_t Size() const
    		{ 
    			return _finish - _start;
    		}
    
    		size_t Capacity() const
    		{ 
    			return _endOfStorage - _start;
    		}
    
    		//构造函数
    		/*Vector() :_start(nullptr) , _finish(nullptr) , _endOfStorage(nullptr) {}*/
    		Vector() = default;
    
    		//拷贝构造
    		Vector(const Vector<T>& v)
    		{ 
    			size_t size = v.Size();
    			_start = new T[v.Capacity()];
    			//memset(_start, v._start, sizeof(T)*v.Size());
    			for (size_t i = 0; i < size; i++)
    			{ 
    				_start[i] = v._start[i];
    			}
    			_finish = _start + v.Size();
    			_endOfStorage = _start + v.Capacity();
    		}
    
    		/*Vector<T>& operator=(Vector<T> v) { size_t size = v.Size(); if (this != &v) { delete[] _start; _start = new T[v.Capacity()]; for (size_t i = 0; i < size; i++) { _start[i] = v._start[i]; } _finish = _start + v.Size(); _endOfStorage = _start + v.Capacity(); } return *this; }*/
    		Vector<T>& operator=(Vector<T> v)
    		{ 
    			this->Swap(v);
    			return *this;
    		}
    
    		void Swap(Vector<T> v)
    		{ 
    			std::swap(_start, v._start);
    			std::swap(_finish, v._finish);
    			std::swap(_endOfStorage, v._endOfStorage);
    		}
    
    		//析构函数
    		~Vector()
    		{ 
    			if (_start)
    			{ 
    				delete[] _start;
    				_start = _finish = _endOfStorage = nullptr;
    			}
    		}
    
    		//reverse()函数用于容器预留空间
    		void Reserve(size_t n)
    		{ 
    			size_t size = Size();
    			if (n > Capacity())
    			{ 
    				T* tmp = new T[n];
    				if (_start)
    				{ 
    					for (size_t i = 0; i < size; i++)
    					{ 
    						tmp[i] = _start[i];
    					}
    				}
    				_start = tmp;
    				_finish = _start + size;
    				_endOfStorage = _start + n;
    			}
    		}
    
    		//改变容器的大小，并创建对象
    		void Resize(size_t n, const T& value = T())
    		{ 
    			if (n <= Size())
    			{ 
    				_finish = _start + n;
    				return;
    			}
    			else
    			{ 
    				if (n > Capacity())
    				{ 
    					Reserve(n);
    				}
    				while (_finish != _start + n)
    				{ 
    					*_finish = value;
    					_finish++;
    				}
    			}
    		}
    
    		void PushBack(const T& x)
    		{ 
    			/*if (_finish == _endOfStorage) { size_t newcapacity = Capacity() == 0 ? 2 : Capacity() * 2; Reserve(newcapacity); } *_finish = x; _finish++;*/
    			Insert(end(), x);
    		}
    
    		void PopBack()
    		{ 
    			assert(Size() > 0);
    			--_finish;
    			/*Erase(--End());*/
    		}
    
    		void Insert(Iterator pos, const T& x)
    		{ 
    			assert(pos <= _finish);
    			size_t len = pos - _start;
    			if (_finish == _endOfStorage)
    			{ 
    				size_t newcapacity = Capacity() == 0 ? 2 : Capacity() * 2;
    				Reserve(newcapacity);
    				pos = _start + len;
    			}
    			Iterator end = _finish;
    			while (end > pos)
    			{ 
    				*end = *(end - 1);
    				--end;
    			}
    			*pos = x;
    			_finish++;
    		}
    
    		//返回删除数据的下一个数据
    		//方便解决：一边遍历一边删除的迭代器失效问题
    		void Erase(Iterator pos)
    		{ 
    			assert(pos <= _finish);
    			//挪动数据进行删除
    			Iterator begin = pos + 1;
    			while (begin < _finish)
    			{ 
    				*(begin - 1) = *begin;
    				++begin;
    			}
    			_finish--;
    		}
    
    		T& operator[](size_t pos)
    		{ 
    			assert(pos < Size());
    			return _start[pos];
    		}
    
    		const T& operator[](size_t pos) const
    		{ 
    			assert(pos < Size());
    			return _start[pos];
    		}
    
    	private:
    		Iterator _start = nullptr;    //nullptr是缺省值
    		Iterator _finish = nullptr;
    		Iterator _endOfStorage = nullptr;
    	};
    
    	void VectorTest1()
    	{ 
    		Vector<int> v1;
    		v1.PushBack(1);
    		v1.PushBack(2);
    		v1.PushBack(3);
    		v1.PushBack(4);
    		v1.PushBack(5);
    
    		for (size_t i = 0; i < v1.Size(); i++)
    		{ 
    			cout << v1[i] << " ";
    		}
    		cout << endl;
    
    		v1.Resize(3);
    		Vector<int>::Iterator it1 = v1.begin();
    		while (it1 != v1.end())
    		{ 
    			cout << *it1 << " ";
    			++it1;
    		}
    		cout << endl;
    
    		v1.PopBack();
    		Vector<int>::Iterator it2 = v1.begin();
    		while (it2 != v1.end())
    		{ 
    			cout << *it2 << " ";
    			++it2;
    		}
    		cout << endl;
    
    		v1.Resize(10, 1);
    		for (auto e : v1)
    		{ 
    			cout << e << " ";
    		}
    		cout << endl;
    	}
    
    	void VectorTest2()
    	{ 
    		Vector<int> v2;
    		v2.PushBack(1);
    		v2.PushBack(2);
    		v2.PushBack(3);
    		v2.PushBack(4);
    		v2.PushBack(5);
    
    		auto pos = std::find(v2.begin(), v2.end(), 3);
    		if (pos != v2.end())
    		{ 
    			v2.Insert(pos, 0);
    		}
    		for (size_t i = 0; i < v2.Size(); i++)
    		{ 
    			cout << v2[i] << " ";
    		}
    		cout << endl;
    
    		pos = std::find(v2.begin(), v2.end(), 3);
    		v2.Erase(pos);
    		for (size_t i = 0; i < v2.Size(); i++)
    		{ 
    			cout << v2[i] << " ";
    		}
    		cout << endl;
    	}
    
    	void VectorTest3()
    	{ 
    		Vector<int> v3;
    		v3.PushBack(1);
    		v3.PushBack(2);
    		v3.PushBack(3);
    		v3.PushBack(4);
    		v3.PushBack(5);
    
    		Vector<int> copy = v3;  //拷贝构造 相当于copy(v3)
    		for (size_t i = 0; i < copy.Size(); i++)
    		{ 
    			cout << copy[i] << " ";
    		}
    		cout << endl;
    
    		Vector<int> v4;
    		v4.PushBack(1);
    		v4.PushBack(2);
    		v4.PushBack(3);
    		for (size_t i = 0; i < v4.Size(); i++)
    		{ 
    			cout << v4[i] << " ";
    		}
    		cout << endl;
    
    		v4 = v3;
    		for (size_t i = 0; i < v4.Size(); i++)
    		{ 
    			cout << v4[i] << " ";
    		}
    		cout << endl;
    	}
    
    	void VectorTest4()
    	{ 
    		Vector<char*> v5;
    		v5.PushBack("111");
    		v5.PushBack("222");
    		v5.PushBack("333");
    		v5.PushBack("444");
    		for (size_t i = 0; i < v5.Size(); i++)
    		{ 
    			cout << v5[i] << " ";
    		}
    		cout << endl;
    	}
    }
    
    int main()
    { 
    	zd::VectorTest1();
    	zd::VectorTest2();
    	zd::VectorTest3();
    	zd::VectorTest4();
    	return 0;
    }