模拟实现：
框架
namespace yx
{
template<class T>
class vector
{
public:
typedef T* iterator;
private:
iterator _start;
iterator _finish;
iterator _end_of_storage;
};
}
这里我们声明定义不分离
reverse()
新开一个空间，拷贝数据，然后释放旧空间
代码：
void reserve(size_t n)//满了要扩容
{
if (n > capacity())
{
T* tmp = new T[n];//new 开空间 + 初始化
memcpy(tmp,_start,sizeof(T) * size());//一个一个字节的拷贝下来
delete[] _start;
_start = tmp;
}
_finish = _start + size();
_end_of_storage = _start + n;
}capacity()
size_t capcaity() const
{
return _end_of_storage - _start;
}size()
size_t size() const
{
return _finsh - _start;
}operator[]
俩版本，一个可读可写，一个只读
T& operator[](size_t i)
{
assert(i < size());
return _start[i];
}
const T& operator[](size_t i) const
{
assert(i < size());
return _start[i];
}push_back()
分析
void push_back(const T& x)
{
if (_finish == _end_of_storage)//扩容
{
size_t newcapacity = capacity() == 0 ? 4 : capcaity * 2;
reverse(newcapacity);
}
*_finish = x;
++_finish;
}这时我们来运行一下
意外的出错了，为什么呢？
我们来调试一下
我们发现_finish竟然等于0，
其实问题出现在size(),size = _finish - _start , 但这不是正好吗？
我们来看一个图，start还是不是原来的start，当然不是了，这是start已经被更新了 ，start = tmp，相当于旧的finish 减新的start,size已经不是我们要的哪个size了。
修改方法
第一种
我们先修改一下start的位置
在reserve中
void reserve(size_t n)//满了要扩容
{
if (n > capacity())
{
T* tmp = new T[n];//new 开空间 + 初始化
if (_start)
{
memcpy(tmp, _start, sizeof(T) * size());//一个一个字节的拷贝下来
delete[] _start;
}
_finish = tmp + size();
_start = tmp;
_end_of_storage = _start + n;
}
}测试成功，但这强依赖顺序了，不太好。
第二种
oldsize方法提前存储
void reserve(size_t n)//满了要扩容
{
if (n > capacity())
{
size_t oldsize = size();//oldsize提前存储
T* tmp = new T[n];//new 开空间 + 初始化
if (_start)
{
memcpy(tmp, _start, sizeof(T) * size());//一个一个字节的拷贝下来
delete[] _start;
}
_start = tmp;
_finish = tmp + oldsize;
_end_of_storage = _start + n;
}
}~vector()
~vector()
{
if (_start)
{
delete[] _start;
_start = _finish = _end_of_storage;
}
}迭代器iterator
下面写的只是一种方式
typedef T* iterator;
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}我们来用范围for遍历测试一下
测试通过
三种遍历方式
for (size_t i = 0; i < v1.size(); i++)
{
cout << v1[i] << " ";
}cout << endl;
for (auto e : v1)
{
cout << e << " ";
}cout << endl;
vector<int>::iterator it = v1.begin();
while (it != v1.end())
{
cout << *it << " ";
++it;
}cout << endl;const迭代器
typedef const T* const_iterator;
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}pop_back()
pop_back()
{
assert(size() > 0);
--_finish;
}insert()
头插
代码：
//头插，在x前插入
void insert(iterator pos, const T& x)
{
//检查是否需要扩容
if (_finish == _end_of_storage)
{
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = x;
++_finish;
}我们测试一下
为什么是个随机值呢？
insert迭代器失效
此时_finish = _end_of_storage ，出现了扩容，
导致出现了迭代器失效，pos变为野指针
扩容后，start，finish _end_of_storage都去了新空间，旧空间释放了，而pos还在旧空间里，pos为野指针，所以导致了随机值。
修改方法，算出pos与start的距离
修改后代码：
void insert(iterator pos, const T& x)
{
//检查是否需要扩容
if (_finish == _end_of_storage)
{
size_t len = pos - _start;
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);//扩容完后pos为野指针
pos = _start + len;//pos找到新空间位置
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = x;
++_finish;
}测试通过
it会不会失效呢？失效后的迭代器还能访问吗？
实参传给形参，形参的改变不会影响实参。但如果出现了扩容呢？insert函数内的pos可以解决野指针问题，但it解决不了。我们就不敢访问这个迭代器了。因为出现了野指针。
我们访问一下迭代器，出现野指针了吧。
迭代器失效后的建议是不要访问。
如果我们给pos加个引用呢？
测试一下
我们发现begin传不过去了，为什么？
v1.begin()，begin() 返回一个迭代器，而且是传值返回，c++规定，传值返回返回的不是_start，返回的是其拷贝，生成临时对象，临时对象具有常性，所以非不要不访问。
erase()
头删
void erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator it = pos + 1;
while (it != _finish)
{
*(it - 1) = *it;
++it;
}
--_finish;
}
测试
erase的迭代器失效
报错了，为什么？
erase迭代器失效
我们界定erase以后，这个it失效了。为什么？
第一种情况：缩容
如果删除后的数据小于容量capacity的一半，就开始缩容
旧的空间释放掉，导致it变为野指针
第二种情况：越界
如果我们删除5呢。
这里出现了越界（非法访问）。迭代器it也失效了
所以erase it 以后，it就失效。
在vs中不会缩容，那它如何判断的呢？vs下的iterator是一个很复杂的类型，不是一个原生指针实现的
我们可以这样理解，erase it以后，就把it的类型改了，我们再访问的时候就会报错。
如何修改呢？
给其一个返回值
我们来删除所有偶数
void test6()
{
std::vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
//删除所有偶数
std::vector<int>::iterator it = v1.begin();
while (it != v1.end())
{
if (*it % 2 == 0)
{
v1.erase(it);
}
else
{
++it;
}
}
for (auto e : v1)
{
cout << e << " ";
}cout << endl;
}程序对不对呢？
当然不对，erase it 一次以后，it就失效了，程序报错。调试一下
删除完2后，it失效，程序报错，如何修改呢？
拷贝构造
我们没有写拷贝构造，编译器会默认生成一个拷贝构造。是浅拷贝，完成的是值的拷贝
void test7()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
vector<int> v2(v1);
for (auto e : v2)
{
cout << e << " ";
}cout << endl;
}我们测试一下
会导致析构两次，报错。
我们没有写默认构造，拷贝构造也是构造，构造函数的定义是，只要你写了任意构造，编译器默认就不生成
这里我们强制编译器生成默认构造
//强制编译器生成默认的构造
vector() = default;
//拷贝构造v2(v1)，拷贝构造也是构造
vector(const vector<T>& v)
{
for (auto e : v)
{
push_back(e);
}
}测试通过
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);
}operator=
v1 = v3，直接传值传参v就是v3的拷贝构造，v1就是this，tihs和v交换，this不要的数据给v，v出了作用域会析构，写法对于所有深拷贝都适合
//赋值 v1 = v3，v1之前的空间要释放，v1要和v3有一样大的空间一样的值
vector<T> operator=(vector<T> v)//直接传值传参v就是v3的拷贝，
{
this->swap(v);
return *this;
}测试通过
迭代器区间初始化
迭代器区间初始化
类模板的成员函数
函数模板，支持任意容器的迭代器初始化
template <class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
++first;
}
}
迭代器区间初始化可以更好的控制初始化范围。
那么再这里写函数模板到底是为了什么？
任意类型的迭代器都能用。
char和转化为int，类型提升，用的ascii码
n个value值构造函数
vector(size_t n, const T& val = T())
{
reserve(n);
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}我们看到val的值为T()，这里是匿名对象，
那val能不能给0呢？答案是不可以的，为什么？
当T的为int时，当然可以；但当T为string呢？T为vector呢？是不是就不行了。
当然，当T()匿名对象的T为int的时候是不是就不对了呢？
这个在C语言中是不对的，但在C++中是正确的。
void test9()
{
int i = 0;
int j(1);
int k = int();
int x = int(2);
}
C++对内置类型进行了升级。C++的内置类型也有了构造，为了兼容模板。
测试
v2初始化为了xxx
当我们再写一个v3初始化为1时，出现编译错误，为什么？
由于此时有两个构造，它会选择更适合自己的模板，所以选择了第一个，*first出现了错误。
如何修改呢？
第一种
在10后面加个u，表示无符号整型
第二种
重载了一个构造函数，size_t修改为int
对于初始化{}
单参数和多参数对象隐式类型转换
class A
{
public:
A(int a1)
:_a1(a1)
, _a2(0)
{
}
A(int a1,int a2)
:_a1(a1)
, _a2(a2)
{
}
private:
int _a1;
int _a2;
};
单参数和多参数对象隐式类型转换
*****************
单参数用括号，多参数必须用花括号{ }
A aa1(1, 1);
A aa2 = { 2,2 };
A aa2{ 2,2 };
const A& aa8 = { 1, 2};
A aa3(1);
A aa4 = 1;const A& aa8 = { 1, 2};aa8引用的是{1，2}中间产生的临时对象，具有常性
c++11规定单参数也可以用花括号{}来初始化
A aa5(1);
A aa6 = { 1 };
A aa7{ 1 };结果是一样的，但单参数不建议这样写。
我们来看一下下面代码是不是隐式类型转换
vector<int> v1 = { 1,2,3,4,5,6 };
for (auto e : v1)
{
cout << e << " ";
}cout << endl;这里当然不是，上面描述的有单参数的和两个参数，本质上都去调自己的构造去了。
这里不是隐式类型转换，上面参数固定，这里参数不固定，可以是3个可以是5个等。
为什么会这样呢？
因为c++11里支持initializer_list，新增的一个类型，方便初始化 ，
vector<int> v1 = { 1,2,3,4,5,6 };这里的1 ，2 ，3 ，4 ，5 ，6 的类型为initializer_list
它的底层其实是俩指针，一个指向开始，一个指向最后一个数据的下一位，所以这里我们可以用范围for遍历。
vector<int> v2 = {1,2,3,4,5,6} 这里的{1，2，3，4，5，6}类型为initializer_list，生成临时对象，拷贝构造给v2，优化为构造。
我们在这里还需要写一个initializer_list的构造
vector(initializer_list<T> il)
{
reserve(il.size());
for (auto e : il)
{
push_back(e);
}
}测试
我们看一下下面这个怎某构造
vector<A> v3 = { };
知识点
我先把结论告诉你：vector<>里面的数据类型是一个自定义类型时，要考虑深拷贝。
我们看一下代码
void test11()
{
vector<string> v1;
v1.push_back("11111111111111");
v1.push_back("11111111111111");
v1.push_back("11111111111111");
v1.push_back("11111111111111");
for (auto e : v1)
{
cout << e << " ";
}cout << endl;
}测试一下
没问题
如果我们再push一次呢
代码出错了，为什么？？？
我们调试一下
空间不够，需要扩容，然后把数据给给tmp，_start释放。而数据拷贝给新空间的时候是浅拷贝，string没有深拷贝
memcpy是一个字节一个字节的拷贝，对任意类型拷贝都是浅拷贝。
tmp指向的还是原来的哪个地址，而_start空间释放了，它的深拷贝没有发生再vector这一层，而是发生在自定义类型存的数据。
如何解决呢？
对_str进行深拷贝，但我们不能访问_str里的数据
我们直接使用赋值来完成工作
void reserve(size_t n)//满了要扩容
{
if (n > capacity())
{
size_t oldsize = size();//oldsize提前存储
T* tmp = new T[n];//new 开空间 + 初始化
//if (_start)
//{
// memcpy(tmp, _start, sizeof(T) * size());//一个一个字节的拷贝下来
// delete[] _start;
//}
if (_start)
{
for (size_t i = 0; i < oldsize; i++)
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = tmp + oldsize;
_end_of_storage = _start + n;
}
}本集完
