目录
1. vector的介绍
vector是表示可变大小数组的序列容器
就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问（支持随机访问），和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
1.1 vector构造函数的定义
这里先介绍5个重要的构造函数给大家看看，现在大家了解一下就可以了，后续会一一实现的。
| 构造函数声明 | 接口声明 |
| vector()（重点） | 无参构造 |
| vector（size_type n, const value_type& val = value_type()） | 构造并初始化n个val |
| vector (const vector& x); （重点） | 拷贝构造 |
| template <class InputIterator> vector (InputIterator first, InputIterator last) | 使用迭代器进行初始化构造 |
| vector(initializer_list<T> il) | 使用花括号进行初始化构造 |
1.2 vector iterator的使用
因为vector是类模板，所以iterator就是模板参数类型的指针
然后vector有三个成员变量
这三个成员变量的作用如下：
1.3 vector的空间增长问题
| 容量问题（这里介绍的是成员函数） | 接口说明 |
| size | 获取数据个数 |
| capacity | 获取容量大小 |
| empty | 判断是否为空 |
| resize（重点） | 改变vector的size |
| reserve | 改变vector的capacity |
-
capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。这个问题经常会考察，不要固化的认为，vector增容都是2倍，具体增长多少是根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本STL。
-
reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以提前将空间设置足够用于缓解vector增容的代价缺陷问题。（在插入的数据的时候避免了边插入边扩容导致效率低下的问题了）
-
resize在开空间的同时还会进行初始化，影响size。
void TestVectorExpandOP()
{
vector<int> v;
size_t sz = v.capacity();
v.reserve(100); // 提前将容量设置好，可以避免一遍插入一遍扩容
cout << "making bar grow:\n";
for (int i = 0; i < 100; ++i)
{
v.push_back(i);
if (sz != v.capacity())
{
sz = v.capacity();
cout << "capacity changed: " << sz << '\n';
}
}
}1.4 vector的增删查改
| vector的增删查改 | 接口说明 |
| push_back（重点） | 尾插 |
| pop_back（重点） | 尾删 |
| find | 查找（注意这个是算法模块实现，不是vector的成员接口） |
| insert | 在position之前插入val |
| erase | 删除position位置的数据 |
| swap | 交换两个vector的数据空间 |
| operator[] | 想数组一样访问 |
2. vector代码的实现
2.1 vector扩容
在实现扩容前，我们首先要把vector最基本的成员函数搭建好，以便于后面我们的使用
成员函数包括：begin()，end()，size()，capacity()
namespace bit
{
template <class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
iterator begin()
{
return _start;
}
const_iterator begin() const
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator end() const
{
return _finish;
}
//这里获取的是容量大小
size_t capacity()
{
return _end_of_storage - _start;
}
//指针-指针得到的是指针之间的元素个数
//这里获取的是数据个数
size_t size()
{
return _finish - _start;
}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
};
}实现完最基础的成员函数后，就要实现扩容了
#pragma once
namespace bit
{
template <class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
iterator begin()
{
return _start;
}
const_iterator begin() const
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator end() const
{
return _finish;
}
size_t capacity() const
{
return _end_of_storage - _start;
}
size_t size()
{
return _finish - _start;
}
void reserve(size_t n)
{
if (n > capacity())
{
iterator tmp = new T[n];
size_t oldsize = size();
//不为空才需要拷贝一份代码，并且释放原本的旧空间
if (_start)
{
//这种是一个字节一个字节进行拷贝
//memcpy(tmp, _start, sizeof(T) * size());
//下面这个方法也是以一个字节一个字节进行进行拷贝，但这种写法巨坑
//一共要拷贝 sizeof(T) * size()个字符个数
strncpy((char*)tmp, (char*)_start, sizeof(T) * size());
delete[] _start;
}
_start = tmp;
//此时size()里面的_start已经不是指向原先数组的起始地址
//而是指向tmp所指向的数组的起始地址，所以
//_finish = _start + _finish - _start;
//求得：_finish = _finish 因此_finish是不变的
//因此finish迭代器失效，因为指向的旧空间，并且旧空间等等会被释放
//_finish = _start + size();
//解决办法1：
//把_finish放到_start = tmp前面
//_finish = tmp + size();
//方法1不推荐哈，因为有点依赖顺序，最好方法是提前记录好size()
// 方法2
_finish = tmp + oldsize;
_end_of_storage = _start + n;
}
}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
};
}
上面代码有非常多的细节需要说明
首先类里面定义的函数是没有顺序可言的，就算我们把reserve扩容函数写在size()函数上面，我们这里依旧是可以调用的！！！
这里我们需要注意的一个点就是如果_start原本指向就是为空，那就没有必要走拷贝步骤，更没必要对_start实施delete[]
重点：
我这边写了两个拷贝空间数据的函数，memcpy(tmp, _start, sizeof(T) * size())和strncpy(tmp, _start, sizeof(T) * size())。大家觉得哪个比较好，因该留哪个。
结论：
strncpy(tmp, _start, sizeof(T) * size()) 这个写法用在这里巨坑
这里我就先补充说明，就是一开始如果数组是没有空间的，那扩容一开始就会分配4个大小数组空间，所以这里一开始我们插入4个元素的时候是正常的，那我们在插入一个元素后就会产生扩容，那扩容我们本意是想把旧空间的元素拷贝到新空间中，在尾插一个5，可最终我们输出的时候不是1,2,3,4,5而是1,0,0,0,5
很明显，这是扩容出现的问题，问题就出在我们拷贝旧空间时使用错了方法
如果我们不知道strncpy的使用规则，我们可以看下面这张图
这里我们假设T是int类型，那我们就要从旧空间拷贝16个字节数据到新空间去
而strncpy有个问题就是如果我们提前遇到了‘\0’，但是我们还没有拷贝完，那就要在目的空间继续添加'\0'，直到拷贝完(num等于0)
因为一开始拷贝元素是1，1在小端存储的时候是01 00 00 00，所以一开始先把01拷贝到新空间去，而接着遇到了00，00就是0，'\0'的ASCII也是0，由于提前遇到了'\0'了，而我们此时还没有拷贝完，所以就要继续追加num个'\0'
所以我说用strncpy这种拷贝方法巨坑，那为什么我一开始会用这种拷贝方法的原因是string自定义实现的时候就是用strncpy的拷贝方式，所以我把在string拷贝旧空间的方法移接到vector的时候就有问题（这个问题真的困扰我有一段时间）
解决了上面的问题，接着面临的问题就是扩容后迭代器失效
所以这里的解决方法有两个：
第一：调换位置，把_finish = _start + size()放在_start = tmp前面，但这样有点依赖顺序，不是最优选择。因为库里面就不是这么实现的
第二：提前记入旧数组的长度。方法：size_t oldsize = size();因此_finish就等于 _start + oldsize
最终扩容的代码
void reserve(size_t n)
{
if (n > capacity())
{
iterator tmp = new T[n];
size_t oldsize = size();
//不为空才需要拷贝一份代码，并且释放原本的旧空间
if (_start)
{
//这种是一个字节一个字节进行拷贝
memcpy(tmp, _start, sizeof(T) * size());
//下面这个方法也是以一个字节一个字节进行进行拷贝，但这种写法巨坑
//一共要拷贝 sizeof(T) * size()个字符个数
//strncpy((char*)tmp, (char*)_start, sizeof(T) * size());
delete[] _start;
}
_start = tmp;
//此时size()里面的_start已经不是指向原先数组的起始地址
//而是指向tmp所指向的数组的起始地址，所以
//_finish = _start + _finish - _start;
//求得：_finish = _finish 因此_finish是不变的
//因此finish迭代器失效，因为指向的旧空间，并且旧空间等等会被释放
//_finish = _start + size();
//解决办法1：
//把_finish放到_start = tmp前面
//_finish = tmp + size();
//方法1不推荐哈，因为有点依赖顺序，最好方法是提前记录好size()
// 方法2
_finish = tmp + oldsize;
_end_of_storage = _start + n;
}
}2.2 插入元素
vector中插入元素有2中方法：第一种是insert；第二种是push_back
我们首先介绍insert
void insert(iterator pos, const T& x)
{
assert(pos >= _start);
assert(pos <= _finish);
if (_finish == _end_of_storage)
{
size_t len = pos - _start;
int newcapacity = capacity() == 0 ? 4 : 2 * capacity();
reserve(newcapacity);
//pos = _start + len，如果不这么写的话，pos还是指向旧空间
//而扩容的时候旧空间会被释放，因此在pos位置的空间插入元素，是错误的
pos = _start + len;
}
iterator end = _finish;
while (end > pos)
{
*end = *(end - 1);
end--;
}
*pos = x;
_finish++;
}首先insert插入的位置要合规，插入位置pos必须在_start和_finish中间
接着，我们考虑个问题，既然扩容的时候会产生迭代器失效的问题，那用insert插入元素也会吗？
答案会（原因如图所示）
那大家想一想，除了这里的插入，其他地方如果调用插入函数，会不会也产生迭代器失效的问题
当程序调试到433行就会报错，原因是访问权限冲突
当然要揭晓答案前，我们先来了解下算法库实现好的find函数
find函数找到了就返回找到位置，找不到就返回开区间的位置
那如果找到了，我们是不是要插入元素，那如果插入元素的时候恰好遇到了扩容，是不是test_vector10()函数中的pos也变成了野指针，所以我们不要访问，如果需要实在想要访问pos位置的元素，那就更新下迭代器
难点来临！！！
那可能也有同学想说，那我们在insert形参第一个参数加引用，我们不就可能完美解决所有的问题了吗？而且insert就可以不用返回值了。
如果实参是这段代码，确实还挺好的
但是我们如果看库里面实现的insert，我们可以发现，库里面都是没有使用引用的
之所以没有这么实现，是因为不是所有场景都能用引用来解决（如下面代码）
这里我们本意是想在v1.begin()也就是v1的_start指针指向的起始位置插入元素0，可是编译器一执行就报错了，报错的原因其实就是形参用引用导致的。
那为什么形参用引用就会报错呢？请继续往下看
首先我们来看begin()是这么实现的
我们begin()返回类型是iterator，而iterator其实是T*，但是编译器却不这么认为
看到没，编译器会认为v1.begin()的返回类型是const int*，这也就是为什么我们使用引用编译器会报错的原因，也是vector中实现insert没使用引用的原因
重点：
因为我们返回的时候没有在类型后加引用，所以是传值返回，而传值返回返回的是临时对象，临时对象具有常性。
此时可能同学看到这里也是很懵，明明我们这里的返回类型是iterator，当T时int，那iterator就是int*，可是编译器却认为begin()返回的类型是const int*。这里是我们确实是返回_start，而且_start的返回类型也确实是iterator，可由于我们是传值返回，所以会产生临时变量来接收_start的值，因为临时变量具有常性，所以类型可看作是const iterator。因此这里实际是把_start传给了临时变量进行存储，并且把临时变量存储的T*地址赋值给了insert的形参pos。
既然我们知道了加引用是不可以的原因是临时变量具有常性，那可能也有人会说那在引用前加上const不就解决了吗？
不行哈。加const就变成了const iterator pos，因为iterator是int，那展开就变成了const int* pos，所以加上const，pos就不能指向别的空间了，那扩容的时候pos要如何修改呢？
push_back(const T& x)插入
//这里要加const，是因为对于自定义类型
//我们可以传入匿名对象和临时对象（他们都具有常性）
void push_back(const T& x)
{
if (_finish == _end_of_storage)
{
int newcapacity = capacity() == 0 ? 4 : 2 * capacity();
reserve(newcapacity);
}
//这里如果T是自定义类型，那不写赋值运算符重载也不会报错
//因为编译器会默认生成
*_finish = x;
//下面这种赋值方法不可以
// 因为数组要传入的是下标
//_start[_finish] = x;
//如果要用数组的方式访问，就只能用下面这种方法
//_start[size()] = x;
_finish++;
}2.3 删除元素
void erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator end = pos;
while (end < _finish - 1)
{
*end = *(end + 1);
end++;
}
_finish--;
}
我们实现erase的原理是吧pos位置后面的数据向前覆盖，覆盖完成后再--_finish。并不是真的把元素删掉
大家先思考个问题，因为vector是类模板，声明的定义是不能分离的，那我们在.h的文件中使用assert，并且我们此时在.h中是没有包含assert的头文件的，那运行的时候会不会有问题？
答案是不会的，因为.h不会被编译，.cpp包含.h，那.h就会在.cpp中展开（在预处理阶段展开）
我们只要在包含vector.h的头文件前提前包含assert的头文件那就不会报错，因为编译器会向上寻找。如果assert的头文件放在vector.h的下面，此时运行就会报错。
言归正题，我们上面写的erase有没有问题？
此时我们运行看看
此时，运行结果是没有问题的，那是真的没有问题吗？
我们不妨看看库里面的erase
我们可以看到如果换成了库里面实现的erase，在同样的场景下运行的结果是不同的
原因是：
因为有这两个原因，所以编译器认为在删除元素后，迭代器失效（外面的，这里是it）
迭代器失效有两种情况
1.位置元素发生更改
2.指向无效空间
我们这里重点说下第二种原因吧！
总结：
解决办法！！！
因此，当我们删除元素后，我们还想去访问迭代器指向位置的元素时，我们就要更新一下迭代器
库里面的erase是有返回值的
vector的删除操作不光会导致指向被删除元素的迭代器失效，删除元素后面的迭代器也会失效
2.4 成员函数初始化
2.4.1 拷贝构造
首先我们看看编译器自动生成的拷贝构造是浅拷贝还是深拷贝
因为编译器自动生成的浅拷贝不能满足我们的需求，所以此时我们需要自己手写一个拷贝构造
//拷贝构造
//v2(v1);
vector(const vector<T>& v)
{
reserve(v.capacity());
for (auto e : v)
{
push_back(e);
}
}注意
下面这种写法是错误的，也是我一开始写拷贝构造的写法。
我们在写拷贝的时候要记住，函数名是类名，不用加模板。没有函数名加模板参数的
但由于我们写了拷贝构造，编辑器就不会生成默认构造了，因为拷贝构造也是构造，只要写了构造编译器就不会生成默认构造，因此这里我们可以强制让编译器生成默认的构造
//如果我们只写了拷贝构造，那编译器就不会自动生成默认构造了（拷贝构造也是构造）
//下面这段代码的意思是，让编译器强制生成默认的构造函数
vector() = default;但此时，我们运行程序依旧会有问题
因为此时v是被const修饰的，因此v内的成员变量是不能修改的。而此时我们的capacity函数中的this指针类型是vector* const this，const修饰的是this，所以this是不能修改的，但是我们可以通过this修改成员v的成员变量，因此这里是权限的放大。解决办法在capacity函数后面加上const
2.4.2 赋值运算符重载
//赋值
//v3 = v1
//此时v就是v1拷贝出来的对象
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
void swap(vector<T>& v2)
{
std::swap(_start, v2._start);
std::swap(_finish, v2._finish);
std::swap(_end_of_storage, v2._end_of_storage);
}首先我们在赋值运算符重载的时候先拷贝构造出来v对象，然后我们写交换函数，交换函数内部来调用std写好的swap函数。
随后我们返回*this，并且我们这里写有个好处就是我们不用手动释放v3原本的空间了，因为v出了函数作用域就销毁了（交换函数执行后v的成员变量就是旧v3的成员变量）。
2.4.3 构造函数（迭代器区间初始化）
在C++98中，支持构造函数使用迭代器区间进行初始化
//使用迭代器区间进行初始化
//类模板的成员函数
//函数模板，类型是自动推演的
//目的就是支持任意容器的迭代器区间初始化
template <class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
first++;
}
}
void test_vector6()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
vector<int>v2(v1.begin(), v1.end());
for (auto e : v2)
{
cout << e << " ";
}
cout << endl;
string s1("hello");
//初始化插入的时候把字符插入到int数组中，插入的就是其对应的ASCII码
vector<int>v3(s1.begin(), s1.end());
for (auto e : v3)
{
cout << e << " ";
}
cout << endl;
}运行结果：
第一个vector<int>v2(v1.begin(), v1.end());此时v1.begin()和v1.end()返回的类型都是iterator，也就是int*，所以函数模板推导处InputIterator是int*的类型
第二个vector<int>v3(s1.begin(), s1.end());由于s1是string类型，所以s1.begin()和s1.end()返回的类型char*，因此函数模板推导出InputIterator是char*的类型
因为v3是int，所以会开辟出int类型的数组，因此在push_back(*first)的时候，我们会把char类型的数据强制类型转换成int类型来插入
2.4.4 构造函数（n个val初始化）
在C++98的第二个构造函数中，支持了用n个val进行构造初始化
//val引用的是匿名对象，const修改了匿名对象的生命周期
//开n大小的空间，空间内用val进行填充
//可以不传第二个参数，这里是半缺省
vector(size_t n, const T& val = T())
{
reserve(n);
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}大家如果是第一次看到T()第一个反应肯定是匿名对象，这里也确实是，val引用的确实是T类型的匿名对象，但是如果T是自定义类型我们好理解，但如果T是int类型呢？
在C++中是支持这种写法的，内置类型也可以用匿名对象进行初始化
可此时如果我们想要用10个1进行初始化就会有问题（出现了非法寻址）
双击点非法寻址，程序调整到这里
我们本意是想让10个1进行初始化的，但这里好像是用迭代器区间初始化，那int类型进行解引用肯定就会报错啊，导致这类问题的原因如下图所示：
所以导致上述错误就是类型匹配的问题，编译器肯定会匹配最优的选择，函数模板是根据类型自动推演而成，所以这里Inputerator是int类型，而n个val初始化第一个形参是size_t类型，第二个是const int& 类型，所以走到肯定就是迭代器初始化。
这里解决上面这种问题有2中方法：
其1
在10后面加u，那第一个参数就是无符号整形了，因此会优先匹配到size_t去。
这里有个小细节就是我们在for循环遍历的时候加上了const auto&，因为范围for对于内置类型是赋值操作，对于自定义类型如果不加引用，就会调用拷贝构造。如果这里是vector<string>v1，那e就是拷贝出来的对象，所以如果确定在使用过程中不会修改e，那加引用对于自定义类型就能避免了拷贝构造
其二
如果我们不想在第一个参数后面加u，并且我们还想走用n个val初始化的方法，那就在构造个函数模板初始化，这里库里也是这么实现的
//val引用的是匿名对象，const修改了匿名对象的生命周期 //开n大小的空间，空间内用val进行填充 //可以不传第二个参数，这里是半缺省 vector(size_t n, const T& val = T()) { reserve(n); for (size_t i = 0; i < n; i++) { push_back(val); } } vector(int n, const T& val = T()) { reserve(n); for (int i = 0; i < n; i++) { push_back(val); } }
2.4.5 构造函数（常量数组初始化）
在C++11中是支持用initializer list进行初始化的
我们去搜initializer_list，我们可以发现他是个类模板
C++主打的就是可以用{}进行初始化，就比如下图
正因如此，所以这里就有了使用{}进行构造，这里使用{}构造有个特点，就是参数个数是不固定的
因为initializer_list内部写了begin()和end()，所以支持范围for
指针指向的数组是左闭右开
vector(initializer_list<T> il)
{
for (auto e : il)
{
reserve(il.size());
push_back(e);
}
}如果我们在范围for的时候不想用auto，那因该用什么？
e的类型不是initializer_list，而是里面存储的元素也就是T。我们可以类比int数组，其实这里是把数组里面的值给e进行插入，那int数组里面值的类型是不是就是T，也就是int
vector(initializer_list<T> il)
{
for (T e : il)
{
reserve(il.size());
push_back(e);
}
}2.5 自定义类型使用memcpy扩容的问题
首先，我们插入4个元素看上去是没有问题来的，但是如果我们在插入一个元素就会产生扩容，此时问题就会提现出来（析构的时候）。
扩容后释放可能操作系统没有马上回收内存，析构的时候才发现，这一块空间已经被释放了。
结论：如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，因为 memcpy是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃。
综上所述，我这边提供2中解决办法
其一
赋值运算符重载（推荐做法）
void reserve(size_t n) { if (n > capacity()) { iterator tmp = new T[n]; size_t oldsize = size(); //不为空才需要拷贝一份代码，并且释放原本的旧空间 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; } }
其二
调用std的swap函数直接交换（不推荐）
void reserve(size_t n) { if (n > capacity()) { iterator tmp = new T[n]; size_t oldsize = size(); //不为空才需要拷贝一份代码，并且释放原本的旧空间 if (_start) { for (size_t i = 0; i < oldsize; i++) { std::swap(tmp[i], _start[i]); } delete[] _start; } _start = tmp; _finish = tmp + oldsize; _end_of_storage = _start + n; } }
2.6 vector迭代器失效的问题
迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对 指针进行了封装，比如：vector的迭代器就是原生态指针T* 。因此迭代器失效，实际就是迭代器 底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即 如果继续使用已经失效的迭代器，程序可能会崩溃)。
对于vector可能会导致其迭代器失效的操作有：
会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、 assign、push_back、erase等。
3. vector总代码
#pragma once
namespace bit
{
template <class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
//如果我们只写了拷贝构造，那编译器就不会自动生成默认构造了（拷贝构造也是构造）
//下面这段代码的意思是，让编译器强制生成默认的构造函数
vector() = default;
//拷贝构造
//v2(v1);
vector(const vector<T>& v)
{
reserve(v.capacity());
for (auto e : v)
{
push_back(e);
}
}
//赋值
//v3 = v1
//此时v就是v1拷贝出来的对象
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
//使用迭代器区间进行初始化
//类模板的成员函数
//函数模板，类型是自动推演的
//目的就是支持任意容器的迭代器区间初始化
template <class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
first++;
}
}
//val引用的是匿名对象，const修改了匿名对象的生命周期
//开n大小的空间，空间内用val进行填充
//可以不传第二个参数，这里是半缺省
vector(size_t n, const T& val = T())
{
reserve(n);
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}
vector(int n, const T& val = T())
{
reserve(n);
for (int i = 0; i < n; i++)
{
push_back(val);
}
}
vector(initializer_list<T> il)
{
for (auto e : il)
{
reserve(il.size());
push_back(e);
}
}
void swap(vector<T>& v2)
{
std::swap(_start, v2._start);
std::swap(_finish, v2._finish);
std::swap(_end_of_storage, v2._end_of_storage);
}
iterator begin()
{
//iterator begin();//你这里的返回值是iterator，typedef之前是T*嘛，返回之后给了临时变量，那么临时变量的值就是这个_start的地址，但是，因为我们返回的是iterator也就是T*，不能说你临时变量是一个const T*的，就把我返回值类型给改了，这不合理对吧。所以这里实际是把临时变量存储的T*的地址赋值给了insert的那个形参pos，就和这个例子是一个意思这里返回int*这里用int*接收，并没有因此改变类型,能理解不
return _start;
}
const_iterator begin() const
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator end() const
{
return _finish;
}
~vector()
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
void reserve(size_t n)
{
if (n > capacity())
{
iterator tmp = new T[n];
size_t oldsize = size();
//不为空才需要拷贝一份代码，并且释放原本的旧空间
if (_start)
{
for (size_t i = 0; i < oldsize; i++)
{
//std::swap(tmp[i], _start[i]);
//赋值运算符重载
tmp[i] = _start[i];
}
//这种是一个字节一个字节进行拷贝
//memcpy(tmp, _start, sizeof(T) * size());
//下面这个方法也是以一个字节一个字节进行进行拷贝，但这种写法巨坑
//一共要拷贝 sizeof(T) * size()个字符个数
//strncpy((char*)tmp, (char*)_start, sizeof(T) * size());
delete[] _start;
}
_start = tmp;
//此时size()里面的_start已经不是指向原先数组的起始地址
//而是指向tmp所指向的数组的起始地址，所以
//_finish = _start + _finish - _start;
//求得：_finish = _finish 因此_finish是不变的
//因此finish迭代器失效，因为指向的旧空间，并且旧空间等等会被释放
//_finish = _start + size();
//解决办法1：
//把_finish放到_start = tmp前面
//_finish = tmp + size();
//方法1不推荐哈，因为有点依赖顺序，最好方法是提前记录好size()
// 方法2
_finish = tmp + oldsize;
_end_of_storage = _start + n;
}
}
//这里获取的是容量大小
size_t capacity() const
{
return _end_of_storage - _start;
}
//指针-指针得到的是指针之间的元素个数
//这里获取的是数据个数
size_t size()
{
return _finish - _start;
}
T& operator[](size_t pos)
{
assert(pos < size());
return _start[pos];
}
//这里要加const，是因为对于自定义类型
//我们可以传入匿名对象和临时对象（他们都具有常性）
void push_back(const T& x)
{
if (_finish == _end_of_storage)
{
int newcapacity = capacity() == 0 ? 4 : 2 * capacity();
reserve(newcapacity);
}
//这里如果T是自定义类型，那不写赋值运算符重载也不会报错
//因为编译器会默认生成
*_finish = x;
//下面这种赋值方法不可以
// 因为数组要传入的是下标
//_start[_finish] = x;
//如果要用数组的方式访问，就只能用下面这种方法
//_start[size()] = x;
_finish++;
}
void pop_back()
{
assert(size() > 0);
_finish--;
}
void insert(iterator pos, const T& x)
{
assert(pos >= _start);
assert(pos <= _finish);
if (_finish == _end_of_storage)
{
size_t len = pos - _start;
int newcapacity = capacity() == 0 ? 4 : 2 * capacity();
reserve(newcapacity);
//pos = _start + len，如果不这么写的话，pos还是指向旧空间
//而扩容的时候旧空间会被释放，因此在pos位置的空间插入元素，是错误的
pos = _start + len;
}
iterator end = _finish;
while (end > pos)
{
*end = *(end - 1);
end--;
}
*pos = x;
_finish++;
}
void erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator end = pos;
while (end < _finish - 1)
{
*end = *(end + 1);
end++;
}
_finish--;
}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
};
void test_vector1()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
//下面的范围for对于内置类型是赋值操作
//对于自定义类型如果不加引用，就会调用拷贝构造
//e就是拷贝出来的对象
//所以这里加引用就是避免了拷贝构造
for (const auto& e : v1)
{
cout << e << endl;
}
v1.push_back(5);
bit::vector<int>::iterator it1 = v1.begin();
while (it1 != v1.end())
{
cout << *it1 << endl;
it1++;
}
}
void test_vector2()
{
bit::vector<int> v2;
v2.push_back(1);
v2.push_back(2);
v2.push_back(3);
v2.push_back(5);
//v2.erase(v2.begin());
bit::vector<int>::iterator it1 = v2.begin();
while (it1 != v2.end())
{
cout << *it1 << endl;
it1++;
}
//v2.insert(v2.begin(), 0);
//it1 = v2.begin();
/*while (it1 != v2.end())
{
cout << *it1 << endl;
it1++;
}*/
}
void test_vector3()
{
bit::vector<int> v3;
v3.push_back(1);
v3.push_back(2);
v3.push_back(3);
v3.push_back(4);
int x;
cin >> x;
bit::vector<int>::iterator it1 = find(v3.begin(), v3.end(), x);
if (it1 != v3.end())
{
v3.insert(it1, 1000);
cout << *it1 << endl;
}
for (auto e : v3)
{
cout << e << " ";
}
cout << endl;
}
void test_vector4()
{
bit::vector<int> v3;
v3.push_back(1);
v3.push_back(2);
v3.push_back(3);
v3.push_back(4);
bit::vector<int> v4(v3);
for (auto e : v4)
{
cout << e;
}
}
void test_vector5()
{
std::vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
int x;
cin >> x;
//找到了，就访问找到的位置，找不到返回最后一个有效元素的下一个位置
//库里面的erase实现，如果外面不更新it，就会报错
std::vector<int>::iterator it = find(v1.begin(), v1.end(), x);
if (it != v1.end())
{
it = v1.erase(it);
if (it != v1.end())
{
cout << *it << endl;
}
}
}
void test_vector6()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
vector<int>v2(v1.begin(), v1.end());
for (auto e : v2)
{
cout << e << " ";
}
cout << endl;
string s1("hello");
//初始化插入的时候把字符插入到int数组中，插入的就是其对应的ASCII码
vector<int>v3(s1.begin(), s1.end());
for (auto e : v3)
{
cout << e << " ";
}
cout << endl;
vector<string>v31(10);
vector<string>v4(10, "xx");
//这里非法的间接寻址的问题是，下面代码调用到迭代器初始去了
// 因为函数模板第一个是size_t，所以优先匹配的是迭代器
//vector<int>v5(10, 10);
//解决方法1
vector<int>v6(10u, 10);
for (auto e : v6)
{
cout << e << " ";
}
cout << endl;
//解决方法2，在构造个函数模板初始化
vector<int>v7(10, 20);
for (auto e : v7)
{
cout << e << " ";
}
cout << endl;
}
void test_vector7()
{
vector<int> v1 = { 1,2,3,4,5 };
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
list<int> lt1 = { 11,2,3,4,5,60 };
lt1.sort();
list<int>::iterator it = lt1.begin();
//while (it != lt1.end())
//{
// cout << *it << " ";
// it++;
//}
//cout << endl;
while (it != lt1.end())
{
cout << *it << " ";
it++;
}
cout << endl;
}
void test_vector8()
{
vector<string> v1(4, "bbbbbb");
for (auto e : v1)
{
cout << e << endl;
}
v1.push_back("1111111");
for (auto e : v1)
{
cout << e << endl;
}
}
void test_vector11()
{
bit::vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.insert(v1.begin(), 0);
//int x;
//cin >> x;
找到了，就访问找到的位置，找不到返回最后一个有效元素的下一个位置
//bit::vector<int>::iterator pos = find(v1.begin(), v1.end(), x);
//if (pos != v1.end())
//{
// //更新迭代器，防止插入元素遇到扩容，导致pos迭代器失效
// v1.insert(pos, 0);
// cout << *pos << endl;
//}
}
void test_vector13()
{
//这里非法的间接寻址的问题是，下面代码调用到迭代器初始去了
// 因为函数模板第一个是size_t，所以优先匹配的是迭代器
//解决方法1
vector<int>v1(10u, 1);
for (const auto& e : v1)
{
cout << e << " ";
}
cout << endl;
//解决方法2，在构造个函数模板初始化
vector<int>v2(10, 20);
for (auto e : v2)
{
cout << e << " ";
}
cout << endl;
}
void test_vector14()
{
vector<string> v1;
v1.push_back("1111111");
v1.push_back("1111111");
v1.push_back("1111111");
v1.push_back("1111111");
for (auto e : v1)
{
cout << e << endl;
}
v1.push_back("1111111");
for (auto e : v1)
{
cout << e << endl;
}
}
class A
{
public:
A(int a1 = 0)
:_a1(a1)
, _a2(0)
{}
A(int a1, int a2)
:_a1(a1)
, _a2(a2)
{}
private:
int _a1;
int _a2;
};
void test_vector9()
{
A aa1(12, 33);
//逗号表达式，最后结果是3，走的是单参数构造，然后进行拷贝构造给aa2
//但由于是连续的构造+拷贝构造，所以最后会被编译器优化为构造
A aa2 = (1, 2, 3);
A aa3 = { 1,2 };
A aa4 = { 1 };
vector<int> v1 = { 1,2,3,4 };
vector<int> v2(v1);
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
for (auto e : v2)
{
cout << e << " ";
}
cout << endl;
}
}
4. 杨辉三角
杨辉三角真实样子
返回数组下标[2][3]位置的元素
总代码
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> vv;
vv.resize(numRows);
for(int i = 0; i < numRows; i++)
{
vv[i].resize(i+1);
vv[i][0] = vv[i][vv[i].size()-1] = 1;
}
for(int i = 2; i < numRows; i++)
{
for(int j = 1; j < vv[i].size(); j++)
{
if(vv[i][j] == 0)
vv[i][j] = vv[i-1][j-1] + vv[i-1][j];
}
}
return vv;
}
};