【C++】STL—容器—vector介绍

分手后的思念是犯贱 2022-11-22 00:12 246阅读 0赞

### 文章目录 ###

*  一、vector的介绍
 *   *  1、概念
     *  2、分配空间策略
     *  3、特点
 *  二、vector的使用
 *   *  1、vector的定义
     *  2、vector iterator 的使用
     *  3、vector 空间增长
     *  4、vector 增删查改
     *  5、vector 迭代器失效问题
 *  三、vector的模拟实现

# 一、vector的介绍 #

## 1、概念 ##

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

## 2、分配空间策略 ##

vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。

## 3、特点 ##

与其它动态序列容器相比（deques, lists and forward\_lists），vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起lists和 forward\_lists统一的迭代器和引用更好。

# 二、vector的使用 #

## 1、vector的定义 ##

void TestVector1()
    {
        
    	vector<int> v1;//无参构造
    	vector<int> v2(10,5);//构造10个整形5
    	
    	int array[] = {
         1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    	vector<int> v3(array, array + sizeof(array) / sizeof(array[0]));//构造整个array数组
    
    	vector<int> v5(v3);//拷贝构造
    
    	vector<int> v6{
         1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };//构造整形数组
    }

## 2、vector iterator 的使用 ##

vector<int> v3(array, array + sizeof(array) / sizeof(array[0]));
    vector<int>::iterator it = v3.begin();//获取第一个数据位置的iterator/const_iterator， 获取最后一个数据的下一个位置iterator/const_iterator
    while (it != v3.end())
    {
        
    	cout << *it << " ";
    	++it;
    }
    cout << endl;
    
    vector<int> v5(v3);
    
    auto rit = v5.rbegin();//获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的 reverse_iterator
    while (rit != v5.rend())
    {
        
    	cout << *rit << " ";
    	++rit;
    }
    cout << endl;

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70_pic_center]

## 3、vector 空间增长 ##

