【C++】STL容器vector详解及简单模拟实现
vector详解及简单模拟实现
一，vector的简单介绍
vector底层是一个由类模板实例化而来的，不像string存储的是字符，vector可以存储各种不同的数据类型，包括内置类型和自定义类型。
在vector部分我们需要不仅要掌握用法，还要知道其底层的一些原理。以及要清楚vector的迭代器失效等问题。
二，vector的用法
2.1 vector的构造
vector<int> v1;
vector<int> v2(10,1);//用10个1初始化v2
vector<int> v3(v1);//拷贝构造
vector<int> v4(v1.begin(),v1.end());//用v1的迭代器区间初始化v4
string s("aaasss");
vector<string> v5(s.begin(),s.end());//用迭代器初始化
2.2 vector的迭代器
vector迭代器的使用和string是一样的，
vector<int> v1(10,1);
vector<int>::iterator it = v1.begin();
while(it != v1.end()){
cout<<*it<<" ";
++it;
}
cout<<endl;
这里注意 rbegin 和 rend 返回的位置，和 begin 和 end 返回位置类似，正向迭代器是左闭右开。反向迭代器是左开右闭。如下图：
2.3 容量相关
vector的容量相关的接口的使用和string一致，所以不做过多解释。
2.4 vector的增删查改
vector的增删查改中push_back 和 pop_back 也就是尾插尾删。我们也比较熟悉，下面我们看一下这两个接口。
2.4.1 operator[]
vector是支持[]下标随机访问的，其底层空间是也是连续的，模拟实现的话也比较简单。
vector<int> v(10,1);
for(int i = 0; i < v.size(); i++){
cout<<v[i]<<" “；
}
2.4.2 insert()和erase()
vector的插入需要传入迭代器，会在传入的迭代器之前插入。
这里的插入一般会和
find搭配使用
vector<int> v{1,2,3,4,5,6,7};
auto pos = find(v.begin(),v.end(),4);
v.insert(pos,10);
这里简单介绍一下find():
可以看到find是包含在算法的头文件中的，传入的参数是一段迭代器区间及要查找的值。
如果找到，则返回这个位置的迭代器，找不到则返回最后一个位置。
vector的删除也要传入一个迭代器，或者传入一段迭代器区间。
vector<int> v{1,2,3,4,5,6,7};
auto pos = find(v.begin(),v.end(),4);
v.erase(pos);
v.erase(v.begin()+1,v.end()-2);
三，模拟实现
成员变量
首先，vector是一个类模板，由所给的数据类型来生成具体的对象
template<class T>
class myvector{
public:
//....
};
vector的底层空间是连续的 ，所以首先要有三个成员变量
分别是：
1.指向vector空间的开始位置的指针
2.指向这段空间中数据存放的结束（得到这段空间的有效大小）
3.这段空间的实际结尾（得到总共存放的大小）
template<class T>
class myvector{
public:
//....
private:
iterator _start = nullptr;//vector起始位置
iterator _finish = nullptr;//存放数据结束位置
iterator _end_of_storage = nullptr;//所开空间的结束位置
};
迭代器
因为vector的底层是连续的，所以其迭代器实际上就是原生指针
template<class T>
class myvector{
typedef T* iterator;
typedef const T* const_iterator;
public:
//....
iterator begin() {
return _start;
}
iterator end() const{
return _finish;
}
iterator begin() const{
return _start;
}
iterator end() {
return _finish;
}
private:
iterator _start = nullptr;//vector起始位置
iterator _finish = nullptr;//存放数据结束位置
iterator _end_of_storage = nullptr;//所开空间的结束位置
};
3.1 模拟实现vector核心框架接口
vector要模拟实现的主要是构造，和容量相关的，数据插入的一些接口，其中插入和删除部分会涉及迭代器失效等问题，我们主要在下面部分讲解。
3.1.1 构造&拷贝构造
1. vector的无参构造函数比较简单，可以直接在声明时用缺省参数构造
class vector
{
public：
myvector()
{}
private:
iterator _start = nullptr;//vector起始位置
iterator _finish = nullptr;//存放数据结束位置
iterator _end_of_storage = nullptr;//所开空间的结束位置
}；
2. 带参的构造函数有多个重载版本，这里先说用用迭代器区间构造的版本
这个迭代器区间可以是如何容器的迭代器区间，也可以是数组，所以我们也用模板来实现
template<class inputIterator>
myvector(inputIterator begin,inputIterator end) {//用迭代器区间构造
while (begin != end) {
push_back(*begin);
++begin;
}
}
下面我们讲解用n个值来构造的版本：
这里实际上可以复用resize()，因为 resize() 可以开空间，并且初始化
myvector(size_t n,const T& val = T()) {
resize(n, val);
}
//
myvector(int n, const T& val = T()) {
resize(n, val);
}
注：这里要重载一个 int 版本 ，因为当输入两个整型参数时，这里编译器会调用上述模板类型的构造函数，所以为了区分，当输入两个整型参数时调用下面的版本。
拷贝构造这是也是要注意深浅拷贝的问题，这里先简单实现一个，具体我们在下面的深浅拷贝问题时分析
myvector(const myvector<T>& v) {
reserve(v.capacity());
for (auto e : v) {
push_back(e);
}
}
析构函数也是比较简单，直接将成员变量置为空即可
~myvector() {
if (_start) {//如果不为空时
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
}
3.1.2 容量相关
这里模拟实现的时
resize()和reserve()，都有一个相同的问题就是，当要进行扩容时，需要再开辟一块空间来存放原来的数据，所以就要跑拷贝原来的数据到新的空间中，如果只是简单的memcpy的话，对于内置类型的数据，memcpy 可以很好的进行拷贝，如果对于一些自定义的数据，则会造成浅拷贝的问题，进而可能会出现内存泄漏或者程序崩溃
先来实现 reserve ，reserve的作用是开空间，所以后面resize可以复用reserve
这里也是只做实现，具体的原因我们在下面的深浅拷贝问题中具体分析
void reserve(size_t n) {
if (n > capacity()) {
T* tmp = new T[n];
size_t old = size();//保存之前的有效长度
if (_start) {
for (size_t i = 0; i < old; i++) {
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + old;
_end_of_storage = _start + n;
}
}
resize() 的作用是开空间加初始化，所以可以复用 reserve()
void resize(size_t n,T val = T()) {
if (n > size()) {
reserve(n);
while (_finish != _start + n) {
*_finish = val;
_finish++;
}
}
else {
_finish = _start + n;
}
}
注：这里C++为了兼容自定义类型，内置类型也有其默认构造，上面代码中
T val = T()
3.1.3 增删查改
这里我们模拟实现的是尾插尾删，insert和erase
push_back() 会在有效长度之后插入元素，如果插入时有效长度对于实际长度，则需要继续扩容
void push_back(const T& x ) {
if (_finish == _end_of_storage) {
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
}
*_finish = x;
++_finish;
}
pop_back()的实现比较简单，将指向有效长度的指针向前挪动即可
void pop_back() {
assert(size() > 0);
--_finish;
}
insert()需要传入迭代器，在pos位置插入元素，如果需要，则进行扩容，插入后，再将后面的数据进行挪动。插入成功后返回pos位置，防止外部迭代器失效。
iterator insert(iterator pos,const T& x) {//
assert(pos >= _start );
assert(pos <= _finish);
if (_finish == _end_of_storage) {
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len;//更新pos,因为扩容后原先的迭代器失效(内部失效)
}
iterator end = _finish-1;//这里使用迭代器可以不用访问下标
while (end >= pos) {
*(end + 1) = *end;
--end;
}
*pos = x;
_finish++;
return pos;//返回更新(外部迭代器失效)
}
erase()转入的也是迭代器位置，可以直接将pos之后的数据依次往前挪动
iterator erase(iterator pos) {
assert(pos >= _start);
assert(pos <= _end_of_storage);
iterator first = pos + 1;//使用迭代器可以避免使用下标
while (first <= _finish) {
*(first - 1) = *(first);
++first;
}
--_finish;
return pos; //为了防止外部迭代器失效
}
vector的容量相关的具体问题（深浅拷贝问题）及insert和erase造成的迭代器失效问题我们在下一节讲解
原文地址：https://blog.csdn.net/weixin_64906519/article/details/135856044
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！