阅读量:0
目录
前言
建议大家看完我之前关于string容器模拟实现的文章，这样在这里看vector容器会更加得心应手~
一.vector容器的模拟实现
1.1 基本配置
#include <assert.h> #include <string.h> namespace lj { template<class T> class vector { public: typedef T* iterator; typedef const T* const_iterator; //构造函数 vector() { _start = nullptr; _finish = nullptr; _endofstorage = nullptr; } //析构函数 ~vector() { if(_start) delete[] _start; _start = nullptr; _finish = nullptr; _endofstorage = nullptr; } //容量 size_t capacity()const { return _endofstorage - _start; } //长度 size_t size()const { return _finish - _start; } iterator begin() { return _start; } iterator end() { return _finish; } const_iterator end()const { return _finish; } private: iterator _start; iterator _finish; iterator _endofstorage; }; } 
1.2 reserve 扩容
避坑指南：
假如我们的扩容函数这么写~
首先在finish指针的更新中size()里面用的仍然是新的strat，而不是没更新前的，这就导致我们的size无法算出原来空间的大小，使得b = a +b-a = b，让finish指向原空间的窘境~
所以我们得保留在异地扩容前原空间的长度，使得finish更新成功~ endofstorage也是同理不要用capacity，因为里面也有新更新的start~
void reserve(size_t n) { if (n>capacity()) { size_t old = size();//记录原空间的大小 T* tmp = new T[n];//开辟新空间——异地扩容 if (_start) { memcpy(tmp, _start, old * sizeof(T));//拷贝数据 delete[] _start;//释放原空间 } _start = tmp;//指向新空间 _finish = _start + old; _endofstorage = _start + n; } }
不过这里面留下了一个小坑，遇到深拷贝类型时，memcpy是完全靠不住的~
memcpy在遇到扩容拷贝数据采用的是浅拷贝，如果我们是int类型那还好说，可一旦涉及到string类型这种有指向空间资源的，一旦进行析构那么最终新开辟的空间所指向的资源就没有了，成为野指针~
所以最好不要用memcy进行数据挪动~
1.3 push_back 尾插
//尾插函数 void push_back(const T& x) { //检查扩容 if (_finish == _endofstorage) { size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2; reserve(newcapacity); } *_finish = x; _finish++; }
1.4 insert 插入
//插入函数 void insert(iterator pos, const T& x) { assert(pos <= _finish && pos >= _start); //检查扩容 if (_finish == _endofstorage) { reserve(capacity() == 0 ? 4 : capacity() * 2); } //开始利用函数插入,往后挪动数据 memmove(pos + 1, pos, (_finish - pos) * sizeof(T)); *pos = x; _finish++; }
有时候发现插入失败了，这是什么原因呢？
避坑指南：迭代器失效~
如果Insert遇到扩容的时候会发现pos会成为野指针，这是因为我们用begin()(让pos指向start)传递过去的时候还没有扩容，那么pos就只能指向原空间，而在insert扩容时，但是这个时候并没有去更新pos指向新空间，毕竟pos不可能会跟着startd的变化而实时变化。所以我们需要重新定位pos。
然后我再分享一个我遇到的错误：
使用迭代器遇到扩容也一定要先分清先后顺序，不然就会像我一样导致死循环~
这里也顺便改一下memmove,因为会跟reserve的memcpy出现一样的情况~
1.5 【】运算符
T& operator[](size_t pos) { assert(pos < size()); return _start[pos]; }
1.6 拷贝构造
//拷贝构造 现代写法 v2(v1) vector(const vector<T>& v) { reserve(v.capacity()); for (auto e : v) { push_back(e); } }
传统写法无非就是开辟新的空间，然后拷贝原空间数据，最后更新指针指向~现代写法的话理解起来更方便，写法更简单吧~
1.7 = 运算符
void swap(vector<T>& v) { std::swap(_start,v._start); std::swap(_finish, v._finish); std::swap(_endofstorage, v._endofstorage); } vector<T>& operator=(vector<T> v) { swap(v); return *this; }
仍然是现代写法~不过这个在string类讲过了，就不画图了~
1.8 resize 扩容初始化
//resize 扩容初始化 void resize(size_t n, const T& val = T()) { if (n > size()) { reserve(n);//扩容 while (_finish < _start + n) { *_finish = val; _finish++; } } else { _finish = _start + n; } }这里默认初始化的值是通过匿名对象调用构造函数进行给值的~
1.9 erase 删除
//erase 删除 void erase(iterator pos) { assert(pos <= _finish && pos >= _start); iterator it = pos + 1; while (it<_finish) { *(it-1) = *it; it++; } _finish--; }在数据挪动这方面利用迭代器可以避开传统挪动出现的类型提升等问题~
不过这样还是有问题：迭代器失效~
例如当我们多次使用erase从而引发某种编译器的缩容条件时，那么指向原本空间的pos就会失效变成野指针~
原则上insert与erase都有空间扩容与缩容的问题，而这些会引发迭代器的失效。尽管我们在insert已经遇到过了，但只是让内部的pos生效，影响不到作为实参的外部迭代器，治标不治本。
最终我们是这样处理的，为了不让使用过这两接口的迭代器失效，我们为其添加返回值。然后调用的时候以it = v.erase(it)这样的形式进行重新定位，避免其失效~
1.10 迭代器构造
//迭代器构造 template <class Inputiterator> vector(Inputiterator first, Inputiterator last) { while (first != end) { push_back(*first); first++; } }
可以利用其他类型来为构造自己~可以当成泛型模板
不过如果我们模拟出了这个迭代器构造需要注意另外一个问题：类型匹配~
本来是想要构造连续5个1的vector，但是却匹配到了这个模板去了，因为类型更匹配~
为此还需要再搞一个函数确保匹配~
二.例题练习
17. 电话号码的字母组合
题目解析：
本质上是多叉树的深度优先遍历，通过考虑用递归的方式解决问题~
而递归通过需要具备两点条件，一为离开条件，二为如何处理深度递进
我们先来构造好递归函数的整体框架~
- 首先形参里面肯定要有digits，毕竟题目在里面。
- 然后就是设置一个可以获取数字的下标di，比如我们想要知道2的映射字符串，那就用di进去digits获取数字2~
- 再来一个形成完整字符串（例如"adg"）的stirng类型的cstr
- 最后就是存放所有结果的容器vector<stirng> v
考虑完递归函数后我们先来尝试写出一次深度遍历~
假设digits为“23"，通过下标di先获取当前数字2，然后再通过数字2映射对应字符串~
然后设置一层循环去下一次递归中链接字符‘d'
离开条件只要字符串长度达标即可，我们可以通过di与digits的关系来作为离开条件~
代码：
class Solution { public: string _numb[10] = { "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" }; void Combin(const string& digits, size_t di, string cstr, vector<string>& v) { //设置离开条件 if (di == digits.size()) { //把完整字符串加入 v.push_back(cstr); return; } //获取当前数字 size_t num = digits[di] - '0'; //通过数字映射对应字符串 string str = _numb[num]; //遍历每个数字对应的字符 for (int i = 0; i < str.size(); i++) { //深度遍历 Combin(digits, di + 1, cstr + str[i], v); } } vector<string> letterCombinations(string digits) { vector<string> v; //特殊判断 if (digits.empty()) { return v; } Combin(digits, 0, "", v); return v; } };
递归展开图：
三.模拟实现全部代码
//vector.h #pragma once #include <assert.h> #include <string.h> namespace lj { template<class T> class vector { public: typedef T* iterator; typedef const T* const_iterator; //构造函数 vector() { _start = nullptr; _finish = nullptr; _endofstorage = nullptr; } //拷贝构造 现代写法 v2(v1) vector(const vector<T>& v) { reserve(v.capacity()); for (auto e : v) { push_back(e); } } T& operator[](size_t pos) { assert(pos < size()); return _start[pos]; } void swap(vector<T>& v) { std::swap(_start,v._start); std::swap(_finish, v._finish); std::swap(_endofstorage, v._endofstorage); } vector<T>& operator=(vector<T> v) { swap(v); return *this; } //析构函数 ~vector() { if(_start) delete[] _start; _start = nullptr; _finish = nullptr; _endofstorage = nullptr; } size_t capacity()const { return _endofstorage - _start; } size_t size()const { return _finish - _start; } iterator begin() { return _start; } const_iterator begin()const { return _start; } iterator end() { return _finish; } const_iterator end()const { return _finish; } void reserve(size_t n) { if (n>capacity()) { size_t old = size();//记录原空间的大小 T* tmp = new T[n];//开辟新空间——异地扩容 if (_start) { for (size_t i = 0; i < old; i++) { tmp[i] = _start[i];//赋值拷贝为深拷贝 } delete[] _start;//释放原空间 } _start = tmp;//指向新空间 _finish = _start + old; _endofstorage = _start + n; } } //尾插函数 void push_back(const T& x) { //检查扩容 if (_finish == _endofstorage) { size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2; reserve(newcapacity); } *_finish = x; _finish++; } //插入函数 iterator insert(iterator pos, const T& x) { assert(pos <= _finish && pos >= _start); //检查扩容 if (_finish == _endofstorage) { size_t len = pos - _start;//记录原空间长度 reserve(capacity() == 0 ? 4 : capacity() * 2); pos = len + _start;//让pos指向新空间并且同步长度 } //开始利用函数插入,往后挪动数据 //memmove(pos + 1, pos, (_finish - pos) * sizeof(T)); iterator end = _finish - 1; while (end >= pos) { *(end + 1) = *end; --end; } *pos = x; _finish++; return pos; } //resize 扩容初始化 void resize(size_t n, const T& val = T()) { if (n > size()) { reserve(n);//扩容 while (_finish < _start + n) { *_finish = val; _finish++; } } else { _finish = _start + n; } } //erase 删除 iterator erase(iterator pos) { assert(pos <= _finish && pos >= _start); iterator it = pos + 1; while (it<_finish) { *(it-1) = *it; it++; } _finish--; return pos; } //迭代器构造 template <class Inputiterator> vector(Inputiterator first, Inputiterator last) { while (first != last) { push_back(*first); first++; } } private: iterator _start = nullptr; iterator _finish = nullptr; iterator _endofstorage = nullptr; }; void test_vector() { //vector<int> v; //v.push_back(1); //v.push_back(2); //v.push_back(3); //v.push_back(4); //v.push_back(5); //v.push_back(5); //v.push_back(5); //v.push_back(5); v.insert(v.begin(), 0); //vector<int>::iterator it = v.begin(); //while (it != v.end()) //{ // cout << *it << ' '; // it++; //} //cout << endl; // //vector<int>::iterator it1 = v.begin();错误示范，这会让it1指向原空间，变成野指针 //vector<int> v; //v.push_back(1); //v.push_back(2); //v.push_back(3); //v.push_back(4); //v.push_back(5); //v.push_back(5); //v.push_back(5); //v.push_back(5); //vector<int> v1; //v1.push_back(1); //v1.push_back(2); //v1.push_back(3); //v1.push_back(4); //v1.insert(v1.begin(), 0); //vector<int>::iterator it1 = v1.begin(); //while (it1 != v1.end()) //{ // v1[0]++; // cout << *it1 << ' '; // it1++; //} //cout << endl; //vector<int> v1; //v1.push_back(1); //v1.push_back(2); //v1.push_back(3); //v1.push_back(4); //v1.push_back(5); //v1.push_back(5); //v1.push_back(5); //v1.push_back(5); //vector<int> v2; //v2 = v1; //vector<int>::iterator it1 = v2.begin(); //while (it1 != v2.end()) //{ // cout << *it1 << ' '; // it1++; //} //cout << endl; //vector<int> v1; //v1.push_back(1); //v1.push_back(2); //v1.push_back(3); //v1.push_back(4); //v1.push_back(5); //v1.push_back(5); //vector<int>::iterator it = v1.begin(); //while (it != v1.end()) //{ // cout << *it << ' '; // it++; //} //cout << endl; //v1.resize(3); //vector<int>::iterator it1 = v1.begin(); //while (it1 != v1.end()) //{ // cout << *it1 << ' '; // it1++; //} //cout << endl; /*vector<int> v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); v1.push_back(5); v1.push_back(5); vector<int>::iterator it = v1.begin(); v1.insert(it + 1,1); v1.insert(it + 1, 1); for (auto e : v1) { cout << e << ' '; } cout << endl;*/ /* vector<string> vstr; vstr.push_back("1111"); vstr.push_back("1111"); vstr.push_back("1111"); vstr.push_back("1111"); vstr.push_back("1111"); vstr.push_back("1111"); vstr.push_back("1111"); vstr.push_back("1111"); vstr.push_back("1111"); vstr.push_back("1111"); for (auto e : vstr) { cout << e << ' '; } cout << endl;*/ int a[] = { 1,2,3 }; vector<int> v(a, a + 3); for (auto e : v) { cout << e << ' '; } cout << endl; } } //test.cpp #define _CRT_SECURE_NO_WARNINGS 1 #include <iostream> using namespace std; #include "vector.h" int main() { lj::test_vector(); return 0; }