STL——vector容器基本使用与常用接口模拟实现

vector的介绍及使用

vector的介绍

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

vector的使用和模拟实现

基本成员定义

template<class T>
	class vector {
	public:
		typedef T* iterator;
		typedef const T* const_iterator;
	private:
			iterator _start;
			iterator _finish;
			iterator _eos;//end of storage
			//_finish - _start = size
			//_eos - _start = capacoty
			};

在这里插入图片描述

size() 和capacity()
模拟实现
 size_t size() const
{
		return _finish - _start;
}
size_t capacity() const
{
	return _eos - _start;
}
empty()
模拟实现
	bool empty()
		{
			/*return size() == 0 ? true : false;*/
			return _finish == _start;
		}
构造函数
使用

构造一个某类型的空容器。

vector<int> v1; //构造int类型的空容器

构造一个含有n个val的某类型容器。

vector<int> v2(10, 2); //构造含有10个2的int类型容器

拷贝构造某类型容器的复制品。

vector<int> v3(v2); //拷贝构造int类型的v2容器的复制品

使用迭代器拷贝构造某一段内容。

vector<int> v4(v2.begin(), v2.end()); //使用迭代器拷贝构造v2容器的某一段内容

该方式也可用于拷贝其他容器的某一段内容。

string s("hello world");
vector<char> v5(s.begin(), s.end()); //拷贝构造string对象的某一段内容
模拟实现
//无参构造
       vector()
			:_start(nullptr)
			,_finish(nullptr)
			,_eos(nullptr)
		{

		}
//传参构造
		vector(size_t n, const T& x)
			:_start(nullptr)
			, _finish(nullptr)
			, _eos(nullptr)
		{
			reserve(n);
			for (size_t i = 0; i < n; i++)
			{
				push_back(x);
			}
		}
//通过迭代器构造
		vector(iterator begin, iterator end)
			:_start(nullptr)
			, _finish(nullptr)
			, _eos(nullptr)
		{
			while (begin != end)
			{
				push_back(*begin);
				begin++;
			}
		}
//拷贝构造

//这里我写的时候迭代器已经写了所以直接用
vector(const vector<T>& s)
			:_start(nullptr)
			, _finish(nullptr)
			,_eos(nullptr)
		{
			T* tmp = new T[s.capacity()];
			auto it = s.begin();
			size_t i = 0;
			while (it != s.end())
			{
				tmp[i] = *it;
				it++;
				i++;
			}

			_start = tmp;
			_finish = tmp + s.size();
			_eos = tmp + s.capacity();
			
		}
///不用迭代器的
vector(const vector<T>& s)
			:_start(nullptr)
			, _finish(nullptr)
			, _eos(nullptr)
		{
			_start = new T[s.capacity()]; //开辟一块和容器v大小相同的空间
			for (size_t i = 0; i < s.size(); i++) //将容器v当中的数据一个个拷贝过来
			{
				_start[i] = s[i];
			}
			_finish = _start + s.size(); //容器有效数据的尾
			_eos = _start + s.capacity(); //整个容器的尾
		}

赋值运算符重载
使用

在这里插入图片描述
这里实现的时候直接改变了原来容器的capacity
用库里的vector会发现,如果=号右边容器的大小小于=左边,被赋值的容器是不会缩容的
在这里插入图片描述
比原来的大才改变capacity
在这里插入图片描述

模拟实现
vector<T>& operator=(const vector<T>& v)
		{
			if (this != &v) //防止自己给自己赋值
			{
				size_t this_capacity = capacity();
				delete[] _start; //释放原来的空间
				_start = new T[v.capacity()]; //开辟一块和容器v大小相同的空间
				for (size_t i = 0; i < v.size(); i++) //将容器v当中的数据一个个拷贝过来
				{
					_start[i] = v[i];
				}
				_finish = _start + v.size(); //容器有效数据的尾
				if (v.capacity() < this_capacity)
				{
					_eos = _start + this_capacity;
				}
				else 
				{
					_eos = _start + v.capacity(); //整个容器的尾
				}	
			}
			return *this; //支持连续赋值
		}
