前言
👧个人主页:@小沈YO.
😚小编介绍:欢迎来到我的乱七八糟小星球🌝
📋专栏:C++ 心愿便利店
🔑本章内容:vector
记得 评论📝 +点赞👍 +收藏😽 +关注💞哦~
提示:以下是本篇文章正文内容,下面案例可供参考
一、STL简介
1.1 什么是STL
STL(standard template libaray-标准模板库):是C++标准库的重要组成部分,不仅是一个可复用的组件库,而且是一个包罗数据结构与算法的软件框架
1.2 STL的六大组件
二、vector的介绍及使用
2.1 vector的介绍
vector的文档介绍
- vector是表示可变大小数组的序列容器。
- 就像数组一样,vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问,和数组一样高效。但是又不像数组,它的大小是可以动态改变的,而且它的大小会被容器自动处理。
- 本质讲,vector使用动态分配数组来存储它的元素。当新元素插入时候,这个数组需要被重新分配大小为了增加存储空间。其做法是,分配一个新的数组,然后将全部元素移到这个数组。就时间而言,这是一个相对代价高的任务,因为每当一个新的元素加入到容器的时候,vector并不会每次都重新分配大小。
- vector分配空间策略:vector会分配一些额外的空间以适应可能的增长,因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何,重新分配都应该是对数增长的间隔大小,以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
- 因此,vector占用了更多的存储空间,为了获得管理存储空间的能力,并且以一种有效的方式动态增长。
- 与其它动态序列容器相比(deque, list and forward_list), vector在访问元素的时候更加高效,在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作,效率更低。比起list和forward_list统一的迭代器和引用更好。
2.2 vector的使用
2.2.1 vector的定义
(constructor)构造函数声明 | 接口说明 |
---|---|
vector()(重点) | 无参构造 |
vector(size_type n, const value_type& val = value_type()) | 构造并初始化n个val |
vector (const vector& x); (重点) | 拷贝构造 |
vector (InputIterator first, InputIterator last); | 使用迭代器进行初始化构造 |
void test_vector1()
{
//构造函数
vector<int> v;//无参构造
vector<int> v1(5, 1);
vector<int> v2(v1.begin(), v1.end());
string s1 = "hello world";
vector<int> v3(s1.begin(), s1.end());//隐式类型转换
vector<int> v4(v3);//拷贝构造
}
2.2.2 vector iterator 的使用
iterator的使用 | 接口说明 |
---|---|
begin + end(重点) | 获取第一个数据位置的iterator/const_iterator,获取最后一个数据的下一个位置的iterator/const_iterator |
rbegin + rend | 获取最后一个数据位置的reverse_iterator,获取第一个数据前一个位置的reverse_iterator |
void test_vector1()
{
vector<int> v2(v1.begin(), v1.end());
string s1 = "hello world";
vector<int> v3(s1.begin(), s1.end());//隐式类型转换
vector<int> v4(v3);//拷贝构造
//1.iterator
vector<int>::iterator it = v3.begin();
while (it != v3.end())
{
cout << *it << " ";
it++;
}
cout << endl;
//2.operator[]
for (size_t i = 0; i < v2.size(); i++)
{
cout << v2[i] << " ";
}
cout << endl;
//3.范围for
for (auto e : v4)
{
cout << e << " ";
}
cout << endl;
}
2.2.3 vector 空间增长问题
容量空间 | 接口说明 |
---|---|
size | 获取数据个数 |
capacity | 获取容量大小 |
empty | 判断是否为空 |
resize(重点) | 改变vector的size |
reserve (重点) | 改变vector的capacity |
// 测试vector的默认扩容机制
void TestVectorExpand()
{
size_t sz;
vector<int> v;
sz = v.capacity();
cout << "making v grow:\n";
for (int i = 0; i < 100; ++i)
{
v.push_back(i);
if (sz != v.capacity())
{
sz = v.capacity();
cout << "capacity changed: " << sz << '\n';
}
}
}
-
capacity的代码在vs和g++下分别运行会发现,vs下capacity是按1.5倍增长的,g++是按2倍增长的。这个问题经常会考察,不要固化的认为,vector增容都是2倍,具体增长多少是根据具体的需求定义的。vs是PJ版本STL,g++是SGI版本STL。
-
reserve只负责开辟空间,如果确定知道需要用多少空间,reserve可以缓解vector增容的代价缺陷问题。
// 如果已经确定vector中要存储元素大概个数,可以提前将空间设置足够
// 就可以避免边插入边扩容导致效率低下的问题了
void TestVectorExpandOP()
{
vector<int> v;
size_t sz = v.capacity();
v.reserve(100); // 提前将容量设置好,可以避免一遍插入一遍扩容
cout << "making bar grow:\n";
for (int i = 0; i < 100; ++i)
{
v.push_back(i);
if (sz != v.capacity())
{
sz = v.capacity();
cout << "capacity changed: " << sz << '\n';
}
}
}
- resize在开空间的同时还会进行初始化,影响size
void test_vector3()
{
vector<int> v1;
cout << v1.max_size() << endl;
size_t sz;
vector<int> v;
//v.reserve(100); ---> size=0,capacity=100
v.resize(100); ---> size=100,capacity=100
//for (size_t i = 0; i < v.size(); i++)//当写成这种形式用reserve(100)是不会进入循环的因为v.size()返回值是0
for (size_t i = 0; i < 100; i++)
{
v[i] = i;//断言在release下不起作用
//虽然空间开出来了100但是不能访问,因为operator[]里面加了断言,断言访问的下标必须是小于size的,大于size就越界了,所以只能访问[0,size-1]的数据,但是reverse(100)--->size=0
}
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
上面的代码用reserve(100)虽然给 v 提前开了 100 个空间,但是 v 中的有效元素个数size还是 0,所以不能直接通过下标去访问 vector 对象中的每一个元素,因为 operator[ ] 实现中的第一步就是检查下标的合理性,防止越界访问,执行 assert(pos < _size),而此时 _size 是 0,就会越界报错。而把 reserve 改成 resize 就可以正常运行,因为 resize 会改变 _size 的大小。
2.2.4 vector 增删查改
vector增删查改 | 接口说明 |
---|---|
push_back(重点) | 尾插 |
pop_back (重点) | 尾删 |
find | 查找 - - -(注意这个是算法模块实现,不是vector的成员接口) |
insert | 在position之前插入val |
erase | 删除position位置的数据 |
swap | 交换两个vector的数据空间 |
operator[] (重点) | 像数组一样访问 |
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
v.insert(v.begin(), 0);
auto it=find(v.begin(), v.end(), 3);寻找--->注意这个是算法模块实现,不是vector的成员接口
if (it != v.end())
{
v.insert(it, 30);插入
}
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
it = find(v.begin(), v.end(), 3);
if (it != v.end())
{
v.erase(it);删除
}
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
cout << v.size() << endl;
cout << v.capacity() << endl;
v.clear();
v.shrink_to_fit();//缩容不建议用
cout << v.size() << endl;
cout << v.capacity() << endl;
}
三、vector模拟实现
3.1 成员变量
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
private:
iterator _start;
iterator _finish;
iterator _end_of_storage;
};
3.2 成员函数
3.2.1 构造函数
//无参构造
vector()
:_start(nullptr)
,_finish(nullptr)
,_end_of_storage(nullptr)
{}
//带参构造并初始化
vector(int n, const T& val = T())
{
reserve(n);
for (int i = 0; i < n; i++)
{
push_back(val);
}
}
vector(size_t n, const T& val = T())
{
rserve(n);
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}
//迭代器区间初始化
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
first++;
}
}
- 无参的构造并不陌生
- 带参的构造并初始化为什么要写两个?
因为如果不单独提供一个 vector(int n, const T& val = T());代码vector v1(10, 1) 会走最匹配的,即和迭代器区间初始化函数匹配(迭代器区间初始化采用的是函数模板),但是我们希望它走 vector(size_t n, const T& val = T()) 构造函数,可是 10 是 int 型,和 size_t 不匹配上(只会走最匹配的),因此就会去和迭代器区间初始化函数进行匹配,InputIterator 就会被实例化成 int 型,函数中会对 int 型解引用,就会报错
- 迭代器区间初始化采用的是函数模板,因为它可能使用不同类型的迭代器。
3.2.2 拷贝构造函数
vector(const vector<T>& v)//const对象
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
reserve(v.capacity());
for (auto& e : v)//这里加上&防止T是个大对象拷贝代价大
{
push_back(e);
}
}
3.2.3 operator=
vector<T> operator=(vector<T> tmp)
{
swap(tmp);
return *this;
}
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
3.2.4 size
size_t size() const
{
return _finish - _start;
}
3.2.5 capacity
size_t capacity() const
{
return _end_of_storage - _start;
}
3.2.6 reserve(注意memcpy的拷贝方式)
void reserve(size_t n)
{
if (n > capacity())
{
T* tmp = new T[n];
if (_start)
{
memcpy(tmp, _start, sizeof(T) * sz);
delete[] _start;
}
_start = tmp;
_finish = _start + size();
_end_of_storage = _start + cp;
}
}
_________________________________________________________________________________________
void reserve(size_t n)
{
if (n > capacity())
{
T* tmp = new T[n];
if (_start)
{
memcpy(tmp, _start, sizeof(T) * sz);
delete[] _start;
}
_finish = tmp + size();
_start = tmp;
_end_of_storage = _start + cp;
}
}
_________________________________________________________________________________________
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);
delete[] _start;
}
_start = tmp;
_finish = _start + sz;
_end_of_storage = _start + n;
}
}
注意:第一种代码的写法是不正确的,因为当开辟新空间tmp,将_start中的数据拷贝到tmp中,释放原空间,将_start指针指向新空间,所以运行代码_finish = _start + size();时要先调用size(),而size=_finish - _start,其中_finish是nullptr(构造时初始化),而_start并不是nullptr(此时是tmp),所以我们预期中的size并不是等于0,而是size=0-_start,所以_finish=_start+0-_start=0
解决方式:
- 写成_finish = tmp + size(); _start = tmp;注意先后顺序,如果写成 _start = tmp; _finish = tmp + size(); 先调用size=_finish-_start=0-tmp;最终_finish=tmp+0-tmp还是没有解决问题,同样也不能写成_finish = _start + size(); _start = tmp; 此时的_start=0,所以_finish=0+0=0,也是不对的
- 第一种的解决方式是可以的但是可读性太差,顺序不对就导致错误,所以可以提前用一个变量存储size()的返回值,size_t sz = size();此时就不会因为顺序报错啦
上面这种扩容逻辑,当 T 是内置类或者是不需要进行深拷贝的自定义类型来说,是可以的。但是当 T 是需要进行深拷贝的类型时,上述这种扩容方式就会出现问题。下述代码以 vector 为例:
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);
delete[] _start;
}
_start = tmp;
_finish = _start + sz;
_end_of_storage = _start + n;
}
}
void test_vector5()
{
vector<string> s;
s.push_back("11111111111111111111");
s.push_back("11111111111111111111");
s.push_back("11111111111111111111");
s.push_back("11111111111111111111");
s.push_back("11111111111111111111");
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
}
通过上图可以明显地观察到当插入4个字符串时是没有问题的但是当插入第五个字符串时就会出现问题,显然是扩容中出现了问题,上述代码用 memcpy 将旧空间的数据拷贝到新空间,那么新旧空间中存储的 string 对象指向同一个堆区上的字符串空间,接着在执行 delete[] _start; 销毁旧空间的时候,由于该 _start 是一个 string* 的指针,所以会先调用 string 的析构函数,将对象中申请的空间释放,也就是释放 _str 指向的空间,然后再去调用 operator delete 函数释放 string 对象的空间。所以新空间中存储的 string 对象就出现了问题,因为它的成员变量 _str 指向的空间已经被释放了。
显然 memcpy 执行的是浅拷贝,只需要修改成tmp[i] = _start[i]; 这样会调用 string 对象的赋值运算重载,进行深拷贝。
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;
}
}
3.2.7 resize
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;
}
}
}
3.2.8 operator[]
//读写
T& operator[](size_t pos)
{
assert(pos < size());
return _start[pos];
}
//只能读
const T& operator[](size_t pos) const
{
assert(pos < size());
return _start[pos];
}
3.2.9 insert(涉及迭代器失效)
void insert(iterator pos, const T& x)
{
assert(pos >= _start);
assert(pos <= _finish);
if (_finish == _end_of_storage)
{
reserve(capacity() == 0 ? 4 : capacity() * 2);//检查容量
}
iterator end = _finish - 1;
//插入数据
while (end >= pos)
{
*(end + 1) = *end;
end--;
}
*pos = x;
_finish++;
}
___________________________________________________________________________________________-
void 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;
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
end--;
}
*pos = x;
_finish++;
}
注意:在进行 insert 的时候,会引发一个问题 ---- 迭代器失效:如果失效就不能再使用这个迭代器,如果使用了,结果未定义。
首先pos 是一个迭代器,在 pos 位置插入一个数据时,要在插入数据之前先检查容量,进行扩容,但是执行了扩容逻辑后,_start、_finish、_end_of_storage 都指向了新空间,旧空间被释放了,且 pos 指向的却还是原来空间中的某个位置,此时 pos 就变成了野指针,再去 pos 指向的位置插入数据时,就会造成非法访问就像第一种所写的代码(总而言之就是扩容导致pos失效)
解决方式:为了解决迭代器失效的问题,可以在检查容量扩容之前先保存一下pos的相对位置,在进行扩容释放旧空间指向新空间逻辑后,更新一下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;
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
end--;
}
*pos = x;
_finish++;
return pos
}
void test_vector3()
{
vector<int>v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
vector<int>::iterator it = v.begin()+2;
v.insert(it, 30);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
对于上述代码调用insert,虽然更新了 pos,但是由于是传值,形参 pos 的更新,并不会改变实参的 it,所以insert后it可能会失效。
解决上述问题很简单直接把形参的 pos 变成引用不就可以吗?这样形参pos的改变也就使得实参it改变。
这样是可以的解决了传值传参的问题,但是也会引发诸多问题,例如:v.insert(v.begin(), 30);当运行这段代码时就会报错,因为实参具有常性(begin()是传值返回,会产生一个临时变量,临时变量具有常性),&必须要传变量不能传带const属性的值。
所以形参 pos 用引用的话,就需要加 const 进行修饰。但是如果用 const 进行修饰,那在函数内部就不能对 pos 进行更新,所以形参 pos 不能用引用,可以采用返回值的方式,将更新后的 pos 返回。文章来源:https://www.toymoban.com/news/detail-755227.html
3.2.10 erase(涉及迭代器失效)
iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator it = pos + 1;
while (it < _finish)
{
*(it - 1) = *it;
it++;
}
_finish--;
return pos
}
根据上述insert实现中迭代器失效是因为扩容引起的,但是erase 只是删除 pos 位置元素,pos 位置之后的元素往前覆盖,没有导致空间的改变,理论上迭代器不会失效
但是根据上述代码,如果 pos 刚好是最后一个元素,删完之后 pos 刚好是 _finish 的位置,而 _finish 位置是没有元素的,那么 pos 就失效了。为了迭代器失效问题,还是可以采用返回值的方式,返回 pos 下一个位置元素的迭代器。文章来源地址https://www.toymoban.com/news/detail-755227.html
3.2.11 push_back
void push_back(const T& x)
{
if (_finish == _end_of_storage)
{
reserve( capacity() == 0 ? 4 : capacity() * 2);
}
*_finish = x;
_finish++;
}
__________________________________________________________________________________
//push_back可以直接复用insert
void push_back(const T& x)
{
insert(end(), x);
}
3.2.12 pop_back
void pop_back()
{
erase(--end());
}
3.2.13 迭代器
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
vector<int>::iterator it = v.begin();
while (it != v.end())
{
*it *= 10;
cout << *it << " ";
it++;
}
cout << endl;
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
到了这里,关于【C++心愿便利店】No.13---C++之探索vector底层原理的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!