C++【STL容器系列（二）】vector的模拟实现
1. vector的结构
我们通过查看vector的底层，能发现结构并不是我们所想的数组，_size，_capacity
而是由三个指针所组成的，这三个指针分别为；start:开始元素，finish:末尾元素的后一个位置，end_of_storage:容量（iterator是在前面typedef过的，原型为 T*）
我们前面讲结构，vector是通过模板来实现的，但模板并不能分离成两个文件，所以本次模拟只会有"vector.h"这个头文件。
由于我们是模拟实现，那么底层结构也要是三个指针
template<class T>
class vector
{
public:
typedef T* iterator;
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
};
2. vector的默认成员函数
2.1构造函数
vector(); //默认构造
template <class InputIterator>
vector(InputIterator first, InputIterator last) //迭代器构造
vector(size_t n, const T& x = T()) //用n个val初始化构造
2.1.1 默认构造
其实默认构造我们并不需要写，因为我们在声明成员变量的时候就已经给了缺省值nullptr，所以写不写都无所谓，用编译器生成的默认构造就可以了，但是如果你写了一个构造函数，那么编译器就不会生成默认构造，这时候就可以使用C++11引入的default，来让编译器生成默认构造。
vector() = default; //让编译器生成默认构造
2.1.2 迭代器构造
这里其实并不复杂，push_back迭代器所代表的内容就好了。
但问题是：为什么要在多写一个模板出来呢？
答案也很简单，因为外面的模板和这个模板推导的类型不一样，外面是推导vector<T>中的T，这个是推导整个vector<T>。
拿vector<int>举例，外面模板类型是 int，里面模板类型是vector<int>
template <class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
++first;
}
}
2.1.3 用n个val初始化构造
这个也很简单，用一个循环来push_back(val)就好了
vector(size_t n, const T& x = T())
{
reserve(n);
for (size_t i = 0; i < n; ++i)
{
push_back(x);
}
}
- reserve: 用于提前开好空间，这样就不用反复扩容了
但是这样写会有问题，我使用其他类型不会报错，但是使用vector<int>(n,val)的时候就会报错！！！
竟然调用了迭代器初始化的构造函数，这是为什么呢，原因就在模板这里。
调用函数的机制是只要类型匹配，怎么简单怎么来，由于用n个val初始化是模板参数（const T& x = T()），迭代器构造也是模板参数，但是用n个val初始化还有一个 size_t 的参数，那么模板推导后有需要类型转换，势必会麻烦一点，而迭代器是两个模板参数，推导完可以直接使用，所以编译器在调用函数的时候，自然而然就会调用迭代器版本的构造。
解决方法也很简单，就是自己再写一个 int 版本的构造（其实库里也是这样实现的）
所以我们实现的时候，要多实现一个整形版本的构造（这里只实现了int版本的）
vector(size_t n, const T& x = T())
{
reserve(n);
for (size_t i = 0; i < n; ++i)
{
push_back(x);
}
}
vector(int n, const T& x = T())
{
reserve(n);
for (size_t i = 0; i < n; ++i)
{
push_back(x);
}
}
2.2 拷贝构造
拷贝构造其实也很简单，不需要局限于传统写法和现代写法，使用范围for就能完美解决拷贝构造。
vector(const vector& v)
{
reserve(v.capacity());
for (auto& e : v)
{
push_back(e);
}
}
2.3 析构函数
~vector()
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
2.4 operator=
在完成operator=的时候，现代写法是目前最好的写法；传参的时候不传引用，而是传值传参（这样会进行拷贝构造，而拷贝构造就完成了形参的深拷贝），然后再交换形参。
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
3. vector iterator函数
还是和string一样，只实现iterator和const_iterator这两个版本
typedef T* iterator;
typedef const T* const_iterator;
3.1 begin 和 cbegin函数
iterator begin()
{
return _start;
}
const_iterator begin() const
{
return _start;
}
3.2 end() 和 cend()函数
iterator end()
{
return _finish;
}
const_iterator end() const
{
return _finish;
}
4. vector的小函数
4.1 size函数
左闭右开，一减就是元素个数
size_t size() const
{
return _finish - _start;
}
4.2 capacity函数
只是被减数的不同，返回容量数
size_t capacity() const
{
return _end_of_storage - _start;
}
4.3 swap函数
调用库里面的swap函数，避免进行深拷贝。
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
5. vector的访问函数
5.1 operator[]
直接返回该位置元素的引用
T& operator[](size_t pos)
{
assert(pos < size());
return _start[pos];
}
T& operator[](size_t pos) const
{
assert(pos < size());
return _start[pos];
}
5.2 front
返回第一个元素的引用
T& front()
{
return *_start;
}
const T& front() const
{
return *_start;
}
5.2 back
返回最后一个元素的引用
T& back()
{
return *(_finish - 1);
}
const T& back() const
{
return *(_finish - 1);
}
6 vector的增删改
6.1 reserve
void reserve(size_t n)
{
if (n > capacity())
{
size_t old_size = size();
T* tmp = new T[n];
memcpy(tmp, _start, size() * sizeof(T));
delete[] _start;
_start = tmp;
_finish = tmp + old_size;
_end_of_storage = tmp + n;
}
}
注意：我们需要在delete[] _start之前存储原本的数据个数，不然会出问题。
如果我们delete在刷新_finish，那么就会用到size()这个函数，但size这个函数是_start - _finish，由于_start这整个空间已经被释放了（_star、_finish、_end_of_storage是一块空间的不同位置），所以我们需要在释放_start之前先存储原来的数据个数size_t old_size = size();，再用old_size来刷新_finish。
但是这会有一个问题，如果我的vector是自定义类型且内部自己有申请空间，这时候扩容就会出问题，因为memcpy是浅拷贝，也就是一个字节一个字节的拷贝，这样虽然tmp是new出来的新空间，但是经过memcpy，_start 和 tmp就会指向同一个空间，delete[] _start，就相当于把tmp也delete了，这时候在尾插，析构的时候程序就会崩溃掉。
解决方法就是调用operator=，这样自定义类型就会调用自己的operator=。
void reserve(size_t n)
{
if (n > capacity())
{
size_t old_size = size();
T* tmp = new T[n];
//浅拷贝 -> 遇到有申请空间的对象出问题
//memcpy(tmp, _start, size() * sizeof(T));
//深拷贝 调用他们自己的 operator=
for (size_t i = 0; i < size(); i++)
{
tmp[i] = _start[i];
}
delete[] _start;
_start = tmp;
_finish = tmp + old_size;
_end_of_storage = tmp + n;
}
}
6.2 push_back（尾插）
void push_back(const T& val)
{
if (_finish == _end_of_storage)
{
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
*_finish = val;
++_finish;
}
6.3 pop_back（尾删）
void pop_back()
{
assert(!empty());
_finish -= 1;
}
6.4 insert（在任意位置插入数据）
iterator insert(iterator pos, const T& val)
{
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 (pos <= end)
{
*(end + 1) = *end;
--end;
}
*pos = val;
++_finish;
return pos;
}
这里和扩容后的size同理，括完容后要更新pos，要提前记录pos与_start之间的距离。
使用完insert会造成迭代器失效，解决方法：使用完这个函数后，认为这个迭代器已经失效，不要使用
6.5 erase（删除数据）
iterator erase(iterator pos)
{
assert(pos <= end());
if (pos == end())
{
pop_back();
}
else
{
iterator end = pos;
while (end != _finish)
{
*end = *(end + 1);
++end;
}
--_finish;
}
return pos;
}
用后面的数据覆盖前面就好了。
这个函数同样会造成迭代器失效，解决方法和 insert 一样。
6.6 clear（清除数据）
void clear()
{
_finish = _start;
}
6.7 empty（判空）
bool empty() const
{
return _finish == _start;
}
结语
那么这次的分享就到这里结束了~
最后感谢您能阅读完此片文章~
如果您认为这篇文章对你有帮助的话，可以用你们的手点一个免费的赞并收藏起来哟~
如果有任何建议或纠正欢迎在评论区留言~
也可以前往我的主页看更多好文哦(点击此处跳转到主页)。
原文地址：https://blog.csdn.net/2301_80216111/article/details/143693626
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！