迭代器

在这里插入图片描述

使用

用迭代器进行遍历
在这里插入图片描述

模拟实现
iterator& begin()
{
	return _start;
}
iterator& end()
{
	return _finish;
}
reserve()和resize()
使用

reserver 扩容不扩size
resize扩容并且扩size,顺便初始化扩出来的size
在这里插入图片描述

模拟实现

这里注意模拟实现可能会踩坑的使用memcpy拷贝问题

void reserve(size_t new_capacity)
		{
			if (new_capacity > capacity())
			{
				size_t sz = size();

				T* tmp = new T[new_capacity];
				if (_start)
				{
					/*memcpy(tmp, _start, sizeof(T) * size()); */ // 再把原空间的数据拷贝到新空间,并释放原有的旧空间。
					for (size_t i = 0; i < sz; i++) {
						// 如果T是int,一个一个拷贝没问题
						// 如果T是string等自定义问题,一个一个拷贝调用的是T的深拷贝,也不会出问题。
						tmp[i] = _start[i];
					}
					delete[] _start;
				}

				_start = tmp;                    // 指向新空间
				_finish = tmp + sz;			     // 现场算size() 会有问题,因为start已经被更新成tmp了
				_eos = _start + new_capacity;
			}
		}
void resize(size_t new_capacity, const T& val = T())
		{
			if (new_capacity < size())
			{
				_finish = _start + new_capacity;
			}
			else {
				if (new_capacity > capacity()) {   // 检查是否需要扩容
					reserve(new_capacity);
				}
				while (_finish != _start + new_capacity) {   // 初始化
					*_finish = val;  // 按val初始化,默认缺省为 T()
					_finish++;
				}
			}
		}
push_back()和pop_back
使用

在这里插入图片描述

模拟实现
		void push_back(const T& x)
		{
			if (_finish == _eos) {
				// 扩容
				reserve(capacity() == 0 ? 4 : capacity() * 2);
			}

			//插入数据
			*_finish = x;
			_finish++;
		}
        void pop_back()
		{
			assert(_start);
			_finish--;
		}
swap()
void swap(vector<T>& v)
		{
			//交换容器当中的各个成员变量
			::swap(_start, v._start);
			::swap(_finish, v._finish);
			::swap(_eos, v._eos);
		}
insert()
		void insert(iterator pos,const T& val)
		{
			if (capacity() == size())
			{
				size_t len = pos - _start;
				size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
				reserve(newcapacity);
				pos = _start + len; // 通过len找到pos在增容后的容器当中的位置 //原因:因为reserve扩容是将数据据拷贝给了另一个新的空间,这里的pos在扩容后是指向旧的空间的 ,此时已经被释放了
			}
			iterator end = _finish;
			//0 1 2 3 4
			//0 1 q 2 3 4  
			while (end > pos )
			{
				*end = *(end - 1);
				end--;
			}
			*pos = val; //将数据插入到pos位置
			_finish++; //数据个数增加一个,_finish后移
			
		}
erase()
iterator erase(iterator pos,iterator behind_pos = nullptr)
		{
			assert(size()!=capacity());
			if (!behind_pos)
			{
				auto it = pos + 1;
				while (it != _finish)
				{
					*(it - 1) = *it;
				}
				_finish--;
				return pos;
			}
			else
			{
				assert(behind_pos > pos && behind_pos < _finish);
				size_t gap = behind_pos - pos;
				auto it = pos;
				auto behind_it = behind_pos ;
 				while (behind_it != _finish)
				{
					*it = *behind_it;
					it++;
					behind_it++;
				}
				_finish -= gap;
				return pos;
			}
		}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/515245.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【Apache Doris】周FAQ集锦:第 1 期

