建行深圳网站,大连seo推广优化,高校网站建设需求分析报告,软件商店下载免费版目录
一.vector的介绍
1.vector的介绍
二.vector的定义模拟实现
三.vector各接口的模拟实现
1.vector迭代器的模拟实现
2.构造函数 2.1无参构造
2.2 n个val构造
2.3迭代器区间构造
2.4通过对象初始化#xff08;拷贝构造#xff09;
3.析构函数
4.size
5.operato…
目录
一.vector的介绍
1.vector的介绍
二.vector的定义模拟实现
三.vector各接口的模拟实现
1.vector迭代器的模拟实现
2.构造函数 2.1无参构造
2.2 n个val构造
2.3迭代器区间构造
2.4通过对象初始化拷贝构造
3.析构函数
4.size
5.operator
6.capacity
7.reserve
8.resize
9.operator[ ]
10.insert
11.push_back
12.erase
13.pop_back
14.empty 一.vector的介绍
1.vector的介绍
这是官方的文档介绍cplusplus.com/reference/vector/vector/ 1. vector是表示可变大小数组的序列容器。 2. 就像数组一样vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问和数组一样高效。但是又不像数组它的大小是可以动态改变的而且它的大小会被容器自动处理。 3. 本质讲vector使用动态分配数组来存储它的元素。当新元素插入时候这个数组需要被重新分配大小为了增加存储空间。其做法是分配一个新的数组然后将全部元素移到这个数组。就时间而言这是一个相对代价高的任务因为每当一个新的元素加入到容器的时候vector并不会每次都重新分配大小。 4. vector分配空间策略vector会分配一些额外的空间以适应可能的增长因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何重新分配都应该是对数增长的间隔大小以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。 5. 因此vector占用了更多的存储空间为了获得管理存储空间的能力并且以一种有效的方式动态增长。 6. 与其它动态序列容器相比deques, lists and forward_lists vector在访问元素的时候更加高效在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作效率更低。比起lists和forward_lists统一的迭代器和引用更好 二.vector的定义模拟实现
首先我们先 定义一个命名空间 来模拟实现咱们的vector类
类里面有三个私有 指针变量 分别指向数据块的开始尾和存储容量的尾
namespace zyl
{templateclass Tclass vector{public:// Vector的迭代器是一个原生指针typedef T* iterator;typedef const T* const_iterator;private:iterator _start; // 指向数据块的开始iterator _finish; // 指向有效数据的尾iterator _endOfStorage; // 指向存储容量的尾};
}
三.vector各接口的模拟实现
1.vector迭代器的模拟实现 vector的迭代器分为俩种 一种是普通迭代器 指向的内容可以被修改 一种是const迭代器 不可以修改只可读 iterator begin(){return _start;}iterator end(){return _finish;}const_iterator cbegin() const{return _start;}const_iterator cend() const{return _finish;}
2.构造函数
vector 的四种构造函数 2.1无参构造 主要是对各个指针初始化 赋值为空 vector():_endOfStorage(nullptr),_start(nullptr),_finish(nullptr){}
2.2 n个val构造 直接向数组中尾插数据用reserve提前扩容, 提高效率 然后需要注意的是 这里传参的第二个参数使用匿名对象const T val T() 这种写法会调用默认构造(可以是任意类型)我们前面讲内置类型是没有默认构造函数的, 理论而言是没有的, 但是调用模板之后必须要支持默认构造 vector(int n, const T value T()):_endOfStorage(nullptr), _start(nullptr), _finish(nullptr){reserve(n);//提前开n个空间for (int i 0;i n;i){push_back(value);//缺省值默认为val}}
2.3迭代器区间构造 这里又要使用模板实现 要实现一个任意类型的迭代器允许任意类型的数据使用直接用迭代器遍历数组, 尾插数据即可 templateclass InputIteratorvector(InputIterator first, InputIterator last):_endOfStorage(nullptr),_start(nullptr),_finish(nullptr){while (first ! last){push_back(*first);first;}2.4通过对象初始化拷贝构造 通过传一个vector对象 然后进行交换 vector(const vectorT v){vectorT tmp(v.cbegin(), v.cend());swap(tmp);} 3.析构函数 析构函数的主要功能 释放掉所有数据 然后三个指针指向空
~vector(){delete[]_start;_start nullptr;_finish nullptr;_endOfStorage nullptr;}
4.size 返回当前vector长度 size_t size() const{return _finish - _start;}
5.operator 运算符重载 实现深拷贝 把v对象赋给this vectorT operator (vectorT v){if (this ! v){delete[] _start;_start new T[v.capacity()];for (size_t i 0;i v.size();i){_start[i] v[i];}_finish _start v.size();_endOfStorage _start v.capacity();}return *this;}
6.capacity 返回当前vector对象的容量是多少 size_t capacity() const{return _endOfStorage - _start;}
7.reserve 在ncapacity时去进行扩容 是为了防止程序缩容 判段当前数据是为为空需不需要旧数据的拷贝转移 遍历的时候一定要使用深拷贝不要使用memcpy去进行拷贝 void reserve(size_t n){if (n capacity()){size_t sz size();T* tmp new T[n];if (_start)//如果为空 则不用将旧数据转移{for (size_t i 0;i size();i){tmp[i] _start[i];}delete[] _start;}_start tmp;_finish _start sz;_endOfStorage _start n;}}
8.resize n size() 就是删除数据直接改变 _finish的指向即可 n capacity()调用reserve函数扩容 后遍历给数组赋值 void resize(size_t n, const T value T()){//查看是否需要扩容if (n capacity()){reserve(n);}if (n size()){while (_finish _start n){*_finish value;_finish;}}else{_finish _start n;}}
9.operator[ ] vector也支持下标访问 重载 [ ] 可以快速的对数据进行访问 T operator[](size_t pos){assert(pos size());return _start[pos];}
10.insert 检查容量观察是否需要扩容, 扩容前计算出pos与start之间pos与start之间相对距离不变扩容后更新pos位置(这里存在迭代器失效的问题) 遍历挪动数据 将val插入pos位置 注意: 检查pos位置的合法性 iterator insert(iterator pos, const T x){//pos范围必须在_start和_finish之间assert(pos_start);assert(pos _finish);//内存满了 进行扩容if (_finish _endOfStorage){size_t len pos - _start;reseve(capacity() 0 ? 4 : capacity * 2);pos _start len;}iterator end _finish;//移动数据 进行插入while (end pos){*end *(end - 1);end--;}*pos x;_finish;return pos;}
11.push_back 尾插 直接调用insert 在_finish位置去插入 void push_back(const T x){insert(_finish, x);}
12.erase erase函数可以删除所给迭代器pos位置的数据 在删除数据前需要判断容器释放为空 若为空则需做断言处理删除数据时直接将pos位置之后的数据统一向前挪动一位将pos位置的数据覆盖即可。 iterator erase(iterator pos){//判断pos是否合法assert(pos _finish);assert(pos _start);assert(!empty());iterator begin pos 1;while (begin _finish){*(begin - 1) *begin;begin;}--_finish;return pos;}
13.pop_back pop_back直接调用erase去_finish位置进行删除 void pop_back(){erase(_finish);}
14.empty 进行判空 直接看_finish _start是否相同就可以了 bool empty() const{return _finish _start;}
