vector深度剖析及模拟实现

前言

本文重点模拟实现vector的核心接口, 帮助我们更好的理解底层逻辑, 以及对vector的深度剖析.

博客主页: 酷酷学!!! 期待关注~

---

正文开始

vector核心框架模拟实现

1. 前期准备

首先, 可以查看到STL源码, 底层vector的实现并不是我们通常顺序表那样定义成员变量, 而是通过迭代器也就是指针进行实现, 那么我们也按照STL来进行模拟实现.

T* _a;
size_t _size;
size_t _capacity;

---

#pragma once#include<iostream>
#include<assert.h>
using namespace std;namespace my
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;//核心接口的实现private:iterator _start; //指向数据块开始iterator _finish; //指向有效数据的尾iterator _endOfStorage; //指向存储容量的尾};
}

2. 构造和销毁

• 默认无参构造

		//默认无参构造vector():_start(nullptr), _finish(nullptr), _endOfStorage(nullptr){}

默认的无参构造, 因为在声明的时候我们并没有给缺省值, 所以我们也可以直接在初始化列表进行初始化.

• 迭代器区间初始化

		//迭代器区间初始化//若使用iterator做迭代器,会导致初始化的迭代器区间[first,last)//只能是vector的迭代器//重新声明迭代器,迭代器区间[first,last)可以是任意容器的迭代器template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}

• 初始化n个相同的值

		//n个相同的值,使用默认的构造函数进行初始化, //对于内置类型,C++对这方面也进行了支持//vector(size_ n, const T& value = 0)//这里缺省值不能给0,如果对于自定义类型就有问题了vector(size_t n, const T& value = T())//匿名对象//相当于缺省值给了一个临时的匿名对象:_start(nullptr), _finish(nullptr), _endOfStorage(nullptr){reserve(n);while (n--){push_back(value);}}/** 理论上讲, 提供了vector(size_t n,const T& value = T())之后,* vector(int n,const T& value = T())就不需要提供了,但是对于:* vector<int> v(10,5);* 编译器在编译时,认为T已经被实例化为int,而10和5编译器会默认其为int类型* 就不会走vector(size_t n,const T& value = T())这个构造方法* 最终选择的是：vector(InputIterator first, InputIterator last)* 因为编译器觉得区间构造两个参数类型一致，因此编译器就会将InputIterator实例化为int* 但是10和5根本不是一个区间，编译时就报错了* 故需要增加该构造方法*/vector(int n, const T& value = T()): _start(new T[n]), _finish(_start + n), _endOfStorage(_finish){for (int i = 0; i < n; ++i){_start[i] = value;}}

这里可能不太理解为什么 const T& value = T() 这个缺省值要给T(), 要给默认构造函数, C++对于内置类型也进行了升级, 内置类型也可以使用构造初始化, 所以这个值, 不管自定义类型还是内置类型都可以适用

		// C++内置类型进行了升级，也有构造int i = 0;int j(1);int k = int();int x = int(2)

---

有时候, 我们会发现有些代码使用vector是这样写的

vector<int> v{ 1, 2, 3, 4 };

查看C++文档, 可以发现这是C++11的新语法让vector用起来更加方便, 使用<initializer_list>这个类进行初始化.

initializer_list中有两个成员变量. begin指针和end指针, 记录了列表的开始位置和结尾位置, 记录列表这段区间, 进行初始化.

• initializer_list进行初始化

		vector(initializer_list<T> il):_start(nullptr),_finish(nullptr),_endOfStorage(nullptr){reserve(il.size());for (auto e : il){push_back(e);}}

首先扩容, 然后遍历il, 将里面的值尾插到vector.

---

• 拷贝构造

		//拷贝构造vector(const vector<T>& v):_start(nullptr),_finish(nullptr),_endOfStorage(nullptr){reserve(v.capacity());iterator it = begin();const_iterator vit = v.cbegin();while (vit != v.cend()){*it++ = *vit++;}_finish = it;}//vector(const vector<T>& v)//	:_start(nullptr)//	,_finish(nullptr)//	,_endOfStorage(nullptr)//{//	reverse(v.capacity());//	for (auto e : v)//	{//		push_back(e);//	}//}

• 赋值运算符重载

		void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endOfStorage, v._endOfStorage);}//赋值运算符重载// v1 = v3vector<T>& operator=(vector<T> v){swap(v);return *this;}

• 析构函数

		//析构函数~vector(){if (_start){delete[] _start;_start = _finish = _endOfStorage = nullptr;}}

补充: 隐式类型转换和多参数构造的区别

