【STL容器】详解vector的使用和模拟实现

2023-12-16 11:51:50

🍎 博客主页:🌙@披星戴月的贾维斯
🍎 欢迎关注:👍点赞🍃收藏🔥留言
🍇系列专栏:🌙 STL函数专栏
🌙请不要相信胜利就像山坡上的蒲公英一样唾手可得,但是请相信,世界上总有一些美好值得我们全力以赴,哪怕粉身碎骨!🌙
🍉一起加油,去追寻、去成为更好的自己!

在这里插入图片描述
????前言:为什么要写在这时候写STL相关的文章呢?原因有以下几点:1. 最实际的,就是在刷力扣时,发现经常碰到放回vector<vector>这种类型的嵌套vector,而且我们也要经常自己建vector容器,利用vector的接口等等,如果对vector等等stl不太熟悉,非常不利于我们刷题。2.懂得vector等stl的使用,这是对一个学习C++的同学最基本的要求,再高点就是了解vector的底层原理和代码实现。所以我们文章也尽可能写得直白/直观,让大家容易理解

🍎1、vector的介绍

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

🍎2、vector的使用(重点)

1.文档中的定义

在这里插入图片描述
size_type一般是自定义(typedef类型)的类型
size_t:无符号的整形
在这里插入图片描述

2. vector iterator 的使用

iterator的使用接口说明
begin + end(重点)获取第一个数据位置的iterator/const_iterator, 获取最后一个数据的下一个位置的iterator/const_iterator
rbegin + rend获取最后一个数据位置的reverse_iterator,获取第一个数据前一个位置的reverse_iterator

在这里插入图片描述

2.vector的空间大小接口以及空间增长问题

接口

容量空间接口说明
size获取数组元素个数
capacity获取容量大小
empty判断是否为空
resize改变vector的size
reserve改变vector的capacity
  • capacity的代码在vs和g++下分别运行会发现,vs下capacity是按1.5倍增长的,g++是按2倍增长的。这个问题经常会考察,不要固化的认为,vector增容都是2倍,具体增长多少是根据具体的需求定义的。vs是PJ版本STL,g++是SGI版本STL。
  • reserve只负责开辟空间,如果确定知道需要用多少空间,reserve可以缓解vector增容的代价缺陷问题。
  • resize在开空间的同时还会进行初始化,影响size。

几种初始化vector的写法,这很重要

	//初始化的方式1
    vector<int> v1; //定义了一个空的可变长的vector,此时不能直接使用v[i] = 2这种赋值
    //<>里的类型可以有很多种,int/double/string/vector/list/结构体等等
    
    //初始化的方式2
    vector<int> v2[10]; //定义可变长的二维数组,数组的行是10,列可以一直增长
    //初始化可变长的二维数组
    vector<vector<int>> v3;
    
 
    //以上都是没初始化空间以及内容的
    vector<int> v4(n);//定义一个长度为n的数组
    vector<int> v5(n, 0);//定义并初始化
    vector<int> v6{1,2,3,4,5};//列表初始化

3种遍历vector的写法

#include<iostream>
#include<vector>
using namespace std;
int main ()
{
    vector<int> v;
    for(int i = 0; i <= 10; i++)
    v.push_back(i);
    
    //第一种遍历方式 像数组一样的用下标
    for(int i = 0; i <= 10; i++)
    cout << v[i] << " ";
    cout << endl;
    //第二种,迭代器遍历
    vector<int>::iterator it = v.begin();
    while(it != v.end())
    {
        cout << *it << " ";
        it++;
    }
    cout << endl;
    //第三种,for循环遍历
    for(auto& e : v)
    {
        cout << e << " ";
    }
    return 0;
}

3.vector 增删查改的接口

vector增删查改接口说明
push_back(重点)尾插
pop_back (重点)尾删
findfind 查找。(注意这个是算法模块实现,不是vector的成员接口)
insert在position之前插入val
erase删除position位置的数据
swap交换两个vector的数据空间
operator[] (重点)像数组一样访问
emplace_back尾插,序列尾部生成一个新元素

4. vector 迭代器失效问题。(重点)

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

迭代器的两种失效情况
在这里插入图片描述
erase的实现

iterator erase(iterator pos)
        {
            assert(pos >= _start && pos < _finish);
            iterator it = pos + 1;//pos位置的前一个往pos位置覆盖
            while (it != _finish)
            {
                *(it - 1) = *it;
                ++ it;
            }
            --_finish;
            return pos;
        }

erase的失效情形

void test_vector6()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
v1.push_back(6);
auto pos = find(v1.begin(), v1.end(), 2);
if (pos != v1.end())
{
    v1.erase(pos);
}
cout << *pos << endl;//把pos位置输出
*pos = 10;
cout << *pos << endl;//把pos位置修改成10
for (auto e : v1)
{
    cout << e << " ";
}
cout << endl;
}

