目录
前言：
模拟实现vector是为了更好地掌握vector的使用。
std::vector是C++ 标准模板库（STL）中的动态数组容器。
准备工作：
首先在自己创建的my_vector的命名空间中创建一个头文件vector.h,再定义一个vector类，同时创建一个test.cpp文件来调用测试。
1. vector的私有成员
vector的私有成员 和 string的私有成员不一样，vector主要使用的是迭代器iterator的类型。
#include<iostream>
#include<assert.h>
using namespace std;
namespace my_vector
{
template <class T>
class vector
{
public:
typedef T* iterator;//定义了一个名为 iterator 的类型别名，实际是 T*
private:
iterator _start = nullptr; //指向动态数组的起始地址（即第一个元素的位置）
iterator _finish = nullptr; //指向当前最后一个有效元素的下一个位置（相当于size()的终点）
iterator _endofstorage = nullptr; //指向整个存储空间的末尾（即容量 capacity() 的终点）
};
}template <class T>
class vector 这是一个类模板，允许用户指定任意类型T（例如 int、string等）来创建不同类型的vector，例如：vector<int>、vector<string>等。
2. 构造函数和析构函数
//constructor
vector(){}
//destructor
~vector()
{
delete[] _start;
_start = _finish = _endofstorage = nullptr;
}3. vector遍历
3.1 push_back
在实现遍历之前，首先保证vector里面有元素，所以先实现一个尾插元素。
传统写法：
先判断是否需要库容，之后再插入元素。扩容的时候，先开辟新空间，再拷贝数据，释放旧空间，指向新空间，修改指针，最后添加数据。
在实现push_back之前要先实现 size() 和 capacity 分别来获取 数据个数和总容量。
size_t capacity() const
{
return _endofstorage - _start;
}
size_t size() const
{
return _finish - _start;
}注意在修改_finish的时候不能单纯的加size(),因为size()是_finish 与 _start两个指针相减的结果，而此时_finish还没有更新仍指向旧空间。
void push_back(const T& val)
{
//先判断是否要扩容
if (_finish == _endofstorage)
{
size_t old_size = size();
//扩容
size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
T* tmp = new T[newcapacity];
//拷贝数据
memcpy(tmp,_start,sizeof(T)*size());
//释放就空间
delete[] _start;
//修改指针
_start = tmp;
//注意
//_finish = tmp + size(); //error
_finish = tmp + old_size;
_endofstorage = tmp + newcapacity;
}
//填充数据
//_start[size()] = val;
*_finish = val;
++_finish;
}解决方法：在扩容前，记录好size()
3.2 下标访问、迭代器、范围for 遍历
3.2.1 下标访问
先判断位置是否合法，再访问数据。注意要重载出 非const和const的。
//允许修改元素
T& operator[](size_t pos)
{
//先判断访问位置是否合法
assert(pos < size());
//返回数据
return _start[pos];
}
//仅访问元素
const T& operator[](size_t pos) const
{
//先判断访问位置是否合法
assert(pos < size());
//返回数据
return _start[pos];
}3.2.2 迭代器
迭代器同样分为const和非const的。
typedef T* iterator;
typedef const T* const_iterator;
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}3.2.3 范围for
范围for是iterator的替换。
//范围for
for (auto e : v)
{
cout << e << " ";
}
cout << endl;3.2.4 print_vector
这里实现一个函数，直接来打印vector。
范围for实现：
template<typename T>
void print_vector(const vector<T>& v)
{
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}注意：
如果想用迭代器实现的时候注意：
编译器编译的时候，语法检查，确保模板实例化，一个类里面的内嵌类型或者内部类，vector<T>没有示例化，无法去找，就区分不出是类型还是静态成员遍历。
解决方法加上typename 告诉编译器是一个类型。
3.3 测试遍历
template<typename T>
void print_vector(const vector<T>& v)
{
//vector<T>::const_iterator it = v.begin(); //error
typename vector<T>::const_iterator it = v.begin(); //true
while (it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
//遍历
void test_vector1()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
for (size_t i = 0; i < v.size();i++)
{
cout << v[i] << " ";
}
cout << endl;
vector<int>::iterator it = v.begin();
//auto it = v.begin(); //这样写更方便
while (it != v.end())
{
cout << *it << " ";
++it;
}
cout << '\n';
//范围for
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}4. vector的增删改查
4.1 reserve
reserve用于预分配内存空间，避免频繁的动态内存分配。
- 如果 n > capacity() 就进行扩容
- 如果 n <= capacity() 什么都不做
根据标准库：
注意提前保存好size()。
void reserve(size_t n)
{
if (n > capacity())
{
//扩容时注意提前保存好size()
size_t old_size = size();
//开新空间,扩容
T* tmp = new T[n];
//拷贝数据
memcpy(tmp,_statr,sizeof(T)*size());
//释放旧空间
delete[] _start;
//修改指针
_start = tmp;
//_finish = tmp + size(); //error ,因为 _finsih仍指向旧空间
_finish = tmp + old_size;
_endofstorage = tmp + n;
}
}但是仍有问题：
如果T是string的时候就有问题，如图
我们发现 memcpy 是按照字节拷贝
memcpy 是按字节复制数据的，它执行的是浅拷贝。对于简单的数据类型（如 int、double），这没有问题。但对于包含动态分配内存的复杂类型（如 string），memcpy 会复制 string 对象的字节，包括其内部的指针（如 string 的 char* 指针），而不会复制指针指向的实际数据。
虽然_start指向的数据是深拷贝，但是_str指向的数据是浅拷贝
解决方法：使用拷贝构造函数来移动实际的数据。
void reserve(size_t n)
{
if (n > capacity())
{
//扩容时注意提前保存好size()
size_t old_size = size();
//开新空间,扩容
T* tmp = new T[n];
//拷贝数据
//memcpy(tmp,_start,sizeof(T)*size()); //error,vector<string> 存在隐藏的浅拷贝问题
//
for (size_t i = 0; i < size();i++)
{
tmp[i] = _start[i];
}
//释放旧空间
delete[] _start;
//修改指针
_start = tmp;
//_finish = tmp + size(); //error ,因为 _finsih仍指向旧空间
_finish = tmp + old_size;
_endofstorage = tmp + n;
}
}4.2 resize
resize 可以直接调整 vector 的有效元素数量（size()），并可以指定新增元素的默认值。
参考标准库里面的resize
如果 n > size()就扩容并插入数据，否则就删除数据。
这里缺省参数使用匿名函数的原因：
无参的匿名函数，会去调对应的默认构造函数来初始化，因为这样可以给到合适缺省值。
测试：
4.3 insert
在pos位置进行插入值value，首先判断插入位置是否合法，插入数据前要判断是否需要扩容，之后再移动数据，最后把数据插入。
//pos位置进行插入
void insert(iterator pos, const T& value)
{
//判断插入位置是否合法
assert(pos >= _start);
assert(pos <= _finish);
//数据插入前，先判断是否需要库容
if (_finish == _endofstorage)
{
reserve(capacity() == 0 ? 4 : 2*capacity());
}
//移动数据
iterator it = _finish - 1;
while (it >= pos) //注意这个时候的pos指向的仍是就空间
{
*(it + 1) = *it;
--it;
}
//插入数据
*pos = value;
++_finish;
}但是发现一下问题：
插入多个数据出现了问题，在调试插入元素的时候发现
这里我们发现it的地址编号 比pos的地址编号小，这样就无法进入while循环来移动元素了。
原因：迭代器失效
在判断空间是否需要进行扩容的时候，发生扩容，pos指向的旧空间被释放回收(可以理解为导致了野指针)。
解决方法：让其指向新空间的pos，提前判断是否扩容前，计算好相对的位置。
正确代码：
//pos位置进行插入
void insert(iterator pos, const T& value)
{
//判断插入位置是否合法
assert(pos >= _start);
assert(pos <= _finish);
//数据插入前，先判断是否需要库容
if (_finish == _endofstorage)
{
size_t len = pos - _start; //提前计算好相对的位置
reserve(capacity() == 0 ? 4 : 2*capacity());
//更新pos
pos = _start + len;
}
//移动数据
iterator it = _finish - 1;
while (it >= pos) //注意这个时候的pos指向的仍是就空间
{
*(it + 1) = *it;
--it;
}
//插入数据
*pos = value;
++_finish;
}测试一下;
4.4 erase
参考一下标准库:
先检查删除位置是否合法，再进行移动元素来完成删除。
void erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
//移动元素
iterator it = pos+1;
while(it < _finish)
{
*(it - 1) = *it;
++it;
}
--_finish;
}移动元素如图：
测试：
4.5 push_back 现代写法
通过复用其他函数的方式来实现。
void push_back(const T& val)
{
//先判断是否要扩容
if (_finish == _endofstorage)
{
reserve(capacity() == 0 ? 4 : 2*capacity());
}
//填数据
*_finish = val;
++_finish;
}push_back 现代写法plus版：
void push_back(const T& val)
{
insert(end(),val);
}4.6 pop_back
bool empty()
{
return _start == _finish;
}
void pop_back()
{
//尾删
//方式1
//assert(!empty());
//--_finish;
//方式2
erase(end()-1);
}测试：
5. 拷贝构造
当没有去手动实现去拷贝构造时
发现 这里对内置类型的拷贝构造仍然时浅拷贝，这里和string一样 都是浅拷贝问题，这里需要手动实现一个拷贝构造。
//v2(v1)
vector(const vector<T>& v)
{
reserve(v.capacity()); //避免频繁扩容
for (auto& e : v) //auto& 避免拷贝
{
push_back(e);
}
}6. swap
这里交换实现和string的类似，都是去调用标准库哦里面的swap去交换成员变量。
void swap(vector<T>& v)
{
std::swap(_start,v._start);
std::swap(_finish,v._finish);
std::swap(_endofstorage,v._endofstorage);
}
7. operator=
赋值操作符重载
将一个对象赋值给另一个对象，这里复用swap的写法。
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
8. 迭代器区间构造
//迭代器区间构造
template<class InputIterator> //类模板里面还可以有函数模板
vector(InputIterator first, InputIterator last)
{
//其他容器的迭代器都可以用
while (first != last)
{
push_back(*first);
++first;
}
}
还需要注意：
vector(size_t n,const T& val = T())
{
reserve(n);
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}
解决方法： 将size_t 改为int 这样就可以保证参数匹配了
9. 迭代器失效
9.1 关于 insert 迭代器失效
在前面的insert函数里面已经去解决迭代器失效，但是void insert(iterator pos, const T& value)，这里的pos参数是形参，形参的改变不影响实参。那给pos加上引用呢？也不可以，在函数调用传参的时候，传的是临时对象，临时对象又具有常性，那再加上const ，如果加上const ，那insert里面的就没有办法修改了。
it 使用insert以后，迭代器it就是失效了，所以就不要使用，重新更新迭代器it。
9.2 关于erase迭代器失效
出现的问题：
在去写删除偶数的函数时，重复的偶数没有删除。
情况1:跳过了一些值
原因：erase的删除是通过元素移动来覆盖前面的元素
情况2：错过了end()
解决方法：
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
{
v.erase(it);
}
else
{
it++;
}
}但是仅仅这样写是解决不了VS环境下的vector的问题。还需要参考标准库。
这里的erase会返回被删除后面的那个元素。
iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
//移动元素
iterator it = pos + 1;
while(it < _finish)
{
*(it - 1) = *it;
++it;
}
--_finish;
return pos;
}迭代器失效以后，不要直接使用，如果要使用按规则重新更新后使用。
10. 源码
vector简单实现源码请猛戳这里