【C++】vector类模拟实现

【C++】vector类模拟实现 命由己造～ 于2022-10-12 19:57:55发布 707 收藏 60 分类专栏： C++ 文章标签： c++ 算法 C++ 专栏收录该内容 9 篇文章 1 订阅 订阅专栏

vector类模拟实现 一、vector类的成员变量二、vector类的接口实现2.1 构造函数2.2 析构函数2.3 size和capacity2.4 扩容2.4.1 reserve扩容2.4.2 resize扩容 2.5 尾插2.6 尾删2.7 []重载2.8 迭代器和const迭代器2.9 拷贝构造2.9.1 现代写法2.9.1.1 迭代器版构造函数❗️❗️2.9.1.2 迭代器的分类❗️❗️ 2.10 赋值拷贝2.10.1 现代写法 2.11 插入2.12 删除

一、vector类的成员变量

跟以前的成员变量不同，vector的成员变量为：

iterator _start;// 数据开始 iterator _finish;// 数据结束 iterator _endofstorage;// 空间结尾

iterator是typedef出来的：

typedef T* iterator;

三个成员变量的含义： _start指向数据的开始，_finish指向结束位置的下一个位置，_endofstorage指向整个空间的最后。

二、vector类的接口实现 2.1 构造函数 // 构造函数 vector() : _start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) {} 2.2 析构函数 ~vector() { if (_start) { delete[]_start; _finish = _endofstorage = _start = nullptr; } } 2.3 size和capacity size_t size() const { return _finish - _start; } size_t capacity() const { return _endofstorage - _start; }

指针相减就代表中间的数据个数

2.4 扩容 2.4.1 reserve扩容 void reserve(size_t n) { if (n < size()) { _finish = _start + n; } else { if (n > capacity()) { size_t sz = size(); T* tmp = new T[n]; if (_start) { //memcpy(tmp, _start, sizeof(T) * sz); 不能这么写 for (size_t i = 0; i < sz; i++) { tmp[i] = _start[i]; } delete[]_start; } _start = tmp; _finish = _start + sz; _endofstorage = _start + n; } } }

需要注意的细节： 1️⃣ 初始空间的大小要提前保存（新空间size会改变） 2️⃣ 要注意改变三个成员函数 3️⃣不能使用memcpy（浅拷贝）

假设现在定义一个vector<string>的类：

当我们扩容需要拷贝时，如果使用memcpy就会发生这种情况： 调用析构函数就会引发崩溃

2.4.2 resize扩容

resize跟reserve比起来就多了一个初始化。

void resize(size_t n, const T& val = T())// 匿名对象 { if (n < size()) { _finish = _start + n; } else { if (n > capacity()) { reserve(n); } while (_finish != _endofstorage) { *_finish = val; _finish++; } } }

要注意的是单独使用T()时，当前行结束就会自动调用销毁。而使用const T& val = T()就可以延长生命周期。

2.5 尾插 void push_back(const T& x) { if (_finish == _endofstorage) { // 扩容 reserve(capacity() == 0 ? 4 : 2 * capacity()); } *_finish = x; _finish++; } 2.6 尾删 void pop_back() { assert(size() > 0); _finish--; } 2.7 []重载 T& operator[](size_t pos) { assert(pos < size()); return _start[pos]; } const T& operator[](size_t pos) const { assert(pos < size()); return _start[pos]; } 2.8 迭代器和const迭代器 iterator begin() { return _start; } const_iterator begin() const { return _start; } iterator end() { return _finish; } const_iterator end() const { return _finish; } 2.9 拷贝构造 // 拷贝构造 vector(const vector<T>& x) { _start = new T[x.capacity()]; _finish = _start; _endofstorage = _start + x.capacity(); // 拷贝 for (size_t i = 0; i < x.size(); i++) { *_finish = x[i]; _finish++; } } 2.9.1 现代写法

要写现代写法我们首先需要构造一个临时的vector类然后交换，而我们现在的构造函数没有参数，所以我们要再写一个构造函数。

2.9.1.1 迭代器版构造函数❗️❗️ template <class InputIterator> vector(InputIterator first, InputIterator last) : _start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) { while (first != last) { push_back(*first); first++; } }

我们可以看到这种迭代器以前没有见过：

2.9.1.2 迭代器的分类❗️❗️

迭代器有很多类型： 只读迭代器：input_iterator 只写迭代器：output_iterator 单向迭代器：forward_iterator只能++操作 双向迭代器： bidirectional_iterator支持++和--操作 随机迭代器：randomAccess_iterator支持++、--、+=、-=、等操作， 访问任意位置

继承关系：

接下来就可以写现代写法的拷贝构造了：

void swap(vector<T>& v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_endofstorage, v._endofstorage); } // 现代写法 // v1(v2) vector(const vector<T>& x) : _start(nullptr) , _finish(nullptr) , _endofstorage(nullptr) { vector<T> tmp(x.begin(), x.end()); swap(tmp); } 2.10 赋值拷贝 vector<T>& operator=(const vector<T>& x) { for (size_t i = 0; i < x.size(); i++) { push_back(x[i]); } return *this; }

赋值拷贝跟拷贝构造的区别是：

赋值拷贝是把一个类赋值给另一个已经构造好的类，而拷贝构造是创建出一个新的类并赋值。

2.10.1 现代写法 //现代写法 vector<T>& operator=(vector<T> x) { swap(x); return *this; } 2.11 插入 iterator insert(iterator pos, const T& val) { assert(pos <= _finish); assert(pos >= _start); if (size() == capacity()) { // 扩容 size_t len = pos - _start; reserve(capacity() == 0 ? 4 : 2 * capacity()); pos = _start + len; } // 移动数据 iterator cur = end() - 1; while (cur >= pos) { *(cur + 1) = *cur; cur--; } *pos = val; _finish++; return pos; }

为什么要用迭代器当返回值？

插入可能改变空间，导致迭代器失效。

2.12 删除 iterator erase(iterator pos) { assert(pos >= _start); assert(pos <= _finish); assert(size() > 0); iterator del = pos; while (del != end()) { *del = *(del + 1); del++; } _finish--; return pos; }

为什么要用迭代器当返回值？

有的删除可能会缩容，导致迭代器失效。