1. vector的基本框架
STL的源代码整体考虑的东西比较多,还要考虑和其他地方的结合,因此整体的设计是比较复杂的。基于这一系列原因,我们会以简单的形式去实现其核心框架接口,方便去学习 vector。我们可以先看一看STL源代码的整体框架,一些要实现的接口函数不会实现的时候才去看看细节。现在自己看源码还不太好,且看不懂,跟着这篇博客看就挺好的(自夸+1)
以下是基于《STL源码剖析》用到的vector的部分源码:
其中最重要的就是三个私有成员 start 、finish 和 end_of_storage。
想想模拟代码的实现,为了和库中的 vector 进行区分,这里依然用命名空间包含起来。
造一个 vector 的类模板去适应各种类型,用 typedef 将 T* 重命名为 iterator。
1.1 构造析构和容量
经过前面string的学习和上面的源码,直接放vector.h :
#pragma once #include<iostream> #include<assert.h> using namespace std; namespace rtx { template<class T> class vector { public: typedef T* iterator; vector() :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) {} ~vector() { delete[] _start; _start = _finish = _end_of_storage = nullptr; } size_t size() const { return _finish - _start; } size_t capacity() const { return _end_of_storage - _start; } private: iterator _start; iterator _fnish; iterator _end_of_storage; }; }
1.2 push_back,reserve和operator[ ]
我们这里先实现一个简单的 push_back,以便于我们能先把 vector 跑起来。我们的 push_back 没有空间配置器,我们就用 new 去替代它。
尾插需要做哪些事?
1:检查是否需要增容
需要增容,就先增容后再插入数据;不需要增容,就直接插入数据。
我们先去思考,如何判断是否需要增容 ——
我们之前的判断方式是 size == capacity 的时候需要增容问题是,这次我们没有定义 _size 和 _capacity,取而代之的是 _start 、 _finish 和_end_of_storage的形式。
想想: 当 _finish == _end_of_storage时,不就说明容量不够了吗?
2:如果需要增容
前面已经知道,vector是有reserve接口的,增容我们先实现reserve:
如果要增容:
① 开一块带有新容量的空间存到 tmp 中。
② 再把原空间的数据拷贝到新空间。(还能用memcpy吗,我们先用着)
③ 并释放原有的旧空间
④ 最后将 _start 、_finish 和 _end_of_storage指向新的空间。
值得注意的是,最后一步如果先将 _start 指向 tmp 后,再计算 _finish 时,
此时不能现场算 size() ,现场算会出问题,因为 _start 已经被更新成 tmp 了,
如果不想改变顺序,还是想按 _start、_finish 和 _eos 的顺序赋值,
我们可以提前把 size() 算好,存到一个变量中。
此外,真 vector 这里扩容是要调空间配置器的,开空间和初始化是分开的。
我们这里的实现也没有空间配置器,对于空间配置器的知识我们放到后面再说,
我们目前的重点不是空间配置器,重点是 vector。
至于新容量给多少,我们还是按照自己的习惯,首次给4默认扩2倍的方式去增容。
reserve代码:
void reserve(size_t n) { if (n > capacity()) { size_t sz = size(); T* tmp = new T[n]; if(_start) { memcpy(tmp, _start, sizeof(T) * sz); delete[] _start; } _start = tmp; _finish = tmp + sz; _end_of_storage = tmp + n; } }
3:插入数据
查增容和增容都已经分析完了,最后就只剩一个插入了,插入是最简单的,
因为_finish指向的是最后一个元素的下一个位置,我们直接让要插入的元素赋值给_finish,
然后++_finish就行了。push_back代码:
void push_back(const T& x) { if (_finish == _end_of_storage) { reserve(capacity() == 0 ? 4 : capacity() * 2); } *_finish = x; ++_finish; }
为了方便测试尾插的效果,我们先来实现一下 operator[] ,利用 "下标+方括号" 的方式遍历。
这有两个接口,我们一起实现了:
T& operator[](size_t pos) { assert(pos < size()); return *(_start + pos); } const T& operator[](size_t pos) const { assert(pos < size()); return *(_start + pos); }
T:由于我们不知道返回值类型,所以给 T。
T&:引用返回减少拷贝。
const是给const对象用的:这里 cosnt 修饰 T 和 this,是为了限制写。
测试一下:(vector.h:)
#pragma once #include<iostream> #include<assert.h> using namespace std; namespace rtx { template<class T> class vector { public: typedef T* iterator; vector() :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) {} ~vector() { delete[] _start; _start = _finish = _end_of_storage = nullptr; } size_t size() const { return _finish - _start; } size_t capacity() const { return _end_of_storage - _start; } void push_back(const T& x) { if (_finish == _end_of_storage) { reserve(capacity() == 0 ? 4 : capacity() * 2); } *_finish = x; ++_finish; } void reserve(size_t n) { if (n > capacity()) { size_t sz = size(); T* tmp = new T[n]; if (_start) { memcpy(tmp, _start, sizeof(T) * sz); delete[] _start; } _start = tmp; _finish = tmp + sz; _end_of_storage = tmp + n; } } T& operator[](size_t pos) { assert(pos < size()); return *(_start + pos); } const T& operator[](size_t pos) const { assert(pos < size()); return *(_start + pos); } private: iterator _start; iterator _finish; iterator _end_of_storage; }; }
Test.c:
#include "vector.h" namespace rtx { void Test1() { vector<int> v; cout << v.size() << " " << v.capacity() << endl; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); cout << v.size() << " " << v.capacity() << endl; v.push_back(5); cout << v.size() << " " << v.capacity() << endl; for (size_t i = 0; i < v.size();++i) { cout << v[i] << " "; } cout << endl; } } int main() { rtx::Test1(); return 0; }
2. vector的迭代器
2.1 四个基本迭代器
vector 的迭代器是一个原生指针:
template<class T> class vector { public: typedef T* iterator; typedef const T* const_iterator;
前面源码看到,begin() 和 end() ,直接分别返回 _start 和 _finish 即可,
const 类型的迭代器,即可读不可写。在实现的时候用 const 修饰即可:
测试迭代器的效果:(范围for也能用了)
void Test2() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); for (size_t i = 0; i < v.size();++i) { ++v[i]; cout << v[i] << " "; } cout << endl; vector<int>::iterator it = v.begin(); while (it != v.end()) { --(*it); cout << *it << " "; ++it; } cout << endl; for (const auto& e : v) { cout << e << " "; } cout << endl; }
2.2 迭代器区间初始化
上一篇说到vector是支持迭代器区间初始化的:
拷贝构造放在后面再讲,先实现迭代器区间初始化:
因为传过来的迭代器可以是任意的,所以这又是一个模板:
(一个类模板的成员函数,又可以是一个函数模板):
void Test2() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); for (size_t i = 0; i < v.size();++i) { ++v[i]; cout << v[i] << " "; } cout << endl; vector<int>::iterator it = v.begin(); while (it != v.end()) { --(*it); cout << *it << " "; ++it; } cout << endl; for (const auto& e : v) { cout << e << " "; } cout << endl; string s("hello world"); vector<int> v1(s.begin(), s.end());// 存了ASCII码 for (const auto& e : v1) { cout << e << " "; } cout << endl; }
为什么这里要叫 InputIterator?不用它行不行?
想要知道这个问题,我们先讲解一下迭代器的分类。
2.3 迭代器的分类
迭代器可以分为这么几类:
① 输入 / 输出迭代器:input_iterator / output_iterator
特点:单步向前迭代,不可写 / 单步向前迭代,可写,无对应类型
② 单向迭代器:forward_iterator
特点:满足以上所有功能,并且能 ++
(不能 - -没有 rbegin / rend)
(C++11)
(C++11)
(C++11)
③ 双向迭代器:bidirectional_iterator
特点:满足以上功能,并且能 ++,还能 - -
④ 随机迭代器:randomaccess_iterator
特点:满足以上所有功能,能 ++ 能 - -,还能 + 和 -
它们本质上是一个继承关系:下面是子类,上面是父类。
子类都是一个父类,因为它满足父类的所有特征。
也就是说,虽然在语法上它是个模板,允许你传任意类型的迭代器,
但是在更深层次上存在着更进一步的限制 ——
它要求你传随机迭代器,你就不能用双向迭代器。因为只有随机迭代器才能满足随机迭代器的所有操作。换言之,你不能用功能比它指定的迭代器少的迭代器。(可以理解为权限的放大)
它要求你用双向迭代器,你就不能用单向迭代器,因为单项迭代器不能满足所有双向迭代器的操作。但是你可以用比它功能多的迭代器,比如随机迭代器,因为随机迭代器也能满足双向迭代器的操作。因为随机迭代器是双向迭代器的子类,它满足父类(双向迭代器)的所有功能。(可以理解为权限的缩小)
我们弄明白了这些,我们再回到刚才提的问题 —为什么这里要叫 InputIterator?
首先,InputIterator 是输入迭代器,这么写是为了满足命名规范。
可以不用,我们可以传单向迭代器、双向迭代器,也可以传随机迭代器。
因为这些迭代器都满足输入迭代器的所有功能。
从C语言到C++_15(vector的模拟实现)+迭代器失效问题(中):https://developer.aliyun.com/article/1521294