【Apache Doris】周FAQ集锦&#xff1a;第 1 期 SQL问题数据操作问题运维常见问题其它问题关于社区 欢迎查阅本周的 Apache Doris 社区 FAQ 栏目&#xff01; 在这个栏目中&#xff0c;每周将筛选社区反馈的热门问题和话题&#xff0c;重点回答并进行深入探讨。旨在为广大用户和…

SD-WAN国际网络专线:高效、合规且可靠的跨境连接解决方案

在数字化时代&#xff0c;企业对跨境网络连接的需求日益增长。SD-WAN技术作为一种新兴的解决方案&#xff0c;正逐渐成为构建跨境网络连接的首选。本文将探讨SD-WAN国际网络专线的发展现状、合规性要求以及选择时需要考虑的关键因素。 SD-WAN技术&#xff1a;跨境网络连接的新…

STM32F407 FSMC并口读取AD7606

先贴一下最终效果图.这个是AD7606并口读取数据一个周期后的数据结果. 原始波形用示波器看是很平滑的. AD7606不知为何就会出现干扰, 我猜测可能是数字信号干扰导致的. 因为干扰的波形很有规律. 这种现象基本上可以排除是程序问题. 应该是干扰或者数字信号干扰,或者是数字和模拟…

MT3017 上色

思路&#xff1a;使用分治&#xff0c;在每个连续区域递归调用heng()和shu() #include <bits/stdc.h> using namespace std; int n, m; int h[5005];int shu(int l, int r) {return r - l 1; } int heng(int l, int r) {int hmin 0x3f3f3f3f;for (int i l; i < r;…

关于C#操作SQLite数据库的一些函数封装

主要功能&#xff1a;增删改查、自定义SQL执行、批量执行&#xff08;事务&#xff09;、防SQL注入、异常处理 1.NuGet中安装System.Data.SQLite 2.SQLiteHelper的封装&#xff1a; using System; using System.Collections.Generic; using System.Data.SQLite; using System.…

EDM邮件推广营销工具多少钱?

云衔科技&#xff0c;凭借专业的技术研发实力与丰富的行业经验&#xff0c;倾力打造了一款智能EDM&#xff08;Electronic Direct Mail&#xff09;邮件营销系统解决方案&#xff0c;以精准、高效、定制化的服务&#xff0c;为企业开启全新的营销之旅。至于价格&#xff0c;云衔…

计算机笔记(3)续20个

41.WWW浏览器和Web服务器都遵循http协议 42.NTSC制式30帧/s 44.三种制式电视&#xff1a;NTSC&#xff0c;PAL&#xff0c;SECAM 45.IP&#xff0c;子网掩码白话文简述&#xff1a; A类地址&#xff1a;取值范围0-127&#xff08;四段数字&#xff08;127.0.0.0&#xff09…

Hadoop和zookeeper集群相关执行脚本(未完,持续更新中~)

1、Hadoop集群查看状态 搭建Hadoop数据集群时&#xff0c;按以下路径操作即可生成脚本 [test_1analysis01 bin]$ pwd /home/test_1/hadoop/bin [test_01analysis01 bin]$ vim jpsall #!/bin/bash for host in analysis01 analysis02 analysis03 do echo $host s…

docker安装jenkins 2024版

docker 指令安装安装 docker run -d --restartalways \ --name jenkins -uroot -p 10340:8080 \ -p 10341:50000 \ -v /home/docker/jenkins:/var/jenkins_home \ -v /var/run/docker.sock:/var/run/docker.sock \ -v /usr/bin/docker:/usr/bin/docker jenkins/jenkins:lts访问…

利用Python将TXT文件中的经纬度数据转换为JSON格式

在处理地理空间数据时&#xff0c;经常需要将数据从一种格式转换为另一种格式&#xff0c;以便于后续的分析或可视化。本文将介绍如何使用Python脚本将存储在TXT文件中的经纬度数据转换为JSON格式。 一、背景介绍 经纬度数据是地理信息系统&#xff08;GIS&#xff09;中的基…

关于ansible的模块 ③

