石家庄快速网站搭建,国内永久免费建站,哈尔滨市招投标信息网,网站建设优化去哪学✨✨ 欢迎大家来到贝蒂大讲堂✨✨ #x1f388;#x1f388;养成好习惯#xff0c;先赞后看哦~#x1f388;#x1f388; 所属专栏#xff1a;C学习 贝蒂的主页#xff1a;Betty’s blog 为了让我们更加深入理解vector#xff0c;接下来我们将模拟实现一个简易版的vect… ✨✨ 欢迎大家来到贝蒂大讲堂✨✨ 养成好习惯先赞后看哦~ 所属专栏C学习 贝蒂的主页Betty’s blog 为了让我们更加深入理解vector接下来我们将模拟实现一个·简易版的vector。而为了和STL库中的vecotr以示区分我们将使用命名空间namespace对其封装。
1. vector的成员变量
vector的底层其实就是我们之前在数据结构学习的顺序表但是与顺序表不同的是vector的成员变量是三个迭代器也可以说是三个指针。
下面是vector的成员变量
namespace betty
{templateclass Tclass vector {public://...private:iterator _start;iterator _finish;iterator _end_of_storage;};
}其中start指向起始位置_finish指向有效数据末尾的后一个位置最后_end_of_storage指向容量大小末尾的后一个位置。 2. vector的成员函数
在知道vector的成员变量之后接下来我们将探究vector的成员函数而常见成员函数的用法我们早在之前就已经介绍过了 下面我们将来具体实现一下
2.1. vector的迭代器
首先我们来模拟实现一下迭代器iterator而在vector中迭代器iterator与string中的迭代器类似就是一个指针。所以我们直接使用typedef实现
typedef char* iterator;//普通迭代器
typedef const char* const_iterator;//const迭代器接下来我们来实现begin()与end()其中begin()指向的是数组的起始位置即_start而end指向有效长度最后的下一位即_finish的位置。
iterator begin()
{return _start;
}iterator end()
{return _finish;
}实现完普通迭代器之后我们可以顺便重载一个const_iterator的版本。
const_iterator begin() const
{return _start;
}const_iterator end() const
{return _finish;
}我们知道在vector中还有一个反向迭代器这个我们在之后会统一实现。
2.2. vector的初始化与销毁
2.2.1. 构造函数与拷贝构造
我们之前在学习vector时知道其初始化方式有很多可以通过默认构造函数给其初始化n个val初始化也可以通过迭代器初始化。
首先我们写一个默认构造函数将其所有变量都设为空。
vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr)
{;
}接下来我们来实现迭代器初始化而因为我们可以通过其他容器的迭代器对其初始化所以要通过模版来实现。
templateclass InputIterator
vector(InputIterator first, InputIterator last)
{while (first ! last){push_back(*first);first;}
}最后我们来实现n个val初始化。
vector(size_t n, const T val T())
{resize(n, val);
}
vector(int n, const T val T())
{resize(n, val);
}至于为什么要同时重载int与size_t两种不同类型那是为了防止在传两个int类型的参数时被编译器交给模版InputIterator识别然后报错。
拷贝构造也十分简单直接拷贝就行但是也有一些注意事项。
vector(const vectorT v)
{_start new T[v.capacity()];//开辟capacity的空间for (size_t i 0; i v.size(); i){_start[i] v._start[i];//进行深拷贝}_finish _start v.size();//更新_finish_end_of_storage _start v.capacity();//更新_end_of_storage
}这里注意不能利用memcpy()等库函数进行拷贝因为这些函数都是进行的浅拷贝。如果模版参数T是stringvector等自定义类型当程序结束回收内存时就会发生内存错误。 当然我们也可以通过一个取巧的方式来实现拷贝构造。
vector(vectorint v)
{// 根据v的capacity()去开出对应的空间reserve(v.capacity());//进行深拷贝for (size_t i 0; i v.size(); i){push_back(v[i]);}
}首先通过构造出一个与数组相同的数组v然后让this所指向的数组与其交换这样出了作用域之后销毁的就是原this所指向的数组。当然我们必须先将this所指向的数组先初始化扩容。
2.2.2. 赋值重载与析构函数
赋值运算符重载与拷贝构造的实现就非常类似了直接实现即可。
vectorT operator (vectorT v)
{swap(v);return *this;
}最后我们实现析构函数只需要清理资源即可
~vector()
{delete[]_start;_start _finish _end_of_storage nullptr;
}2.3. vector的容量操作
2.3.1. 有效长度与容量大小
首先我们先实现返回数组有效长度的size() 与容量大小的capacity()。并且为了适配const对象最后用const修饰this指针。
size_t size() const
{return _finish - _start;
}
size_t capacity() const
{return _end_of_storage - _start;
}2.3.2. 容量操作
接下来我们来实现扩容函数reserve()与·resize()其中reserve()最简单只要新容量大于旧容量就发生扩容其中注意需要提前记录size大小防止数组异地扩容原数组释放之后找不到原数组大小。
void reserve(size_t n)
{//提前原本记录长度size_t sz size();if (n capacity()){T* tmp new T[n];if (_start){//深拷贝for (size_t i 0; i size(); i){tmp[i] _start[i];//赋值重载}delete[]_start;}_start tmp;_finish _start sz;_end_of_storage _start n;}
}而resize()的逻辑就比较复杂需要分三种情况讨论。设字符串原来有效长度为size容量为capacity新容量为n 当nsize时resize会删除有效字符到指定大小。当sizencapcity时resize会补充有效字符(默认为0)到指定大小。当ncapacity时resize会补充有效字符(默认为0)到指定大小。 void resize(size_t n,const TvalT())
{if (n size()){//更新数组大小_finish _start n;}else{//扩容reserve(n);while (_finish ! _start n){*_finish val;_finish;}}
}2.4. vector的访问操作
为了符合我们C语言访问数组的习惯我们可以先重载operator[]。当然我们也要提供两种不同的接口可读可写与可读不可写。并且使用引用返回减少不必要的拷贝。
// 可读可写
T operator[](size_t pos)
{assert(pos size());return _start[pos];
}
// 可读不可写
T operator[](size_t pos)const
{assert(pos size());return _start[pos];
}同理我们也可以实现front()与back()函数。
// 可读可写
char front()
{return _start[0];
}
char back()
{return _start[_size() - 1];
}
// 可读不可写
const char front()const
{return _start[0];
}
const char back()const
{return _start[_size() - 1];
}2.5. vector的修改操作
2.5.1. 常见的修改操作
首先我们将实现两个常用的修改函数push_back()与pop_back()。
void push_back(const T x)
{//判断是否扩容if (_finish _end_of_storage){size_t newCapacity capacity() 0 ? 4 : 2 * capacity();reserve(newCapacity);}*_finish x;_finish;
}
void pop_back()
{--_finish;
}随后我们来实现数组的交换swap()函数我们知道vector的交换其实就是指针_start_finish_end_of_storage的交换。
void swap(vectorT v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);
}2.5.2. 迭代器失效
接下来我们实现insert()与erase()两个函数。其中insert()在插入时可能扩容这时就需要记录起始长度方便更新迭代器返回。
iterator insert(iterator pos, const T x)
{assert(pos _finish pos _start);//检查是否扩容if (_finish _end_of_storage){//先记录长度size_t len pos - _start;size_t newCapacity capacity() 0 ? 4 : capacity() * 2;reserve(newCapacity);//更新迭代器指向新空间pos _start len;}//往后覆盖iterator end _finish;while (end pos){*end *(end - 1);--end;}*pos x;_finish;return pos;
}同样的为了防止迭代器失效需要返回新的迭代器。
iterator erase(iterator pos)
{assert(pos _start pos _finish);iterator end pos 1;while (end ! _finish){*(end - 1) *end;end;}--_finish;return pos;
}3. 源码
#pragma once
namespace betty
{templateclass Tclass vector{public:typedef T* iterator;typedef const T* const_iterator;vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){;}vector(size_t n, const T val T()){resize(n, val);}vector(int n, const T val T()){resize(n, val);}templateclass InputIteratorvector(InputIterator first, InputIterator last){while (first ! last){push_back(*first);first;}}//vector(const vectorT v)//{// _start new T[v.capacity()];//开辟capacity的空间// for (size_t i 0; i v.size(); i)// {// _start[i] v._start[i];//循环拷贝// }// _finish _start v.size();//更新_finish// _end_of_storage _start v.capacity();//更新_end_of_storage//}vector(vectorint v){// 根据v的capacity()去开出对应的空间reserve(v.capacity());//进行深拷贝for (size_t i 0; i v.size(); i){push_back(v[i]);}}vectorT operator(vectorT v){swap(v);return *this;}iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin()const{return _start;}const_iterator end()const{return _finish;}size_t size() const{return _finish - _start;}size_t capacity() const{return _end_of_storage - _start;}void reserve(size_t n){//提前原本记录长度size_t sz size();if (n capacity()){T* tmp new T[n];if (_start){//深拷贝for (size_t i 0; i size(); i){tmp[i] _start[i];//赋值重载}delete[]_start;}_start tmp;_finish _start sz;_end_of_storage _start n;}}void push_back(const T x){//判断是否扩容if (_finish _end_of_storage){size_t newCapacity capacity() 0 ? 4 : 2 * capacity();reserve(newCapacity);}*_finish x;_finish;}void resize(size_t n,const TvalT()){if (n size()){_finish _start n;}else{reserve(n);while (_finish ! _start n){*_finish val;_finish;}}}T operator[](size_t pos){assert(pos size());return _start[pos];}T operator[](size_t pos)const{assert(pos size());return _start[pos];}iterator insert(iterator pos, const T x){assert(pos _finish pos _start);//检查是否扩容if (_finish _end_of_storage){//先记录长度size_t len pos - _start;size_t newCapacity capacity() 0 ? 4 : capacity() * 2;reserve(newCapacity);//更新迭代器指向新空间pos _start len;}//往后覆盖iterator end _finish;while (end pos){*end *(end - 1);--end;}*pos x;_finish;return pos;}iterator erase(iterator pos){assert(pos _start pos _finish);iterator end pos 1;while (end ! _finish){*(end - 1) *end;end;}--_finish;return pos;}void pop_back(){--_finish;}void swap(vectorT v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}~vector(){delete[]_start;_start _finish _end_of_storage nullptr;}private:iterator _start;iterator _finish;iterator _end_of_storage;};
}
ase(iterator pos){assert(pos _start pos _finish);iterator end pos 1;while (end ! _finish){*(end - 1) *end;end;}--_finish;return pos;}void pop_back(){--_finish;}void swap(vectorT v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}~vector(){delete[]_start;_start _finish _end_of_storage nullptr;}private:iterator _start;iterator _finish;iterator _end_of_storage;};
}
