🔥博客主页：小王又困了
📚系列专栏：C++
🌟人之为学，不日近则日退
❤️感谢大家点赞👍收藏⭐评论✍️
目录
一、存储结构
二、默认成员函数
📒2.1构造函数
📒2.2拷贝构造
📒2.3赋值重载
三、容量操作
📒3.1获取有效元素个数
📒3.2获取空间容量大小
📒3.3使用reverse扩容
四、数据访问
📒4.1下标访问
📒4.1迭代器访问
五、修正操作
📒5.1尾插数据
📒5.2尾删数据
📒5.3在任意位置插入数据
📒5.4在任意位置删除数据
🗒️前言：
vector是STL容器之一，其底层实现类似于数据结构顺序表，相当于string来说得益于泛型模板的加持使得vector可以变为任何类型，且是可以动态扩容。接下来我们就通过vector各种接口的模拟实现来深入了解vector。
一、存储结构
与string底层结构不同，vector底层空间结构为三个指针:
namespace bit
{
template<class T> //模板参数T
class vector
{
public:
typedef T* iterator; //指针重命名为迭代器
typedef const T* const_iterator;
private:
iterator _start;
iterator _finish;
iterator _end_of_storage;
}；
}- _start：指向空间的起始地址
- _finish：指向最后一个数据的下一个地址，相当于_size
- _end_of_stroage：指向空间最后一个最末地址,相当于_capacity
小Tips：由于vector使用了模板，所以函数实现都在头文件中，防止因为模板导致的链接错误的问题！
二、默认成员函数
📒2.1构造函数
我们在这里实现三个版本，分别是：默认构造函数，带参构造函数和迭代器区间构造。
- 默认构造函数：初始化三个指针置空即可
- 带参构造函数：初始化n个T类型的value值在对象中
- 迭代器区间构造：通过其他容器迭代器或指针迭代插入其所有值
//默认构造函数
vector()
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{}
vector () = default //强制编译器生存默认构造
//构造n个T类型数据
vector(size_t n, const T& value = T())
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
reserve(n);
for (int i = 0; i < n; ++i)
{
*(_finish++) = value;
}
}
//迭代器区间构造
template<class InputIterator>
vector(InputIterator first, InputIterator last)
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
while (first != last) //迭代器插入数据
{
push_back(*first);
++first;
}
}
注意：我们实现了带参构造函数的n为size_t类型的版本，如果我们使用带参构造函数实例化，则会发生非法间接寻址的错误！这是因为size_t是整型，实例化T数据类型也是整型，此时编译器会自动匹配最合适的构造函数，于是匹配到了迭代器区间构造。我们只要写一个n为int类型的带参构造参数去匹配，就可以解决问题。
📒2.2拷贝构造
对于拷贝构造我们要考虑深浅拷贝的问题，我们希望当一个vector对象拷贝另一个对象时新对象开辟新的空间拷贝数据，而不是两个对象共用同一块空间，否则会析构两次造成内存泄漏。
vector(const vector<T>& v)
{
reserve(v.capacity());
for (auto e : v)
{
push_back(e);
}
}
📒2.3赋值重载
赋值重载与拷贝构造的问题类似，也要注意深拷贝问题；区别于拷贝构造的地方在于不需要新建对象，但是需要判断是否为同一个对象避免重复开空间。
//传统写法
vector<T>& operator=(const vector<T>& v)
{
if (&v != this)
{
clear();
reserve(v.capacity());
for (int i = 0; i < v.size(); ++i)
{
*(_finish++) = v._start[i];
}
}
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);
}
// v1 = v3
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}三、容量操作
📒3.1获取有效元素个数
size_t size() const
{
return _finish - _start;
}📒3.2获取空间容量大小
size_t capacity() const
{
return _end_of_storage - _start;
}小Tips：vevtor是使用3个指针对空间进行管理，使用_finish(有效数据指针)减去_start(空间首地址)就能得出有效数据个数，容量同理。我们只是对数据进行访问不涉及修改，所以使用const修饰this指针。
📒3.3使用reverse扩容
void reserve(size_t n)
{
if (n > capacity())
{
size_t oldsize = size();//获取扩容前有效数据个数
T* tmp = new T[n];
if(_start)
{
//memcpy(tmp, _start, sizeof(T*) * size());
for (size_t i = 0; i < oldsize; i++)
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + oldsize;
_end_of_storage = _start + n;
}
}
//错误写法：_finish = _start + size() ；小Tips：我们要用oldsize记录扩容前有效数据的个数，按照错误写法size()是用扩容前的_finish和扩容后的_start来计算的，结果是错误的。当string类型的对象要扩容时，memcpy对数据进行的是浅拷贝，两个对象指向同一块空间，会析构两次造成内存泄漏。
四、数据访问
📒4.1下标访问
下标访问是通过重载 [ ] 运算符实现的，在下标pos正确的情况下，返回当前下标字符的引用，否则assert报错。
T& operator[](size_t pos)
{
assert(pos < size());
return _start[pos];
}
const T& operator[](size_t pos) const //const引用版本,不可以修改
{
assert(pos < size());
return _start[pos];
}
at 函数我们可以复用运算符[ ]来实现。 at 函数的检查手段是抛异常。
T& at(size_t pos)
{
return (*this)[pos];
}
const T& at(size_t pos) const
{
return (*this)[pos];
}
📒4.1迭代器访问
typedef T* iterator;
typedef const T* const_iterator;
const_iterator begin() const { return _start; }
const_iterator end() const { return _finish; }
iterator begin() { return _start; }
iterator end() { return _finish; }
//范围for
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;五、修正操作
📒5.1尾插数据
在尾插前检查容量是否充足，空间不够扩容，然后直接插入_finish的空位下即可，_finish指针移动到下一个空位。
void push_back(const T x)
{
if (_finish == _end_of_storage)
{
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
}
*_finish = x;
++_finish;
//insert(end(), x); //复用
}📒5.2尾删数据
尾删只需要--_finish，但需要判断size是否>0。
void pop_back()
{
assert(size() > 0);
--_finish;
}📒5.3在任意位置插入数据
当我们传递一个迭代器在pos位置插入数据时，可能涉及容器扩容，如果扩容，那么迭代器是旧空间的迭代器，则会导致迭代器失效，因为原有空间已经被释放，但迭代器还是指向原空间(那么就是野指针)，所以我们在插入或删除后要更新迭代器。
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start);
assert(pos <= _finish);
if (_finish == _end_of_storage)
{
size_t 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 = x;
_finish++;
return pos;
}小Tips：如果要进行扩容我们用len来记录扩容前从_start到pos位置数据的个数，然后扩容后更新pos的位置。
📒5.4在任意位置删除数据
删除元素也会有迭代器失效的问题，可能会越界访问 。
iterator earse(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator it = pos + 1;
while (it != _finish)
{
*(it - 1) = *it;
it++;
}
--_finish;
return pos; //返回删除元素位置的下一个元素的迭代器
}🎁结语：
本次的内容到这里就结束啦。希望大家阅读完可以有所收获，同时也感谢各位读者三连支持。文章有问题可以在评论区留言，博主一定认真认真修改，以后写出更好的文章。你们的支持就是博主最大的动力。
