💓博主CSDN主页:杭电码农-NEO💓
⏩专栏分类:C++从入门到精通⏪
🚚代码仓库:NEO的学习日记🚚
🌹关注我🫵带你学习C++
🔝🔝
1. 前言
和string的学习不同
vector即要掌握它的用法
更要会自己去实现一个vector
本章重点:
熟悉STL库中vector的接口函数
自己实现一个简易vector类
本章只实现容量相关函数
和构造,析构,拷贝构造函数
注:vector其实就是顺序容器
string类只用考虑存储字符
然而vector中可以存储任一类型所以vector的自我实现需要用模板
2. 熟悉vector的接口函数
还是借助老朋友:cplusplus来查阅文档
库中的vector的模板参数有两个
后一个是内存池,用来提升空间利用效率对于现阶段的学习而言可有可无
2.1 vector的构造与拷贝构造
常见的构造有:
vector<int> v1;
vector<int> v2(10,1);
vector<int> v3(v2);
v2:构造并初始化10个值为1的顺序表
vector可以用迭代器区间初始化:
string str("abcdefg");
vector<string> vv(str.begin(),str.end());
2.2 vector迭代器的使用
和string一样,vector有正向和反向
两种迭代器,且使用方法和string相同
vector<int> vv{1,2,3,4,5,6};
vector<int>::iterator it = vv.begin();
while(it!=vv.end())
{
cout<<*it;
it++;
}
2.3 vector空间相关函数
vector的空间相关的函数
和string的机会一模一样
如果你看了文档还不懂的话
可以先阅读此篇文章:string接口函数
2.4 vector的增删查改
push_back和pop_back
都是老朋友了,这里就不多说了
在介绍insert和erase之前先来了解几个算法库的函数
2.41 find,swap和sort
这三个函数都在头文件:algorithm
中
find函数:参数是一段迭代器区间
以及在此区间你需要查找的值
找到后返回这个值对应的迭代器位置
若找不到,则返回迭代器last
find的使用:
vector<int> vv{1,2,3,4,5,6,7,8,9};
auto pos = find(vv.begin(),vv.end(),5);
cout<<*pos;
注:使用auto是为了简写迭代器
也可以用vector< int >::iterator
替代
swap想必是大家的常客了
这里给它个面子,就不介绍它了
sort非常方便,它内部实现是快排
我们只需要传一个迭代器区间
就可以将整个区间排好序
sort的使用:
vector<int> vv{5,7,3,9,6,4,1,2,8};
sort(vv.begin().vv.end());
2.42 insert和erase
和string不同,vector的insert
的参数pos不是整型,而是迭代器
默认是在pos位置前插入一个数据
insert和find常常配合在一起使用
在整型5前面插入一个100:
vector<int> vv{1,2,3,4,5,6,7,8,9};
auto pos = find(vv.begin(),vv.end(),5);
vv.insert(pos,100);
和string的erase不同,vector
的erase一次只删除一个数据
然而string如果使用缺省值就是
将全部数据删完
vector的erase甚至可以删除一段区间
删除顺序表中值为100的元素
vector<int> vv{1,2,3,4,5,6,7,8,9,100};
auto pos = find(vv.begin(),vv.end(),100);
vv.erase(pos);
//删除一个区间
vv.erase(vv.begin()+2,vv.end()-2);
2.43 随机访问operator[ ]
vector中最喜欢用的是[ ]
它支持随机访问,是否方便
operator[]的使用:
vector<int> vv{1,2,3,4,5,6,7,8,9};
for(int i=0;i<vv.size();i++)
{
cout<<vv[i]<<" ";
}
3. vector的模拟实现
首先要关注的是成员变量
vector是顺序表,所以和实现C语言
时的顺序表一样,至少有三个参数
- 指向一段空间的指针
- 空间的有效大小
- 空间的实际大小
由于vector的迭代器就是普通指针
所以成员变量的类型其实是迭代器
template<class T>
class vector
{
public:
typedef T* iterator;
private:
iterator _start;
iterator _finish;
iterator _endof_storage;
这里使用迭代器作为三个参数的类型
是因为:求vector的size和capacity时
可以直接使用finish-start
也就是指针相减求出长度
成员变量和空间的关系:
3.1 vector容量相关函数
上来首先要考虑的容量相关的函数:
- size
- capacity
- empty
- resize
- reverse
前三个十分简单:
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _endof_storage - _finish;
}
bool empty() const
{
return (size()==0);
}
3.11 reverse函数
reverse只会改变capacity的大小
并不会改变size的大小
void reserve(size_t n)
{
if (n > capacity())
{
size_t sz = size();
T* tmp = new T[n];
if (_start)
{
//memcpy(tmp, _start, sizeof(T)*sz);
for (size_t i = 0; i < sz; ++i)
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + sz;
_end_of_storage = _start + n;
}
}
注:当n小于capacity时,不进行扩容
由于C++内存管理的new
无法像C语言的realloc一样原地扩容
所以必须先开辟n个空间,再将数据
拷贝到新空间,且释放旧空间
3.12 resize函数
resize即会改变size大小
也会改变capacity大小
resize要分三种情况:
- n大于capacity时
- n大于size小于capacity时
- n小于size时
它们的解决方案分别是:
-
直接套用reverse
zhu -
初始有效值不变,在此之后
初始化新的内容
-
直接将size缩小到n
void resize(size_t n, const T& val = T())
{
if (n > capacity())
{
reserve(n);
}
if (n > size())
{
// 初始化填值
while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
else
{
_finish = _start + n;
}
}
注:参数val=T()使用了匿名对象
C++将内置类型特殊处理过
int/char等等都被升级为了类
所以可以使用int()表示匿名对象
int tmp1 = int();
int tmp2 = int(10);
int的缺省值为0
3.2 vector的构造函数
- 首先最简单的无参构造:
vector()
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{}
- 紧接着是带参的构造函数
我们跟着STL库的风格走:
vector(size_t n, const T& val = T())
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
reserve(n);//开辟n个空间
for (size_t i = 0; i < n; ++i)
{
push_back(val);//给初始值赋值
}
}
- 最后是使用迭代器区间来构造
比如我想在顺序表中存放string类型:
string str("abcdefg");
vector<string> vv(str.begin(),str.end());
此时在模板类中还应该有一个模板
template <class InputIterator>
vector(InputIterator first, InputIterator last)
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
while (first != last)
{
push_back(*first);
++first;
}
}
注:inputiterator取名是模仿STL的
你也可以取任一除了T
的名字
3.3 vector的析构函数
vector的析构函数非常简单
只需要将空间释放
并且将各个指针置为空就行了
~vector()
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
3.4 vector的拷贝构造函数
拷贝构造的实现有很多种写法
大家可以先自己尝试一下
vector(const vector<T>& v)
:_start(nullptr)
, _finish(nullptr)
, _endof_storage(nullptr)
{
reserve(v.size());
for (const auto& e : v)
{
push_back(e);
}
}
4. 总结以及拓展
vector模拟实现的全部代码我将在
下一篇文章中分享给大家
可以发现:STL的神奇之处在于
它把所有接口函数都做了统一化处理
每一个容器的接口函数的使用都相似
但是内部实现被这种封装隐藏起来了
进一步又体现了C++的三大特性:封装
并且C++实现了所有容器通用的算法库
比如sort和find都只需要传迭代器
然而所有容器都会被迭代器封装
所以一份代码就能实现对不同容器的操作
拓展题目:
熟悉了vector的基本使用
可以尝试解决一下下面几个问题:文章来源:https://www.toymoban.com/news/detail-679111.html
- 只出现一次的数字
- 删除有序数组中的重复项
- 数组中出现次数超过一半的数字
- 杨辉三角
留给大家当作小试牛刀了~
文章来源地址https://www.toymoban.com/news/detail-679111.html
到了这里,关于【C++进阶(二)】STL大法--vector的深度剖析以及模拟实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!