郑州中扬科技网站建设公司怎么样,仿一个展示型网站多少钱,网站重定向代码,淮滨网站建设公司这里写目录标题一、vector的介绍及使用1. vector的介绍2. 构造函数3. 遍历方式4. 容量操作及空间增长问题5. 增删查改6. vector二维数组二、vector的模拟实现1. 构造函数2. 迭代器和基本接口3. reserve和resize4. push_back和pop_back5. insert和erase5. 迭代器失效问题5. 浅拷…
这里写目录标题一、vector的介绍及使用1. vector的介绍2. 构造函数3. 遍历方式4. 容量操作及空间增长问题5. 增删查改6. vector二维数组二、vector的模拟实现1. 构造函数2. 迭代器和基本接口3. reserve和resize4. push_back和pop_back5. insert和erase5. 迭代器失效问题5. 浅拷贝问题三、vector模拟实现整体源码一、vector的介绍及使用
1. vector的介绍 vector是表示可变大小数组的序列容器。就像数组一样vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问和数组一样高效。但是又不像数组它的大小是可以动态改变的而且它的大小会被容器自动处理。本质讲vector使用动态分配数组来存储它的元素。当新元素插入时候这个数组需要被重新分配大小为了增加存储空间。其做法是分配一个新的数组然后将全部元素移到这个数组。 就时间而言这是一个相对代价高的任务因为每当一个新的元素加入到容器的时候vector并不会每次都重新分配大小。vector分配空间策略vector会分配一些额外的空间以适应可能的增长因为存储空间比实际需要的存储空间更大。 不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何重新分配都应该是对数增长的间隔大小以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。因此vector占用了更多的存储空间为了获得管理存储空间的能力并且以一种有效的方式动态增长。与其它动态序列容器相比deque, list and forward_list vector在访问元素的时候更加高效在末尾添加和删除元素相对高效。 对于其它不在末尾的删除和插入操作效率更低。比起list和forward_list统一的迭代器和引用更好。 2. 构造函数
vector学习时一定要学会查看文档vector文档介绍vector在实际中非常的重要在实际中我们熟悉常见的接口就可以。当然我们使用vector之前需要包头文件#includevector。
下面我们来看一下vector的构造函数 因为在vector中是重载了[]访问运算符的所以我们可以直接使用[]访问运算符来访问vector中的元素。下面我们直接来举几个例子来看一下构造函数的用法 这里我们可以看到和string不同的是这里的capacity表示的就是所开辟的空间中最多能存储的元素的个数但在string中则需要多开辟一个空间为’\0’预留位置。
迭代器区间构造本质上是一个函数模板所以我们可以用任意类来构造vector对象。 3. 遍历方式 [ ]遍历 int main()
{vectorint v2(5, 0);for (int i 0; i v2.size(); i)cout v2[i] ;cout endl;return 0;
}当然了因为[ ]重载了const和非const两个版本所以[ ]既可以对const对象使用又可以对非const对象使用。 使用迭代器遍历 vector和string一样也有反向迭代器rbegin和rend他们表示获取最后一个数据位置的reverse_iterator和第一个数据前一个位置的reverse_iterator。
int main()
{vectorint v2;v2.push_back(1);v2.push_back(2);v2.push_back(3);v2.push_back(4);v2.push_back(5);vectorint::iterator it v2.begin();while (it ! v2.end()){cout *it ;}cout endl;vectorint::reverse_iterator rit v2.rbegin();while (rit ! v2.rend()){cout *rit ;}cout endl;return 0;
}使用范围for遍历
int main()
{vectorint v2;v2.push_back(1);v2.push_back(2);v2.push_back(3);v2.push_back(4);v2.push_back(5);for (auto e : v2)cout e ;cout endl;return 0;
}当然范围for遍历并不是什么高深的语法它的本质还是被替换成了迭代器进行遍历。 4. 容量操作及空间增长问题 容量操作 这是vector中的容量操作的几个api接口其中第二个max_size和shrink_to_fit是我们在之前学习string的时候没有见过的接口其中max_size是返回这个容器中可以容纳的最多的元素的个数这个接口我们一般都不会用。shrink_to_fit是让我们容器的容量减少到容器中元素的个数。因为缩容所消耗的代价是比较大的。一般都不会轻易缩容所以这个接口我们一般也不会用。 最重要的两个接口还是reserve和rsizereserve只用于扩容不会改变size的大小但是resize不仅会扩容他还会改变size的个数。 空间增长问题
对于不同的STL版本他的扩容机制也是不同的。我们知道vs下和g分别用的是不同的STL版本下面我们分别来看一下他们的扩容机制有什么不同。
//测试vector的默认扩容机制
void TestVectorExpand()
{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;}}
}vs下的扩容机制 g下的扩容机制 这里我们需要注意几点 capacity的代码在vs和g下分别运行会发现vs下capacity是按1.5倍增长的g是按2倍增长的。这个问题经常会考察不要固化的认为vector增容都是2倍具体增长多少是根据具体的需求定义的。vs是PJ版本STLg是SGI版本STLreserve只负责开辟空间如果确定知道需要用多少空间reserve可以缓解vector增容的代价缺陷问 题。resize在开空间的同时还会进行初始化影响size 5. 增删查改 push_back和push_back这两个接口我们在string中见过表示的是尾插和尾删这里我们不再细说。
find和swap
注意 这里的find函数是算法库里的一个函数而并非vector提供的接口。 这里需要提供一段迭代器区间然后在后面跟上我们需要查找的元素如果查找成功就返回他的迭代器如果查找不成功就返回end迭代器位置。 既然算法库里面已经有swap这个接口了为什么在vector中还要再次设计一个呢 其实这是因为算法库中的swap函数具有深拷贝的问题深拷贝的代价是很大的对于vector这样的类来说直接使用算法库里面的swap函数的拷贝代价太大所以vector自己提供了一个自己的swap函数其实vector中的swap函数的内部也是用了算法库中的swap。 insert和erase
这里的insert和erase和string也有所不同string中的这两个接口在操作完成后会返回对象本身但是在vector中则是操作完成后返回要插入或者删除的那个位置的迭代器。当然了不光光是vectorSTL中的所有容器的插入和删除接口都是这样设计的。 基本用法如下 这里我们需要注意一点是当我们删除一个元素的时候删除位置的范围是【begin()end()),但是当我们插入一个元素的时候插入位置的范围是【begin()end()】。 当然了这里存在一种迭代器失效的问题下面我们在模拟实现的时候再来细说。 6. vector二维数组
int main()
{//设置二维数组的行数和列数int row 5, col 5;//创建二维数组并初始化为全0vectorvectorint vv(row, vectorint(col, 0));//获取二维数组的行数int size_row vv.size();//获取二维数组的列数int size_col vv[0].size();//插入列元素vv[0].push_back(100);//插入行vv.push_back(vectorint(5, 1));//遍历二维数组for (size_t i 0; i vv.size(); i){for (size_t j 0; j vv[i].size(); j){cout vv[i][j] ;}cout endl;}return 0;
}二、vector的模拟实现 当我们在模拟实现vector容器之前需要先来参考一下源码主要是为了整体看一下库里面vector的底层实现逻辑。 那么我们应该如何参考源码呢让我们完全看懂源码是不可能的所以我们应该抓住重点核心来看最重要的就是这个类的成员变量和核心的成员函数下面我们来看一下我们在模拟vector之前需要关注的源码中的地方。
template class T, class Alloc alloc
class vector
{
public:typedef T value_type;typedef value_type* iterator;typedef const value_type* const_iterator;//...size_type size() const { return size_type(end() - begin()); }size_type max_size() const { return size_type(-1) / sizeof(T); }size_type capacity() const { return size_type(end_of_storage - begin()); }iterator begin() {return start;}iterator end() {return finish;}
private:iterator start;iterator finish;iterator end_of_storage;
};通过这一部分的源码我们可以看到vector中的三个成员变量是由三个迭代器实现的在这里迭代器是一个原生指针。然后我们根据源码中的size()和capacity()等函数。可以推断出这三个指针所代表的意义 start指向第一个元素的位置finish指向容器中有效元素中最后一个元素后面的位置end_of_storage指向容器能容纳最大容量之后的位置。其实和我们在C数据结构阶段实现的顺序表没有什么本质的区别不过是使用了三个指针来维护所开辟的空间罢了。 1. 构造函数 默认无参构造
//无参构造
vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr)
{}n个val构造
vector(size_t n, const T val T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{reserve(n);for (int i 0; i n; i){push_back(val);}
}我们在写构造函数的时候为了防止野指针的出现需要在初始化列表中将三个指针全部初始化为空。为了减少频繁扩容所带来的消耗可以先调用reserve函数预先开辟一块空间然后依次将要初始化的对象进行尾插。这里我们可以要初始化的值val预先设定缺省参数这里我们不能将缺省值设置为0因为要初始化的对象可能是int类型、double类型、还有可能是一个自定义类型所以这里我们可以将缺省值给定为一个T类型的匿名对象。
这里我们还需要注意的是引用会延长匿名对象的生命周期到引用对象域结束因为这里的val就是匿名对象的别名如果匿名对象在当前行就之后就销毁的话val也会被销毁。同时因为匿名对象具有常性所以我们需要用const来修饰val。 迭代器区间构造
template class InputIterator
vector(InputIterator first, InputIterator end):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr)
{while (first ! end){push_back(*first);first;}
}这里我们提供一个迭代器模板可以提供任意类型的迭代器。 在提供以上的函数接口之后如果我们尝试构造一个内容为5个10的对象时候这里会出现间接寻址的错误这是因为编译器在进行模板实例化以及函数参数匹配时会调用最匹配的那一个函数当我们将T实例化为int之后由于两个参数都是int所以迭代器构造函数会直接将Inputlterator实例化为int但是如果n个val构造来说不仅需要将T实例化为int还需要将第一个参数隐式转换为size_t所以编译器会优先调用迭代器区间构造函数直接对int类型解引用的话就会报错。
为了防止这种情况发生我们可以采取和STL中一样的解决方式——重载一份第一个参数为int的构造函数。
vector(int n, const T val T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{reserve(n);for (int i 0; i n; i){push_back(val);}
}拷贝构造
vector(const vectorT v):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{_start new T[v.capacity()];memcpy(_start, v._start, v.size() * sizeof(T));//——会导致浅拷贝问题_finish _start v.size();_end_of_storage _start v.capacity();
}2. 迭代器和基本接口 迭代器的实现
为了能够使用范围for循环和其他别的功能这里我们来实现一下vector的迭代器同时为了能够对const对象也使用迭代器这里我们还需要设计一份const版本的迭代器。
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;
}基本接口的实现
size_t size() const
{return _finish - _start;
}
size_t capacity() const
{return _end_of_storage - _start;
}
size_t empty() const
{return _start _finish;
}
void clear()
{_finish _start;
}
//析构函数
~vector()
{delete[] _start;_start _finish _end_of_storage nullptr;
}T operator[](size_t pos)
{assert(pos size());return _start[pos];
}
const T operator[](size_t pos) const
{assert(pos size());return _start[pos];
}由于以上的接口比较简单这里我们就不再做过多的解释。 3. reserve和resize reserve的实现
void reserve(size_t n)
{if (n capacity()){int sz size();T* tmp new T[n];if (_start){memcpy(tmp, _start, size() * sizeof(T));delete[] _start;}_start tmp;_finish _start sz;_end_of_storage _start n;}
}如果我们需要扩的容量的大小小于原来的容量时我们默认不执行扩容操作。这里我们需要先定义一个临时变量sz将扩容之前的元素个数保存下来因为扩容之后给finish赋值时start已经指向了新的空间但是finishi还未改变所以直接使用size()会出现问题当然了在这个接口里面存在着一个严重的问题我们到后面会指正。 resize的实现
void resize(size_t n,T val T())
{if (n size()){//删除数据_finish _start n;}else{if (n capacity()){reserve(n);}while (_finish ! _start n){*_finish val;_finish;}}
}这里我们和前面的构造函数一样给一个匿名对象的缺省值如果需要扩的容量比原来的容量小时 我们只需要将容器中的有效的数据个数size()减少即可。否则的话如果n的个数大于原来的容量时我们可以先使用reserve函数将原来的空间扩大然后再依次添加到finish之后即可。直到finish的大小等于capacity的大小。 4. push_back和pop_back
//push_back的实现
void push_back(const T x)
{if (_finish _end_of_storage){reserve(capacity() 0 ? 4 : capacity() * 2);}*_finish x;_finish;
}//pop_back的实现
void pop_back()
{assert(!empty());_finish--;
}这两个接口的实现就非常简单了push_back的实现如果finish等于capacity容量的大小我们则需要先调用reserve函数进行扩容。当然在这里我们判断capacity的时候需要特殊处理一下因为如果第一次创建的未初始化的对象的capacity是0时直接调用reverse(capacity)会出现问题。对于pop_back的实现我们还需要先实现一个判空操作的函数。 5. insert和erase insert
iterator insert(iterator pos, const T val)
{assert(pos _start pos _finish);if (_finish _end_of_storage){reserve(capacity() 0 ? 4 : capacity() * 2);}iterator end _finish - 1;while (end pos){*(end 1) *end;end--;}*pos val;_finish;return pos;
}这里的实现逻辑也很简单先判断要插入的位置是否符合规范在判断是否需要扩容最后我们重后往前挪动数据即可。当然最后别忘了finish需要。 erase
iterator erase(iterator pos)
{assert(pos _start pos _finish);iterator end pos 1;while (end _finish){*(end - 1) *end;end;}_finish--;return pos;
}这里我们首先需要注意的是pos位置不能等于finish因为finish是最后一个有效元素的后一个位置重前往后挪动数据。最后记得finish–。 5. 迭代器失效问题 野指针问题 这里我们可以看到当我们插入一个元素后再次打印的时候就会出现问题其实本质上还是我们的insert函数写的有问题。 这里我们修改一下insert函数当需要扩容的时候先使用一个变量记录一下pos位置相对于第一个元素的位置再扩容之后更新一下pos指针的位置。这样第一种迭代器失效的问题就得到解决了。
iterator insert(iterator pos, const T val)
{assert(pos _start pos _finish);if (_finish _end_of_storage){int sz pos - _start;reserve(capacity() 0 ? 4 : capacity() * 2);pos _start sz;}iterator end _finish - 1;while (end pos){*(end 1) *end;end--;}*pos val;_finish;return pos;
}扩容之后pos位置的迭代器失效 这里我们可以看到在我们将某个位置插入一个数字后迭代器可能会失效因为是传值传递所以insert之后pos的地址可能已经发生改变了所以insert之后默认pos迭代器失效了的因为不知道哪一次会进行扩容操作。所以insert之后的我们需要用pos接受一下就可以解决这种问题。
vectorint v2;
v2.push_back(1);
v2.push_back(2);
v2.push_back(3);
v2.push_back(4);func(v2);
auto pos find(v2.begin(), v2.end(), 3);
if (pos ! v2.end())
{pos v2.insert(pos, 100);
}
(*pos);
func(v2);erase之后默认迭代器失效
其实不仅仅是inserterase之后迭代器也会失效下面我们来看一下erase之后迭代器失效的问题这里我们先来举三个例子——删除一个序列中所有的偶数。 为什么同样的代码当数据不同时会出现截然不同的结果呢 第一份代码能够运行出正确的结果完全是一个偶然。可以看到第二份代码由于删除元素后 pos 不再指向原位置而是指向下一个位置所以 erase 之后会导致一个元素被跳过导致部分偶数没有被删除但好在末尾是奇数所以程序能够正常运行。但是最后一份代码就没那么好运了由于最后一个元素是偶数所以 erase 之后 pos 直接指向了 _finish 的下一个位置循环终止条件失效发生越界。 所以我们统一认为 insert 和 erase 之后迭代器失效必须更新后才能再次使用。
那么正确的做法就是当每次插入或者删除数据后都是用pos来接受一下。更新一下pos位置的数据如果没有插入或者删除数据则直接pos即可。 auto it2 v3.begin();while (it2 ! v3.end()){if (*it2 % 2 0){it2 v3.erase(it2);}else{it2;}}for (auto e : v3){cout e ;}cout endl;5. 浅拷贝问题 拷贝构造问题
//拷贝构造
vector(const vectorT v):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{_start new T[v.capacity()];memcpy(_start, v._start, v.size() * sizeof(T));//——会导致浅拷贝问题_finish _start v.size();_end_of_storage _start v.capacity();
}这份代码在我们看来并没有什么问题但其实它存在一个隐藏的问题当我们实例化的对象是内置类型时并不会发生浅拷贝但是如果我们实例化的对象是自定义类型时特别是自定义类型的对象中有资源分配的时候这份代码就会导致严重的问题。 当我们的vector中的元素是string类型时直接这样写就会导致浅拷贝问题这里我们来看一下原因。 在这里我们确实是开辟了一块新的空间同时也将原来对象中的数据拷贝到了新的空间中但是由于这个对象是一个string字符串类型直接使用memcpy进行拷贝是按照字节进行了拷贝也就是说两个对象中的vector中的string中的_str同时指向了一块空间所以最后调用自定义类型的析构函数时同一块空间会被析构两次。最后程序奔溃。
正确的写法
vector(const vectorT v):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{_start new T[v.capacity()];for (size_t i 0; i v.size(); i){_start[i] v._start[i];}_finish _start v.size();_end_of_storage _start v.capacity();
}reserve问题
//reserve扩容
void reserve(size_t n)
{if (n capacity()){int sz size();T* tmp new T[n];if (_start){memcpy(tmp, _start, size() * sizeof(T));delete[] _start;}_start tmp;_finish _start sz;_end_of_storage _start n;}
}这份代码和上面的代码的原因大同小异也是因为memcpy会带来浅拷贝问题下面我们来看一个例子当我们大量插入元素的时候会导致扩容的出现那么扩容又会带来什么样的问题呢 当在push_back内部调用 reserve 函数进行扩容时扩容时我们虽然进行了深拷贝但是空间里面的内容我们是使用 memcpy 按字节拷贝过来的这就导致原来的 v 里面的 string 元素和临时空间里面的string元素指向的是同一块空间。所以当拷贝完数据就会delete掉原来的空间由于二者指向的是同一块空间所以现在v中的string元素指向的是一块已经被释放掉的空间当最后出了作用域调用析构的时候就会出现问题。
正确的写法
void reserve(size_t n)
{if (n capacity()){int sz size();T* tmp new T[n];if (_start){for (size_t i 0; i sz; i){tmp[i] _start[i];}delete[] _start;}_start tmp;_finish _start sz;_end_of_storage _start n;}
}赋值运算符重载的问题
如果我们不重载赋值运算符使用vector中的元素是vector类型时这里还是会出现浅拷贝问题因为库中的string类重载了所以直接赋值进行的是深拷贝这里我们需要重载一下这样无论我们的vector中存储的是哪一种自定义类型都可以进行深拷贝了。
vectorT operator(const vectorT v)
{vectorT tmp(v);swap(tmp);return *this;
}三、vector模拟实现整体源码
namespace cjl
{template class 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()// :_start(nullptr)// ,_finish(nullptr)// ,_end_of_storage(nullptr)//{}构造函数//vector(size_t n, const T val T())// :_start(nullptr)// ,_finish(nullptr)// ,_end_of_storage(nullptr)//{// reserve(n);// for (int i 0; i n; i)// {// push_back(val);// }//}//构造函数的——现代写法(在成员变量声明的时候给缺省值)//无参构造vector(){}//构造函数vector(size_t n, const T val T()){reserve(n);for (int i 0; i n; i){push_back(val);}}vector(int n, const T val T()){reserve(n);for (int i 0; i n; i){push_back(val);}}//拷贝构造vector(const vectorT v){_start new T[v.capacity()];for (size_t i 0; i v.size(); i){_start[i] v._start[i];}_finish _start v.size();_end_of_storage _start v.capacity();}//迭代器区间构造template class InputIterator vector(InputIterator first, InputIterator end){while (first ! end){push_back(*first);first;}}//resize的实现void resize(size_t n,T val T()){if (n size()){//删除数据_finish _start n;}else{if (n capacity()){reserve(n);}while (_finish ! _start n){*_finish val;_finish;}}}//reserve的实现void reserve(size_t n){if (n capacity()){int sz size();T* tmp new T[n];if (_start){for (size_t i 0; i sz; i){tmp[i] _start[i];}delete[] _start;}_start tmp;_finish _start sz;_end_of_storage _start n;}}//push_back的实现void push_back(const T x){if (_finish _end_of_storage){reserve(capacity() 0 ? 4 : capacity() * 2);}*_finish x;_finish;}//pop_back的实现void pop_back(){assert(!empty());_finish--;}//insert的实现iterator insert(iterator pos, const T val){assert(pos _start pos _finish);if (_finish _end_of_storage){int sz pos - _start;reserve(capacity() 0 ? 4 : capacity() * 2);pos _start sz;}iterator end _finish - 1;while (end pos){*(end 1) *end;end--;}*pos val;_finish;return pos;}//erase的实现iterator erase(iterator pos){assert(pos _start pos _finish);iterator end pos 1;while (end _finish){*(end - 1) *end;end;}_finish--;return pos;}//重载[]T operator[](size_t pos){assert(pos size());return _start[pos];}const T operator[](size_t pos) const{assert(pos size());return _start[pos];}//重载运算符vectorT operator(const vectorT v){vectorT tmp(v);swap(tmp);return *this;}//swap函数的实现void swap(vectorT v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}size_t size() const{return _finish - _start;}size_t capacity() const{return _end_of_storage - _start;}size_t empty() const{return _start _finish;}void clear(){_finish _start;}//析构函数~vector(){delete[] _start;_start _finish _end_of_storage nullptr;}private:iterator _start nullptr;iterator _finish nullptr;iterator _end_of_storage nullptr;};
}
