带你攻克STL —— 如何正确使用vector (重难点剖析及其模拟实现)

秒速五厘米 2022-12-10 14:33 65阅读 0赞

### 文章目录 ###

*  vector介绍
 *  正确使用vecotr
 *   *  初始化
     *  iterator
     *  空间问题
     *   *  扩容机制
         *  resize 和 reverse
     *  vector 其他常用接口
     *  迭代器失效问题
 *  vector模拟实现

# vector介绍 #

c++官方文档定义  
简单来说，vector就是一个被封装了的类， 这个类实例化的对象可以存储各种类型的成员，通过类中的成员函数我们可以高效的操作我们的数据。

1.  **vector是表示可变大小数组的序列容器。**
2.  就像数组一样，vector也**采用的连续存储空间来存储元素**。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
3.  本质讲，vector使用**动态分配数组来存储它的元素**。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。
4.  **vector分配空间策略**：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存  
    储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
5.  与其它动态序列容器相比（deques, lists and forward\_lists）， vector在**访问元素的时候更加高效**，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起lists和forward\_lists统一的迭代器和引用更好。

# 正确使用vecotr #

## 初始化 ##

常见的初始化方式有以下五种，

//定义具有10个整型元素的向量（尖括号为元素类型名，它可以是任何合法的数据类型），不具有初值，其值不确定
    vector<int>a(10);
    
    //定义具有10个整型元素的向量，且给出的每个元素初值为1
    vector<int>a(10,1);
    
    //用向量b给向量a赋值，a的值完全等价于b的值
    vector<int>a(b);
    
    //将向量b中从0-2（共三个）的元素赋值给a，a的类型为int型
    vector<int>a(b.begin(),b.begin+3);
    
     //从数组中获得初值
    int b[7]={
        1,2,3,4,5,6,7};
    vector<int> a(b,b+7）;

## iterator ##

vector的迭代器分为 begin end （从前往后遍历）以及 rbegin rend（从后往前遍历）；  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2lmd2VjYW5kZQ_size_16_color_FFFFFF_t_70_pic_center]  
使用方式：

vector<int>::iterator it = v.begin();
    vector<int>::reverse_iterator rit = v.rbegin();

## 空间问题 ##

首先列举一下vector中与空间有关系的接口

1.  size 获取数据个数
2.  capacity 获取容量大小
3.  empty 判断是否为空
4.  resize 改变vector的size
5.  reserve 改变vector放入capacity

### 扩容机制 ###

vector的空间是开辟在堆上的，vector对于空间的分配是随着用户使用而分配的，也就是说，你用多少，vector尽量给你分配多少，每当空间不够用的时候vector就会扩容。

