怎样建设自己网站,做网站公司昆明,外贸精品网站建设,企业网站 用个人备案#x1f493;博主CSDN主页:杭电码农-NEO#x1f493; ⏩专栏分类:C从入门到精通⏪ #x1f69a;代码仓库:NEO的学习日记#x1f69a; #x1f339;关注我#x1faf5;带你学习C #x1f51d;#x1f51d; vector 1. 前言2. 熟悉vector的接口函数2.1 vec… 博主CSDN主页:杭电码农-NEO ⏩专栏分类:C从入门到精通⏪ 代码仓库:NEO的学习日记 关注我带你学习C vector 1. 前言2. 熟悉vector的接口函数2.1 vector的构造与拷贝构造2.2 vector迭代器的使用2.3 vector空间相关函数2.4 vector的增删查改2.41 find,swap和sort2.42 insert和erase2.43 随机访问operator[ ] 3. vector的模拟实现3.1 vector容量相关函数3.11 reverse函数3.12 resize函数 3.2 vector的构造函数3.3 vector的析构函数3.4 vector的拷贝构造函数 4. 总结以及拓展 1. 前言
和string的学习不同 vector即要掌握它的用法 更要会自己去实现一个vector
本章重点: 熟悉STL库中vector的接口函数 自己实现一个简易vector类 本章只实现容量相关函数 和构造,析构,拷贝构造函数 注:vector其实就是顺序容器 string类只用考虑存储字符 然而vector中可以存储任一类型 所以vector的自我实现需要用模板 2. 熟悉vector的接口函数
还是借助老朋友:cplusplus来查阅文档 库中的vector的模板参数有两个 后一个是内存池,用来提升空间利用效率 对于现阶段的学习而言可有可无 2.1 vector的构造与拷贝构造 常见的构造有:
vectorint v1;
vectorint v2(10,1);
vectorint v3(v2);v2:构造并初始化10个值为1的顺序表
vector可以用迭代器区间初始化:
string str(abcdefg);
vectorstring vv(str.begin(),str.end());2.2 vector迭代器的使用 和string一样,vector有正向和反向 两种迭代器,且使用方法和string相同 vectorint vv{1,2,3,4,5,6};
vectorint::iterator it vv.begin();
while(it!vv.end())
{cout*it;it;
}2.3 vector空间相关函数 vector的空间相关的函数 和string的机会一模一样 如果你看了文档还不懂的话 可以先阅读此篇文章:string接口函数 2.4 vector的增删查改 push_back和pop_back 都是老朋友了,这里就不多说了 在介绍insert和erase之前 先来了解几个算法库的函数 2.41 find,swap和sort
这三个函数都在头文件:algorithm中 find函数:参数是一段迭代器区间 以及在此区间你需要查找的值 找到后返回这个值对应的迭代器位置 若找不到,则返回迭代器last find的使用:
vectorint vv{1,2,3,4,5,6,7,8,9};
auto pos find(vv.begin(),vv.end(),5);
cout*pos;注:使用auto是为了简写迭代器也可以用 vector int ::iterator替代 swap想必是大家的常客了 这里给它个面子,就不介绍它了 sort非常方便,它内部实现是快排 我们只需要传一个迭代器区间 就可以将整个区间排好序
sort的使用:
vectorint vv{5,7,3,9,6,4,1,2,8};
sort(vv.begin().vv.end());2.42 insert和erase 和string不同,vector的insert 的参数pos不是整型,而是迭代器 默认是在pos位置前插入一个数据
insert和find常常配合在一起使用
在整型5前面插入一个100:
vectorint vv{1,2,3,4,5,6,7,8,9};
auto pos find(vv.begin(),vv.end(),5);
vv.insert(pos,100);和string的erase不同,vector 的erase一次只删除一个数据 然而string如果使用缺省值就是 将全部数据删完
vector的erase甚至可以删除一段区间
删除顺序表中值为100的元素
vectorint vv{1,2,3,4,5,6,7,8,9,100};
auto pos find(vv.begin(),vv.end(),100);
vv.erase(pos);
//删除一个区间
vv.erase(vv.begin()2,vv.end()-2);2.43 随机访问operator[ ] vector中最喜欢用的是[ ] 它支持随机访问,是否方便
operator[]的使用:
vectorint vv{1,2,3,4,5,6,7,8,9};
for(int i0;ivv.size();i)
{coutvv[i] ;
}3. vector的模拟实现
首先要关注的是成员变量 vector是顺序表,所以和实现C语言 时的顺序表一样,至少有三个参数
指向一段空间的指针空间的有效大小空间的实际大小
由于vector的迭代器就是普通指针 所以成员变量的类型其实是迭代器
templateclass T
class vector
{
public:typedef T* iterator;private:iterator _start;iterator _finish;iterator _endof_storage;这里使用迭代器作为三个参数的类型 是因为:求vector的size和capacity时 可以直接使用finish-start 也就是指针相减求出长度 成员变量和空间的关系: 3.1 vector容量相关函数
上来首先要考虑的容量相关的函数:
sizecapacityemptyresizereverse
前三个十分简单:
size_t size() const
{return _finish - _start;
}size_t capacity() const
{return _endof_storage - _finish;
}bool empty() const
{return (size()0);
}3.11 reverse函数
reverse只会改变capacity的大小 并不会改变size的大小
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);for (size_t i 0; i sz; i){tmp[i] _start[i];}delete[] _start;}_start tmp;_finish _start sz;_end_of_storage _start n;}
}注:当n小于capacity时,不进行扩容 由于C内存管理的new 无法像C语言的realloc一样原地扩容 所以必须先开辟n个空间,再将数据 拷贝到新空间,且释放旧空间 3.12 resize函数
resize即会改变size大小 也会改变capacity大小 resize要分三种情况: n大于capacity时n大于size小于capacity时n小于size时 它们的解决方案分别是: 直接套用reversezhu 初始有效值不变,在此之后 初始化新的内容 直接将size缩小到n
void resize(size_t n, const T val T())
{if (n capacity()){reserve(n);}if (n size()){// 初始化填值while (_finish _start n){*_finish val;_finish;}}else{_finish _start n;}
}注:参数valT()使用了匿名对象 C将内置类型特殊处理过 int/char等等都被升级为了类 所以可以使用int()表示匿名对象
int tmp1 int();
int tmp2 int(10);int的缺省值为0 3.2 vector的构造函数
首先最简单的无参构造:
vector():_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{}紧接着是带参的构造函数 我们跟着STL库的风格走:
vector(size_t n, const T val T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{reserve(n);//开辟n个空间for (size_t i 0; i n; i){push_back(val);//给初始值赋值}
}最后是使用迭代器区间来构造 比如我想在顺序表中存放string类型:
string str(abcdefg);
vectorstring vv(str.begin(),str.end());此时在模板类中还应该有一个模板
template class InputIterator
vector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{while (first ! last){push_back(*first);first;}
}注:inputiterator取名是模仿STL的 你也可以取任一除了T的名字 3.3 vector的析构函数
vector的析构函数非常简单 只需要将空间释放 并且将各个指针置为空就行了
~vector()
{delete[] _start;_start _finish _end_of_storage nullptr;
}3.4 vector的拷贝构造函数
拷贝构造的实现有很多种写法 大家可以先自己尝试一下
vector(const vectorT v):_start(nullptr), _finish(nullptr), _endof_storage(nullptr){reserve(v.size());for (const auto e : v){push_back(e);}}4. 总结以及拓展
vector模拟实现的全部代码我将在 下一篇文章中分享给大家 可以发现:STL的神奇之处在于 它把所有接口函数都做了统一化处理 每一个容器的接口函数的使用都相似 但是内部实现被这种封装隐藏起来了 进一步又体现了C的三大特性:封装 并且C实现了所有容器通用的算法库 比如sort和find都只需要传迭代器 然而所有容器都会被迭代器封装 所以一份代码就能实现对不同容器的操作 拓展题目:
熟悉了vector的基本使用 可以尝试解决一下下面几个问题:
只出现一次的数字删除有序数组中的重复项数组中出现次数超过一半的数字 杨辉三角
留给大家当作小试牛刀了~ 下期预告:迭代器失效和深浅拷贝问题
