C++ -- vector的模拟实现
vector.h的内容：
#pragma once
#include <iostream>
#include <assert.h>
#include <vector>
namespace kk
{
template <class T>
class vector
{
public:
typedef T *iterator; // 指针版迭代器
typedef const T *const_iterator;
// 注：这里的bgein()、end()写的都是用的传值返回，所以不能对返回值进行++，--这种操作(就是++v.begin(),--v.end())，这是会报错的(因为临时变量具有常性)
// 但是可以进行 +、-；ex：v.begin() + 1
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
// cbegin()、cend()用不了范围for，范围for适配的是非const版本的迭代器
// 补充：initializer_list版本的构造
// 就是：vector<int> v = { 1,2,3,4,5,6,7,8,9,10 };
vector(std::initializer_list<T> il)
{
reserve(il.size());
for (auto& e : il)
{
push_back(e);
}
}
// 补充：initializer_list本质就是两个指针，一个指向这组数的开始，一个指向这组数的结束。
// ex：initializer_list<int> x = { 1,2,3,4,5,6,7,8,9,10 }; -- sizeof x 的值为8。(32位下)
// 无参构造
vector()
: _start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{
}
// 用n个值去构造
vector(size_t n, const T &val = T()) // 理论上匿名对象的生命周期是只在当前这一行的
// 但是：你对其(T())使用了const引用之后，
// 它的生命周期就变成了跟这个引用对象(val)的生命周期一样了
// 总结：就是该匿名对象的生命周期被延长了
// 注意：一定要加上const才行，因为不管是临时变量还是匿名对象都具有常性
: _start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
// 注意：这里要记得初始化一下，不然下面就会问题
{
reserve(n); // 提前开好空间，减少尾插的消耗
// 直接尾插就好
for (size_t i = 0; i < n; ++i)
{
push_back(val);
}
}
// 迭代器版本的构造
template <class InputIterator> // 语法规定允许了一个类模板中的成员函数可以是一个函数模板
// 用一个函数模板才能允许用各种类型的迭代器去构造
vector(InputIterator first, InputIterator last)
: _start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{
while (first != last) // 注意：迭代器的比较一定要用 !=
{
push_back(*first);
++first;
}
}
// 补充：只写了上面三个构造函数，在某些情况下还是会出问题的
// 举个栗子：
// vector<int> v(10,5); // 这句代码在构造时就会出错，因为编译器通过匹配之后，会去使用迭代器版本的构造函数去构造这个v
// 迭代器版本的构造中有一句*first就是导致这个错误的根源
// 因为这里传过去的 10 和 5 会被推到为 int 类型，int 怎么可以解引用呢？
// 所以就会出错
// 那么要怎么解决这个问题呢？
// 解决方法有两种：
// 解决方法一：写成 vector<int> v(10u,5); 这样，10后面加个u，就是默认这个10是无符号的整型，
// 这样编译器就会去调用第二个版本的构造函数去构造这个v了
// 解决方法二：库里是又重载了几个构造函数，来特殊处理类似的情况
// vector(int n, const T& val = T()) // 比如说再搞个适合 int 的构造函数就能处理上面的情况了
// 补充：上面的三个构造函数如果你懒得去显示写初始化列表，那你也可以在下面的声明中给缺省值
// 因为：这里的三个数据都是内置类型(C++11之后支持了这种给缺省值的方式)
// 传统写法的拷贝构造函数
// vector(const vector<T>& v)
//{
// _start = new T[v.capacity()];
// // memcpy(_start, v._start, sizeof(T) * v.size());
// for (size_t i = 0; i < v.size(); ++i)
// {
// _start[i] = v._start[i];
// }
// _finish = _start + v.size();
// _end_of_storage = _start + v.capacity();
// }
// 注：这个写法如果用memcpy来进行拷贝实际上还是有问题的
// 因为：memcpy的拷贝也是一种值拷贝(浅拷贝)
// 举个栗子：下面这两句代码运行就会出问题
// vector<std::string> v1(10, "love love"); // 这句代码没什么问题
// vector<std::string> v2(v1); // 但这句代码就会在运行时报错
// 因为：v2和v1中的字符串用的是同一块空间
// 拷贝构造函数的现代写法1(注：现代写法没有上面的那个问题)
// vector(const vector<T>& v)
//{
// reserve(v.capacity()); // 先扩好容，提高下面插入时的效率
// for (auto& e : v) // 这里的auto加个&比较好，不然这里又会出现需要拷贝的情况，影响效率
// {
// push_back(e); // 因为：push_back里是先*(解引用)之后，找到了_start所指向的数据，然后再进行的赋值
// // 如果是内置类型，赋值自然没什么问题
// // 如果是自定义类型，则这个赋值会去调用它重载的赋值运算符，完成赋值
// // 而：memcpy中的拷贝之所以是浅拷贝，
// //我认为：因为memcpy没有对_start等指针进行解引用，
// // 是直接类似于这样整的_start = v._start，
// // ex：int i = 0;
// // int* p = &i;
// // int* q = p;
// // q，p两个指针它们本身的地址是不一样的，但是它们所指向的地址是一样的(就是i的地址)
// //这样写：并不是 p 和 q 指向了两块不同的空间，然后都存着i的值
// // 而是：p 和 q 都是指向同一块空间，也就是i初始化时分配给i的空间
// }
// }
// 拷贝构造函数的现代写法2
vector(const vector<T> &v)
{
vector<T> tmp(v.begin(), v.end()); // 复用上面的迭代器区间构造函数
swap(tmp);
}
void swap(vector<T> &v)
{
// 注意：这里要加std，不加std的话，编译器在这里去调用swap函数的时候，会采取就近原则，先去调你自己写的swap
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
// 注意：赋值的参数不能加&
vector<T> &operator=(vector<T> v) // 注：vector<T>& operator=(vector<T> v)可以写成vector<T>& operator=(vector v)
// 语法上是允许你不加<T>的，因为库里也是这样弄的，但是推荐加上
// 注：拷贝构造函数也可以这样
{
swap(v);
return *this;
}
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _end_of_storage - _start;
}
void resize(size_t n, T val = T()) // 这是用一个匿名对象来调用默认构造来做缺省值
{
// n == size() 就不需要进行任何操作了
if (n < size())
{
_finish = _start + n;
}
else if (n > size())
{
while (n > capacity())
{
reserve(capacity() == 0 ? 4 : 2 * capacity());
}
while (size() < n)
{
(*_finish) = val;
++_finish;
}
}
}
void reserve(size_t n)
{
if (n > capacity()) // 这里需要判断一下，万一n比capacity还要小，然后你没判断，岂不是变成了缩容
{
T *tmp = new T[n];
if (_start) // 如果原本的vector里啥都没有，就不需要再进行数据的拷贝了
{
// memcpy(tmp, _start, sizeof(T) * size()); // 注意：这里用memcpy也会有问题，跟上面的拷贝构造函数遇到的问题一样
for (size_t i = 0; i < size(); ++i)
{
tmp[i] = _start[i]; // 这里它会去专门去调用这个T(类型)的赋值。ex：T是一个string类，就会去调用string类它自己的赋值
}
delete[] _start;
}
// 注：这里要先进行_finish的赋值，
// 如果是：先进行_start的赋值，
// 那么：tmp + size() == _start + _finish - _start == _finish
// 于是：_finish的值一直都不会变，岂不是出问题了
// 当然：你也可以选择在上面先用个变量把size()的值保存一下
_finish = tmp + size(); // 注：reserve()不改变size，只可能改变capacity
_start = tmp;
_end_of_storage = tmp + n;
}
}
void push_back(const T &x) // 补充：这里的参数加 const，除了说避免其值被修改，也是为了支持以下这种场景：
// vector<string> v;
// v.push_back("77"); -- 单参数的构造函数，有隐式类型转换，构造的是临时对象，临时对象具有常性。
// 注：如果这里的参数没有加 const，上面的代码就会出错。
{
if (size() == capacity())
{
reserve(capacity() == 0 ? 4 : 2 * capacity()); // 这要先判断一下capacity是不是为0
}
*_finish = x;
++_finish;
}
void pop_back()
{
assert(!empty()); // 如果为空就不要再删了
--_finish;
}
bool empty()
{
return _finish == _start;
}
iterator insert(iterator pos, const T &val)
{
assert(pos >= _start && pos <= _finish); // insert支持尾插，所以 pos 可以等于 _finish
if (_finish == _end_of_storage) // 先判断需不需要扩容
{
size_t len = pos - _start; // 如果要扩容，先保存一下pos和_start的相对距离
reserve(capacity() == 0 ? 4 : 2 * capacity());
pos = _start + len; // 扩容后进行更新pos，解决pos的失效问题
}
// 注意：这里的扩容可能会导致迭代器失效的问题
// 那么：什么是迭代器失效呢？
// 答：最常见的迭代器失效就是类似于野指针
// 原因：扩容一般都是异地扩容(这里自己写的都是异地扩)，扩容之后_start、_finish两个迭代器都指向了新的空间
// 而：pos迭代器还是指向原本的那块空间
// 所以：就可能出现下面的循环中end永远都大于pos，出现死循环，或者end就直接变成小于pos了，循环都不会进去
// 这就算是pos迭代器失效了
// 那么：该怎么解决这种问题呢？
// 答：更新一下pos
iterator end = _finish - 1;
while (end >= pos) // 这里可以不用担心 <0 的情况，因为这里的迭代器是指针版本的迭代器，指针是没有小于0的，指针是地址，是对内存单位的编号，这个编号是从0开始的，也可以认为最小的指针就是空指针了
{
*(end + 1) = *end; // 挪动数据
--end;
}
*pos = val;
++_finish;
return pos;
}
iterator erase(iterator pos)
{
assert(pos >= _start && pos < _finish);
iterator start = pos + 1;
while (start != _finish) // 不断覆盖
{
*(start - 1) = *start;
++start;
}
--_finish;
return pos;
}
T &operator[](size_t pos)
{
assert(pos < size());
return *(_start + pos);
}
const T &operator[](size_t pos) const
{
assert(pos < size());
return *(_start + pos);
}
~vector()
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
};
// 函数模板
template <typename T>
void Print(const vector<T> &v)
{
// vector<T>::const_iterator it = v.begin(); // 这句代码在编译的时候会报错，因为编译器在编译到这里的时候这个模板还没被实例化(实例化是在下面)
// 所以，编译器无法区分前面 vector<T>::const_iterator 这一坨是什么(是类型还是静态成员变量呢？)
// typename vector<T>::const_iterator it = v.begin(); // 加个 typename 就可以避免这种问题(这就是 typename 和 class 的一个区别)
// 这个 typename 就是用来告诉编译器 vector<T>::const_iterator 这是一个类型
// auto it = v.begin(); // 当然你用 auto 可以直接避免上面的问题，因为auto是根据这里调用的函数的返回值来推导类型的，你返回什么，就推导成什么
for (auto e : v)
{
std::cout << e << " ";
}
std::cout << std::endl;
}
void test_push_back()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
for (size_t i = 0; i < v.size(); ++i)
{
std::cout << v[i] << " ";
}
std::cout << std::endl;
}
void test_pop_back()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
Print(v);
v.pop_back();
Print(v);
v.pop_back();
Print(v);
v.pop_back();
Print(v);
}
void test_initializer_list()
{
vector<int> v = { 1,2,3,4,5,6,7,8,9,10 }; // 隐式类型转换
Print(v);
vector<int> v2({ 1,2,3,4,5,6,7,8,9,10 }); // 直接构造
Print(v2);
vector<int> v3{ 1,2,3,4,5,6,7,8,9,10 }; // C++11之后出的一种写法，不推荐，毫无美感
Print(v3);
}
void test_iterator()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
vector<int>::iterator it = v.begin();
while (it != v.end())
{
std::cout << *it << " ";
++it;
}
std::cout << std::endl;
for (auto e : v)
{
std::cout << e << " ";
}
std::cout << std::endl;
// vector<int> v2(++v.begin(), --v.end()); // 这句代码编译会出错，
// 因为模拟实现里写的迭代器用的是传值返回，返回的是一个临时变量，临时变量具有常性，不能被修改。
// 然后，这里用传引用返回也不好，这会导致 v 的 _start 和 _finish 被修改了
// 补充一些迭代器的神奇用法：
// 1、
std::string s3("hello world");
vector<int> v3(s3.begin(), s3.end()); // char是可以转换成int的
Print(v3);
// 这也是可行的，只有数据类型能匹配，能转换过去就行
// 2、
int arr[] = {10, 20, 30};
vector<int> v4(arr, arr + 3);
Print(v4);
// 这样都行
}
void test_const_iterator()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
Print(v);
}
void test_reserve()
{
vector<int> v;
v.reserve(100);
std::cout << "v.reserve(100)" << std::endl;
std::cout << "v.size():" << v.size() << std::endl;
std::cout << "v.capacity():" << v.capacity() << std::endl;
vector<std::string> v1; // 这里<>中间包的只要是自定义类型，然后reserve里面用的还是memcpy，就会出问题
v1.push_back("11111");
v1.push_back("22222");
v1.push_back("33333");
v1.push_back("44444");
v1.push_back("55555");
Print(v1);
// 如果reserve里面用的还是memcpy，这一小段代码就会出错(会在析构时出现问题，因为vector里面存的string出现了浅拷贝的问题，vector本身是深拷贝没有问题)
}
void test_resize()
{
vector<int> v;
v.resize(10);
std::cout << "v.resize(10)" << std::endl;
std::cout << "v.size():" << v.size() << std::endl;
std::cout << "v.capacity():" << v.capacity() << std::endl;
}
void test_insert()
{
vector<int> v;
for (int i = 0; i < 10; ++i)
{
v.insert(v.begin() + i, i);
}
Print(v);
std::cout << "在原本3的位置上插入30:" << std::endl;
vector<int>::iterator pos = std::find(v.begin(), v.end(), 3);
if (pos != v.end())
{
v.insert(pos, 30);
}
Print(v);
// 补充一个问题：insert之后pos迭代器失效了吗？
// 假设上面在最后一次插入时，发生了扩容，那么下面这句代码就是越界访问了
// (*pos)++;
// 为什么呢？
// 原因：因为insert那里的传参是传值传参，形参的改变不影响实参
// 所以：如果上面在最后一次插入时，发生了扩容，那么这里的这个pos迭代器就是已经失效了
// 即使：没发生扩容，那也算是失效了，因为它指向的位置的数据不是原本的3，而是刚插入的30
// 那么：把上面的insert的传参改成传引用可以吗？
// 答：不行，这会导致上面的 v.insert(v.begin() + i, i); 这句代码报错
// 因为：v.begin()函数 是传值返回的，传回来的是一个临时对象，临时对象具有常性，不能被修改(当然还有一些其他的各种原因)
// 所以：如果你就是想这样用，就把insert的返回值改成iterator，不用void，把修改后的pos传回来
// 总结：最好的方式就是直接统一认为insert之后，这个pos迭代器失效了，不能再使用
}
void test_erase()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
Print(v);
vector<int>::iterator pos = std::find(v.begin(), v.end(), 3);
std::cout << "删除数字3" << std::endl;
v.erase(pos);
Print(v);
// 补充一个问题：erase之后，pos迭代器失效了吗？
// (*pos)++;
// 根据insert的经验，很容易认为它没有失效，因为没有发生什么扩容或者缩容的情况，空间位置没有发生变化嘛
// 但是：在VS里，你erase之后，它就认为这个pos迭代器失效了，不能在通过这个迭代器去访问那块空间了，并进行了强制的检查
// 补充：VS是怎么做到的强制检查呢？(自己写的(g++版本)做不到，因为两个版本对迭代器的实现方式不一样)
// 原因：VS对 * 进行了重载(operator)，这里的 *pos 实际上是去调用了 operator* 函数(具体怎么做的，后面讲)
// 但是：要注意不同的平台对这句代码的处理不一样，g++对这句代码就没有什么强制检查(g++对这块的实现跟这里自己写的一样)
// 那么：对这句(*pos)++是否需要报错呢？
// 是VS中，pos不管有没有越界都直接进行报错的方式更合理?
// 还是g++中，对pos不做检查的方式更合理呢？
// ex：如果你删除的刚好是最后一个数据呢？虽然删除最后一个数据的做法只是--_finish，并不是释放那一块空间
// 但：我们没法保证那块空间会不会又被用了，所以此时进行(*pos)++，该行为结果是不确定的，你不知道它会发生什么
// 总结：我们应该认为erase之后，pos迭代器就失效了，最好不要再用这个pos去访问什么东西了，因为行为结果未定义(可能没报错，也可能报错，还可能就是正常运行，但是结果不对)
// 再举一个有关erase之后迭代器失效的栗子
// 假设：你要删除v2中的偶数
// 下面这段代码放在VS中一定是报错的，但是给它放在g++下(自己写的这个跟g++是一样的)运行会有什么现象呢？
// vector<int> v2;
// v2.push_back(1);
// v2.push_back(2);
// v2.push_back(3);
// v2.push_back(4);
// // v2.push_back(5); // 如果：你加上这句代码，g++下就不会有什么意外发生，看起来就是一切正常
// // 但是：你没加上这句代码，g++下就会在运行时出错
// // 原因：下面的循环无法终止，it就一直++，就出现了段错误(内存方面的问题)
// vector<int>::iterator it = v2.begin();
// while (it != v2.end()) // 那么：把这里的 != 改成 < 是不是能解决死循环的问题呢？
// 答：在这里确实可以解决这个问题，因为这里的vector在内存里的存储是一段连续的空间
// 但是：以后比如在链表那里就不行了，因为链表的存储不是一段连续的空间，你用 < 没法比啊
//{
// if (*it % 2 == 0)
// {
// v2.erase(it);
// }
// ++it;
//}
// 那么，库里都是怎么解决这种迭代器失效的问题呢？
// 答：不管是insert还是erase库里都是靠返回值(将指向那个新位置的迭代器返回)来解决的
// 补充：string也是有迭代器失效的问题的，但是不容易出现，因为string的insert和erase不爱使用迭代器，所以不容易出现问题
}
void test_copy_construct()
{
vector<std::string> v1(3, "kkk");
for (auto e : v1)
{
std::cout << e << " ";
}
std::cout << std::endl;
vector<std::string> v2(v1);
for (auto e : v2)
{
std::cout << e << " ";
}
std::cout << std::endl;
std::string str("abcd");
vector<int> v3(str.begin(), str.end());
Print(v3);
// 补充：C++11支持的一种玩法
auto x = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
std::cout << typeid(x).name() << std::endl; // 这里打印出来的东西是一个initializer_list模板
std::cout << sizeof(x) << std::endl; // 本质也是用的两个迭代器(但是initializer_list里用的迭代器本质就是指针)
std::vector<int> v4 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; // 就像初始化数组一样(本质就是有隐式类型转换，库里它有支持一个initializer_list的构造：vector(initializer_list<value_type> il); 所以它能这样初始化)
// C++11在这方面做的特别狠，甚至这里可以省略调=
// ex：
std::vector<int> v5{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int i = 1;
int j = {1};
int k{1};
// 总结：看到能懂就行，不推荐这样玩
// 注：下面这段程序在没有写重载=成员函数时，运行会报错
// 因为：没有重载=成员函数时，vector<vector<int>>的拷贝是深拷贝，但是里面的vector<int>是浅拷贝
vector<vector<int>> ret;
ret = Solution().generate(10);
for (size_t i = 0; i < ret.size(); ++i)
{
for (size_t j = 0; j < ret[i].size(); ++j)
{
std::cout << ret[i][j] << " ";
}
std::cout << std::endl;
}
std::cout << std::endl;
}
}vector_test.cpp的内容：
#include "vector.h"
int main()
{
std::cout << "test_push_back:" << std::endl;
kk::test_push_back();
std::cout << std::endl;
std::cout << "test_pop_back:" << std::endl;
kk::test_pop_back();
std::cout << std::endl;
std::cout << "test_initializer_list:" << std::endl;
kk::test_initializer_list();
std::cout << std::endl;
std::cout << "test_iterator:" << std::endl;
kk::test_iterator();
std::cout << std::endl;
std::cout << "test_reserve:" << std::endl;
kk::test_reserve();
std::cout << std::endl;
std::cout << "test_resize:" << std::endl;
kk::test_resize();
std::cout << std::endl;
std::cout << "test_insert:" << std::endl;
kk::test_insert();
std::cout << std::endl;
std::cout << "test_erase:" << std::endl;
kk::test_erase();
std::cout << std::endl;
std::cout << "test_copy_construct:" << std::endl;
kk::test_copy_construct();
std::cout << std::endl;
return 0;
}