一， 函数原型部分分析(简单举例使用便于理解)
- 简单测试使用:
int main() { std::vector<int> vint; vint.reserve(3); cout << vint.capacity() << endl; vint.resize(10, 5); cout << vint.size() << endl; for (auto& e : vint) { cout << e << " "; } cout << endl; return 0; }
如上可以证明的就是resize改变的size ，reserve改变的是capacity是预先开出空间，至于使用reserve的使用可以减少扩容的次数.. 提高效率..
迭代器函数, 返回迭代器. 支持迭代器, 有了迭代器才能支持范围的遍历方式. 像是上述使用的for (aoto& e : vint) 的遍历方式都是因为存在迭代器作为支撑才可以的
为了验证, 简单的使用迭代器模板类模拟实现一下 for_each
引入一下小小的知识点，迭代器类型 + 仿函数类型 作为类型模板是一种很常见的使用方式. 这种方式常用在对于一段区间的元素做函数处理的场景下: (很重要的trait)
template<class InputIterator, class Function> void Func(InputIterator first, InputIterator last, Function f) { while (first != last) { f(*first); ++first; } return; }
eg : 
template<class T > struct Print { void operator()(T& val)const { cout << val << " "; } }; template<class InputIterator, class Function> void for_each(InputIterator first, InputIterator last, Function f) { while (first != last) { f(*first); ++first; } return; } } int main() { std::vector<int> vint; vint.reserve(3); cout << vint.capacity() << endl; vint.resize(10, 5); cout << vint.size() << endl; //for (auto& e : vint) { // cout << e << " "; //} tyj::for_each(vint.begin(), vint.end(), tyj::Print<int>()); cout << endl; return 0; }
- 所以可以证明的是for(aoto& e : 容器)的这种遍历方式应该底层也是基于迭代器实现的
二、 迭代器设计思想,vector迭代器分析
因为 vector 的底层就是一个动态数组.维护的是一个线性空间, 所以普通的原生指针可以直接使用做迭代器, 因为本身指针就是支持operator++ operator-- operator*这些运算的
typedef T* iterator; typedef const T* const_iterator;
三，整体的大体可以快速看见效果的框架
对于上述先解释一下，很多时候我们要写一个很大的东西, 为了降低deBug的成本, 其实可以先实现必要性的可以看见效果的区块, 大体的框架性写好, 效果看到了然后
插入元素时候的扩容机制： 如果是需要扩容，采取的一般是二倍扩容的方式进行扩容的，扩容分为三部，新开空间，转移数据，销毁原有空间... (记住转移数据调用深拷贝,不可以memcpy) why?
namespace tyj { template <class T> class vector { typedef T* iterator; typedef const T* const_iterator; public: vector() //默认构造 : start(nullptr) , finish(nullptr) , end_of_storage(nullptr) { } vector(int n, const T& val = T()) //带参构造 : start(new T[n]) { finish = start + n; end_of_storage = finish; for (int i = 0; i < n; ++i) { start[i] = val; } } iterator begin() { return start; } const_iterator begin() const { return start; } iterator end() { return finish; } const_iterator end() const { return finish - 1; } size_t size() const { return finish - start; } size_t capacity() const { return end_of_storage - start; } void reserve(int n) {//预先开空间 if (n <= capacity()) return; //说明需要新开空间, 三步 //1.新开空间 T* pTemp = new T[n]; //2.转移数据 int _size = size(); for (int i = 0; i < _size; ++i) { pTemp[i] = start[i]; } //3.销毁原有空间 delete[] start; start = pTemp; finish = start + _size; end_of_storage = start + n; } void push_back(const T& val) { if (size() == capacity()) { reserve(size() == 0 ? 8 : (size() << 1)); } //放入数据 *finish = val; finish++; //尾部迭代器后移 } private: //[start, finish) iterator start;//当前使用空间起点 iterator finish;//当前使用空间末尾 iterator end_of_storage; //空间末尾 }; template <class T > struct Print { void operator()(T& val) const { cout << val << " "; } }; template<class InputIterator, class Function> void for_each(InputIterator first, InputIterator last, Function f) { while (first != last) { f(*first); ++first; } } } int main() { tyj::vector<int> vint; for (int i = 0; i < 5; ++i) vint.push_back(i); cout << vint.size() << endl; tyj::for_each(vint.begin(), vint.end(), tyj::Print<int>()); cout << endl; return 0; }
三，重点函数分块分析图解实现, 仅仅只是写哪些可能大家不清楚的，都可以写的部分写了也没用
- 然后就是一个一个函数的分析应该如何设计的问题
各种构造函数的设计思想，如何只写一个然后实现代码复用
- 区间范围range构造
- swap为复用代码做准备
- 赋值重载
同样的道理，已经复用了拷贝构造函数构造出来了 vec 对象直接 窃取 vec 换成自己的，马匪看过吗，让我成为你, 你成为空气
- 移动构造 (更加强盗，不齿，直接抢将死之人的身份)
insert + erase 的设计，以及分析返回值，加之分析迭代器失效会出现的位置，和抛出设计中的细节之处
- insert
- erase
- 再看 insert + erase 都存在一个 iterator作为返回值，为啥，跟新旧的迭代器，防止迭代器失效。。。 向如下的代码为啥要 接收一下 erase 之后的返回值也就可以理解了，防止使用失效的迭代器
void test() { std::vector<int> vec(5, 1); for (auto it = vec.begin(); it != vec.end(); ++it) { it = vec.erase(it); } } it = v.begin(); PrintVector(v); while (it != v.end()) { if (*it % 2 == 0) it = v.erase(it); else ++it; }
- 至此比较有用的部分都已经分析完成了。
四. 整体代码 (实现代码)
#include <vector> #include <algorithm> #include <iostream> #include <assert.h> using namespace std; namespace tyj { template <class T > class vector { public: //原生指针作为迭代器 typedef T* iterator; typedef const T* const_iterator; //无参构造函数 vector() : start(nullptr) , finish(nullptr) , end_of_storage(nullptr) { } vector(int n, const T& val = T()) : start(new T[n]), finish(start + n), end_of_storage(start + n) { //放入数据 for (int i = 0; i < n; ++i) { start[i] = val; } } //写范围构造函数 template<class InputIterator> vector(InputIterator first, InputIterator last) { //利用范围进行构造 while (first != last) { push_back(*first++);//直接进行复用接口 } } //接下来写拷贝构造， 赋值运算符重载，移动构造，全部进行复用接口 void swap(vector<T>& vec) { ::swap(start, vec.start); ::swap(finish, vec.finish); ::swap(end_of_storage, vec.end_of_storage); } vector(const vector<T>& vec) : start(nullptr) , finish(nullptr) , end_of_storage(nullptr) { vector<T> tmp(vec.begin(), vec.end()); swap(tmp);//复用范围构造代码 } vector<T>& operator=(vector<T> vec) { swap(vec);//复用拷贝构造代码 return *this; } //移动构造， 窃取资源，窃取将亡对象的底层堆区资源 //反正你都要死亡了不如用来给我构造 vector(vector<T>&& vec) : start(nullptr) , finish(nullptr) , end_of_storage(nullptr) { swap(vec); } iterator begin() { return start; } const_iterator begin() const { return start; } iterator end() { return finish; } const_iterator end() const { return finish; } void resize(size_t n, const T& val = T()) { if (n <= size()) return; //啥事不用做 //至此说明了超出的部分需要设置为val if (n > capacity()) reserve(n);//先扩容 //然后赋值 while (finish != start + n) { *finish++ = val; } } void reserve(int n) { //预先开空间，三部曲目 if (n <= capacity()) return; //至此说明需要重新开空间 T* pTemp = new T[n]; size_t sz = size();//保存之前容器中的元素大小 //转移数据 for (int i = 0; i < sz; ++i) { pTemp[i] = start[i]; } delete [] start;//删除掉原有的空间 start = pTemp; finish = pTemp + sz; end_of_storage = start + n; } void push_back(const T& val) { if (finish == end_of_storage) { reserve(capacity() > 0 ? capacity() << 1 : 4); } //有了空间，然后就是进行数据插入 *finish++ = val;//放入数据 } bool empty() { return start == nullptr; } size_t size() { return finish - start; } size_t capacity() { return end_of_storage - start; } //网pos位置插入一个元素，插入一定谨防的是插入扩容的原有迭代器失效问题 iterator insert(iterator pos, const T& val) { assert(pos >= start && pos <= finish);//断言位置合法 if (finish == end_of_storage) { size_t step = pos - start; //扩容首先 reserve(capacity() > 0 ? capacity() << 1 : 4); //扩容之后原有的pos迭代器会失效跟新 pos = start + step; } //拿到finish迭代器同时finish迭代器后移动 iterator it = finish++; //腾出空间 while (it != pos) { *it = *(it - 1); --it; } *pos = val;//放入插入数据 return pos;//返回插入位置元素 } //删除一定注意的是删除的位置其实还是pos 因为返回下一个元素其实是覆盖到pos位置了 iterator erase(iterator pos) { //覆盖删除整个元素 assert(pos >= start && pos < finish); iterator it = pos + 1; while (it <= finish) { *(it - 1) = *it;//覆盖删除 ++it; } --finish;//尾部迭代器前移动 return pos; } ~vector() { if (start) { delete[] start; } start = finish = end_of_storage = nullptr; } private: T* start; T* finish; T* end_of_storage; }; template<class InputIterator, class Function> void for_each(InputIterator first, InputIterator last, Function f) { while (first != last) { f(*first); ++first; } } template<class T> struct Print { void operator()(T& val) const { cout << val << " "; } }; } template<class T> void PrintVector(tyj::vector<T>& vec) { tyj::for_each(vec.begin(), vec.end(), tyj::Print<T>()); cout << endl; }
测试代码
void TestVector3() { int a[] = { 1, 2, 3, 4 }; tyj::vector<int> v(a, a + sizeof(a) / sizeof(a[0])); // 使用find查找3所在位置的iterator auto pos = find(v.begin(), v.end(), 3); //pos迭代器可以失效, 插入操作迭代器也会失效 // 在pos位置之前插入30 v.insert(pos, 30); PrintVector(v); // 删除pos位置的数据 pos = find(v.begin(), v.end(), 3); v.erase(pos); PrintVector(v); } void TestVector1() { // constructors used in the same order as described above: tyj::vector<int> first; // empty vector of tyj::vector<int> second(4, 100); // four ints with value tyj::vector<int> third(second.begin(), second.end()); // iterating through tyj::vector<int> fourth(third); // a copy of third // the iterator constructor can also be used to construct from arrays: int myints[] = { 16, 2, 77, 29 }; tyj::vector<int> fifth(myints, myints + sizeof(myints) / sizeof(int)); std::cout << "The contents of fifth are:"; for (tyj::vector<int>::iterator it = fifth.begin(); it != fifth.end(); ++it) std::cout << *it << " "; std::cout << endl; // 测试T是string时，拷贝问题 tyj::vector<string> strV; strV.push_back("1111"); strV.push_back("2222"); strV.push_back("3333"); strV.push_back("4444"); } void TestVector2() { // 使用push_back插入4个数据 tyj::vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); PrintVector(v); // 使用迭代器进行修改 auto it = v.begin(); while (it != v.end()) { *it *= 2; ++it; } PrintVector(v); // 这里可以看出C++11支持iterator及接口，就支持范围for for (auto e : v) cout << e << " "; } // iterator失效问题 void TestVector4() { int a[] = { 1, 2, 3, 4 }; tyj::vector<int> v(a, a + sizeof(a) / sizeof(a[0])); // 删除pos位置的数据，导致pos迭代器失效 auto pos = find(v.begin(), v.end(), 3); v.erase(pos); cout << *pos << endl; // 此处会导致非法访问 // 在pos位置插入数据，导致pos迭代器失效。 // insert会导致迭代器失效，是因为insert可 // 能会导致增容，增容后pos还指向原来的空间，而原来的空间已经释放了。 pos = find(v.begin(), v.end(), 3); v.insert(pos, 30); cout << *pos << endl; // 此处会导致非法访问 // 实现删除v中的所有偶数 // 下面的程序会崩溃掉，如果是偶数，erase导致it失效 // 对失效的迭代器进行++it，会导致程序崩溃 auto it = v.begin(); //while (it != v.end()) //{ // if (*it % 2 == 0) // v.erase(it); // ++it;//每一次erase之后进行跳跃 //} // 以上程序要改成下面这样，erase会返回删除位置的下一个位置 it = v.begin(); PrintVector(v); while (it != v.end()) { if (*it % 2 == 0) it = v.erase(it); else ++it; } } int main() { //tyj::vector<int> vec1; //for (int i = 0; i < 5; ++i) { // vec1.push_back(i); //} //PrintVector<int>(vec1); //tyj::vector<int> vec2; //vec2.resize(5, 1); //PrintVector<int>(vec2); //int nums[5] = { 1, 2, 3, 4, 5 }; //tyj::vector<int> vec3(nums, nums + sizeof(nums) / sizeof(int)); //PrintVector<int>(vec3); //tyj::vector<int> vec4(vec3); //PrintVector<int>(vec4); //TestVector3(); //TestVector2(); //TestVector4(); TestVector1(); return 0; }
五. 整合小结一下，以及特别谈一谈如何写一个STL容器和迭代器设计思想(迭代器是什么)，迭代器失效的问题.
如何实现一个STL书写的方法论
首先分析如果要写一个STL容器应该如何下手的问题，找到一个官方文档分析组件 + 接口
推荐官方文档网址: www.cplusplus.com
写一个STL 需要将迭代器设计和整体的设计分开来，先实现迭代器的设计 + 实现最简单的插入接口 （完成框架），测试插入接口，一来可以获得一定成就，而来可以知道自己基本框架是否搭建正确
阅读文档分析重点接口函数，可以买一本STL源码刨析，结合侯捷老师的讲述去设计接口， 将有用的接口一一实现. (在实现的过程中不断测试以及发现细节坑点)
总结实现细节中出现的坑点 + 快速复现重写整个框架 (记忆熟练)
其实谈迭代器的设计在此处不算很合适，因为T* 就是一个原生指针，而且还是连续的线性存储空间，原生指针作为迭代器，本身迭代器就支持 ++ -- * 这些操作，加之元素本身就是连续存储的， 所以此处没有对迭代器的设计画太多功夫。
迭代器，算是一个智能指针类的感觉，但是也不完全是，可以帮助我们管理访问容器中的元素，支持 ++ -- * 这些操作来访问复杂存储结构中的 元素。
迭代器的设计是为了统一，是为了做粘合剂，做通用各式各样容器和算法之间的粘合剂， 有了迭代器，我们才能做各式各样容器的统一泛型算法操作，才能统一各种格式各样的容器元素的遍历方式，提供统一遍历接口. 是STL中特别重要的组件
上述这些算法，没有迭代器根本不可能这样写
迭代器失效，说白了其实本质是内存问题，扩容后，原来的迭代器全部不可以用了，因为原来的迭代器指向原来的那片空间，可是 扩容后原来那片空间都释放掉了，你如何敢访问，所以每一次关于迭代器的操作我们需要接收返回值就是这个道理，跟新旧的迭代器，避免使用失效迭代器, it = e.erase(it) 不能是 e.erase(it++); ; 因为删除之后你不清楚，it 的情况如何，但是返回迭代器是指向下一个元素的有效迭代器，所以需要接收返回值. 删除it 之后 it 本质是一个失效迭代器了，如何赶直接 ++ 因为他的本质在接收返回值之前还是哪个即将别删除的迭代器
所以 删除，插入扩容，都可能导致迭代器失效，插入失效是因为扩容，删除失效是因为它已经别干掉了，很可能是delete 或者其他操作
