【玩转c++】vector讲解和模拟底层实现

本期主题：vector的讲解和模拟实现
博客主页：小峰同学
分享小编的在Linux中学习到的知识和遇到的问题
小编的能力有限，出现错误希望大家不吝赐

1. vector的介绍及使用

1.1vector的介绍

vector其实就是一个数组的模板 ，存放的数据可以改变而已。
使用：vector<存放的数据类型> 类名称

vector是表示可变大小数组的序列容器。
就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素 进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自 动处理。
与其它动态序列容器相比（deque, list and forward_list）， vector在访问元素的时候更加高效，在末 尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起list和forward_list 统一的迭代器和引用更好。

1.2vector的使用

1.2.1. 成员函数

1.2.2. 迭代器

这里和string几乎相同就不一一介绍了。

1.2.3.容量相关

capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。 这个问题经常会考察，不要固化的认为，vector增容都是2倍，具体增长多少是根据具体的需求定义 的。vs是PJ版本STL，g++是SGI版本STL。
reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问 题。
resize在开空间的同时还会进行初始化，影响size。

1.2.4.元素访问

注意：
at和[ ]的区别，at发生越界会抛异常，[ ]发生越界直接断言检查
断言检查只在debug版本下才会起作用。relesae版本不起作用。

1.2.5.元素修改

assign：赋值前会先把元数据清空

2. vector的模拟实现

2.1.常见错误

2.1.1. vector 迭代器失效问题

迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了 封装，比如：vector的迭代器就是原生态指针T* 。因此迭代器失效，实际就是迭代器底层对应指针所指向的 空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用经失效的迭代器， 程序可能会崩溃)。

#include <iostream>
using namespace std;
#include <vector>
int main()
{vector<int> v{1,2,3,4,5,6};auto it = v.begin();// 将有效元素个数增加到100个，多出的位置使用8填充，操作期间底层会扩容// v.resize(100, 8);// reserve的作用就是改变扩容大小但不改变有效元素个数，操作期间可能会引起底层容量改变// v.reserve(100);// 插入元素期间，可能会引起扩容，而导致原空间被释放// v.insert(v.begin(), 0);// v.push_back(8);// 给vector重新赋值，可能会引起底层容量改变v.assign(100, 8);/*出错原因：以上操作，都有可能会导致vector扩容，也就是说vector底层原理旧空间被释放掉，
而在打印时，it还使用的是释放之间的旧空间，在对it迭代器操作时，实际操作的是一块已经被释放的
空间，而引起代码运行时崩溃。解决方式：在以上操作完成之后，如果想要继续通过迭代器操作vector中的元素，只需给it重新
赋值即可。*/while(it != v.end()){cout<< *it << " " ;++it;}cout<<endl;return 0;
}

2.1.2. insert传进去的迭代器出了函数还能用吗？

int main()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);vector<int>::iterator it = find(v.begin(), v.end(), 4);v.insert(it, 100);cout << *it << endl;return 0;
}

大家觉得这个代码 有问题吗？

在vs2019上运行起来会报出访问异常的问题，这就是insert迭代器失效的问题。
但是在LInux下不会出现问题，因为底层的模拟实现，是的g++做不到这样的检查。但是有时候g++有时候也会出问题，所以统一认为迭代器失效了。

2.1.3. erase删除偶数的问题

先看代码

int main()
{zxf::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);zxf::vector<int>::iterator it = v.begin();while (it != v.end()){if (*it % 2 == 0){v.erase(it);}else{it++;}}for (auto i : v) {cout << i << endl;}return 0;
}

这个程序在vs2019下绝对报错，但是在Linux下一般只要控制得好不会报错。

注意erase有一个返回值，返回欲删除元素的下一个元素的迭代器。

所以一般要给it重新赋值。一般不使用删除位置的迭代器，要想使用就要更新it。

2.1.4. 用n个m去初始化的时候，vector<int>会出问题。

先看我们实现的代码:其中的两个构造函数。

vector(size_t n ,const T& val = T()):_start(nullptr),_finish(nullptr),_end_of_storagr(nullptr)
{reserve(n);while(n--){push_back(val);}
}template <class InputIterator>
vector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{while (first != last){push_back(*first);++first;}
}

假如我们现在，是一个vector<int>的数组，初始化的时候 ：vector<int> v(5,6) 。5 6是会被识别成int类型。
本意是想用5个6进行初始化的，但是我们发现它把他识别成为了迭代器初始化。
就会出现报错：非法访问的问题。

库里面的改进方法：

可以看到LInux中的g++（SGI版本的stl）使用的是重载多个vector（），但是最后都调用同一个函数。这样就避免了走模板的困扰，就很好的解决了这个问题。

2.1.5.深层次的拷贝问题。

观察代码