在这里插入图片描述
往前挪动之后还会++
(1)第一种刚刚好
(2)第二种就是2没判断就跳过了
(3)第三种就是最后想删4的时候,erase删完4之后it的位置已经大于v1.end(),所以报错了
在这里插入图片描述
在这里插入图片描述

🍎3、vector的模拟实现

vector.h代码实现如下,感兴趣的同学可以看看

#pragma once
//模拟实现 --加深对这个容器的理解,而不是造更好的轮子
#include<assert.h>
namespace jiang
{
	template<class T>
	class Myvector
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;
		Myvector()
			:_start(nullptr)
			,_finish(nullptr)
			,_endofstoage(nullptr)
		{}
		template <class InputItrerator>
		//带参的构造函数
		Myvector(InputItrerator first, InputItrerator last)
			: _start(nullptr)
			, _finish(nullptr)
			, _endofstoage(nullptr)
		{
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}
		//交换函数
		void swap(Myvector<T>& v)
		{
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_endofstoage, v._endofstoage);
		}
		Myvector(const Myvector<T>& v)//拷贝构造
			: _start(nullptr)
			, _finish(nullptr)
			, _endofstoage(nullptr)
		{
			Myvector<T>tmp(v.begin(), v.end());
			swap(tmp);
		}  
		Myvector<T>& operator=(Myvector<T> v)
		{
			this->swap(v);//这里默认也有this可以不用加this->
			return *this;
		}
		//n个拷贝构造一个新的
		Myvector(size_t n, const T& val = T())
			: _start(nullptr)
			, _finish(nullptr)
			, _endofstoage(nullptr)
		{
			reserve(n);  
			for (size_t i = 0; i < n; ++i)
			{
				push_back(val);
			}
		} 
	 
		 
		//资源管理
		~Myvector()
		{
			if (_start)
			{
				delete[] _start;
				_start = _finish = _endofstoage = nullptr;
			}
		}
		iterator begin()
		{
			return _start;
		}
		iterator begin() const 
		{
			return _start;
		}
		iterator end()
		{
			return _finish;
		}
		iterator end() const
		{
			return _finish;
		}
		size_t size() const
		{
			return _finish - _start;
		}
		size_t capacity() const
		{
			return _endofstoage - _start;
		}
		void reserve(size_t n)
		{
			size_t sz = size(); 
			if (n > capacity())
			{
				T* tmp = new T[n];//先新生成一块空间
				//然后把旧空间的数据拷贝到新空间
				if (_start)
				{
					//memcpy(tmp, _start, size() * sizeof(T));
					//里面分别填新空间的名字,旧空间的起始地址和旧空间大小
					for(size_t i = 0; i < size(); i++)
					{
						tmp[i] = _start[i];
					}
					delete[] _start;
				}
				_start = tmp;
			}
			_finish = _start + sz;//这里的size = _finish -start = -start
			_endofstoage = _start + n;
		}
		/*void resize(size_t n,const T& val  = T())*/
		void resize(size_t n, T val = T())
		{
			if (n > capacity())
			{
				reserve(n);
			}
			if (n > size())
			{
				while (_finish < _start + n)
				{
					*_finish = val;//放缺省值
					++_finish;
				}
			}
			else//删数据
			{
				_finish = _start + n;
			}
		}
		void push_back(const T& x)
		{
			/*if (_finish == _endofstoage)
			{
				size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newCapacity);
			} 

			*_finish = x;
			++_finish;*/
			insert(end(), x); 
		}
		void pop_back() 
		{
			/*if (_finish > _start)
			{ 
				--_finish;
			}*/
			erase(end() - 1);
		}
		T& operator[](size_t pos)
		{
			assert(pos < size());
			return _start[pos];//返回pos位置的数据
		}
		const T& operator[](size_t pos) const
		{
			assert(pos < size());
			return _start[pos];//返回pos位置的数据
		}
		iterator insert(iterator pos, const T& x)
		{
			//检查参数
			assert(pos >= _start && pos <= _finish);
			//扩容
			if (_finish == _endofstoage)
			{
				size_t n = pos - _start;//先算出原来Pos和 _start的距离
				size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newCapacity);
				pos = _start + n;//再更新pos
			}
			//挪动数据
			iterator end = _finish - 1;
			while (end >= pos)
			{
				*(end + 1) = *end;
				--end;
			}
			*pos = x;
			++_finish;

			return pos;
		}
		iterator erase(iterator pos)
		{
			assert(pos >= _start && pos < _finish);
			iterator it = pos + 1;//pos位置的前一个往pos位置覆盖
			while (it != _finish)
			{
				*(it - 1) = *it;
				++ it;
			}
			--_finish;
			return pos;
		}


	private: 
		iterator _start;
		iterator _finish;
		iterator _endofstoage;
};

🍎总结

????**这次和大家分享了基本的vector的用法以及基础的模拟实现,希望对大家快速上手vector有帮助。

文章来源:https://blog.csdn.net/qq_62662919/article/details/135025937
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。