#include <iostream>
    #include <vector>
    int main ()
    {
        
     size_t sz;
     std::vector<int> foo;
     sz = foo.capacity();
     std::cout << "making foo grow:\n";
     for (int i=0; i<100; ++i) {
        
     foo.push_back(i);
     if (sz!=foo.capacity()) {
        
     sz = foo.capacity();
     std::cout << "capacity changed: " << sz << '\n';
     }
     }

上述代码就很好的测试了vector的扩容机制，capacity的代码在vs和g++下分别运行会发现，**vs下capacity是按1.5倍增长的，g++是按2倍增长的。原因是因为stl的版本不同导致，因此各有优劣。**

### resize 和 reverse ###

resize和reverse一定程度上缓解了这种缺陷，这两个方法都会开辟空间，但是不同的是， reserve只负责开辟空间，resize在开空间的同时还会进行初始化，影响size。  
//开辟空间小了

## vector 其他常用接口 ##

#include<vector>
    vector<int> a,b;
    //b为向量，将b的0-2个元素赋值给向量a
    a.assign(b.begin(),b.begin()+3);
    //a含有4个值为2的元素
    a.assign(4,2);
    //返回a的最后一个元素
    a.back();
    //返回a的第一个元素
    a.front();
    //返回a的第i元素,当且仅当a存在
    a[i];
    //清空a中的元素
    a.clear();
    //判断a是否为空，空则返回true，非空则返回false
    a.empty();
    //删除a向量的最后一个元素
    a.pop_back();
    //删除a中第一个（从第0个算起）到第二个元素，也就是说删除的元素从a.begin()+1算起（包括它）一直到a.begin()+3（不包括它）结束
    a.erase(a.begin()+1,a.begin()+3);
    //在a的最后一个向量后插入一个元素，其值为5
    a.push_back(5);
    //在a的第一个元素（从第0个算起）位置插入数值5,
    a.insert(a.begin()+1,5);
    //在a的第一个元素（从第0个算起）位置插入3个数，其值都为5
    a.insert(a.begin()+1,3,5);
    //b为数组，在a的第一个元素（从第0个元素算起）的位置插入b的第三个元素到第5个元素（不包括b+6）
    a.insert(a.begin()+1,b+3,b+6);
    //返回a中元素的个数
    a.size();
    //返回a在内存中总共可以容纳的元素个数
    a.capacity();
    //将a的现有元素个数调整至10个，多则删，少则补，其值随机
    a.resize(10);
    //将a的现有元素个数调整至10个，多则删，少则补，其值为2
    a.resize(10,2);
    //将a的容量扩充至100，
    a.reserve(100);
    //b为向量，将a中的元素和b中的元素整体交换
    a.swap(b);
    //b为向量，向量的比较操作还有 != >= > <= <
    a==b;

## 迭代器失效问题 ##

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

vector可能导致迭代器失效的原因：

会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、push\_back等。

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

解决方式：  
使用前重新赋值。

# vector模拟实现 #

#pragma once
    #include <assert.h>
    #include <iostream>
    namespace my_vector {
        
    
    	//模板的使用示例
    //	template<class T>
    //	class vector{
        
    //public:
    //
    //private:
    //	T* _a;
    //	size_t _size;
    //	size_t _capacity;
    //	};
    
    	template<class T>
    	class vector{
        
    public:
    	typedef T* iterator; // 对模板进行重命名
    	typedef const T* const_iterator;
    
    	vector() //初始化列表 初始化迭代器指针
    		:_start(nullptr)
    		,_finish(nullptr)
    		,_endofstorage(nullptr)
    	{
        }
    
    	//构造
    	v2(v1) 
    	//vector(const vector<T>& v) { //直接 构造出一个想要的空间 然后逐一赋值 
    	//	_start = new T[v.capacity()]; //指向空间首地址
    	//	_finish = _start;
    	//	_endofstorage = _start + v.capacity(); //指向最大容量处
    
    	//	for (size_t i = 0; i < v.size(); i++) { //循环赋值
    	//		*_finish = v[i];
    	//		++_finish;
    	//	}
    	//}
    	//v2(v1)
    	vector(const vector<T>& v)//先初始化 然后reverse开空间 逐一赋值
    		:_start(nullptr)
    		, _finish(nullptr)
    		, _endofstorage(nullptr)
    		{
        
    			reverse(v.capacity());
    			for (const auto& e : v) {
        
    				push_back(e);
    			}
    		}
    		
    
    	//赋值运算符重载 现代写法 
    	//vector<T>& operator=(vector<T> v) { //进来的系统自动拷贝一份v
    	//	swap(v); //其实是交换 this 和 v
    	//	return *this;
    	//}
    	///
    	vector<T>& operator=(vector<T>& v) {
        
    		//释放原来的空间
    		delete[] _start;
    		_start = _finish = _endofstorage = nullptr;
    		//开辟新空间
    		T* tmp = new T[v.capacity()];
    		//赋值
    		for (size_t i = 0; i < v.size(); i++) {
        
    			tmp[i] = v[i];
    		}
    		//结束
    		_start = tmp;
    		_finish = tmp + v.size();
    		_endofstorage = tmp + v.capacity();
    		return *this;
    	}
    	//
    	void swap(vector<T>& v) {
         
    		::swap(_start, v._start);
    		::swap(_finish, v._finish);
    		::swap(_endofstorage, v._endofstorage);
    	}
    
    	~vector() {
         //析构
    		delete[] _start;
    		_start = _finish = _endofstorage = nullptr;
    	}
    	iterator begin() {
        
    		return _start;
    	}
    	iterator end() {
         //_finish 指向的是末尾位置
    		return _finish;
    	}
    	const_iterator begin() const{
         //只读迭代器重载
    		return _start;
    	}
    	const_iterator end() const{
        
    		return _finish;
    	}
    	void reverse(size_t n) {
        
    		if (n >capacity()) {
        
    			size_t sz = size();
    			T* tmp = new T[n];
    			if (_start) {
         //判断是不是空 如果为空则只需要进行指针的大小变化 无需进行值拷贝
    				//memcpy(tmp, _start, sizeof(T)*sz);浅拷贝 
    				for (size_t i = 0; i < sz; ++i) {
        
    					tmp[i] = _start[i];
    				}
    				delete[] _start;//赋值结束后删除原来的数据 
    			}
    			_start = tmp;//更新指针位置
    			_finish = tmp + sz;
    			_endofstorage = tmp + n;
    		}
    	}
    
    	void resize(size_t n, const T& val = T()) {
         //此处为缺省参数
    		if (n < size()) {
        
    			_finish = _start + n;
    		}
    		else {
        
    			if (n > capacity()) {
        
    				reverse(n);
    			}
    			while (_finish != _start + n) {
        
    				*_finish = val;
    				++_finish;
    			}
    		}
    	}
    
    	void push_back(const T& x) {
        
    		if (_finish == _endofstorage) {
        
    			size_t newcapacity = capacity() == 0 ? 2 : capacity() * 2;
    			reverse(newcapacity);
    		}
    		/
    		*_finish = x;
    		_finish++;
    		//insert(_finish, x);
    	}
    
    	void pop_back() {
        
    		assert(_start < _finish);
    		--_finish;
    	}
    	void insert(iterator pos, const T& x) {
        
    		assert(pos <= _finish);
    		if (_finish == _endofstorage) {
        
    			size_t n = pos - _start;//扩容时保存相对位置
    			size_t newcapacity = capacity() == 0 ? 2 : capacity() * 2;
    			reverse(newcapacity);
    			pos = _start + n;
    		}
    		iterator end = _finish - 1;
    		while (end >= pos) {
        
    			*(end + 1) = *end;
    			--end;
    		}
    		*pos = x;
    		++_finish;
    	}
    
    	iterator erase(iterator pos) {
        
    		assert(pos >= _start && pos < _finish);
    		iterator it = pos;
    		while (it < _finish) {
        
    			*it = *(it + 1);
    			it++;
    		}
    		--_finish;
    		return pos;
    	}
    	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;
    	}
    private:
    	iterator _start;
    	iterator _finish;
    	iterator _endofstorage;
    	};
    
    	//测试
    	//迭代器失效问题
    
    	void print_vector(const vector<int>& v) {
        
    		vector<int>::const_iterator it = v.begin();
    		while (it != v.end()) {
        
    			std::cout << *it << " ";
    			++it;
    		}
    		std::cout << std::endl;
    	}
    	void test1() {
        
    		vector<int> v;
    		v.push_back(1);
    		v.push_back(3);
    		v.push_back(2);
    		print_vector(v);
    
    		//std::cout << v.size() << std::endl;
    		//std::cout << v.capacity() << std::endl;
    		//print_vector(v);
    
    		vector<int> x;
    		x.push_back(100);
    		print_vector(x);
    		x = v;
    		print_vector(x);
    		print_vector(v);
    
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2lmd2VjYW5kZQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/837446bdf04f4a47a09031c164253ca3.png