【C++】STL学习——vector模拟实现

本文主要是介绍【C++】STL学习——vector模拟实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

vector介绍

vector是表示可变大小数组的序列容器，是STL中的容器之一；其底层结构为可扩容的数组，所以vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。vector与其它动态序列容器相比（deque, list and forward_list）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。具体结构和使用方法可查阅相关文档进行了解vector学习参考文档

vector函数接口总览

namespace djs
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;//默认成员函数vector();                                           //默认构造函数vector(size_t n, const T& val=T());                 //构造函数，构造n个valtemplate<class InputIterator>vector(InputIterator first, InputIterator last);    //迭代器区间构造函数vector(const vector<T>& v);                         //拷贝构造函数vector<T>& operator=(const vector<T>& v);           //赋值运算符重载函数~vector();                                          //析构函数//迭代器iterator begin();iterator end();const_iterator begin()const;const_iterator end()const;//容量相关size_t size() const;size_t capacity() const;bool empty() const;void reserve(size_t n);void resize(size_t n, const T& val = T())//访问相关T& operator[] (size_t n);const T& operator[] (size_t n) const;//修改相关iterator insert(iterator position, const T& val);template <class InputIterator>void insert(iterator position, InputIterator first, InputIterator last);void push_back (const T& val);iterator erase (iterator position);void pop_back();void clear();void swap (vector& x);private:iterator _start;//开始iterator _finish;//数据个数iterator _end_of_storage;//容量大小};
}

还是一样，为了不与库的vector冲突，将其放在自己的命名空间里。

结构介绍

vector作为可变大小数组的序列容器，可以存各种类型的数据；在C语言模拟实现顺序表这一数据结构时，我们可以利用typedef重命名数据类型达到一键替换所要存放的数据类型的效果，但是无法做到使用同一份代码同时存储两种数据结构的效果，而C++中的模板很好解决了这个问题，模板是 STL 的基础支撑。 模板介绍。
所以vector是一个类模板，可以存储指定类型的数据。我们参考SGI版的STL中vector的源码发现，vector是用三个指针来维护存储的数据的：

成员

private：iterator _start;//开始iterator _finish;//数据个数iterator _end_of_storage;//容量大小

注意：

• _finish指向的是最后一个数据的下一位，如上图所示。

实现文件介绍：
上一篇string的模拟实现中，采用了声明定义分离的方式实现；但由于vector是类模板，模板是不建议声明定义分离实现的，容易导致链接问题。SGI版的STL中声明和定义也都是放在头文件中的。

所以此次vector的模拟实现使用两个文件实现
vector.h：函数的声明和实现。
test.cpp：测试各函数。

默认成员函数

对于一些不认识的类型可以对着文档的成员类型表查看其typedef前的具体类型。

const allocator_type& alloc = allocator_type()//空间配置器，直接忽略就好。

库里实现了三个构造，一个拷贝构造函数；三个构造分别为：

1. 默认构造
2. 构造n个值为val的构造函数
3. 迭代器区间构造
   

构造函数1

默认构造不写使用编译器自动生成的也行，写的话如下：将三个指针置为nullptr即可。

	vector():_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){}

构造函数2

构造n个值为val的对象。
思路也很简单，在堆区开辟一段空间，然后将val存放进去。需要注意的是参数中const T& val = T()的使用，具体请到类和对象篇的匿名对象查看；使用匿名对象是因为不知道传入的值val的T具体是什么类型，所以使用内置构造将其置为0(T为int时)

		vector(size_t n, const T& val = T())//类型转化int -> size_t{size_t endofstorage = n * 2;_start = new T[endofstorage];for (int i = 0; i < n; i++){_start[i] = val;}_finish = _start + n;//更新位置_end_of_storage = _start + endofstorage;//更新容量}

构造函数3

迭代器区间构造：正如其名，该构造函数可以用一段区间来构造。该区间范围遵从迭代器使用的范围[左闭右开)，如：使用一个数组来构造。

    int arr[] = { 1,2,3,4,5,6,7,8,9 };vector<int>v2(arr, arr+sizeof(arr) / sizeof(int));

