C++模拟如何实现vector
目录
- 一、迭代器
- 定义
- 普通迭代器
- const类型迭代器
- 二、构造类
- 构造函数
- 拷贝构造函数
- 赋值运算符重载
- 析构函数
- 三、容量相关操作
- size、capacity
- empty
- resize
- reserve
- 三、元素访问
- [ ]重载
- front
- back
- 四、修改类接口
- push_back
- pop_back
- insert
- erase
- clear
- swap
- 五、成员变量
- 总结
一、迭代器
定义
vector类型的迭代器就是原生态的指针,对T*进行重命名即可
typedef T* iterator; typedef const T* const_iterator;
普通迭代器
iterator begin() { return start; } iterator end() { return finish; }
const类型迭代器
const类型迭代器可以访问const成员变量
const iterator cbegin()const { return start; } const iterator cend()const { return finish; }
二、构造类
构造函数
构造空对象
在初始化列表中对三个成员变量进行初始化
vector() :start(nullptr) , finish(nullptr) , endOfStorage(nullptr) {}
n个T类型
开辟空间以后,对finish进行自增,在空间填充元素
vector(size_t n, const T& value = T()) :start(new T[n]) , finish(start) , endOfStorage(start + n) { for (int i = 0; i < n; i++) { *finish++ = value; } }
重载前一个构造函数,将第一个参数设置为int类型
vector(int n, const T& value = T()) :start(new T[n]) , finish(start) , endOfStorage(start + n) { for (int i = 0; i < n; i++) { *finish++ = value; } }
之所以要对这种类型的构造函数进行重载,是因为在调用构造函数时,如果实参传两个整型数字,编译器会默认为int类型数据,进行推演之后与前面的size_t类型不匹配,则会调用下面的区间构造的方法,导致程序报错,如图:
迭代器构造
将构造方法中迭代器的类型写成模板类型,这样便可以接收其它类型的迭代器,如:T类型为char,Iterator迭代器为string类型,便可以从字符串中截取字符,构造vector<char>类型的对象。
//写成函数模板,可以接受任意类型的迭代器 template<typename Iterator> vector(Iterator first, Iterator last) { size_t n = ZH::distance(first, last);//获取长度 start = new T[n]; finish = start; endOfStorage = start + n; while (first != last){ *finish = *first; first++; finish++;//完成赋值的同时也移动了finish的位置 } }
将distance方法写到另一个.hpp头文件中
template<typename Iterator> //此处的Iterator是模板参数,表示可以传任意类型的迭代器 size_t distance(Iterator first, Iterator last) { //获取元素个数,暂时只考虑底层空间连续的情况 int count = 0; while (first != last) { first++; count++; } return count; }
拷贝构造函数
拷贝构造函数的形参必须是const类对象的引用,必须使用const类型的迭代器才能访问,复用迭代器构造的方法定义一个临时变量temp,交换temp与当前对象
//此处拷贝构造函数的形参是const类型 vector(const vector<T>& v) :start(nullptr) , finish(nullptr) , endOfStorage(nullptr) { //▲用const类型的迭代器访问const变量 vector<T> temp(v.cbegin(), v.cend()); this->swap(temp); }
赋值运算符重载
形参设置为类类型对象,调用赋值运算符重载函数时,形参会拷贝实参,交换当前对象与形参的值。
vector<T>& operator=(const vector<T> v) { this->swap(v); return *this; }
析构函数
释放空间,将三个迭代器赋值为空
~vector() { delete[]start; start = nullptr; finish = nullptr; endOfStorage = nullptr; }
三、容量相关操作
size、capacity
size_t size() { return finish - start; } size_t capacity() { return endOfStorage - start; }
empty
判断fiinsh与start是否相等即可,相等则为空
size_t empty() { return finish == start; }
resize
定义一个变量保存旧的size的值‘判断是减小还是增加size;判断是否需要扩容,需要则调用reserve函数,从旧空间的结束位置开始,给新增加的空间填充元素;最后改变finish的值。
void resize(size_t newsize, const T& value = T()) { size_t oldsize = size(); if (newsize > oldsize){ if (newsize > capacity()){ reserve(newsize); } for (size_t i = oldsize; i < newsize; i++) { start[i] = value; } } finish = start + newsize;//不用考虑增加或减小 }
reserve
reserve的步骤:申请新空间,拷贝旧空间的元素,释放旧的空间。
void reserve(size_t newcapacity) { size_t oldcapacity = capacity(); if (newcapacity > oldcapacity) { size_t n = size();//保存size()的值 T* temp = new T[newcapacity]; //start不为空时才进行拷贝旧空间元素和释放的操作 if (start) { //memcpy浅拷贝,当vector中存放的对象内部设计资源管理 // 会有内存泄漏和野指针问题 //memcpy(temp, start, sizeof(T) * n); for (size_t i = 0; i < n; i++) { temp[i] = start[i];//调用赋值运算符重载 } delete[] start; } start = temp; //▲此处不能用satart+size(),因为size方法中有finish-start,而start值已经改变 finish = start + n; endOfStorage = start + newcapacity; } }
▲易错点:
- 判断start的值是否为空 ,如果原来的start为空,则不需要再拷贝元素和释放
- 浅拷贝问题
finish更新问题
size()的方法内部finish-start,而此时start已经发生改变,finish还是旧的,所以要提前定义一个临时变量保存size()的值
三、元素访问
[ ]重载
重载成普通类型和const类型,const类型可以访问const成员
T& operator[](size_t index) { assert(index < size()); return start[index]; } const T& operator[](size_t index)const { assert(index < size()); return start[index]; }
front
返回动态数组第一个元素
T& front() { return start[0]; } const T& front()const { return start[0]; }
back
返回最后一个位置前一个元素
T& back() { return *(finish - 1); } const T& back()const { return *(finish - 1); }
四、修改类接口
push_back
插入前先判断空间是否已满,空间若满则进行扩容,扩容时,要原来的空间容量为0的情况;将value放置到末尾位置,并将finish向后移动一个单位
void push_back(const T& value) { if (finish == endOfStorage) { //因为原来的capacity可能为0,所以要+3 reserve(capacity() * 2 + 3); } *finish++ = value; }
pop_back
尾删,先判断对象是否为空,若不为空则将finish位置前移一个单位
void pop_back() { if (empty()) { return; } finish--; }
insert
任意位置插入,insert的返回值为新插入的第一个元素位置的迭代器;因为插入可能会进行扩容,导致start的值改变,所以先定义一个变量保存pos与start的相对位置;判断是否需要扩容;从插入位置开始,将所有元素向后搬移一个位置;将pos位置的值置为要插入的值;更新finish的值。
//第二个参数用const修饰,常量引用 //不用const修饰则为非常量引用 iterator insert(iterator pos, const T& value) { int index = pos - start; assert(pos >= start && pos < finish); //判断空间是否足够 if (finish == endOfStorage) { reserve(capacity() * 2); } pos = start + index; for (auto it = finish; it > pos; it--) { *it = *(it - 1); } *pos = value; finish++; return pos; }
erase
判断下标合法性;从pos位置下一个位置开始,将所有元素向前搬移一个位置;更新finish的值
iterator erase(iterator pos) { assert(pos >= start && pos < finish); auto it = pos; while (it < finish - 1) { *it = *(it + 1); it++; } finish--; return pos; }
clear
清空所有元素,令finish=start即可
void clear() { finish = start; }
swap
vector内置的swap函数,调用标准库中的swap交换vector的三个成员变量的值
void swap(vector<T>& v) { std::swap(start, v.start); std::swap(finish, v.finish); std::swap(endOfStorage, v.endOfStorage); }
五、成员变量
private: iterator start; iterator finish; iterator endOfStorage;
vector内部有三个成员变量,start表示起始位置,finish表示有效元素的末尾位置,endOfStorage表示空间的末尾位置;通过这三个成员变量可以得到size和capacity等值,如图:
总结
以上为个人经验,希望能给大家一个参考,也希望大家多多支持我们。