深度学习 vector 之模拟实现 vector (C++)

1. 基础框架

这里我们有三个私有变量，使用 _finish - _start 代表 _size，_end_of_storage - _start 代表 _capacity，并且使用到了模版，可以灵活定义存储不同类型的 vector，这里将代码量较小的函数直接定义在类的内部使其成为内联函数

namespace bit
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;//迭代器iterator begin(){return _start;}iterator end(){return _finish;}//const 迭代器const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}size_t size(){return _finish - _start;}size_t capacity(){return _end_of_storage - _start;}//可读可写T& operator[](size_t i){assert(i < size());return _start[i];}//只读const T& operator[](size_t i) const{assert(i < size());return _start[i];}bool empty(){return _start == _finish;}private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;};
}

2. 核心接口

2.1 增删与扩容

增删接口主要讲解的有尾删尾删、插入删除以及扩容

2.1.1 push_back & pop_back

尾插尾删

这里的尾插首先要判断是否需要扩容，然后在数据尾部插入数据即可

尾删则只需要保证所给的位置不超出范围后直接 --_finish 即可

//尾插
void push_back(const T& x)
{if (finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*finish = x;finish++;
}
//尾删
void pop_back()
{assert(!empty());--_finish;
}

2.1.2 insert

在指定位置插入数据

这里首先判断是否需要扩容，然后将指定位置pos之后的数据均向后移动，最后插入数据即可，这里需要注意的是在扩容后原来的pos位置就会失效，也就是迭代器失效，这里就相当于成为了野指针，所以解决方法是将原来的位置记录下来在扩容后更新即可

void insert(iterator pos, const T& x)
{assert(pos >= _start);assert(pos <= _finish);if (_finish == _end_of_stroage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : 2 * capacity());pos = _start + len;}iterator end = _finish - 1;while (pos != end){*(end + 1) = *end;--end;}++_finish;
}

2.1.3 erase

删除指定位置数据

这里删除就是保证所给位置在范围内然后直接将要删除的位置之后的数据覆盖到原来位置即可，需要注意的是在erase操作后也会出现迭代器失效，所以要继续使用pos的话需要记录原来的位置然后更新

//erase后的迭代器也看做是失效的
void erase(iterator pos)
{assert(pos >= _start);assert(pos < _finish);iterator it = pos + 1;while (it != end()){*(it + 1) = *it;it++;}_finish--;
}

2.1.4 resize 

初始化指定长度的指定数据

这里主要注意的是要分三种情况：1. n < size()，这时就直接缩容即可；2. size() < n < capacity()，这里就直接插入数据，不用扩容；3. capacity() < n，这里需要扩容后插入数据

//这里的T可以是string类也可以是内置类型int等，string类有自己的默认构造函数
//内置类型同样有自己的默认构造函数
void resize(size_t n, T val = T())
{if (n < size())//n小于_size则缩容{_finish = _start + n;}else{reserve(n);//如果n超过_capacity则扩容while (_finish != _start + n){*_finish = val;++_finish;}}
}

2.1.5 reserve 

判断空间是否充足后进行扩容

扩容操作就是判断原容量是否足够插入新数据，不够则二倍扩容即可，这里的注意事项有：1. 要将原来的size()保存成为old_size，以保证之后的_finish在计算时不会出现野指针的情况，因为如果不保存原来的size()，那么在之后size()就会更新成为新的size()，这里计算就会出现差错

2. 注意memcpy是浅拷贝，在处理内置类型int、double这样的数据不会出错，但是如果是string或者vector这样需要深拷贝类型的数据就会出错导致内存泄漏，解决方法就是使用其本身的赋值运算，这样可以兼顾二者