转载说明&#xff1a;如果您喜欢这篇文章并打算转载它&#xff0c;请私信作者取得授权。感谢您喜爱本文&#xff0c;请文明转载&#xff0c;谢谢。 接《关于Ansible的模块①》和《关于Ansible的模块②》&#xff0c;继续学习ansible的user模块。 user模块可以增、删、改linux远…

BugKu:Simple SSTI

1.进入此题 2.查看源代码 可以知道要传入一个名为flag的参数&#xff0c;又说我们经常设置一个secret_key 3.flask模版注入 /?flag{{config.SECRET_KEY}} 4.学有所思 4.1 什么是flask&#xff1f; flask是用python编写的一个轻量web开发框架 4.2 SSTI成因&#xff08;SST…

[图解]DDD领域驱动设计伪创新-通用语言05

0 00:00:01,060 --> 00:00:04,370 甚至有的人把这个当成恩典 1 00:00:08,730 --> 00:00:11,500 他认为这个对技术人员有好处 2 00:00:13,010 --> 00:00:14,790 他掌握了主动权 3 00:00:15,730 --> 00:00:16,501 这样的话 4 00:00:16,501 --> 00:00:18,430 你…

CANoe自带的TCP/IP协议栈中TCP的keep alive机制是如何工作的

TCP keep alive机制我们已经讲过太多次,车内很多控制器的TCP keep alive机制相信很多开发和测试的人也配置或者测试过。我们今天想知道CANoe软件自带的TCP/IP协议栈中TCP keep alive机制是如何工作的。 首先大家需要知道TCP keep alive的参数有哪些?其实就三个参数:CP_KEEP…

JVM之常用监控工具

JVM之常用监控工具 jps jinfo 获取配置信息 基本语法 jinfo [options] <pid>常用选项 -sysprops&#xff1a;显示JVM进程的系统属性。-flags&#xff1a;显示用于启动JVM的命令行标志和VM选项。-flag <name>&#xff1a;显示指定JVM标志的当前值。-flag [|-]&…

【JSON2WEB】 12基于Amis-admin的动态导航菜单树

【JSON2WEB】01 WEB管理信息系统架构设计 【JSON2WEB】02 JSON2WEB初步UI设计 【JSON2WEB】03 go的模板包html/template的使用 【JSON2WEB】04 amis低代码前端框架介绍 【JSON2WEB】05 前端开发三件套 HTML CSS JavaScript 速成 【JSON2WEB】06 JSON2WEB前端框架搭建 【J…

Firefox 关键词高亮插件的简单实现

目录 1、配置 manifest.json 文件 2、编写侧边栏结构 3、查找关键词并高亮的方法 3-1&#xff09; 如果直接使用 innerHTML 进行替换 4、清除关键词高亮 5、页面脚本代码 6、参考 1、配置 manifest.json 文件 {"manifest_version": 2,"name": &quo…

配置zookeeper的时候三个节点都启动了但是查询zookeeper的角色的时候显示没启动成功

场景 搭建了一个音乐平台数仓&#xff0c;一共有五个节点&#xff0c;其中三个节点配置zookeeper&#xff0c;我的操作是先把这三个节点的zookeeper全部启动&#xff0c;然后再分别查询各自zookeeper的角色。出现了一下问题&#xff1a; Error contacting service. It is proba…

网络层

网络层主要负责两方面的事情 1.地址管理&#xff1a;制定一系列的规则&#xff0c;通过地址&#xff0c;描述出网络中的设备的位置 2.路由选择&#xff1a;网络环境是非常复杂的。从一个节点到另外一个节点之间&#xff0c;存在很多条不同的路径&#xff0c;通过路由选择来筛…

【nc工具信息传输】

nc&#xff0c;全名叫 netcat&#xff0c;它可以用来完成很多的网络功能&#xff0c;譬如端口扫描、建立TCP/UDP连接&#xff0c;数据传输、网络调试等等&#xff0c;因此&#xff0c;它也常被称为网络工具的 瑞士军刀 。 nc [-46DdhklnrStUuvzC] [-i interval] [-p source_po…