自学内容网 自学内容网

【C++】STL容器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;

这里注意 rbeginrend 返回的位置,和 beginend 返回位置类似,正向迭代器是左闭右开。反向迭代器是左开右闭。如下图:

在这里插入图片描述

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
{
publicmyvector()
{}
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)!