//扩容
void reserve(size_t n)
{if (n > capacity()){size_t old_size = size();T* tmp = new T[n];//memcpy(tmp, _start, old_size * sizeof(T));//拷贝数据for (size_t i = 0; i < old_size; i++){tmp[i] = _start[i];}delete[] _start;//释放旧空间_start = tmp;//指向新空间_finish = tmp + old_size;//tmp(新的) + _finish(原来) - _start(原来)_end_of_storage = tmp + n;}
}

2.2 拷贝构造

2.2.1 构造函数与析构函数

这里涉及的知识点有：

1. 类模版的成员函数仍然可以是函数模版

2. 在迭代器区间构造的函数时可以使用函数模版，这样可以使用任意容器的迭代器初始化，例如链表

//直接走初始化列表，如果没有则使用缺省值
vector()
{}
//C++11强制生成默认构造
//vector() = default;//类模版的成员函数仍然可以是函数模版
//迭代器区间构造
//可以使用任意容器的迭代器初始化
//例如链表
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{while (first != last){push_back(*first);first++;}
}//使用n个val初始化
vector(size_t n, const T& val = T())
{reserve(n);for (size_t i = 0; i < n; i++){ push_back(val);}
}~vector()
{if (_start){delete[] _start;_start = _finish = _end_of_storage;}
}

2.2.2 拷贝构造函数 

这里直接只用范围for进行深拷贝操作，简单便捷，并且提前保存空间减少扩容带来的消耗

//拷贝构造
vector(const vector<T>& v)
{reserve(v.size());for (auto& e : v){//这里默认有一个this指针//直接完成了深拷贝的工作push_back(e);}
}

2.3 赋值重载 

这里涉及了两种写法：

1. 自己完成赋值：人为进行赋值的操作，过程比较清晰

2. 交给编译器完成赋值：交给编译器直接完成交换以达到赋值的目的，操作更加简便

//赋值重载
1、传统写法
void clear()
{_finish = _start;
}vector<T>& operator=(const vector<T>& v)//传地址
{if (this != &v){clear();reserve(v.size());for (auto& e : v){push_back(e);}}return *this;
}//2、现代写法
void swap(const vector<T> v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);
}
vector<T>& operator=(const vector<T> v)//传值
{swap(v);return *this;
}

3. 常见问题

3.1 迭代器失效

这里的迭代器失效有两种情况：

1. 扩容后迭代器失效：这里首先了解扩容的原理是开辟一个原来空间二倍的空间，将原空间数据拷贝到扩容后的空间，然后释放原空间，所以由于pos在扩容后仍然指向的是原空间，而原空间已经释放，所以导致了类似野指针的效果，也就是第一种迭代器失效

2. 未扩容但是挪动数据导致的迭代器失效：即在使用原来pos完成挪动数据的操作后，pos已经不指向原来的位置，这时如果仍然想要访问原来位置就会导致迭代器失效

解决方法：保存原来的迭代器指向的位置或者相对位置，然后在扩容或者挪动数据之后更新pos指向的位置即可

void insert(iterator pos, const T& x)
{assert(pos >= _start);assert(pos <= _finish);//1.扩容,注意避免迭代器失效，即pos在扩容后仍然指向之前的空间//在之后对新空间的操作时会失效，类似野指针，就是迭代器失效//这里使用相对位置来避免迭代器失效//还需要注意，在insert之后的迭代器是失效的，不可以直接继续访问，但是可以在更新后访问//2.不扩容,但是由于数据的挪动导致p不再指向原来的位置，也看做迭代器失效//关于迭代器失效的处理方法就是接收操作之后的迭代器，然后对更新后的迭代器进行操作即可if (_finish == _end_of_stroage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : 2 * capacity());pos = _start + len;}iterator end = _finish - 1;while (pos != end){*(end + 1) = *end;--end;}++_finish;
}
//erase后的迭代器也看做是失效的
void erase(iterator pos)
{assert(pos >= _start);assert(pos < _finish);iterator it = pos + 1;while (it != end()){*(it + 1) = *it;it++;}_finish--;
}

3.2 浅拷贝 

浅拷贝就是指两个指针指向同一块空间，这时如果一个指针对该空间进行释放或者其他操作会影响另一个指针导致内存泄漏等后果，解决方法很简单就是深拷贝使两指针指向不同的空间然后使其数据保持一致即可

//扩容
void reserve(size_t n)
{if (n > capacity()){size_t old_size = size();T* tmp = new T[n];//memcpy(tmp, _start, old_size * sizeof(T));//拷贝数据//这里的T如果是string或者vector类型这种需要深拷贝的类型// 则需要赋值进行拷贝数据，否则浅拷贝会导致内存泄漏//这里调用的赋值就是string/vector的赋值，就是深拷贝for (size_t i = 0; i < old_size; i++){tmp[i] = _start[i];}delete[] _start;//释放旧空间_start = tmp;//指向新空间_finish = tmp + old_size;//tmp(新的) + _finish(原来) - _start(原来)_end_of_storage = tmp + n;}
}

 3.3 类型转换

这个问题是因为由于给出的代码编译器不知道该代码是类型还是变量，所以导致识别不出来，解决方法就是改为 auto 自动转换或者前面加上 typename 来告诉编译器即可

template<class T>
void print_vector(const vector<T>& v)
{//编译器无法确定此处的const_iterator是类型还是静态成员变量//所以规定不能从未实例化的类模版内取东西，需要程序员自己规定//即加一个 typename 来表示这里的const_iterator是类型即可typename vector<T>::const_iterator it = v.begin();while (it != v.end()){cout << *it << " ";it++;}cout << endl;for (auto e : v){cout << e << " ";}cout << endl;
}