成都网站建设推广在线咨询,wordpress分页导航菜单,甘肃省建设社厅网站,十款看免费行情的软件推荐本文已收录至《C语言和高级数据结构》专栏#xff01; 作者#xff1a;ARMCSKGT STL之vector模拟实现 前言正文空间结构默认成员函数构造函数拷贝构造函数赋值重载析构函数关于数据拷贝问题 迭代器容量操作查询容量容量操作 数据访问下标访问头尾数据访问 数据增删尾插尾删重… 本文已收录至《C语言和高级数据结构》专栏 作者ARMCSKGT STL之vector模拟实现 前言正文空间结构默认成员函数构造函数拷贝构造函数赋值重载析构函数关于数据拷贝问题 迭代器容量操作查询容量容量操作 数据访问下标访问头尾数据访问 数据增删尾插尾删重新分配任意位置插入删除迭代器失效问题概述 其他操作清空函数交换函数关于排序 最后 前言
vector是STL容器容器之一其底层实现类似于数据结构顺序表相当于string来说得益于泛型模板的加持使得vector可以变为任何类型且是可以动态扩容堪称大号数组在vector的实现中有许多值得我们学习的细节接下来将为大家一一介绍 正文
本文将实现一些有学习意义的常规简单接口提高我们的代码能力 空间结构 与C语言实现顺序表不同vector底层空间结构为三个指针: _start指向空间的起始地址_finish指向最后一个数据的下一个地址(下一个空位)_end_of_stroage指向空间最后一个最末地址 namespace My_vector
{templateclass T //模板参数Tclass vector{typedef T* iterator; //指针重命名为迭代器typedef const T* const_iterator;private:iterator _start; //首地址iterator _finish; //空位地址iterator _end_of_storage; //空间末地址}
}这里需要注意的是由于vector使用了模板所以函数实现都在头文件中防止因为模板导致的链接错误的问题 默认成员函数 无一例外常用的默认成员函数有四个 构造函数拷贝构造函数赋值重载函数析构函数 这里的默认成员函数都需要自己设计因为涉及深拷贝和一些其他细节问题 构造函数 构造函数有三个版本分别是默认构造函数带参构造函数和迭代器区间构造 默认构造函数初始化三个指针置空即可带参构造函数初始化n个T类型的value值在对象中迭代器区间构造通过其他容器迭代器或指针迭代插入其所有值 //迭代器区间构造
vector():_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{}//带参构造函数
//vector(size_t n, const T value T()) //初始化n个t类型数据
// :_start(nullptr)
// , _finish(nullptr)
// , _end_of_storage(nullptr)
//{
// reserve(n);
// for (int i 0; i n; i)
// {
// *(_finish) value;
// }
//}//带参构造函数 int修复版本
vector(int n, const T value T()) //初始化n个t类型数据:_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{if (n 0) //n必须大于0才能处理{reserve(n); //提前开辟空间for (int i 0; i n; i) //逐一插入{*(_finish) value;}}
}//迭代器区间构造
templateclass InputIterator
vector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{auto it first;int n 0;while (it ! last) { n; it; } //计算数据长度reserve(n); //提前开辟空间while (first ! last) //迭代器插入数据{push_back(*first);first;}
}这里需要注意几个问题 我们首先实现了带参构造函数的n为size_t类型的版本因为不可能插入负数个T类型的value数据但是如果我们使用带参构造函数实例化则会发生非法间接寻址的错误这是因为size_t是整型实例化T数据类型也是整型此时编译器会自动匹配最合适的构造函数于是匹配到了迭代器区间构造 vector(size_t n, const T value T()) //int类型n vectorint v(2,1);时会冲突
vector(int n, const T value T()) //size_t类型n 解决方法就是写一个n为int类型的带参构造参数去匹配而且可以不用size_t版本 此外这里多处使用了匿名对象初始化缺省参数这里T()就是一个匿名对象用于初始化value。当我们只输入n参数时匿名对象会作为缺省值传递给value这里需要注意 匿名对象的生命周期只在这一行但是被const修饰后会延长生命周期内置类型也支持像构造对象一样初始化 //例如
int a(1)
int b(); //默认初始化为0
char c(c);//所以可以这样赋值
double d double(1.23);
float f float()拷贝构造函数 拷贝构造最大的问题就是涉及深拷贝问题我们希望当一个vector对象拷贝另一个对象时新对象开辟独立的空间拷贝数据而不是两个对象共用一段空间否则在析构时会出现异常现象 //传统写法
vector(const vectorT v):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{reserve(v.capacity()); 提前开辟空间for(int i 0;iv.size();i){*(_finish) v._start[i]; //访问v中的数据并赋值}
}//现代写法 - 在实现swap后可以构造临时对象然后交换资源
//vector(const vectorT v)
// :_start(nullptr)
// , _finish(nullptr)
// , _end_of_storage(nullptr)
//{
// vectorT tmp(v.begin(), v.end()); //迭代器区间构造局部对象
// swap(tmp); //swap交换数据
//}默认生成的构造函数是浅拷贝所以我们自己实现在插入数据时预先开辟空间然后逐一赋值这样就能避免浅拷贝问题因为如果是自定义对象在赋值时会调用其自己的拷贝构造 现代写法需要先实现swap函数然后构造临时对象交换对应的指针即可 赋值重载 赋值重载与拷贝构造的问题类似也要注意深拷贝问题区别于拷贝构造的地方在于不需要新建对象但是需要判断是否为同一个对象避免重复开空间clear先清空已有数据reserve开v对象空间大小的容量如果v对象空间小于现有空间则不开此时_finish无论是否开空间都在空间的起始位置(也就是容器为空)直接使用_finish赋值即可 当然赋值重载也有基于swap的现代写法现代写法无论是否是同一个对象都会重新开空间拷贝两者各有优劣 //传统写法
vectorT operator(const vectorT v)
{if (v ! this) //判断是否为同一个对象{clear(); //先清空原空间 方便下面继续使用reserve(v.capacity()); //开v对象大的空间如果比v对象大则不开for (int i 0; i v.size(); i){*(_finish) v._start[i]; //无论是否开了空间_finish指针重新开始赋值}}return *this;
}//现代写法
//vectorT operator(vectorT tmp) //使用传值参数临时对象
//{// swap(tmp);// return *this;
//}析构函数 析构函数就非常简单了释放_start指向的空间置空三个指针即可 但是在此之前要判断一下_start是否有空间如果是空指针则不需要释放 ~vector()
{if (_start) //判断是否为空指针{delete[] _start;_start _finish _end_of_storage nullptr;}
}关于数据拷贝问题 拷贝构造和赋值重载自己实现的意义 浅拷贝也称值拷贝只是拷贝这个值而已但我们需要的是独立开辟空间然后将数据拷贝一份下来两者完全独立 对于浅拷贝带来的问题 两个对象指向同一片空间最后delete两次这片空间最终导致报错 所以在涉及空间操作和扩容操作的情况下必须注意自定义对象深拷贝问题对于自定义类型只需要其自己调用对应的拷贝构造而不是我们自己擅自操作空间 数据拷贝使用赋值的意义 因为vector是模板在string实现中我们对于字符串数据是通过strcpy拷贝的那么vector数据的拷贝能不能用内存拷贝函数memcpy或memmove呢答案是肯定不能 vector实例化为内置类型使用内存拷贝函数没有问题但是实例化为自定义类型就会出现内存问题因为内存拷贝函数在拷贝数据时是从内存中逐字节拷贝我们实际需要的是内置类型直接拷贝而自定义类型去调用其对应的拷贝构造但是使用了mem等内存函数自定义类型就无法调用拷贝构造最终导致也出现内存错误 因为这个问题在vector拷贝构造和reserve扩容等涉及数据拷贝的函数中我们使用的不是内存拷贝函数而是直接赋值 迭代器 vector存储数据使用的是一段连续的存储空间所以迭代器只需要将指针typedef即可对指针 和- - 就能遍历数据 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; }const_iterator cbegin() const { return begin(); } //const迭代器
const_iterator cend() const { return end(); }这里我们提供了普通迭代器和const迭代器对于const迭代器有许多人吐槽cbegin和cend没必要设计因为begin和end普通迭代器可以设计为自适应模式 对于下面的函数 void func(const vectorint v)
{auto vit v.begin();
}如果begin没有重载const_iterator类型的迭代器则会报错但是重载后编译器会识别这个对象是const引用类型就会调用begin的const_iterator版本 这里begin和end迭代器就非常智能实现了自适应很多人觉得cbegin和cend设计就冗余了 其实库里面也是为了保持一致尽量让所有的容器都有这些接口降低学习成本 所以我们模拟实现还是实现了cbegin和cend只不过复用了普通迭代器的const版本 至于库中还存在反向迭代器这个我们后面会就行介绍(其实是对普通迭代器的封装对反向迭代器的就是对普通迭代器的- -) 容量操作 查询容量 对于查询容量常用的就三个函数 size()查询有效元素个数capacity()查询当前容量大小empty()查询当前容器是否为空(没有数据) //元素个数
size_t size() const { return _finish - _start; }
//容量大小
size_t capacity() const { return _end_of_storage - _start; }
//判空
bool empty() const { return _start _finish; }这三个函数都比较简单直接实现即可 唯一需要注意的两点是首先这些函数只是查询函数不涉及修改可以使用const修饰this指针其次因为对空间的管理使用的是三个指针所以使用_finish(有效数据指针)减去_start(空间首地址)就能得出有效数据个数容量也是如此 容量操作 扩容操作 对于reserve函数前面我们介绍了关于数据拷贝的问题reserve最重要的点就是不能使用内存函数拷贝数据而是使用赋值调用拷贝构造就行数据拷贝 对于reserve函数的首先有以下几点情况 对于申请的空间大小n进行判断小于当前空间大小就不进行任何操作开辟n大小的空间使用tmp临时变量存储地址方便准备数据拷贝判断当前空间是否存有数据以及是否为空指针进行数据迁移在数据迁移时一定要用赋值而不是内存拷贝(否则释放旧空间时vector实例的自定义类型会调用对于的析构而我们拷贝的是旧空间中的旧对象而不是拷贝构造的新对象在旧空间释放后新空间中的自定义对象也会释放则存储的都是无效数据)最后交付数据初始化三个指针 void reserve(size_t n)
{if (n capacity()){size_t len size(); //获取当前原空间下数据个数T* tmp new T[n]; //开辟n个空间(nsize())if (begin() (len 0)) {for (int i 0; i size(); i) //有数据则拷贝{tmp[i] _start[i];}delete[] _start; //拷贝完成后释放原空间}_start tmp; //交付空间_finish _start len;_end_of_storage _start n;}
}数据大小调整 对于resize函数最大的区别在于新的数据空间的初始化 对于resize 先判断n是否大于容量准备扩容将新的数据位置为val(val有缺省参数为T())最后初始化_finish指针 void resize(size_t n, T val T()) //数据长度设置为n新的数据位置为val
{if (n capacity()) //如果n大于容量就先扩容{reserve(n);}iterator it _start n; //初始化新空间while (_finish it){*_finish val; //逐一置为val_finish;}_finish it; //最后初始化_finish
}数据访问 下标访问 下标访问通过重载运算符[ ]首先的这里我们首先了两个版本的[ ]重载函数在对应不同的场景 T operator[](size_t pos) //引用版本
{assert(pos size() pos 0); //检查下标合法性return _start[pos];
}const T operator[](size_t pos) const //const引用版本
{assert(pos size() pos 0); //检查下标合法性return _start[pos];
}对于at函数由于其抛异常的特性这里我们简单实现复用运算符[ ]对于异常问题以后会为大家进行介绍 T at(size_t pos) { return (*this)[pos]; }
const T at(size_t pos) const { return (*this)[pos]; }头尾数据访问 同样的front和back函数也有普通版本和const版本在不同场景下编译器会选择合适的函数进行调用 //front 首个数据
T front() { return (*this)[0]; }
const T front() const { return (*this)[0]; }
//back //末尾数据
T back() { return (*this)[size()-1]; }
const T back() const { return (*this)[size() - 1]; }这里复用运算符[ ]复用下标和容量的检查 数据增删 尾插尾删 对于尾插在插入前需要检查容量是否充足不充足需要扩容然后直接插入_finish的空位下即可_finish指针移动到下一个空位对于尾删只需要将_finish指针向前移动即可(- -指针)但需要判断size是否0 //尾插
void push_back(const T val)
{if (_finish _end_of_storage){//扩容时采用两倍策略如果为空则赋予四个空间的初值reserve(capacity() 0 ? 4 : capacity() * 2); }*_finish val; //赋予_finish指向的空位_finish; //_finish指针后移
}//尾删
void pop_back()
{assert(size() 0); //判断是否有数据可删--_finish; //_finish指针前移
}重新分配 vector通过了重新分配函数assign这个函数类似于赋值重载会清空里面原有的所有数据然后重新赋值如果空间不足则会扩容 这个函数有两个版本 迭代器区间分配分配n个val值到容器中 //迭代器区间分配
templateclass InputIterator
void assign(InputIterator first, InputIterator last)
{size_t n 0;auto it first;while (it ! last) { n; it; }if (n capacity()){reserve(n); //扩容}clear(); //默认清空数据while (first ! last){(*(_finish)) (*(first)); //赋值完成后_finish会指向下一个空位}
}//分配n个val值
void assign(int n, const T val)
{reserve(n); //默认扩容如果空间足够就不会执行任何操作clear(); //默认清空数据while (n--) { push_back(val); } //插入n个数据
}这里要注意的首先是容量问题其次是分配数据需要清空原有的数据 任意位置插入删除 任意位置插入和删除是我们常用的函数但是这里最大的问题就是迭代器失效的问题 当我们使用现在的迭代器插入一个数据可能涉及容器扩容如果扩容那么迭代器是旧空间的迭代器则会导致迭代器失效因为原有空间已经被释放但迭代器还是指向原空间(那么就是野指针)所以我们在插入或删除后要更新迭代器那么我们的插入删除函数必须在操作后返回一个迭代器 对于插入来说插入一个元素后返回这个新插入元素位置的迭代器 – 对于插入来说如果涉及扩容则将迭代器更新到新空间的对应数据位置对于删除来说删除一个元素后返回其下一个元素的迭代器 – 对于删除来说删除是后面的数据覆盖前面的数据最终从pos位置开始所有数据会向前挪动一位那么挪动完成后当前pos位置就是下一个迭代器的位置直接返回即可 //在pos迭代器位置插入x
iterator insert(iterator pos, const T x)
{assert(pos _start);assert(pos _finish);if (_finish _end_of_storage) //判断容量问题{size_t len pos - _start;reserve(capacity() 0 ? 4 : capacity() * 2);//扩容后迭代器失效了需要更新同步迭代器pos _start len;}iterator cur _finish;while (cur ! pos){*cur *(cur - 1);--cur;}*cur x;return cur;
}//删除pos迭代器位置的数据
iterator erase(iterator pos)
{assert(pos _start);assert(pos _finish);iterator cur pos;while (cur ! _finish - 1){*cur *(cur 1); //挪动数据cur;}--_finish;return pos; //挪动完成后pos位置的数据已经被下一个数据覆盖了直接返回即可
}迭代器失效问题概述 对于我们扩容后迭代器失效的现象 对于迭代器失效的现象删除也可能出现此现象 对于迭代器失效问题编译器也会检查 VS下(PJ)版本是一旦插入或删除必须更新迭代器哪怕没有发生扩容否则报错g下(SGI)版本不会主动检查迭代器更新问题但是如果发生扩容或删除完了元素没有更新迭代器就会发生段错误 其他操作 清空函数 对于vector元素的清空我们只需要将_finish指针设置为_start即可这样就代表当前vector中没有任何元素同时清空不需要缩容 //清空函数
void clear() { _finish _start; }交换函数 对于vector的交换只需要交换两个vector对象的三个指针即可 //交换函数
void swap(vectorT v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);
}关于排序 vector因为连续的空间对排序是非常有利的库函数中已经实现了快排也就是sort函数可以对支持迭代器的容器排序 关于sort的使用这里需要给大家介绍一下 sort有两个版本都是通过迭代器区间进行排序默认升序第二个版本支持控制升序和降序 int arr[] { 3,2,1,5,4 };
vectorint v(arr,arr5);
sort(v.begin(), v.end());// 默认升序
for (const auto x : v)
{cout x ;
}
cout endl;
sort(v.begin(), v.end(), greaterint()); //排降序
for (const auto x : v)
{cout x ;
}
cout endl;//控制函数Compare是一个仿函数
lessT(); //T类型的升序比较仿函数
greaterT(); //T类型的升降序比较仿函数这里需要注意的是sort函数需要声明algorithm算法头文件并声明std命名空间greater和less也需要在std命名空间中声明 最后
vector模拟实现到这里就结束了相信vector的模拟实现让大家对底层代码的细节问题又有了新的认识这就是我们学习和使用这些容器代码的意义
本次 C vector模拟实现 就先介绍到这里啦希望能够尽可能帮助到大家。
如果文章中有瑕疵还请各位大佬细心点评和留言我将立即修补错误谢谢
本文整体代码vector模拟实现代码 其他文章阅读推荐 C STL之vector的使用 -CSDN博客 C STL之string的使用 -CSDN博客 C STL之string模拟实现 -CSDN博客 C STL简介 -CSDN博客 C 模板 -CSDN博客 欢迎读者多多浏览多多支持!
