目录
一、前言
vector源代码看了一下过于复杂，这里取其精华把大体的框架和重要函数罗列出来并分析实现
二、vecotr框架搭建
在实现vector前需要弄明白这幅图，与string相似也会记录size和capacity的大小
在这个数组中，有三个指针分别指向起始位置start，数据结束位置finish以及空间容量的末尾end_of_storage位置，剩余空间备用，如果增加的数据超过capacity，则需要进行增容
1. vector介绍
1. vector是大小可变的数组序列容器
2. 和数组一样，空间上是连续存储
3. 使用动态分配数组存储元素；增容时，并不会每次都重新分配大小，而是分配一些额外的空间以适应可能的增长(finish和endofstorage之间)。
vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。
4. 与其它动态序列容器相比（deques, lists and forward_lists）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。
对于其它不在末尾的删除和插入操作，效率更低。比起lists和forward_lists统一的迭代器和引用更好。
2. 框架
下面为vector的大体框架，和顺序表也很类似实现了增删查改
namespace vectorSimu{
template<class T>
class vector{
public:
typedef T* iterator;
iterator begin();
iterator end();
//默认成员函数
vector();
vecotr(size_t n, const T& val);
vector(const vector<T>& val); //拷贝构造
//大小和rongliang
size_t size();
size_t capacity();
//扩容
void reserve(size_t n);
void resize(size_t n, const T& val = T());
//读取容器信息
T& operator[](size_t pos);
//修改与删除
void push_back(const T& val);
void pop_back();
void insert(iterator pos, const T& val);
iterator erase(iterator pos);
void swap(vector<T>& v);
//析构
~vector();
private:
iterator _start;
iterator _finish;
iterator _endofstorage;
};
}
3. 构造函数
构造一个不带参的函数，将其成员置为nullptr
vector()
: _start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{}
带参构造，调用可支持初始为T类型的n个这样的val，先去调用reserve以此判断n是否超出当前的容量，如果超出则重新分配一组n个大小的空间
vector(size_t n, const T& val = T())
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{
reserve(n);
//判断n是否超出capacity
reserve(n);
for(int i=0; i<n; ++i){
push_back(val);
}
}
我们也可以利用区间迭代器进行构造，将数据尾插
//类模版到成员函数，还可以再定义模版参数
template <class InputIterator>
vector(InputIterator first, InputIterator last){
while(first != last){
push_back(*first);
++first;
}
}
4. 拷贝构造
传统写法方式一：
vector(const vector<T>& v){
_start = new T[v.capacity()];
memcpy(_start, v._start, sizeof(T)*v.size());
_finish = _start + v.size();
_endofstorage = _start + v.capacity();
}
传统写法方式二：
vector(const vector<T>& v)
: _start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
reserve(v.capacity());
for(const auto& e: v){
push_back(e);
}
}
深拷贝的现代写法，和上面的传统写法有所不同，传统写法是直接开一组新空间，然后将原来存储的数据放入新空间，而现代写法是通过拷贝构造给临时变量后进行交换
vector(const vector<T>& v)
: _start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
vector<T> tmp(v.begin(), v.end());
this->swap(tmp);
}
void swap(vector<T>& v){
::swap(_start, v._start);
::swap(_finish, v._finish);
::swap(_endofstorage, v._endofstorage);
}
5. 赋值重载
传统写法，此方法和拷贝构造的效果是一样的
vector<T>& operator=(const vector<T>& v){
if(this != &v){
delete [] _start;
_start = _finish = _endofstorage = nullptr;
reserve(v.capacity());
for(const auto& e:v){
push_back(e);
}
}
return *this;
}
现代写法，利用形参进行了一次拷贝，然后this类和拷贝的类进行交换
vector<T>& operator=(vector<T> v){
swap(v);
return *this;
}
6. 迭代器函数
其实迭代器的begin就是封装了此类型的首地址，end对应类型的末尾
typedef T* iterator;
iterator begin(){
return _start;
}
iterator end(){
return _finish;
}
7. size和capacity
这个也比较简单，把地址做一下运算就可以得出来
size_t size(){
return _finish - _start;
}
//总的容量大小
size_t capacity(){
return _endofstorage - _start;
}
8. 扩容
当我们pushback信息到vector时需要判断需不需要增容，如果大于当前容器，那么新开一组空间，将原空间释放即可
void reserve(size_t n){
if(n>capacity()){
size_t sz = size();
T* tmp = new T[n];
if(_start){ //如果开头不为空
for(size_t i=0; i<sz; ++i){
tmp[i] = _start[i];
}
delete[] _start; //释放原容器数据
}
_start = tmp;
_finish = _start + sz;
_endofstorage = _start + n;
}
}
重新分配大小需要考虑三种情况
第一种情况当重新分配的大小小于size，也就是首地址到N的位置，剩余的进行裁剪
第二种情况，当N大于当前容量需要重新reserve()新的空间，并初始化为给定的val值
第三种情况，当N小于当前容量又比size大，剩余的补为给定的val值
void resize(size_t n, const T& val = T()){
if(n < size()){
_finish = _start + n;
}else{
if(n > capacity()){
reserve(n);
}
while(_finish < n + _start){
*_finish = val;
++_finish;
}
}
}
9. pushback和popback
这里需要注意，首次push需要判断finish指针是否和容量指针在同一个位置，那么就需要进行扩容了
//修改与删除
void push_back(const T& val){
if(_finish == _endofstorage){
size_t newcapacity = capacity()==0 ? 4 : capacity() * 2;
reserve(newcapacity);
}
*_finish = val;
_finish++;
}
pop数据也比较简单，直接将finish指针向前移动
void pop_back()
{
assert(!empty());
--_finish;
}
10. 插入和删除指定位置数据
插入前需要判断pos是否在start和finish之间，否则报错
插入数据前需要判断容量是否足够
在中间插入数据时，pos后面的数据都需要依次向后挪动，此算法效率不高，所以不推荐用
iterator insert(iterator pos, const T& val){
assert(pos >= _start && pos<=_finish);
if(_finish == _endofstorage){
size_t len = pos - _start;
size_t newcapacity = capacity() == 0 ? 4: capacity()*2;
reserve(newcapacity);
pos = _start + len;
}
iterator end = _finish - 1;
while(end >= pos){
*(end+1) = *end;
--end;
}
*pos = val;
++_finish;
return pos;
}
将pos以后的数据都去掉
iterator erase(iterator pos){
assert(pos>=_start && pos < _finish);
iterator it = pos + 1;
while(it != _finish){
*(it-1) = *it;
++it;
}
--_finish;
return pos;
}
11. 通过下标访问
//读取容器信息
T& operator[](size_t pos){
assert(pos < size());
return _start[pos];
}
Test进行验证
三、完整代码
Gitee链接🔗 🔗 🔗
👉 👉 👉 vector simulation 👈 👈 👈
创作不易，如果文章对你帮助的话，点赞三连哦:)