企业网站的建设的目标人物是,意派h5制作平台,南山做网站公司有哪些,中国建设银行个人卡信息网站送给大家一句话#xff1a; 努力一点#xff0c;漂亮—点#xff0c;阳光一点。早晚有一天#xff0c;你会惊艳了时光#xff0c;既无人能替#xff0c;又光芒万丈。 vector容器初步模拟 1 认识vector开始了解底层实现 2 开始实现成员变量构造函数 析构函数尾插迭代器插入… 送给大家一句话 努力一点漂亮—点阳光一点。早晚有一天你会惊艳了时光既无人能替又光芒万丈。 vector容器初步模拟 1 认识vector开始了解底层实现 2 开始实现成员变量构造函数 析构函数尾插迭代器插入 删除 寻找操作操作符重载swap函数 总结Thanks♪(ω)谢谢阅读下一篇文章见 今天我我来进行vector的模拟实现先简单的实现一下初步功能使其对内置类型可以适配。大部分与string很类似 1 认识vector
开始了解
vector是表示可变大小数组的序列容器。就像数组一样vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问和数组一样高效。但是又不像数组它的大小是可以动态改变的而且它的大小会被容器自动处理。本质讲vector使用动态分配数组来存储它的元素。当新元素插入时候这个数组需要被重新分配大小为了增加存储空间。其做法是分配一个新的数组然后将全部元素移到这个数组。就时间而言这是一个相对代价高的任务因为每当一个新的元素加入到容器的时候vector并不会每次都重新分配大小。vector分配空间策略vector会分配一些额外的空间以适应可能的增长因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何重新分配都应该是对数增长的间隔大小以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。因此vector占用了更多的存储空间为了获得管理存储空间的能力并且以一种有效的方式动态增长。与其它动态序列容器相比deque, list and forward_list vector在访问元素的时候更加高效在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作效率更低。比起list和forward_list统一的迭代器和引用更好。
使用STL的三个境界能用明理能扩展 那么下面学习vector我们也是按照这个方法去学习
底层实现
我们来了解一下vector的底层实现是如何做到首先就要了解其类成员是如何定义的这样我们才能更好的复刻vector以下是1996年的STL版本还比较简单
protected:typedef simple_allocvalue_type, Alloc data_allocator;iterator start; iterator finish;iterator end_of_storage //容量结束;可以看到受保护的内部成员变量是由三个迭代器构成的。 迭代器的底层是
typedef T value_type;
typedef value_type* iterator;也就是说底层是指针T是模版类的参数。接下来我们在观察一下构造函数是如何操作的(参考一部分) vector() : start(0), finish(0), end_of_storage(0) {}vector(size_type n, const T value) { fill_initialize(n, value); }vector(int n, const T value) { fill_initialize(n, value); }vector(long n, const T value) { fill_initialize(n, value); }这个fill_initialize又是什么呢是初始化函数在工程文件中经常使用一层又一层的嵌套由于我还没有丰富的工程经验我看起来还是很费劲晕乎乎的。我们看一部分即可现在我们开始手搓vector针对内置类型进行操作。
2 开始实现
我们开始逐步进行实现。
成员变量
根据我们刚才所查看的源码我们要使用三个迭代器要使用迭代器我们可以使用指针进行模拟。
//使用模版 兼容各种类型
templatetypename T
class vector {
public://重命名 指针即可模拟迭代器 常量与非常量都要提供哦typedef T* iterator;typedef const T* const_iterator;private:iterator _start nullptr;iterator _finish nullptr;iterator _end nullptr;};写出三个迭代器指针后我们对构造函数应该也有了大致思路需要初始化三个迭代器所以我们给与初始值nullptr。让后进行开辟空间。
构造函数 析构函数
这里的构造函数我设置三个接口一个是空构造一个是开辟 N 个空间并初始化为val一个是拷贝构造:
//空构造
vector()
{}
//开辟 N 个空间并初始化为val
vector(size_t n,T val T()) {iterator tmp new T[n];_start tmp;for (iterator it begin(); it _start n ;it) {*it val;}_finish _start n;_end tmp n ;}
/拷贝构造
vector(vectorT v) {//依次尾插即可完成操作for (auto s : v) {push_back(s);}
}
析构函数就是简单的释放空间即可 ~vector(){delete[] _start;_start _finish _end nullptr;}我们完成了构造函数和析构函数为了能够进行测试我们现在来实现尾插操作
尾插
尾插操作之前根据我们实现string的经验来说我们需要做一些准备工作实现一些常用接口size(),capacity(),reserve(),resize(): 注意如果对象中涉及到资源管理时千万不能使用memcpy进行对象之间的拷贝因为memcpy是浅拷贝否则可能会引起内存泄漏甚至程序崩溃。 //注意const 保证不会进行权限的放大size_t size() const{return _finish - _start;}size_t capacity() const{return _end - _start;}bool empty(){return size() 0;}//扩容void reserve(size_t newcapacity) {//记录位置size_t n _finish - _start;T* tmp new T[newcapacity];//拷贝memcpy(tmp, _start, size() * sizeof(T));_start tmp;_finish _start n;_end _start newcapacity;}//改变大小void resize(size_t n, T val T()) {//x需要扩容if ( n size()){reserve(n);;while (_finish ! _end) {*_finish val;_finish;}}//不需扩容else {_finish _start n;}}实现了这些接口就可以顺畅的进行尾插的书写通过size和capacity可以判断是否需要扩容reserve可以进行扩容。然后再_finish位置插入新的数据再移动_finish即可。 //尾插void push_back(T val) {if (size() capacity()) {//扩容reserve(capacity() 0 ? 4 : 2 * capacity());}*_finish val;_finish;}接下来我们在完善一下迭代器。
迭代器
迭代器的实现很简单对指针进行重命名即可真正的迭代器没有这么简单
typedef T* iterator;
typedef const T* const_iterator;//迭代器
iterator begin() { return _start; }
iterator end() { return _finish; }
const_iterator begin() const{ return _start; }
const_iterator end() const{ return _finish; }
完成了begin 和end()函数就可以使用基于范围的for循环了。 我们进行一个简单的测试来看看我们写的构造尾插是否正常。
templateclass T
void print_vector(const vectorT v) {for (size_t i 0; i v.size(); i) {cout v[i] ;}cout endl;
}
//构造尾插测试
void vector_test1() {cout ---------构造 尾插测试---------\n;vectorint v1;vectorint v2(4);v2.push_back(1);v2.push_back(2);v2.push_back(3);v2.push_back(4);print_vector(v2);v1.push_back(5);v1.push_back(6);print_vector(v1);cout v1.size() endl;cout v1.capacity() endl;vectorint v3(v1);print_vector(v3);
}看一下效果 没有问题
插入 删除 寻找操作
这个也很简单对数据进行挪动就可以完成
//任意位置插入
void insert(size_t pos 0,T val T()) {
//保证在数据范围之内assert(pos 0);assert(pos size());//检查if (size() capacity()) {//扩容reserve(capacity() 0 ? 4 : 2 * capacity());}iterator it end();//依次后移 然后插入while (it begin() pos) {*(it 1) *it;it--;}it;*it val;_finish;
}
void erease(size_t pos)
{
//保证在数据范围之内assert(pos 0);assert(pos size());iterator it begin() pos;//依次前移while (it end()) {*it *(it 1);it;}_finish--;}
//尾删
void pop_back() {erease(size());}
size_t find(T val T())
{//依次寻找for (iterator it _start; it _finish;it) {if (*it val) return it - _start;}return -1;
}操作符重载
vector容器最重要的操作符应该就是[ ]操作了吧此外重载一个
//提供常量与非常量
T operator[](size_t n) { assert(n 0); assert(n size()); return *(_start n); }
const T operator[](size_t n) const { assert(n 0); assert(n size()); return *(_start n); }
//类似拷贝
vectorT operator(vectorT v){T* tmp new T[v.capacity()];memcpy(tmp, v._start, v.size() * sizeof(T));size_t pos v.size();size_t n v.capacity();_start tmp;_finish _start pos;_end _start capacity();return *this;
}这样就完成了 我们进行一个测试来看看是否可行
void vector_test2() {cout ---------resize find insert erase测试---------\n;vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);v1.push_back(6);print_vector(v1);cout v1.find(2) endl;v1.resize(10, 0);print_vector(v1);v1.insert(0, 0);print_vector(v1);v1.erease(5);print_vector(v1);}来看效果 成功
swap函数
接下来在提供一个swap 函数以供交换注意一定是深拷贝 void swap(vector v) {T* tmp new T[v.capacity()];memcpy(tmp, v._start, v.size() * sizeof(T));size_t pos v.size();size_t n v.capacity();v._start _start;v._finish _finish;v._end _end;_start tmp;_finish _start pos;_end _start capacity();}来进行一个简单测试
//交换测试
void vector_test3() {cout ---------swap 测试---------\n;vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);v1.push_back(6);print_vector(v1);vectorint v2(4);v2.push_back(1);v2.push_back(3);v2.push_back(1);v2.push_back(4);print_vector(v2);v2.swap(v1);print_vector(v1);print_vector(v2);}来看效果 成功交换
总结
我们初步完成了对vector 的模拟实现但是依然有问题比如不支持string等特殊类型。所以下一篇文章我们来一起完善一下。
Thanks♪(ω)谢谢阅读
下一篇文章见
