C++——vector介绍及其简要模拟实现

vector的介绍

此主题介绍转载自(https://cplusplus.com/reference/vector/vector/)

1.vector是一个表示可变大小数组的序列容器

2.vector同数组一样，采用连续存储空间来存储元素，这样可以用下标来对vector中的元素进行访问，但是vector的大小可以动态改变，，且可以其元素被容器vector自动处理。

3.从本质上讲，vector使用动态分配数组来存储器元素，当有元素插入的时候，这个数组需要重新分配大小，然后再将全部元素移入到这个数组里，但是这个过程及其消耗时间，所以为了解决这个问题，vector并不会每次都重新分配大小。

vector的使用/用法

数组的创建

vector <int> v1;//创建一个整型数组v1
vector <int> v2(10,0);//初始化一个数组，count nums  存放count个nums
vector<int> v5(v4);//将v4中的元素拷贝给v5

vector iterator 迭代器的使用

vector<int> v3(v2.begin(),v2.end());//string类和vector类的的迭代器是互通的
string str("hello world");
vector<int> v4(str.begin(), str.end());
vector<int> v5(v4);vector<int>::iterator it = v4.begin();//同时也可以进行迭代器，实现循环遍历
while (it != v4.end())
{cout << *it << " ";++it;
}
cout << endl;for (auto e : v5)
{cout << e << " ";
}
cout << endl;

vector空间增长相关函数

vector<int> v;
v.reserve(100);//reserve改变的是capacity
v.resize(100);//reserve改变的是size 若仅开拓空间，那么仍然不能使用v.size();//读取size
v.capacity();//读取capacity

vector的增删查改

vector<int> v;
//尾插
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);//尾删
v.pop_back()//查找
auto it=find(v.begin(),v.end(),3);//first last dest(firts和last都是迭代器，dest是查找的目标，会返回查找目标的下标)//删除
it =find(v.begin(),v.end(),3);
v.erase(it);//删除找到需要删除的数据的下标，然后进行删除//清除数据
v.clear();//释放空间呢？
v.shrink_to_fit();//同时也能按照数组下标去访问
for(int i=0;i<v.size();i++)
{cout<<v[i]<<endl;
}

vector类和string类的函数用法基本相同，所以这里不作过多的解释，用法也很简单，详细可以参考(https://cplusplus.com/reference/vector/vector/)

---

vector简要模拟

首先我们要知道vector实现的底层逻辑。找其源代码

可以知道其是进行指针的初始化，模板命名重命名为' iterator ' ' T* == iterator '

 大致模板

namespace an
{template<class T>class vector {public:typedef T* iterator;typedef const T* const_iterator;iterator begin()iterator end()vector(){}vector(size_t n,const T& val=T())；vector(const vector<T>& v)；void swap(vector<T>& v)；vector<T>& operator=(vector<T> tmp)；~vector()void reserve(size_t n)；void resize(size_t n,const T& val=T())；void push_back(const T& x)T& operator[](size_t pos)const T& operator[](size_t pos) constsize_t capacity();size_t size();void insert(iterator& pos, const T& x)；iterator erase(iterator pos)；private:iterator _start;//原生指针,其实就是T* iterator _finish;iterator _endofstorage;};
}

初始化

vector():_start(nullptr),_finish(nullptr),_endofstorage(nullptr)
{}
~vector()
{delete[] _start;_start=_finish=_endofstorage=nullptr;
}

获取大小/容量

size_t size() const
{return _finish-_start;//指针相减就是个数
}size_t capacity()const
{return _endofstorage-_start;
}

迭代器开头/结尾

iterator begin()
{return _start;
}
iterator end()
{return _finish;
}

开拓空间/重新定义空间

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];//由于是指针，所以需要深拷贝，memcpy仅能支持浅拷贝}delete[] _start;//清除空间}    _start=tmp;_finish=_start+sz;_endofstorage=_start+n;}
}void resize(size_t n,const T& val=T())
{if(n<=size())    {        _finish=_start+n;}else{reserve(n);while(_finish<_start+n)    {*_finish=val;++_finish;}    }
}    

尾插

void push_back(const T& x)
{if(_finish==_endofstorage)//扩容里的代码也可以用reserve(capacity()==0?4:capacity()*2)来代替{size_t sz=size();size_t cp=capacity()==0?4:22*capacity();T* tmp=new T[cp];if(_start!=nullptr){memcpy(tmp,_start,sizeof(T)*size());delete[] _start;}_start=tmp;_finish=_start+sz;_endofstorage=_start+cp;}    *_finish=x;//最后一个位置赋值++_finish;//地址往后挪一位
}

下标引用读取

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

随机位置插入/删除

void insert(iterator pos,const T& x)
{assert(pos>=_start);assert(pos<=_finish);if(_finish==_endofstorage){size_t len=pos-_start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos=_start+len;//注意，这里更新后的start指向的空间和原来的pos不一样，需要进行更新}iterator end=_finish-1;while(end>=pos){*(end+1)=*end;--end;}*pos=x;++_finish;
}iterator erase(iterator pos)
{assert(pos>=_start);assert(pos<=_finish);iterator it=pos+1;while(it<_finish){*(it-1)=*it;++it;}--_finish;return pos;//返回删除数据的下一个数据的位置
}

赋值重载/拷贝构造

vector(const vector<T>& v)
{reserve(v.capacity());for(auto e: v){push_back(e);}
}void swap(vector<T>& v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);
}
vector<T>& operator=(vector<T> tmp)
{swap(tmp);//有this指针，直接作用于要作用的对象return *this;
}

迭代器初始化

template<class InputIterator>
vector(InputIterator first, InputIterator last)//迭代器初始化
{while (first != last){push_back(*first);++first;}
}

vector初始值初始化

vector(size_t n,const T& val=T())//n个数据去初始化
{reserve(capacity());for (size_t i = 0; i < n; i++){push_back(val);}
}
//为了与迭代器的模板类型进行区分，所以这里形参T加上了' & ' 符号

统一初始化

因为上述有多个构造函数，为了简化代码不出现多个初始化列表，所以在声明的时候就进行定义

private://原生指针,其实就是T* iterator _start=nullptr;//指向数据的开始 iterator _finish=nullptr;//指向数据的结束iterator _endofstorage=nullptr;//指向空间位置的结束