void TestVector2()
    {
        
    	vector<int> v{
         1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    	cout << v.size() << endl;//获取数据个数
    
    	cout << v.capacity() << endl;//获取容量大小
    
    	if (v.empty())//判断是否为空
    	{
        
    		cout << "v empty" << endl;
    	}
    	else
    	{
        
    		cout << "v not empty" << endl;
    	}
    }
    
        v.reserve(40);//将容量扩大到40
    
        v.resize(20, 100);//将数据个数设置为20，不够用100补充

**capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。**

## 4、vector 增删查改 ##

void TestVector6()
    {
        
    	// 注意：push_back和insert在插入元素期间，可能需要扩容
    	vector<int> v;
    	v.push_back(1);//尾插
    	v.push_back(2);
    	v.push_back(3);
    	v.push_back(4);
    
    	v.pop_back();//尾删
    
    	v.insert(v.begin(), 0);//头部位置插入0
    
    	// 在元素2的位置插入10个值为5的元素
    	v.insert(find(v.begin(), v.end(), 2), 10, 5);
    
    	//将数组array中的元素插入到v的尾部
    	int array[] = {
         4, 5, 6, 7 };
    	v.insert(v.end(), array, array + sizeof(array) / sizeof(array[0]));
    }
    
        vector<int> v1{
         1, 2, 3 };
    	vector<int> v2{
         4, 5, 6, 7, 8, 9 };
    	v1.swap(v2);//v1和v2交换
    
        vector<int> v3{
         1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    	v3.erase(v3.begin());//头部元素删除
    	v3.erase(v3.begin(), v3.begin() + 3);//头部元素开始，后3个元素删除

## 5、vector 迭代器失效问题 ##

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

对于vector可能会导致其迭代器失效的操作有：

1.  会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、 push\_back等
2.  指定位置元素的删除操作–erase

void TestVector11()
    {
        
    	vector<int> v{
         1, 2, 3 };
    	auto it = v.begin();
    
    	v.clear();
    	cout << *it << endl;//迭代器失效
    
    	while (it != v.end())
    	{
        
    		it = v.erase(it);
    		it++;//迭代器失效
    	}
    }

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

**迭代器失效解决办法：在使用前，对迭代器重新赋值即可。**

# 三、vector的模拟实现 #

#include <assert.h>
    
    namespace bite
    {
        
    	template<class T>
    	class vector
    	{
        
    	public:
    		typedef T* iterator;
    	public:
    		vector()
    			: start(nullptr)
    			, finish(nullptr)
    			, endofstorage(nullptr)
    		{
        }
    
    		vector(int n, const T& data = T())
    			: start(new T[n])
    			, finish(start + n)
    			, endofstorage(finish)
    		{
        
    			for (int i = 0; i < n; ++i)
    			{
        
    				start[i] = data;
    			}
    		}
    
    		template<class Iterator>
    		vector(Iterator first, Iterator last)
    		{
        
    			// 确定该区间中有多少个元素
    			Iterator it = first;
    			size_t count = 0;
    			while (it != last)
    			{
        
    				count++;
    				++it;
    			}
    
    			// 给当前对象开辟空间，并初始化成员变量
    			start = new T[count];
    			finish = start;
    			endofstorage = start + count;
    
    			//赋值
    			while (first != last)
    			{
        
    				*finish++ = *first++;
    			}
    		}
    
    		vector(const vector<T>& v)
    		{
        
    			size_t vsize = v.size();
    			start = new T[vsize];
    			finish = endofstorage = start + vsize;
    			for (size_t i = 0; i < vsize; ++i)
    				start[i] = v[i];
    		}
    
    		~vector()
    		{
        
    			if (start)
    			{
        
    				delete[] start;
    				start = finish = endofstorage = nullptr;
    			}
    		}
    
    		iterator begin()
    		{
        
    			return start;
    		}
    
    		iterator end()
    		{
        
    			return finish;
    		}
    
    		size_t size()const
    		{
        
    			return finish - start;
    		}
    
    		size_t capacity()const
    		{
        
    			return endofstorage - start;
    		}
    
    		bool empty()const
    		{
        
    			return start == finish;
    		}
    
    		void resize(size_t newsize, const T& data = T())
    		{
        
    			size_t oldsize = size();
    			if (newsize <= oldsize)
    			{
        
    				finish = start + newsize;
    			}
    			else
    			{
        
    				if (newsize > capacity())
    					reserve(newsize);
    				for (size_t i = oldsize; i < newsize; ++i)
    					start[i] = data;
    				finish = start + newsize;
    			}
    		}
    
    		void reserve(size_t newcapacity)
    		{
        
    			size_t oldcapacity = capacity();
    			size_t oldsize = size();
    			if (newcapacity > oldcapacity)
    			{
        
    				// 开辟新空间
    				T* temp = new T[newcapacity];
    
    				// 拷贝元素
    				for (size_t i = 0; i < oldsize; ++i)
    					temp[i] = start[i];
    
    				// 释放旧空间
    				delete start;
    
    				start = temp;
    				finish = start + oldsize;
    				endofstorage = start + newcapacity;
    			}
    		}
    
    		//acess
    		T& operator[](size_t index)
    		{
        
    			assert(index < size());
    			return start[index];
    		}
    
    		const T&operator[](size_t index)const
    		{
        
    			assert(index < size());
    			return start[index];
    		}
    
    		T& front()
    		{
        
    			return start[0];
    		}
    
    		const T& front()const
    		{
        
    			return start[0];
    		}
    
    		T& back()
    		{
        
    			return start[size() - 1];
    		}
    
    		const T& back()const
    		{
        
    			return start[size() - 1];
    		}
    
    		void push_back(const T& data)
    		{
        
    			if (size() == capacity())
    				reserve(capacity() * 2 + 3);
    
    			*finish++ = data;
    		}
    
    		void pop_back()
    		{
        
    			if (empty())
    				return;
    
    			--finish;
    		}
    
    		iterator insert(iterator pos, const T& data)
    		{
        
    			assert(pos <= end());
    			if (size() == capacity())
    				reserve(capacity() * 2);
    
    			auto it = end();
    			while (it > pos)
    			{
        
    				*it = *(it - 1);
    				--it;
    			}
    
    			*pos = data;
    			++finish;
    
    			return pos;
    		}
    
    		iterator erase(iterator pos)
    		{
        
    			assert(pos < end());
    			if (size() == 1)
    			{
        
    				pop_back();
    				return end();
    			}
    
    			auto it = pos;
    			while (it < end())
    			{
        
    				*it = *(it + 1);
    				++it;
    			}
    
    			--finish;
    			return pos;
    		}
    
    		void clear()
    		{
        
    			finish = start;
    		}
    
    		void swap(const vector<T>& v)
    		{
        
    			std::swap(start, v.start);
    			std::swap(finish, v.finish);
    			std::swap(endofstorage, v.endofstorage);
    		}
    	private:
    		iterator start;
    		iterator finish;
    		iterator endofstorage;
    	};
    }
    
    #include <iostream>
    using namespace std;
    
    #include <string>
    
    void TestMyvector1()
    {
        
    	bite::vector<int> v1;
    	bite::vector<int> v2(10, 5);
    	
    	for (size_t i = 0; i < v2.size(); ++i)
    		cout << v2[i] << " ";
    	cout << endl;
    
    	int array[] = {
         1, 2, 3, 4, 5 };
    	bite::vector<int> v3(array, array + 5);
    	auto it = v3.begin();
    	while (it!=v3.end())
    	{
        
    		cout << *it << " ";
    		++it;
    	}
    	cout << endl;
    
    	std::string s("hello");
    	bite::vector<char> vc(s.begin(), s.end());
    	bite::vector<int> v4(v3);
    	for (auto e : v4)
    		cout << e << " ";
    	cout << endl;
    }
    
    void TestMyvector2()
    {
        
    	bite::vector<int> v;
    	v.push_back(1);
    	v.push_back(2);
    	v.push_back(3);
    	v.push_back(4);
    
    	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());
    	for (auto e : v)
    		cout << e << " ";
    	cout << endl;
    
    	v.clear();
    	cout << v.size() << endl;
    	cout << v.capacity() << endl;
    }
    
    void TestMyvector3()
    {
        
    	bite::vector<int> v;
    	v.push_back(1);
    	v.push_back(2);
    	v.push_back(3);
    	v.push_back(4);
    
    	cout << v[0] << endl;
    	cout << v.front() << endl;
    	cout << v.back() <<endl;
    
    	v.resize(8, 5);
    	cout << v.size() << endl;
    	cout << v.capacity() << endl;
    	for (auto e : v)
    	{
        
    		cout << e << " ";
    	}
    	cout << endl;
    
    	v.resize(15, 6);
    	cout << v.size() << endl;
    	cout << v.capacity() << endl;
    	for (auto e : v)
    	{
        
    		cout << e << " ";
    	}
    	cout << endl;
    
    	v.resize(20, 6);
    	cout << v.size() << endl;
    	cout << v.capacity() << endl;
    	for (auto e : v)
    	{
        
    		cout << e << " ";
    	}
    	cout << endl;
    
    	v.resize(12);
    	cout << v.size() << endl;
    	cout << v.capacity() << endl;
    	for (auto e : v)
    	{
        
    		cout << e << " ";
    	}
    	cout << endl;
    
    	v.resize(5);
    	cout << v.size() << endl;
    	cout << v.capacity() << endl;
    	for (auto e : v)
    	{
        
    		cout << e << " ";
    	}
    	cout << endl;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/b4bb6cd396a547f8a6b887706e527d1c.png