【C++】- STL之vector模拟实现
1.vector的介绍
- vector是表示可变大小数组的序列容器。
- vector采用的连续存储空间来存储元素。意味着也可以采用下标对vector的元素进行访问，和数组一样高效。但是它的大小是可以动态改变的，而且它的大小会被容器自动处理。
- vector使用动态分配数组来存储它的元素，当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。
- vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比时间需要的存储更大，不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
- vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。
- 与其他动态序列容器相比（deque、list and forward_list），vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其他不在末尾的删除和插入操作，效率更低。比起list和forward_list统一的迭代器和引用更好。
2.vector的基本结构
vector是一个顺序存储的容器，也可以说是一个数组，那么对于它的结构，我们可以用三个迭代器来组成，如下图：
在vector当中，其实迭代器就是一个指针。所以我们的vector类的基本成员变量可以这样设计。
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
private:
iterator _start;
iterator _finish;
iterator _endofstorage;
};3.vector模拟实现
3.1 构造函数
构造函数最主要的有两个：无参构造函数和拷贝构造函数。
3.1.1无参构造函数
无参构造函数只需要将全部迭代器赋值空。
//无参构造函数：直接全部给nullptr
vector()
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{}3.1.2 带参数的构造函数（包括size_t和int类型）
对于带参数的构造函数，当参数类型为size_t时，会先为vector分配指定数量的空间，并为每个元素进行初始化。
vector(size_t n, const T& val = T())
{
_start = new T[n];
_finish = _start;
_end_of_storage = _start + n;
for (size_t i = 0; i < n; i++)
{
*_finish++ = val;
}
}3.1.2区间构造函数
区间构造函数接收两个迭代器first和last，由于不同类型的容器迭代器类型可能不同，因此设计成函数模板，将区间内的内容尾插到vector，但是调用push_back接口通过_finish == _endofstorage判断是否满，需要初始化
template<class InoutIterator>
vector(InoutIterator first, InoutIterator last)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
while (first != last)
{
push_back(*first);
++first;
}
}3.1.3 拷贝构造函数
拷贝构造的模拟实现可以通过一个个尾插的方式实现：
vector<int> v2(v1);
即将v1的数据从头到尾遍历一遍，遍历的时候顺便将v1的数据尾插到v2。
//拷贝构造函数
//vector<int> v1;
//vector<int> v2(v1);
vecotr(const vector<T>& v)
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{
const_iterator it = v.begin();//定义一个迭代器指向v1的头
while (it != v.end())
{
push_back(*it); //将v1的数据一个个尾插到v2中，这里尾插在后面实现
it++;
}
}注意：不要使用memcpy函数拷贝数据，如果数据是内置类型或浅拷贝的自定义类型，使用memcoy是没什么问题的，但如果数据是需要深拷贝的自定义类型（string），就会出现问题，拷贝的数据和源数据指向同一块空间，因此，我们使用for循环依次赋值，调用string的赋值运算符重载完成深拷贝，push_back在实现的时候会调用深拷贝类型的赋值运算符重载。
3.2 析构函数
将空间释放掉，_start,_finish,_endofstorage置为空指针
//析构函数
~vector()
{
delete[] _start;
_start = _finish = _endofstrorage = nullptr;
}3.3赋值运算符重载
3.3.1传统写法
vector<T>& operator=(const vector<T>& v)
{
//防止自己给自己赋值
if (this != &v)
{
//1.开辟空间
T* tmp = new T[v.capacity()];
//2.将数据拷贝到新空间当中
for (int i = 0; i < v.size(); i++)
{
tmp[i] = v._start[i];
}
//3.释放原有空间
delete[] _start;
//4.指向新空间
_start = tmp;
_finish = _start + v.size();
_endofstorage = _start + v.capacity();
}
return *this;
}3.3.2现代写法
//赋值运算符重载现代写法
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
//只需要交换this和v的桑指针即可
void swap(vector<T>& v)
{
//调用标准库中的swap函数
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstorage, v._endofstorage);
}注意：传值传参时，自定义类型会调用拷贝构造函数形成形参，形参是实参的一份临时拷贝，因此我们可以让这个形参跟我们的this交换。
这样我们的this就成功被复制为我们想要的值了，this指向的旧空间在交换后被形参v所指向，出了这个作用域之后，形参v会调用其析构函数释放掉this指向的旧空间
因此，只需要传值传参swap交换就可以完成开辟新空间+拷贝数据+释放原有空间+指向新空间
3.4扩容函数 reserve
当n大于对象当前的capacity时，将capacity扩大到n或大于n
当n小于对象当前的capacity是，就不需要
实现步骤：
1.新开辟一块空间，若容器为空，将_start,_finish指向新开辟空间的首元素地址，_endofstorage指向新开辟空间的最后一个元素下一个位置
2.若容器不为空，将数据拷贝到新空间，释放掉旧空间，更新_start,_finish,_endofstorage的位置
注意：将数据拷贝到新空间，仍然不能用memcpy函数，因为对于需要深拷贝的自定义类型，使用memcpy函数以后，新开辟空间里的元素原空间里的元素所指向的内存空间是一样的，当旧空间被释放时，会调用自定义类型的析构函数，从而使得新开辟空间里的元素指向的内存空间也被释放
void reserve(size_t n)
{
if (n > capacity())
{
T* tmp = new T[n];//新开辟一块空间
//容器不为空
if (_start)
{
size_t sizec = size();// 计算原来容器size个数
for (size_t i = 0; i < size(); i++)
{
tmp[i] = _start[i];
}
delete[] _start;//释放旧空间
_start = tmp; //更新_start
_finish = _start + sizec;// 更新_finish
_endofstorage = _start + n; // 更新_endofstorage
}
//容器为空，更新_start,_finish,_endofstorage的位置
else
{
_start = _finish = tmp;
_endofstorage = _start + n;
}
}
}3.5改变数组长度函数 resize
当n<size时，直接将_finish = _start+n（将有效数据长度缩小）
当size<n<=capacity时，我们将有效数据的长度增加到n，增加出来的有效数据内容是val
当n>capacity时，先调用上面的reserve函数进行增容，再将有效数据的长度增加到你，增加出来的有效数据内容是val
void resize(size_t n, const T& val = T())
{
//n<size()
if (n < size())
{
_finish = _start + n;
}
//n>size()
else
{
//增容
if (n > capacity())
reserve(n);
//填充数据val
size_t count = n - size();
while (count--)
{
*_finish = val;
++_finish;
}
}
}3.6 判空函数 empty
判断size() == 0
bool empty() const
{
return size() == 0;
}3.7 尾插函数 push_back
尾插入数据，首先要检查是否已满，已满则进行增容，增容后尾插
void push_back(const T& x)
{
//扩容
if (_finish == _end_of_storage)
{
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
*_finish = x;
++_finish;
}
3.8 尾删函数 pop_back
对于尾删，首先要判断容器是否为空，若为空，则断言报错，不为空，_finish--
void pop_back()
{
assert(!empty());
--_finish;
}3.9 插入函数 insert
容量不够，先增容，增容之前先记录下pos - _start的值，否则增容之后，pos还指向原来已经被释放的空间；
将pos位置往后的数据往后挪动一位，在pos位置插入值val；
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;
}
3.10 删除函数 erase
容器若为空，则做断言处理，若不为空，将pos位置往后的数据向前挪动一位,删除数字之后返回pos位置的迭代器，否则会失去该位置的迭代器，导致失效。
iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator it = pos + 1;
while (it != end())
{
*(it - 1) = *it;
++it;
}
--_finish;
}