当前位置：首页 > news >正文

【C++】vector的模拟实现

news 2025/6/7 1:27:09

1. vector的模拟实现

template<class T>
class vector
{private:iterator _start = nullptr;// 指向数组的起始位置（第一个元素）iterator _finish = nullptr;// 指向数组的末尾位置（最后一个元素的下一个位置）iterator _end_of_storage = nullptr;// 指向已分配内存的末尾（容量的下一个位置）};
}

1.1 扩容reserve

（1）当需要分配的内存比原来内存的大的时候才选择扩容，否则不进行任何操作。

（2）首先开一个新空间，然后将原来空间的数据转移到新的空间，最后让成员变量指向新空间。

注意：这里的数据转移不能用memcpy，因为memcpy拷贝数据是一个字节一个拷贝的，当vector里面存放的是需要开辟资源的数据时候（如int*），memcpy是直接把资源的地址拷贝过去的，这样就会导致tmp在出了作用域以后将资源释放时，成员变量就变成了野指针。

		void reserve(size_t n){if (n > capacity()){size_t old_size = size();iterator tmp = new T[n];//memcpy的是浅拷贝// memcpy(tmp, _start, size() * sizeof(T));for (size_t i = 0; i < old_size; i++){tmp[i] = _start[i];}delete[] _start;_start = tmp;_finish = tmp + old_size;_end_of_storage = tmp + n;}}

1.2 尾插push_back

当没有内存的时候先进行扩容，扩容的时候建议2倍扩。

 		void push_back(const T& x){// 扩容if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;++_finish;}

1.3 尾删pop_back

	void pop_back(){assert(!empty());--_finish;}

1.4 size、capacity、empty、

		size_t size() const{return _finish - _start;}size_t capacity() const{return _end_of_storage - _start;}bool empty() const {return _start == _finish;}void clear(){_finish = _start;}

1.6 []重载

		T& operator[](size_t i){assert(i < size());return _start[i];}const T& operator[](size_t i) const{assert(i < size());return _start[i];}

1.7 迭代器

		typedef T* iterator;typedef const T* const_iterator;iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}

1.8 指定位置删除erase

将要删除的数据的后面数据前面移动一位，把要删除的数据覆盖掉就行了

		void erase(iterator pos){assert(pos >= _start);assert(pos < _finish);iterator it = pos + 1;while (it != end()){*(it - 1) = *it;++it;}--_finish;}

1.9 指定位置插入数据insert

（1）没有内存先进行扩容，pos应该更新到扩容后的位置。

（2）将插入位置和插入位置后面的数据全部向后移动一位，然后在指定位置插入数据就行了。

		iterator insert(iterator pos, const T& x){assert(pos >= _start);assert(pos <= _finish);if (_finish == _end_of_storage){//扩容了pos应该更新到扩容后的位置size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;return pos;}

1.10 调整容器大小resize

分两种情况讨论：

（1）当n<size()时，应该删除n之后的所有元素。容量不变，仅元素数量减少。

（2）当n>size()时，应该在原元素后新增元素，使容器大小达到n。新增元素用val初始化。若容量不足，会触发扩容。

	void resize(size_t n, T val = T()){if (n < size()){_finish = _start + n;}else{reserve(n);while (_finish < _start + n){*_finish = val;++_finish;}}}

1.11 拷贝构造

		vector(const vector<T>& v){reserve(v.size());for (auto& e : v){push_back(e);}}//写了任意的构造编译器将不会自动生成默认的构造，所以得自己写构造vector() = default;

1.12 迭代器区间初始化

		template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}

1.13 填充初始化

		vector(size_t n, const T& val = T()){//直接开够空间避免频繁扩容，降级效率性能reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}}

1.14 赋值重载

直接将形参v的空间换到过来，将原来的空间交给形参，当出了作用域形参将会带着原来的空间销毁，这样就省去了手动开空间和析构的步骤。

		void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}//赋值重载vector<T>& operator=(vector<T> v){clear();swap(v);return *this;}

1.15 析构

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

2. 完整代码：

namespace coder_vtr
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;//写了任意的构造编译器将不会自动生成默认的构造，所以得自己写一份vector() = default;//拷贝构造vector(const vector<T>& v){reserve(v.size());for (auto& e : v){push_back(e);}}//迭代器区间构造template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}vector(size_t n, const T& val = T()){reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}}//再写一个int类型的重载是因为在定义vector v(10,1)的时候c++规定这种数字默认是int类型// 编译器会调用“更合适”的迭代器区间构造导致编译报错vector(int n, const T& val = T()){reserve(n);for (int i = 0; i < n; i++){push_back(val);}}void clear(){_finish = _start;}void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}//赋值重载vector<T>& operator=(vector<T> v){swap(v);return *this;}	//析构~vector(){if (_start){delete[] _start;_start = _finish = _end_of_storage = nullptr;}}iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}void reserve(size_t n){if (n > capacity()){size_t old_size = size();iterator tmp = new T[n];//memcpy的是浅拷贝// memcpy(tmp, _start, size() * sizeof(T));for (size_t i = 0; i < old_size; i++){tmp[i] = _start[i];}delete[] _start;_start = tmp;_finish = tmp + old_size;_end_of_storage = tmp + n;}}// //n>size//size<n<capacity//n>capacityvoid resize(size_t n, T val = T()){if (n < size()){_finish = _start + n;}else{reserve(n);while (_finish < _start + n){*_finish = val;++_finish;}}}size_t size() const{return _finish - _start;}size_t capacity() const{return _end_of_storage - _start;}bool empty() const {return _start == _finish;}//尾插void push_back(const T& x){// 扩容if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;++_finish;}//尾删void pop_back(){assert(!empty());--_finish;}//插入iterator insert(iterator pos, const T& x){assert(pos >= _start);assert(pos <= _finish);if (_finish == _end_of_storage){//扩容了pos应该更新到扩容后的位置size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;return pos;}void erase(iterator pos){assert(pos >= _start);assert(pos < _finish);iterator it = pos + 1;while (it != end()){*(it - 1) = *it;++it;}--_finish;}T& operator[](size_t i){assert(i < size());return _start[i];}const T& operator[](size_t i) const{assert(i < size());return _start[i];}private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;};
}

查看全文

http://www.xdnf.cn/news/761311.html