带你深入理解STL中的vector
vector底层是一个动态数组，包含三个迭代器，start和finish之间是已经被使用的空间范围，end_of_storage是整块连续空间包括备用空间的尾部。当空间不够装下数据（vec.push_back(val)）时，会自动申请另一片更大的空间（1.5倍或者2倍），然后把原来的数据拷贝到新的内存空间，接着释放原来的那片空间【vector内存增长机制】。当释放或者删除（vec.clear()）
文章目录
一、vector的底层原理
vector底层是一个动态数组，包含三个迭代器，start和finish之间是已经被使用的空间范围，end_of_storage是整块连续空间包括备用空间的尾部。
当空间不够装下数据（vec.push_back(val)）时，会自动申请另一片更大的空间（1.5倍或者2倍），然后把原来的数据拷贝到新的内存空间，接着释放原来的那片空间【vector内存增长机制】。
当释放或者删除（vec.clear()）里面的数据时，其存储空间不释放，仅仅是清空了里面的数据。
因此，对vector的任何操作一旦引起了空间的重新配置，指向原vector的所有迭代器会都失效了。
我们以SGI版本的stl30作为研究对象，了解底层的设计思想：
vector维护的是一个连续的线性空间，所以不论其元素类型为何，普通指针都可以作为vector的迭代器而满足所以必要条件，如operator*，operator->，operator++，operator–，普通指针天生就具备。vector支持随机存取，而普通指针正有这样的能力。所以底层直接将指针封装成了iterator。
二、vector的扩容机制
根据查阅的资料显示，考虑可能产生的堆空间浪费，成倍增长倍数不能太大，使用较为广泛的扩容方式有两种，以2倍的方式扩容，或者以1.5倍的方式扩容。
以2倍的方式扩容，导致下一次申请的内存必然大于之前分配内存的总和，导致之前分配的内存不能再被使用，所以最好倍增长因子设置为(1,2)之间：
1.不同编译器的扩容机制
我们以下面这段代码来测试不同编译器中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';
}
例如在Microsoft Visual Studio中以1.5倍扩容：
在Linux下vector以2倍方式扩容：
2.理解reserve()和resize()
reserve()文档介绍：
- reserve()函数有一个参数size_type n
- 如果n大于当前capacity，那么扩容至n
- 其他情况均不会影响当前capacity（n即使小于当前capacity也不缩容）
- 该函数不影响vector的size
resize()的文档介绍：
- 该函数需要传递一个size_type的参数n
- 如果n小于当前size，size减至n，并丢弃后面的值
- 如果n大于当前size，如果n小于capacity，size可以扩大，如果n大于capacity，先扩容
- 该函数可能会影响vector的capacity
三、vector的迭代器iterator
1.底层实现
前面已经介绍过：底层直接将指针封装成了iterator。
typedef T value_type;
typedef value_type* iterator;
typedef const value_type* const_iterator;
//正向迭代器
iterator begin() { return start; }
const_iterator begin() const { return start; }
iterator end() { return finish; }
const_iterator end() const { return finish; }
//反向迭代器（了解，具体设计我们在下一篇文章再介绍）
reverse_iterator rbegin() { return reverse_iterator(end()); }
const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
reverse_iterator rend() { return reverse_iterator(begin()); }
const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
2.迭代器失效问题
迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装，比如：vector的迭代器就是原生态指针T* 。因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器，程序可能会崩溃)。
- 当插入一个元素到vector中，由于引起了内存重新分配，所以指向原内存的迭代器全部失效。如resize、reserve、insert、assign、push_back等操作；
- 当删除容器中一个元素后,该迭代器所指向的元素已经被删除，那么也造成迭代器失效。erase方法会返回下一个有效的迭代器，所以当我们要删除某个元素时，需要it=vec.erase(it);
因为扩容失效的情况：
int main()
{
vector<int> v{ 1,2,3,4,5,6 };
auto it = v.begin();
cout << *it << endl;
v.reserve(100);
cout << *it << endl;
return 0;
}
我们通过监视窗口查看扩容前it的指向：
扩容后：
it的指向未变，但是指向的空间已经销毁了，所以该迭代器失效了。解决该问题只需重新赋值即可。
因为删除失效：
int main()
{
vector<int> v{ 1,2,3,4,5,6 };
auto it = v.begin();
cout << *it << endl;
v.erase(it);
cout << *it << endl;
}
erase删除it位置元素后，it位置之后的元素会往前移，没有导致底层空间的改变，理论上讲迭代器不应该会失效，但是：如果it刚好是最后一个元素，删完之后it刚好是end的位置，而end位置是没有元素的，那么it就失效了。因此删除vector中任意位置上元素时，vs就认为该位置迭代器失效了。在不同的编译器下，对于失效的处理不尽相同，比如在g++下，it还是认定为有效的。
解决该问题只需要对it重新赋值即可，it = v.erase(it)。而库中的erase()函数返回值是下一个迭代器：
3.深浅拷贝的问题
在之前对于类的学习中，我们知道类中默认的拷贝构造函数只能支持浅拷贝，而不能支持深拷贝。所以为了实现深拷贝，我们必须显示的定义拷贝构造函数。
而对于常用的内存拷贝函数memcpy()，它有以下特点：
- memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中
- 如果拷贝的是默认类型的元素，memcpy既高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝。
所以我们需要开辟新的空间，然后将数据拷贝到新的空间：
我们先从生成拷贝构造函数来解决：
//默认的构造函数
explicit vector(int n, const T& val = T())
: _start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
reserve(n);
for (int i = 0; i < n; i++) push_back(val);
cout << "vector(int n, const T& val = T())" << endl;
}
//拷贝构造函数
vector(const vector<T>& v)
: _start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
vector<T> tmp(v.begin, v.end);
swap(tmp);
}
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
//赋值构造函数
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
所以我们可以用上述思想来设计深拷贝。
对于reserve()函数，我们需要考虑，如果其中每个元素都是自定义类型，所以设计如下：
void reserve(size_t n)
{
if (n > capacity())
{
T* tmp = new T[n];//tmp空间内可能有n个自定义元素，对于这些元素，我们也需要深拷贝
size_t oldSize = size();
if (_start)
{
for (size_t i = 0; i < oldSize; i++)
{
tmp[i] = _start[i];//这里调用了赋值构造函数进行了深拷贝
}
delete[] _start;
}
_start = tmp;
_finish = tmp + oldSize;
//size() == _finish-_start == _finish-tmp
//而原来的_finish已经被释放，造成了访问野指针
_end_of_storage = _start + n;
}
}
四、模拟实现vector
#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
namespace myVector
{
template<class T>
class vector {
public:
typedef T* iterator;
typedef const T* const_iterator;
private:
iterator _start;
iterator _finish;
iterator _end_of_storage;
public:
iterator begin() { return _start; }
iterator end() { return _finish; }
const_iterator begin() const { return _start; }
const_iterator end() const { return _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]; }
bool empty() const { return _finish == _start; }
size_t size() const { return _finish - _start; }
size_t capacity() const { return _end_of_storage - _start; }
void clear() { _finish = _start; }
vector()
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{}
//vector<char> v1(10, 'A');
explicit vector(int n, const T& val = T())
: _start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
reserve(n);
for (int i = 0; i < n; i++) push_back(val);
cout << "vector(int n, const T& val = T())" << endl;
}
//vector<int> v1(10, 1);----->可能会匹配vector(InputIterator first, InputIterator last)
vector(size_t n,const T& val = T())
: _start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
reserve(n);
for (size_t i = 0; i < n; i++)push_back(val);
cout << "vector(size_t n,const T& val = T())" << endl;
}
template<class InputIterator>
vector(InputIterator first, InputIterator last)
: _start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
while (first != last)
{
push_back(*first);
first++;
}
cout << "vector(InputIterator first, InputIterator last)" << endl;
}
vector(const vector<T>& v)
: _start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
vector<T> tmp(v.begin(), v.end());
swap(tmp);
}
//利用了传值传参时的拷贝构造函数
vector<T>& operator=(vector<T> v)
{
swap(v);
//cout << "opeartor=" << endl;
return *this;
}
~vector()
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
void reserve(size_t n)
{
if (n > capacity())
{
T* tmp = new T[n];
size_t oldSize = size();
if (_start)
{
for (size_t i = 0; i < oldSize; i++)
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = tmp + oldSize;
//size() == _finish-_start == _finish-tmp
//而原来的_finish已经被释放，造成了访问野指针
_end_of_storage = _start + n;
}
}
void resize(size_t n,T val = T())
{
if (n > capacity()) reserve(n);
if (n > size())
{
while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
else
_finish = _start + n;
}
void push_back(const T& x )
{
if (_finish == _end_of_storage)
{
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
}
*_finish = x;
_finish++;
}
void pop_back()
{
assert(!empty());
--_finish;
}
iterator insert(iterator pos, const T& val)
{
assert(pos <= _finish);
assert(pos >= _start);
if (_finish == _end_of_storage)
{
//插入时扩容导致pos指针失效
int len = pos - _start;
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
pos = _start + len;
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = val;
++_finish;
return pos;
}
iterator erase(iterator pos)
{
assert(pos <= _finish);
assert(pos >= _start);
iterator begin = pos + 1;
while (begin < _finish)
{
*(begin - 1) = *begin;
++begin;
}
--_finish;
return pos;
}
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
};
}
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
2
0- 0
已为社区贡献4条内容
所有评论(0)