void reserve(size_t n){if (n > capacity()){size_t oldsize = size();iterator tmp = new T[n];if (_start){memmove(tmp, _start, sizeof(T) * oldsize);delete[] _start;}_finish = tmp + oldsize;_start = tmp;//注意这里的顺序，或者提前记录 oldsize的值。_end_of_storage = tmp + n;}}

分析是不是发现没有什么问题？
但是这个代码是不对的，为什么呢？reserve是扩容的意思，但是假设T是一个自定义类型。
比如T == vector<int> ,这个时候tmp开好空间，直接把原空间的值（指向vetor<int>指针)拷贝给tmp数组（vecto<vector<int>>,然后在delete原来的vector<vector<int>>,这个时候vector里面放的是一个自定义类型（vector<int>)，就会调用自定义类型的析构函数释放掉原空间，以及原空间内容指向的空间，这个时候tmp的内容指向的空间就被释放了，tmp里面的元素指向的空间被释放了，他就是存了一系列的野指针。就会出问题。

改进

void reserve(size_t n){if (n > capacity()){size_t oldsize = size();iterator tmp = new T[n];if (_start){
1·                    //memmove(tmp, _start, sizeof(T) * oldsize);for (size_t i = 0; i < oldsize; i++){tmp[i] = _start[i];}delete[] _start;}_finish = tmp + oldsize;_start = tmp;//注意这里的顺序，或者提前记录 oldsize的值。_end_of_storage = tmp + n;}}

这样的话直接调用赋值重载，就不会涉及到浅拷贝的问题。这样tmp里面元素vector<int>指向的空间就不同了，就很好的解决了这个问题，虽然这样写效率不高但是现在的水平只能这样写。

2.2.源码

直接上源码

vector.h

#pragma once#include<assert.h>
#include<iostream>using namespace std;namespace zxf
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;const_iterator begin()const{return _start;}    iterator begin(){return _start;}iterator end(){return _finish;}        const_iterator end()const{return _finish;}size_t size()const{//return (_finish - _start) / sizeof(T);return (_finish - _start);//注意这里对指针的正确理解}size_t capacity()const{return _end_of_storage - _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];}vector():_start(nullptr), _finish(nullptr), _end_of_storage(nullptr) {}~vector(){delete[] _start;_start = nullptr;_finish = nullptr;_end_of_storage = nullptr;}template<class Intput>vector(Intput frist, Intput last):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){while (frist < last){push_back(*frist);++frist;}}//拷贝构造vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){reserve(v.capacity());for (const auto& a : v)//注意这里要加引用{push_back(a);}//想一想为何要加引用。//}vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){vector<T> tmp(v.begin(), v.end());swap(tmp);}vector<T>& operator=(vector<T> v)//这种写法简单//如果v1 == v1 不太好//但是也不会出错{swap(v);return *this;}//vector<T>& operator=(const vector<T>& v)//{//    vector<T> tmp(v.begin(),v.end())//    swap(tmp);//    return *this;//}void reserve(size_t n){if (n > capacity()){size_t oldsize = size();iterator tmp = new T[n];if (_start){//memmove(tmp, _start, sizeof(T) * oldsize);for (size_t i = 0; i < oldsize; i++){tmp[i] = _start[i];}delete[] _start;}_finish = tmp + oldsize;_start = tmp;//注意这里的顺序，或者提前记录 oldsize的值。_end_of_storage = tmp + n;}}void push_back(const T& value){if (_end_of_storage ==  _finish){size_t newcapacity = _start == nullptr ? 4 : capacity() * 2;reserve(newcapacity);}*_finish = value;++_finish;}bool empty(){return _start == _finish;}void pop_back(){//注意判断是否为空，不能一直减，assert(!empty());--_finish;}void resize(size_t n, T value = T()){if (n > capacity()){reserve(n);}if (n < size()){_finish = _start + n;}else{while (size() != n){*_finish = value;++_finish;}}}iterator insert(iterator pos, const T& value){assert(pos <= _finish);assert(pos >= _start);size_t p = pos - _start;//注意这里迭代器失效的问题if (_finish == _end_of_storage){size_t  newcapacity = _start == nullptr ? 4 : capacity() * 2;reserve(newcapacity);}pos = _start + p;for (iterator i = _finish; i >= pos; i--){*(i + 1) = *i;}*pos = value;_finish++;return _start;}void insert(iterator pos, size_t n, const T& val){assert(pos <= _finish);assert(pos >= _start);size_t p = pos - _start;//注意也有迭代器失效问题if (_finish + n >= _end_of_storage){size_t  newcapacity = capacity() + n+2;reserve(newcapacity);}pos = _start + p;for (iterator i = _finish; i >= pos; i--){*(i + n) = *i;}int i = n;while (i--){*pos = val;pos++;}  _finish += n;}iterator erase(iterator pos){assert(pos <= _finish);assert(pos >= _start);if (_start != nullptr){for (iterator i = pos; i < _finish -1; i++){*i = *(i + 1);}}--_finish;return pos;//这里是为了个库里面保持一致}void swap(vector& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}void clear(){_finish = _start;}private:iterator _start;iterator _finish;iterator _end_of_storage;};}