class A{public:A(int a1 = 0):_a1(a1), _a2(0){}A(int a1, int a2):_a1(a1),_a2(a2){}private:int _a1;int _a2;};void test()
{//单参数构造和多参数对象隐式类型转换A aa1(1); //这里是单参数构造A aa2 = 1; //这里是隐式类型转换A aa3(1,1); //这里是多参数构造A aa4 = {1,1}; //这里是多参数隐式类型转换A aa5{1,1}; //这里是多参数隐式类型转换省略=, 一般不要这种写法A aa6{1};A aa7 = {1}; //这两个是C++为了想让{}进行统一, 所以单参数也可以使用{}进行构造, 比较冗余,一般不要这样写/////自定义类型动态开辟调用构造函数A* p1 = new A;//无参构造A* p2 = new A(2); //单参数传参构造A* p3 = new A(2,3); //多参数传参构造A* p1 = newA[10]; //连续申请10个空间,无参构造A aa1(1);A aa2(2);A aa3(3);A *p2 = new A[10]{aa1,aa2,aa3};//拷贝构造,其余为0A* p3 = new A[10]{1,2,3,4,{6,7}};//也可以直接写,进行隐式类型转换///这里的隐式类型转换，跟上面不一样，这里参数个数不固定vector<int> v1({ 1,2,3,4,5,6 });vector<int> v2 = { 10, 20, 30};//()可以省略for (auto e : v1){cout << e << " ";}cout << endl;for (auto e : v2){cout << e << " ";}cout << endl;vector<A> v3 = { 1, A(1), A(2,2), A{1}, A{2,2}, {1}, {2,2} };//这个是首先创建一个存储A的列表然后进行构造}

3. 迭代器相关

这里分别对应静态和非静态vector

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

4. 容器相关

• size和capacity

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

• 修改空间容量, 默认增容

		void reserve(size_t n){if (n > capacity()){size_t oldSize = size();//1.开辟新的空间T* tmp = new T[n];//2.拷贝元素/*if (_start){memcpy(tmp, _start, sizeof(T) * size);}*///不可以用memcpy拷贝if (_start){for (size_t i = 0; i < oldSize; ++i){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + oldSize;_endOfStorage = _start + n;}}

补充: memcpy拷贝问题

1. memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中.
2. 如果拷贝的是内置类型的元素，memcpy既高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝。(比如拷贝int类型既高效又不会出错, 那如果vector里面存储的都是一个个的指针类型呢? 比如string类)

比如下面这段代码

		vector<string> v1;v1.push_back("111111111111111111");v1.push_back("111111111111111111");v1.push_back("111111111111111111");v1.push_back("111111111111111111");v1.push_back("111111111111111111");for (auto e : v1){cout << e << " ";}cout << endl;

当插入第五个值的时候, vector需要进行扩容, memcpy会继续拷贝, 但这是浅拷贝, 将_start里面的值拷贝到tmp中, 此时tmp中成员_str也指向了原来的那段空间, 当_start释放后, 区间就会被销毁, 此时tmp里面的内容就指向了野指针.

而这里使用赋值拷贝, 会调用我们的赋值拷贝函数, 就不会出现浅拷贝的问题了.

结论: 如果对象中涉及到资源管理时, 千万不能使用memcpy进行对象之间的拷贝, 因为memcpy是浅拷贝, 否则可能会引起内存泄漏甚至程序崩溃

• rsize()函数

		void resize(size_t n, const T& value = T()){//1.如果n小于当前的size,则数据缩小到nif (n <= size()){_finish = _start + n;return;}//2.空间不够则增容if (n > capacity())reserve(n);//3.将size扩大到n,并使用value填充后面的值iterator it = _finish;_finish = _start + n;while (it != _finish){*it = value;++it;}}

5. 元素访问

		T& operator[](size_t pos){assert(pos < size());return _start[pos];}const T& operator[](size_t pos)const{assert(pos < size());return _start[pos];}T& front(){return *_start;}const T& front() const{return *_start;}T& back(){return *(_finish - 1);}const T& back() const{return *(_finish - 1);}

6. vector的修改

		void push_back(const T& x){insert(end(), x);}void pop_back(){erase(end() - 1);}iterator insert(iterator pos, const T& x){assert(pos <= _finish);assert(pos >= _start);//空间不够先进性增容if (_finish == _endOfStorage){size_t newcapacity = (capacity() == 0) ? 4 : capacity() * 2;reserve(newcapacity);pos = _start + size();}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;return pos;}//返回删除数据的下一个数据,//方便解决迭代器失效的问题iterator erase(iterator pos){iterator begin = pos + 1;while (begin != _finish){*(begin - 1) = *begin;++begin;}--_finish;return pos;}

测试代码

void TestVector1()
{my::vector<int> v1;my::vector<int> v2(10, 5);int array[] = { 1,2,3,4,5 };my::vector<int> v3(array, array + sizeof(array) / sizeof(array[0]));my::vector<int> v4(v3);for (size_t i = 0; i < v2.size(); i++){cout << v2[i] << " ";}cout << endl;
}void TestVector2()
{my::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);cout << v.size() << endl;cout << v.capacity() << endl;cout << v.front() << endl;cout << v.back() << endl;cout << v[0] << endl;for (auto e : v){cout << e << " ";}cout << endl;v.pop_back();v.pop_back();for (auto e : v){cout << e << " ";}cout << endl;v.insert(v.begin(), 0);for (auto e : v){cout << e<<" ";}cout << endl;v.erase(v.begin() + 1);for (auto e : v){cout << e << " ";}cout << endl;
}

总结

本篇对vector的核心接口进行了模拟实现和探究, C++这门语言本身就比较偏向底层, 希望能够帮助大家进一步理解底层逻辑以及实现思路, 感谢三连!!!

---

完