C++ STL : 模拟实现STL中的vector类
文章目录
vector
vector的介绍
vector的文档介绍
- vector是表示可变大小数组的序列容器。
- 就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素 进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自 动处理。
- 本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小 为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是
一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大 小。- vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存 储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是
对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。- 因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增 长。
- 与其它动态序列容器相比（deques, lists and forward_lists）， vector在访问元素的时候更加高效，在 末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起lists和 forward_lists统一的迭代器和引用更好。
其实vector就是数据结构中的顺序表， 关于顺序表的实现思路我之前有写过
https://blog.csdn.net/qq_35423154/article/details/104017476
但是他又有些不同，我们传统的顺序表使用了capacity，size和data，而stl中的vector分别使用三个迭代器来实现，start指向数据起始位置，finish指向数据结束位置，endOfStorage指向这块存储空间的结束位置。
我简单的画了一个图
这就是vector的内存布局。
从start到finish这一段就是目前已经存储的数据域
从start到endOfStorage这一段就是可存储的空间大小
vector的优缺点
优点：
支持下标的随机访问，可以很好的支持很多算法，如二分、排序等
缺点：
1.插入删除的效率较低，因为需要挪动数据，效率为O（n ）
2.因为是顺序结构，所以空间不够时需要增容，而增容需要申请新空间，将数据拷贝到新空间，释放旧空间，造成了效率的低下。
vector的优缺点其实也就是顺序表的优缺点，所以STL还加入了与顺序表互补的链表，也就是list，list的模拟实现我也会抽空写一篇博客
实现时需要注意的细节问题
具体的思路和细节我都写在了注释里，这部分是我觉得需要单独拿出来说一下的
1. Capacity增长问题
在Windows的vs环境下，capacity的增长接近于1.5倍，而在Linux的g++环境下，capacity的增长是2倍。
两者之间的分歧主要体现在，是优先考虑时间还是空间的问题。
1.对于g++2倍增容：
优点：每次申请的空间足够多时，就能减少申请的次数，每次扩容都代表着要申请新空间，拷贝数据，销毁原空间几个步骤。所以这样能够大大的提升效率，
缺点：有可能因为申请的空间过多造成资源的浪费
所以这是典型的以空间换时间的做法。
2.对于vs的1.5倍增容：
优点：每次申请1.5倍的空间，这样就可以更好的利用空间，比起2倍更不容易造成资源浪费。
缺点：如果需求的空间过大，就需要多次扩容，因为扩容的次数过多，导致效率低
所以这是典型的以时间换空间的做法。
这里我选用的是g++的2倍增容
2. memset等函数来带的按字节拷贝问题
我在实现resize中对多出空间初始化时复用了之前string的代码，使用了memset拷贝数据，然后出现了错误，所有数据都和我给的不同。
错误的原因是因为memset等string.h中的函数都是按照一个一个字节拷贝的，这种按字节拷贝的方法对于char类型并没有什么问题，但是对于其他大小不为1字节的类型，就有问题了。
例如我是用memset给整型的数组初始化为1
int arr[10];
memset(arr, 1, sizeof(int) * 10);
可以看到初始化后的结果是这个
原因就是它是将1这个数据，拷贝到每一个字节中，所以实际上初始化的值是
00000001000000010000000100000001
也就是16843009
3. 深浅拷贝问题
这个问题也与上面有点关联，对于reserve，我也复用了上次的代码，其中使用memcpy来拷贝原数据到新的空间中，使用这种方法对于内置类型来说的确是深拷贝，但是对于自定义类型和一些容器如：string来说就是浅拷贝了。
当拷贝string时，拷贝size和capacity都没有问题，但是拷贝str时他就直接把str的地址拷贝过去了，这时当释放原空间时，str也被释放掉，而新数据中的str指向一个被释放的空间，当调用析构函数，或者对这段空间进行访问的时候，都会出现错误。
解决方法：使用赋值运算符进行深拷贝，因为会自动调用对应类型的重载后的赋值运算符，这样就可以避免自定义类型中部分成员浅拷贝的问题
void reserve(size_t n)
{
//容量没增大则不操作
if (n <= capacity())
return;
//后面会修改到_finish和_start，所以后面无法调用size（）
size_t length = size();
T* temp = new T[n];
//判断_start是否为空，防止释放空指针
if (_start)
{
//深拷贝，这里不能像string一样使用strcpy或者memcpy，因为这两个都是按照字节拷贝
//还有一个原因，就是对于某些容器如string，memcpy拷贝时会直接浅拷贝_str,就会出现问题，而如果使用赋值则会自动调用对应类型的重载赋值运算符
for (size_t i = 0; i < length; i++)
{
temp[i] = _start[i];
}
delete[] _start;
}
_start = temp;
_finish = _start + length;
_endOfStorage = _start + n;
}
4. 迭代器失效问题
这也是最常见的问题，这样的问题也分几种情况
1.数据挪动造成的迭代器失效
比如删除数据中的偶数
it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
erase(it);
else
++it;
}
}
这样的代码就容易出现问题，因为erase和insert都会因为插入删除数据，造成数据的挪动，这时因为数据地址的变动，导致了使用旧的迭代器访问不到原本想要访问的数据。
这个问题在vs下会直接报错,g++检查不够严格，不会报错。
这里只需要把erase那一行改成这样，就可以解决，因为erase会返回新的迭代器，使用新的迭代器即可
it = erase(it);
2.增容带来的迭代器失效问题
当使用push_back，reserve，insert等会造成增容的函数时，就会出现这种情况，因为扩容会先申请一个新的空间，然后将原数据拷贝到新空间，再释放旧空间，此时原来的迭代器就会全部失效，这个问题也需要注意。
实现的接口
默认成员函数部分
vector();
vector(int n, const T& value = T());
vector(const_iterator first, const_iterator last);
vector(const vector<T>& v);
vector<T>& operator=(vector<T> v);
~vector();
迭代器部分
typedef T* iterator;
typedef const T* const_iterator;
iterator begin();
iterator end();
const_iterator begin() const;
const_iterator end() const;
容量部分
size_t capacity() const;
size_t size() const;
bool empty() const;
void reserve(size_t n);
void resize(size_t n, const T& value = T());
元素访问部分
T& operator[](size_t pos);
const T& operator[](size_t pos) const;
修改部分
void push_back(const T& x);
void pop_back();
void swap(vector<T>& v);
iterator insert(iterator pos, const T& x);
iterator erase(iterator pos);
void clear();
私有成员
iterator _start; // 指向数据的开始
iterator _finish; // 指向数据的结束
iterator _endOfStorage; // 指向存储容量的尾
代码实现
#pragma once
#include<cassert>
namespace lee
{
//类模板
template<class T>
class vector
{
public:
//迭代器
typedef T* iterator;
typedef const T* const_iterator;
/*
------------------------------------------------------------
默认成员函数部分
Member functions
------------------------------------------------------------
*/
vector()
: _start(nullptr)
, _finish(nullptr)
, _endOfStorage(nullptr)
{}
vector(int n, const T& value = T())
{
assert(n > 0);
//直接用resize就可以，功能一样
resize(n, value);
}
vector(const_iterator first, const_iterator last)
: _start(nullptr)
, _finish(nullptr)
, _endOfStorage(nullptr)
{
reserve(last - first);
//深拷贝
while (first != last)
{
*_finish++ = *first++;
}
_endOfStorage = _finish;
}
vector(const vector<T>& v)
: _start(nullptr)
, _finish(nullptr)
, _endOfStorage(nullptr)
{
/*
直接构建一个然后交换
vector temp(v.begin(), v.end());
swap(temp);
*/
reserve(v.capacity());
for (const auto& i : v)
{
push_back(i);
}
}
vector<T>& operator=(vector<T> v)
{
//直接和形参交换，交换过去的数据也会在栈帧销毁时清除。
swap(v);
return *this;
}
~vector()
{
delete[] _start;
_start = _finish = _endOfStorage = nullptr;
}
/*
------------------------------------------------------------
迭代器部分
Iterators:
------------------------------------------------------------
*/
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
/*
------------------------------------------------------------
容量部分
Capacity
------------------------------------------------------------
*/
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _endOfStorage - _start;
}
void reserve(size_t n)
{
//容量没增大则不操作
if (n <= capacity())
return;
//后面会修改到_finish和_start，所以后面无法调用size（）
size_t length = size();
T* temp = new T[n];
//判断_start是否为空，防止释放空指针
if (_start)
{
//深拷贝，这里不能像string一样使用strcpy或者memcpy，因为这两个都是按照字节拷贝
//还有一个原因，就是对于某些容器如string，memcpy拷贝时会直接浅拷贝_str,就会出现问题，而如果使用赋值则会自动调用对应类型的重载赋值运算符
for (size_t i = 0; i < length; i++)
{
temp[i] = _start[i];
}
delete[] _start;
}
_start = temp;
_finish = _start + length;
_endOfStorage = _start + n;
}
//value为该类型的缺省值
void resize(size_t n, const T& value = T())
{
//如果原来的大则初始化后面的数据
if (size() < n)
{
//如果容量不够则扩容
if (capacity() < n)
{
reserve(n);
}
//将多出来的部分初始化为value
while (_finish < _start + n)
{
*_finish++ = value;
}
}
//如果容量比原来的小，则直接从对应位置截断数据
else
{
_finish = _start + n;
}
}
bool empty() const
{
return _start == _finish;
}
/*
------------------------------------------------------------
元素访问部分
Element access:
------------------------------------------------------------
*/
T& operator[](size_t pos)
{
assert(pos < size());
return _start[pos];
}
const T& operator[](size_t pos) const
{
assert(pos < size());
return _start[pos];
}
/*
------------------------------------------------------------
修改部分
Modifiers:
------------------------------------------------------------
*/
void push_back(const T& x)
{
//容量满了则扩容
if (_finish == _endOfStorage)
{
size_t newCapacity = capacity() == 0 ? 2 : 2 * capacity();
reserve(newCapacity);
}
*_finish++ = x;
}
void pop_back()
{
assert(_start < _finish);
_finish--;
}
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endOfStorage, v._endOfStorage);
}
iterator insert(iterator pos, const T& x)
{
assert(pos <= _finish);
//空间满了则扩容
if (_finish == _endOfStorage)
{
size_t newCapacity = capacity() == 0 ? 2 : 2 * capacity();
reserve(newCapacity);
}
//数据后移
for (auto i = _finish; i >= pos; i--)
{
*i = *(i - 1);
}
//插入数据，并且结束位置后移
*pos = x;
_finish++;
return pos;
}
iterator erase(iterator pos)
{
assert(pos <= _finish);
//数据前移
for (auto i = pos; i <= _finish; i++)
{
*i = *(i + 1);
}
_finish--;
return pos;
}
void clear()
{
_finish = _start;
}
private:
iterator _start; // 指向数据的开始
iterator _finish; // 指向数据的结束
iterator _endOfStorage; // 指向存储容量的尾
};
}