做网站公司简介模版,建设公司属于工业企业吗,100件智能创意产品设计,网站关键词百度没有收录#x1f44d;作者主页#xff1a;进击的1 #x1f929; 专栏链接#xff1a;【1的C初阶】 文章目录 一#xff0c;什么是vector?二#xff0c;构造与析构三#xff0c;vector迭代器的实现四#xff0c;vector部分重要接口的实现 一#xff0c;什么是vector?
vector… 作者主页进击的1 专栏链接【1的C初阶】 文章目录 一什么是vector?二构造与析构三vector迭代器的实现四vector部分重要接口的实现 一什么是vector?
vector是一种表示大小可变数组的容器。其本质就是动态数组与我们前面写过的顺序表是大同小异的。与其他动态序列容器相比vector的随机访问更加高效。但是其插入与删除由于需要移动数据的原因就显得效率较低。接下来我们将从其基本构成各接口的实现原理以及易发生的问题等方面进行vector的学习
二构造与析构
与string不同的是string一定是字符串,而vector中却可以存储多种类型的数据。这是模板就起了很大的作用。我们暂且将其数据类型叫做T。 vector采用的数据结构非常简单线性连续空间它以两个迭代器start,finish分别指向已经被使用了的空间。以end_of_storage来指向整块空间的尾端。 因此其构造函数如下
vector():_start(nullptr),_finish(nullptr),end_of_storage(nullptr){}讲完了构造函数我们再来讲讲拷贝构造。 先来传统写法的构造函数。 vector(const vectorT v){//深拷贝_start new T[v.capacity()];//弊端当有vectorvectorT这样的结构时vectorT进行的是浅拷贝。// //memcpy(_start, v._start, sizeof(T) * v.size());// //改for (size_t i 0; i v.size(); i){_start[i] v._start[i];}_finish _start v.size();end_of_storage _start v.capacity();}这里需要注意的就是我们在注释中提到的当vector中存储的数据是自定义类型涉及到空间时如果仅仅使用memcpy则将会出现两对象指向同一块空间。导致同一块空间被析构两次就会报错。 在说明解决方法前我们再补充一段代码 void swap(vectorT tmp){std::swap(_start, tmp._start);std::swap(_finish, tmp._finish);std::swap(end_of_storage, tmp.end_of_storage);}
//赋值重载
vectorT operator( vectorT v)//在传参时就进行了深拷贝{swap(v);return *this;}有了上述补充代码我们就可以解决出现的问题了。 解决办法就是让vector中存储的数据也进行深拷贝便捷的方法就是利用遍历其自己的赋值重载自定义类型。这样每个vector中的数据自定义类型都经过深拷贝就不会发生同一空间被析构两次的情况。 我们再来学一种用迭代器进行初始化的构造构造。
template class InputIteratorvector(InputIterator first, InputIterator last):_start(nullptr),_finish(nullptr),end_of_storage(nullptr){while (first ! last){push_back(*first);first;}}这里的迭代器也是使用了模板使其能够用各种类型的迭代器进行初始化。
在上面我们讲述了拷贝构造的传统写法接下来我们在学习一种现代写法。
vector(const vectorT v):_start(nullptr),_finish(nullptr),end_of_storage(nullptr){vectorT tmp(v.begin(), v.end());swap(tmp);}其先是利用迭代器初始化构造出一个临时对象。然后将临时对象内的三个成员交换由于其三个成员类型为迭代器本质为T*因此交换就是原来tmp对象的空间由*this维护*this原来的空间则交给了tmp维护并且tmp是在函数内定义的因此出了此函数其生命周期结束进行析构。**要注意的是在进行交换前this对象要进行初始化若不对其初始化this中的成员是野指针释放野指针指向的空间是错误的。) 最后我们来讲一讲析构的实现----超简单的 直接上代码 ~vector(){delete[] _start;_start nullptr;_finish nullptr;end_of_storage nullptr;}三vector迭代器的实现
在第二小节我们就提到过其迭代器的本质为T*指针。 其迭代器主要作用就是进行遍历。 演示如下
void test4(){vectorint v;v.push_back(1);v.push_back(1);v.push_back(1);v.push_back(1);vectorint::iterator it v.begin();while (it! v.end()){cout (*it) endl;it;}}除了上述遍历方法还有一种范围for的遍历方法其底层的实现就是用的迭代器。演示如下
void test4(){vectorint v;v.push_back(1);v.push_back(1);v.push_back(1);v.push_back(1);for (auto e : v){cout e ;}cout endl;}四vector部分重要接口的实现
reserve的实现
void reserve(size_t n){size_t sz size();if (n capacity()){iterator 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;end_of_storage _start n;}}在文章【1的C初阶】之内存管理中我们有说过newdelete与malloc,free等的一个区别就是前者能够自动调用构造与析构函数因此我们在申请空间或者是扩容时选择用new。当用new进行间接的扩容时就涉及到了数据的拷贝解决方法与拷贝构造相同。
resize的实现
void resize(size_t n, T val T()){if (n capacity()){reserve(n);}if (n size() ){while(_finish_startn){*_finish val;_finish;}}else{_finish _start n;}}resize是调整其容器的大小当其大小大于开辟空间的大小时就进行扩容并且其还具有初始的功能。
insert实现
iterator insert(iterator pos, T val){size_t len pos - _start;assert(pos begin() pos end());//扩容if (end_of_storage _finish){reserve(capacity() 0 ? 4 : capacity() * 2);}//更新pospos _start len;//移动数据iterator end _finish-1;while ( end pos){*(end 1) *end;end--;}*pos val;_finish;return pos;}insert是将数据插入到pos位置首先就要判断pos是否合法然后要判断空间大小是否满足。**这里要注意的是当扩容后pos就会失效因为pos原来指向的空间已经不是我们要的空间了因此要更新pos。**在插入时由于是连续的空间因此要进行数据的移动。返回插入位置的迭代器。
erase的实现
iterator erase(iterator pos){//不考虑缩容//移动数据assert(pos _start pos _finish);iterator begin pos;while (begin _finish){*begin *(begin 1);begin;}_finish--;return pos;}
在有些编译器下会涉及到缩容因此与insert一样会面临迭代器失效的问题因此要更新pos,但我们的实现不考虑缩容的情况。erase原理与insert相似都要进行数据的挪动。
