STL之vector

目录

vector概念

vector的遍历

1、[ ]的重载

2、迭代器

3、范围for

vector的模拟实现

成员变量

reserve函数与拷贝构造

增删函数

push_back

pop_back

迭代器

运算符重载

赋值运算符

[ ]运算符

其他函数

vector概念

1、vector是表示可变大小数组的序列容器。

2、就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。

3、本质讲，vector使用动态分配数组来存储它的元素。

4、vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。

vector的遍历

vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4);

1、[ ]的重载

for (size_t i = 0; i < v.size(); i++) { 	cout << v[i] << " "; }

2、迭代器

vector<int>::iterator it = v.begin(); while (it != v.end()) { 	cout << *it << " "; 	it++; } cout << endl;

3、范围for

for (auto& e : v) 	cout << e; cout << endl;

vector是一个类模板，参考stl3.0的写法

成员变量

库里面的写法

 这里的iterator是被typdef了一下

所以他的类型是 T*。传入int 就为int*，传入string就为string*。

start用来标注数组的起点，finish用来标注数组有效长度的尾部，endofstorage标注数组的尾部。

所以基本上的框架就是下面这样

template<class T> class myvector { public:     typedef T* iterator;     //--------构造函数---------     myvector() 	    :_start(nullptr) 	    ,_finish(nullptr) 	    ,_endofstorage(nullptr)     {}     ~myvector()     { 	    delete[] _start; 	    _start = nullptr; 	    _finish = nullptr; 	    _endofstorage = nullptr;     }  private: 	iterator _start; 	iterator _finish; 	iterator _endofstorage; };

reserve函数与拷贝构造

先谈谈reserve函数，因为插入元素首先是增容问题，自我感觉也是这个类的核心。

先看一下下面的代码

void reserve(size_t cap) { 	if (cap > capacity()) 	{ 		size_t len = size(); 		T* tmp = new T[cap]; 		if (_start)//防止为空的时候增容 		{ 			memcpy(tmp, _start, len * sizeof(T));//拷贝 			delete[] _start;//释放原来的空间 		} 		_start = tmp; 		_finish = _start + len; 		_endofstorage = _start + cap; 	} }

当大于实际容量时，才增容，否则不增容。增容的逻辑就是开辟一块新容量的空间，将之前的内容拷贝过来（如果没有之前相等），然后更改对应的三个指针。

上面的代码表面看着没什么问题，其实存在一个很严重的bug，那就是浅拷贝。

memcpy 将_start内容拷贝到tmp里面，如果是基本类型的数据，还不会出bug，如果是自定义类型，就有可能会出错。例如string类型，string类型里面有一个char*类型的指针，该指针指向了一块堆上的空间，如果只是单独的把_start的内容拷贝给tmp中，则一旦释放掉_start，会调用string的析构函数，则tmp里面的内容都被析构了，代码会崩溃。

正确的方法

void reserve(size_t cap) { 	if (cap > capacity()) 	{ 		size_t len = size(); 		T* tmp = new T[cap]; 		if (_start) 		{ 			for (size_t i = 0; i < len; i++) 			{ 				tmp[i] = _start[i];//调用类型T自带的赋值完成深拷贝 			} 			delete[] _start; 		} 		_start = tmp; 		_finish = _start + len; 		_endofstorage = _start + cap; 	}

拷贝构造

myvector(const myvector<T>& v)//深拷贝     :_start(nullptr)     ,_finish(nullptr)     ,_endofstorage(nullptr) { 	reserve(v.capacity()); 	for (size_t i = 0; i < v.size(); i++) 	{ 		*_finish = v[i]; 		_finish++; 	} }

增删函数

push_back

尾插，如果_finish == endofstorage，则需要增容，注意刚开始为为空时的情况。

void push_back(const T& x) { 	if (_finish == _endofstorage) 	{ 		size_t newcapacity = capacity() == 0 ? 2 : capacity() * 2; 		reserve(newcapacity); 	} 	*_finish = x; 	_finish++; }

pop_back

尾删，在入口处判断是否合法，即_start<_finish。

void pop_back() { 	assert(_start < _finish);//首先得判断是否为空数组 	_finish--; }

迭代器

vector的迭代器也比较简单，和string的类似。

iterator begin() { 	return _start; } iterator end() { 	return _finish; } const_iterator begin() const//const迭代器 typedef const T* const_iterator; { 	return _start; } const_iterator end() const { 	return _finish; }

运算符重载

赋值运算符

const myvector<T>& operator=(const myvector<T>& v) { 	delete[] _start; 	_start = nullptr; 	_finish = nullptr; 	_endofstorage = nullptr;//先清除之前的内容，然后记得置空，不然重新开辟空间会出错 	reserve(v.capacity()); 	for (size_t i = 0; i < v.size(); i++) 	{ 		*_finish = v[i]; 		_finish++; 	} 	return *this; }

现代写法思路一样，用swap函数，利用临时对象的特性，交换空间

void swap(myvector<T>& v) { 	std::swap(_start, v._start); 	std::swap(_finish, v._finish); 	std::swap(_endofstorage, v._endofstorage); }  myvector<T>& operator=(myvector<T> v) { 	swap(v); 	return *this; }

[ ]运算符

T& operator[](size_t i) { 	assert(i < size()); 	return _start[i]; } const T& operator[](size_t i)const { 	assert(i < size()); 	return _start[i]; }

其他函数

size_t size()const//获取大小 { 	return _finish - _start; } size_t capacity()const//获取容量 { 	return _endofstorage - _start; } void resize(size_t n, const T& val = T())//修改size的大小，分情况 { 	if (n < size()) 	{ 		_finish -= size()-n; 	} 	else  	{	 		if (n > capacity()) 		{ 			reserve(n); 		} 		size_t tmp = n - size(); 		while (tmp) 		{ 			*_finish = val; 			_finish++; 			tmp--; 		} 	} }