在类中也还是可以继续使用模板的，迭代器区间构造就是一个函数模板；实现起来也简单，先计算好构造的区间大小，再去堆区开辟对应的大小，用_finish来将元素添加进去，最后更新一下容量_end_of_storage。

		template<class InputIterator>vector(InputIterator first, InputIterator last){size_t endofstorage = last - first;_start = new T[endofstorage];_finish = _start;//让_finish为尾，一直往后走while (first != last){*_finish = *first;_finish++;first++;//更新位置}_end_of_storage = _start + endofstorage;//更新容量}

需要注意的是，由于构造函数2与3的存在，需要再添加一个第一个参数为int类型的构造函数；因为当我们想要用构造函数2，构造n个值为val的对象时（如下面v3）而构造函数2的参数为size_t类型，编译器会自动发生类型转化；但是有了迭代器区间后，v3的构造会更加匹配迭代器区间构造，对int解引用，导致非法的间接寻址；

解决办法就是添加一个类型更为匹配的int类型的构造函数

		//由于有迭代器区间构造，构造(10,6)这种就会匹配到区间构造，造成非法寻址vector(int n, const T& val = T())//加个整型的构造{size_t endofstorage = n * 2;_start = new T[endofstorage];for (int i = 0; i < n; i++){_start[i] = val;//push_back(val);}_finish = _start + n;//更新位置_end_of_storage = _start + endofstorage;//更新容量}

经典的深浅拷贝

拷贝构造始终都是那一套，但这里的关键点还是之前提过的深浅拷贝问题；实现拷贝构造的时候可能会贪方便，使用memcpy这个函数来实现，对于类中不涉及资源管理的使用memcpy进行拷贝那是没问题的，但是对于涉及资源管理的类再去使memcpy那就会出大麻烦，原因就是memcpy的拷贝是值拷贝，只会无脑的将内容ctrl c，ctrl v，也就是浅拷贝；而我们不写，使用编译器的拷贝构造也是浅拷贝，效果是一样的，接下来再次深入探讨深浅拷贝的问题。

使用编译器默认生成的拷贝构造就会引发以下问题，根本原因就是对同一块空间进行重复的释放，对一个非空指针调用delete[]两次（或更多次），那么程序将表现出未定义行为，这通常会导致程序崩溃或数据损坏。

• 对空指针释放是不会有问题的，但是对一个非空指针调用delete[]两次或更多就会出错。
  
  通过监视窗口看到v2完完全全就是v1的副本

当对v1进行释放后，v2还没释放，但是v2的内容已经被释放了，因为v2是v1是副本，那么此时再对v2析构，就对造成对已释放的空间再次释放，导致程序崩溃。

浅拷贝如下图，v1，v2指向同一块内容。析构时导致崩溃。

深拷贝则为每个对象都有自己独立的一份数据。

总结：
凡是涉及了资源管理的类，其拷贝构造以及赋值重载一定要进行深拷贝。

拷贝构造

进行深拷贝，将数据一个一个喂进去。

		vector(const vector<T>& v){size_t endofstorage = v._end_of_storage - v._start;_start = new T[endofstorage];int i;//写外面for (i=0; v._start + i < v._finish; i++){_start[i] = v._start[i];//运用了赋值重载}_finish = _start + i;_end_of_storage = _start + endofstorage;}

也有更简洁的写法，使用等会要实现的reserve开好空间，再利用范围for将数据尾插进去。

		//现代写法vector(const vector<T>& v){reserve(v.capacity()); //调用reserve函数将容器容量设置为与v相同for (auto e : v) //将容器v当中的数据一个个尾插过来{push_back(e);}}

赋值重载

拷贝构造将数据一个一个插进去时就用到了赋值重载，所以赋值重载也需要进行深拷贝；开后空间将数据插入后别忘记对原有空间进行释放，最后再把_start,_finish,_end_of_storage更新。

		vector<T>& operator=(const vector<T>& v){//赋值重载是对已存在对象而言，记得确保数据拷贝完成再释放原有空间if (this != &v)//避免给自己赋值{size_t endofstorage = v._end_of_storage - v._start;T* tmp = new T[endofstorage];//临时数组接收int i;for (i = 0; v._start+i < v._finish; i++){tmp[i] = v._start[i];}if (_start)//判断一下{delete[] _start;//释放空指针不会出错，但还是要注意规范。}_start = tmp;_finish = _start + i;_end_of_storage = _start + endofstorage;return *this;}}

析构函数

释放掉由_start指向的空间即可。

		~vector(){if (_start){delete[] _start;_start = _finish = _end_of_storage = nullptr;}}

迭代器

SGI版下的vector的迭代器还是原生指针，所以将模板类型T* typedef为iterator及const版。

• 注意：VS(PJ版)下vector的迭代器不是原生指针

	public:typedef T* iterator;typedef const T* const_iterator;

begin和end

vector当中的begin函数返回容器的首地址，end函数返回容器当中有效数据的下一个数据的地址。

        iterator begin(){return _start;}iterator end(){return _finish;}

还需要重载一对适用于const对象的begin和end函数，使得const对象调用begin和end函数时所得到的迭代器只能对数据进行读操作，而不能进行修改。

	    const_iterator begin()const{return _start;}const_iterator end()const{return _finish;}

有了迭代器，范围for也就支持了。

	int arr[] = { 1,2,3,4,5,6,7,8,9 };vector<int> v1(arr, arr + sizeof(arr) / sizeof(int));for (auto e : v1){cout << e;}cout << endl;

容量相关函数

size

获取数据个数：指针_finish 和_start相减便是数据个数

	    size_t size() const{return _finish - _start;}

capacity

获取容量：指针_end_of_storage ， _start相减为容量。

		size_t capacity() const{return _end_of_storage - _start;}

empty

判断是否为空：检查_start与_finish是否相等。

		bool empty() const{return _start == _finish;}

reserve

功能：

1. 当n大于对象当前的capacity时，将capacity扩大到n或大于n。
2. 当n小于对象当前的capacity时，不做响应。

这里需要注意的是我们是用三个指针来维护数据的，一旦开辟了新的空间并把原有数据拷贝过去后，三个指针那就都失效了，必须更新指针的位置；扩容前需要记录_finish与_start的间距，有了这间距等会才能恢复_finish的位置。

		void reserve(size_t n){if (n > capacity()){size_t 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;}}

resize

功能：

1. 当n大于当前的size时，将size扩大到n，扩大的数据为val，若val未给出，则默认为容器所存储类型的默认构造函数所构造出来的值。
2. 当n小于当前的size时，将size缩小到n。

首先检查是否需要扩容，之后利用一个循环比较n与sz的关系，若n大于sz则插入数据，否则不做处理。最后重新定位一下_finish的位置。

		void resize(size_t n, const T& val = T())//库的不是引用，而是传值{if (n > capacity()){reserve(n);}size_t sz = size();//当前个数while (n > sz)//小了不处理，大了加{*_finish = val;_finish++;sz++;//进入循环说明n>sz,结束条件则为n==sz}//重新定位(也处理小的情况)_finish = _start + n;}

访问

operator[]

vector的底层还是数组，支持下标访问：_start维护的是整段数据，支持下标访问，所以直接返回对应的数据即可；下标访问是可以修改内容的，采用引用返回。

		T& operator[] (size_t n)//下标{return _start[n];}

重载运算符[ ]时需要重载一个适用于const容器的，因为const容器通过“下标+[ ]”获取到的数据只允许进行读操作，不能对数据进行修改。

        const T& operator[] (size_t n) const{return _start[n];}

修改相关函数

insert

库里有三个insert的重载，我们实现第一，三个

一：
insert函数可以在所给迭代器position位置插入数据，在插入数据前先判断是否需要增容，然后将position位置及其之后的数据统一向后挪动一位，以留出position位置进行插入，最后将数据插入到position位置并返回position的位置。

• 需要注意的是position是迭代器类型，一旦进行扩容，就需要重新定位position在新区间的位置，所以在扩容前记录position与_start的间距。
• 其返回值为返回插入位置的迭代器，也就是position。

iterator insert(iterator position, const T& val){assert(position >= _start);assert(position <= _finish);if (_finish + 1 > _end_of_storage)//检查是否需要扩容{size_t gap = position - _start;reserve(capacity()==0?4:capacity() * 2);//防止capacity为0的情况position = _start + gap;}iterator end = _finish;//T*endwhile (end > position)//end==pos时不需要移{*end = *(end - 1);end--;}*end = val;//插入_finish++;return position;}

二：
插入一段迭代器区间:用一个循环其中调用第一个insert将数据添加进去。

• 使用insert后注意迭代器失效问题，这里用重新接受其返回值解决。

	    template <class InputIterator>void insert(iterator position, InputIterator first, InputIterator last){assert(position >= _start);assert(position <= _finish);while (first != last){position = insert(position, *first);//注意迭代器失效问题position++;first++;}}

push_back

尾插一个元素：调用insert完成。

	    void push_back(const T& val){insert(_finish, val);}

erase

删除传入迭代器位置的元素：从position位置开始从后往前覆盖。返回值为：返回删除元素后一位，但已覆盖，实际还是position

		iterator erase(iterator position){assert(position >= _start);assert(position <= _finish);assert(!empty());iterator end = position;while (end<_finish){*end = *(end + 1);end++;}_finish--;return position;//返回删除元素后一位，但已覆盖，实际还是position}

pop_back

尾删：调用erase。

		void pop_back(){erase(_finish - 1);}

clear

清空数据但容量不改：让_finish=_start即可。

	    void clear(){_finish = _start;//只是禁止了迭代器访问的方式，数据还在}

swap

交换两个vector：由于swap的重载非常多，可以使用交换单一变量的swap，逐个指针交换。也可以直接使用交换vector的swap（非成员函数）。

        void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);//std::swap(*this,v);}

迭代器失效问题

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

对于vector可能会导致其迭代器失效的操作有：
问题一：会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、
push_back等。

如：使用reserve
SGI版的vector的reserve虽然没有报错，但是可以看到其行为是未定义或者说越界访问了。

而PJ版(VS)的vector的reserve则是崩溃了。

出错原因：使用reserve有可能会导致vector扩容，也就是说vector底层原理旧空间被释放掉，而在打印时，it还使用的是释放之间的旧空间，在对it迭代器操作时，实际操作的是一块已经被释放的空间，而引起代码运行时崩溃。

解决办法也简单：使用前重新赋值获取迭代器位置。

问题二：指定位置元素的删除操作——erase
程序没有崩溃，但是可以看到此时的it2已经不是指向1了，所以其结果也还是错的。

VS的直接崩溃

erase删除it2位置元素后，it2位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代器不应该会失效，但是：如果it2刚好是最后一个元素，删完之后it2刚好是end的位置，而end位置是没有元素的，那么it2就失效了。因此删除vector中任意位置上元素时，VS就认为该位置迭代器失效了，不能再使用了。

同样的，该问题也能通过重新赋值解决。

再如以下代码：
删除容器中所有的偶数。

	int arr[] = { 1,2,3,4,5,6 };std::vector<int>v2(arr, arr+sizeof(arr)/sizeof(int));auto it2 = v2.begin();v2.erase(it2);while (it2 != v2.end()){if (*it2 % 2 == 0){v2.erase(it2);}	else{++it2;}}

此时可以看到VS处理得很极端，直接崩溃了。

而解决办法是接受其返回值，重新获取迭代器位置。

总结：
迭代器失效解决方法：使用迭代器时，永远记住一句话：每次使用前，对迭代器进行重新赋值。

PJ版的与SGI版的迭代器由于实现不同，导致他们的处理方式也不一样。

• Linux下(SGI版)，g++编译器对迭代器失效的检测并不是非常严格，处理也没有VS(PJ版)下极端。
• SGI版的STL中，迭代器失效后，代码并不一定会崩溃，但是运行结果肯定不对，如果it不在begin和end范围内，肯定会崩溃的。

string也会有以上问题，但是我们一般不使用迭代器访问。

这篇关于【C++】STL学习——vector模拟实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---