网站建设与制作好学吗,响应的网站,公司网站建设 意义,wordpress模板双响目录 前言1. vector介绍及使用1.1vector的介绍1.2 vector的使用1.2.1 构造函数 1.2.2 vector对象遍历1.2.3 reserve和resize1.2.4 insert和erase 2. vector模拟实现2.1 vector迭代器失效问题2.2 模拟实现reserve函数浅拷贝问题2.3模拟实现源码2.3.1 vector.h2.3.2 test.cpp 前言… 目录 前言1. vector介绍及使用1.1vector的介绍1.2 vector的使用1.2.1 构造函数 1.2.2 vector对象遍历1.2.3 reserve和resize1.2.4 insert和erase 2. vector模拟实现2.1 vector迭代器失效问题2.2 模拟实现reserve函数浅拷贝问题2.3模拟实现源码2.3.1 vector.h2.3.2 test.cpp 前言 这篇文章我们来学习一下STL容器里的vector我们先来学习一下它的使用然后对vector进行模拟实现。 1. vector介绍及使用
1.1vector的介绍
vector文档介绍
vector是一个大小可以更改的数组序列容器。 其实这里可以简单认为vector就是之前数据结构学的顺序表。 1.2 vector的使用 vector提供的接口跟string是非常相似的所以经过前面string的学习再学习vector成本降低了很多。 下面我们来介绍一下常用接口。 1.2.1 构造函数 首先看第一个 这个是用来传空间配置器的我们可以认为这个就是无参的构造函数构造一个空的vector。 注意 vector是一个类模板类模板实例化只能显式实例化即需要在类模板名字后跟然后将实例化的类型放在中即可。 类模板不是真正的类其实例化的结果才是真正的类。 这个就是支持用n个val构造一个vector对象。 这个就是支持迭代器区间构造也不难理解我们来给大家演示一下 这个就是拷贝构造了 1.2.2 vector对象遍历 vector也重载了[]这里可以使用for循环遍历 也可以使用迭代器也就是支持范围for 1.2.3 reserve和resize
首先我们来看一下vector的扩容机制
#include iostream
#include vector
using namespace std;
int main()
{// 测试vector的默认扩容机制size_t sz;vectorint v;sz v.capacity();cout making v grow:\n;for (int i 0; i 100; i){v.push_back(i);if (sz ! v.capacity()){sz v.capacity();cout capacity changed: sz \n;}}return 0;
}这里g下是二倍扩 当我们知道需要多少空间直接用reserve把空间开好就可以减少频繁扩容的一个消耗。 确定知道需要用多少空间reserve可以缓解vector增容的代价缺陷问题。 我们再来看一下resize(): resize在开空间的同时还会进行初始化,当然如果传的n比size小那它还会删除多余的数据。 1.2.4 insert和erase 与string相比vector只支持我们去传迭代器和迭代器区间了 2. vector模拟实现
2.1 vector迭代器失效问题 会引起其底层空间改变的操作都有可能导致迭代器失效比如resize、reserve、insert、assign、push_back等。 出错原因 以上操作都有可能会导致vector扩容迭代器失效实际就是迭代器底层对应指针所指向的空间被销毁了而使用一块已经被释放的空间造成的后果是程序崩溃(即如果继续使用已经失效的迭代器程序可能会崩溃)。 这里我们举个简单的例子以下代码用于输出v1中所有偶数
int main()
{vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);v1.push_back(6);for (auto e : v1){cout e ;}cout endl;auto it v1.begin();while(it ! v1.end())//错误代码{if(*it % 2 0){v1.erase(it);}it;}// while (it ! v1.end())// {// if (*it % 2 0)// {// it v1.erase(it);// }// else// {// it;// }// }
}这里程序会报错出现段错误。实际上这里是因为是因为erase删除pos位置元素后pos位置之后的元素会往前搬移他没有接收返回值而是一味的进行操作导致程序越界奔溃。 2.2 模拟实现reserve函数浅拷贝问题 这里主要出现错误的原因就是内部使用了memcpy来拷贝数据。 memcpy是内存的二进制格式拷贝将一段内存空间中内容原封不动的拷贝到另外一段内存空间中如果拷贝的是内置类型的元素memcpy既高效又不会出错 但如果拷贝的是自定义类型元素并且 自定义类型元素中涉及到资源管理时就会出错因为memcpy的拷贝实际是浅拷贝 我们这里以vector string 为例 2.3模拟实现源码
2.3.1 vector.h
#includeiostream
#includeassert.h
using namespace std;namespace w
{templateclass Tclass vector{public: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;}vector(size_t n, const T val T()){resize(n, val);}vector(int n, const T val T()){resize(n, val);}// [first, last)templateclass InputIteratorvector(InputIterator first, InputIterator last){while (first ! last){push_back(*first);first;}}vector(){}vector(const vectorT v){_start new T[v.capacity()];//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();_endofstorage _start v.capacity();}void swap(vectorT v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}vectorT operator(vectorT v){swap(v);return *this;}~vector(){if (_start){delete[] _start;_start _finish _endofstorage nullptr;}}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;_endofstorage _start n;}}void resize(size_t n, const T val T()){if (n size()){_finish _start n;}else{reserve(n);while (_finish ! _start n){*_finish val;_finish;}}}void push_back(const T x){insert(end(), x);}void pop_back(){erase(--end());}size_t capacity() const{return _endofstorage - _start;}size_t size() const{return _finish - _start;}T operator[](size_t pos){assert(pos size());return _start[pos];}const T operator[](size_t pos) const{assert(pos size());return _start[pos];}iterator insert(iterator pos, const T x){assert(pos _start pos _finish);if (_finish _endofstorage){size_t len pos - _start;size_t newcapacity capacity() 0 ? 4 : capacity() * 2;reserve(newcapacity);// 解决pos迭代器失效问题pos _start len;}iterator end _finish - 1;while (end pos){*(end 1) *end;--end;}*pos x;_finish;return pos;}iterator erase(iterator pos){assert(pos _start pos _finish);iterator it pos 1;while (it ! _finish){*(it - 1) *it;it;}--_finish;return pos;}private:iterator _start nullptr;iterator _finish nullptr;iterator _endofstorage nullptr;};}2.3.2 test.cpp
#include vector.h
void test_vector1(){w:: vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);for (auto e : v1){cout e ;}coutendl;for (size_t i 0; i v1.size(); i){v1[i];}for (auto e : v1){cout e ;}cout endl;}void test_vector2(){w ::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(5);v1.push_back(5);v1.push_back(5);for (auto e : v1){cout e ;}cout endl;v1.insert(v1.begin(), 100);for (auto e : v1){cout e ;}cout endl;}int main()
{test_vector2();return 0;
}
