STL容器之vector

1.vector的介绍及使用

1.1vector的介绍

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

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

3. 本质讲,vector使用动态分配数组来存储它的元素。当新元素插入时候,这个数组需要被重新分配大小为了增加存储空间。其做法是,分配一个新的数组,然后将全部元素移到这个数组。就时间而言,这是 一个相对代价高的任务,因为每当一个新的元素加入到容器的时候,vector并不会每次都重新分配大小。

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

5. 因此,vector占用了更多的存储空间,为了获得管理存储空间的能力,并且以一种有效的方式动态增长。

6. 与其它动态序列容器相比(deque, list and forward_list), vector在访问元素的时候更加高效,在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作,效率更低。比起list和forward_list 统一的迭代器和引用更好。

1.2 vector的使用

vector学习时一定要学会查看文档:文档链接,vector在实际中非常的重要,在实际中我们熟悉常见的接口就可以,下面列出了哪些接口是要重点掌握的。

1.2.1 vector的定义

1.2.2 vector iterator 的使用

1.2.3 vector 容量空间接口

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

1.2.4 vector 迭代器失效问题

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

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

1. 会引起其底层空间改变的操作,都有可能是迭代器失效,比如:resize、reserve、insert、assign、 push_back等。

#include <iostream>
using namespace std;
#include <vector>int main()
{vector<int> v{1,2,3,4,5,6};auto it = v.begin();// 将有效元素个数增加到100个,多出的位置使用8填充,操作期间底层会扩容// v.resize(100, 8);// reserve的作用就是改变扩容大小但不改变有效元素个数,操作期间可能会引起底层容量改变// v.reserve(100);// 插入元素期间,可能会引起扩容,而导致原空间被释放// v.insert(v.begin(), 0);// v.push_back(8);// 给vector重新赋值,可能会引起底层容量改变v.assign(100, 8);/*出错原因:以上操作,都有可能会导致vector扩容,也就是说vector底层原理旧空间被释放掉,
而在打印时,it还使用的是释放之间的旧空间,在对it迭代器操作时,实际操作的是一块已经被释放的
空间,而引起代码运行时崩溃。解决方式:在以上操作完成之后,如果想要继续通过迭代器操作vector中的元素,只需给it重新
赋值即可。*/while(it != v.end()){cout<< *it << " " ;++it;}cout<<endl;return 0;
}

2. 指定位置元素的删除操作--erase

#include <iostream>
using namespace std;
#include <vector>int main()
{int a[] = { 1, 2, 3, 4 };vector<int> v(a, a + sizeof(a) / sizeof(int));// 使用find查找3所在位置的iteratorvector<int>::iterator pos = find(v.begin(), v.end(), 3);// 删除pos位置的数据,导致pos迭代器失效。v.erase(pos);cout << *pos << endl; // 此处会导致非法访问return 0;
}

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

2.vector模拟实现

因为模拟实现中涉及到模版所以只在.h文件中对vector进行实现。

#pragma once
namespace bit
{template<class T>class vector{public:// Vector的迭代器是一个原生指针typedef T* iterator;typedef const T* const_iterator;iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}const_iterator cbegin() const{return _start;}const_iterator cend() const{return _finish;}// construct and destroyvector(){_start = nullptr;_finish = nullptr;_endOfStorage = nullptr;}vector(int n, const T& value = T()){reserve(n);for (int i = 0; i < n; i++){push_back(value);}}//initializer_list的构造vector(initializer_list<T> il){reserve(il.size());for (auto e:il){push_back(e);}}// 类模板的成员函数// 函数模板 -- 目的支持任意容器的迭代器区间初始化template<class InputIterator>vector(InputIterator first, InputIterator last){InputIterator begin = first;while (begin != last){push_back(*begin);begin++;}}vector(const vector<T>& v){reserve(v.capacity());for (auto e : v)  //这里的原因是因为范围fo调用的是begin() 但是你的begin函数的this指针是没有const属性的  现在是一个权限//放大的问题  加上刚刚的begin() const  现在的this就有了cosnt属性了  现在理解了吗  end()也是一样的{push_back(e);}//for (const auto& e : v)//{//	push_back(e);//}//const_iterator it = cbegin();//while (it != cend())//{//	push_back(*it);//	++it;//}}vector<T>& operator= (vector<T> v){swap(v);return *this;}~vector(){delete[]_start;_start = nullptr;_finish = _endOfStorage = nullptr;}// capacitysize_t size() const{return _finish - _start;}size_t capacity() const{return _endOfStorage - _start;}void reserve(size_t n){   //防止缩容if (n > capacity()){T* tmp = new T[n];size_t oldsize = size();//提前存好size防止delete _start之后size出现问题//利用for循环防止浅拷贝的问题if (_start){for (size_t i = 0; i < oldsize; ++i){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + oldsize;_endOfStorage = _start + n;}}void resize(size_t n, const T& value = T()){reserve(n);for (size_t i = 0; i < n; i++){push_back(value);}}///access///T& operator[](size_t pos){return _start[pos];}const T& operator[](size_t pos)const{return _start[pos];}///modify/void push_back(const T& x){if (_finish == _endOfStorage){size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);}*_finish = x;_finish++;}void pop_back(){--_finish;}void swap(vector<T>& v){std::swap(_start,v._start);std::swap(_finish,v._finish);std::swap(_endOfStorage,v._endOfStorage);}iterator insert(iterator pos, const T& x){assert(pos <= end());assert(pos >= begin());if (_finish == _endOfStorage){size_t len = pos - _start;size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);pos = _start + len;//扩容之后内存会变 要更新pos的位置}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *(end);end--;}*pos = x;_finish++;return pos;//返回迭代器解决迭代器失效问题}iterator erase(iterator pos){assert(pos < end());assert(pos >= begin());iterator end = pos+1 ;while (end < _finish){*(end-1) = *(end);end++;}_finish--;return  pos + 1;}private:iterator _start; // 指向数据块的开始iterator _finish; // 指向有效数据的尾iterator _endOfStorage; // 指向存储容量的尾};void test01(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);//v1.pop_back();//v1.pop_back();//v1.pop_back();//for (size_t i = 0; i < 5; i++)//{//	cout << v1[i] ;//}//cout << endl;//for (auto e : v1)//{//	cout << e;//}vector<int>::iterator it1 = v1.begin();while (it1 != v1.end()){*it1 +=2;//++和--有问题cout << *it1;it1++;}cout << endl;}void test02(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.insert(v1.begin(), 10);v1.insert(v1.begin(), 20);v1.insert(v1.begin(), 60);v1.erase(v1.begin());for (auto e : v1){cout << e<<" ";}cout << endl;}void test03(){vector<int> v1(10,1);vector<int> v2(v1.begin()+2,v1.end());//v2 = v1;for (auto e : v1){cout << e << " ";}cout << endl;for (auto e : v2){cout << e << " ";}}void test04(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);vector<int> v2=v1;for (auto e : v1){cout << e << " ";}cout << endl;for (auto e : v2){cout << e << " ";}}void test05(){//initializer_listvector<int> v1 = {1,2,5,4,6,7,8};for (auto e : v1){cout << e << " ";}cout << endl;}void test06(){vector<int> v1 = { 1,2,3,4,5 };auto it1 = v1.begin();while (it1 != v1.end())it1=v1.insert(v1.begin(), 2);{cout << *it1 << " ";it1++;}}
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

快速基于 ClickHouse + Grafana 搭建可观测性解决方案 - 分布式链路追踪篇(ClickHouse 官方博客)...

引言 在 ClickHouse&#xff0c;我们认为可观测性仅仅是另一个实时分析问题。作为一款高性能的实时分析数据库&#xff0c;ClickHouse 被用于多种场景&#xff0c;包括时间序列数据的实时分析。其应用场景的多样性推动了大量分析函数的发展&#xff0c;这些函数有助于查询大多数…

【Python】PyWebIO 初体验:用 Python 写网页

目录 前言1 使用方法1.1 安装 Pywebio1.2 输出内容1.3 输入内容 2 示例程序2.1 BMI 计算器2.2 Markdown 编辑器2.3 聊天室2.4 五子棋 前言 前两天正在逛 Github&#xff0c;偶然看到一个很有意思的项目&#xff1a;PyWebIo。 这是一个 Python 第三方库&#xff0c;可以只用 P…

Atcoder Beginner Contest 366

传送门 A - Election 2 时间限制&#xff1a;2秒 内存限制&#xff1a;1024MB 分数&#xff1a;100分 问题描述 在 AtCoder 市举行市长选举。候选人是 Takahashi 和 Aoki。 目前有 N 张有效选票投给了这两个候选人&#xff0c;并且计票正在进行中。这里&#xff0…

配置Cuttlefish 虚拟 Android 设备

google 参考资料&#xff1a; https://source.android.com/docs/setup/start?hlzh-cn https://source.android.com/docs/devices/cuttlefish/get-started?hlzh-cn Cuttlefish 开始 验证 KVM 可用性 Cuttlefish 是一种虚拟设备&#xff0c;依赖于宿主机上可用的虚拟化。 …

Laravel 使用Excel导出的文件中,指定列数据格式为日期,方便后期的数据筛选操作

背景 最近&#xff0c;后台运营人员要求导出的 Excel 文件&#xff0c; 要求能够满足对于 [下单日期] 的筛选操作&#xff0c;即满足在年份、月份上的选择 通过了解&#xff0c;发现&#xff1a; 先前导出的文件&#xff0c;默认列数据都是字符串&#xff08;文本&#xff09;格…

bia文件中码偏差对实时PPP解算分析

1. 码偏差对定位影响 码偏差对未知收敛时间有影响&#xff0c;对最终精度影响不大&#xff08;权比1000:1&#xff09;

前端工程化14-git merge 以及 git rebase。

rebase会把当前分支的 commit 放到公共分支的最后面,所以叫变基。就好像从公共分支又重新拉出来这个分支一样。 举例&#xff1a; 如果从 master 拉个feature分支出来,然后提交了几个 commit,这个时候刚好有人把他开发的东西合并到 master 了,这个时候 master 就比你拉分支的…

【Hot100】LeetCode—295. 数据流的中位数

目录 1- 思路① 添加元素实现② 计算实现 2- 实现⭐295. 数据流的中位数——题解思路 原题链接&#xff1a;295. 数据流的中位数 1- 思路 利用优先级队列实现一个大顶堆和一个小顶堆大顶堆用来存放较小的元素&#xff0c;小顶堆用来存放较大的元素 ① 添加元素实现 如果当前…

JVM知识总结(双亲委派机制)

文章收录在网站&#xff1a;http://hardyfish.top/ 文章收录在网站&#xff1a;http://hardyfish.top/ 文章收录在网站&#xff1a;http://hardyfish.top/ 文章收录在网站&#xff1a;http://hardyfish.top/ 双亲委派机制 双亲委派类加载过程 当App尝试加载一个类时&#x…

haproxy基础

HAProxy (High Availability Proxy) 是一款强大的开源负载均衡器和代理服务器。它主要用于提高 Web 应用程序和服务的可用性和性能。HAProxy 可以在 TCP 和 HTTP 层面上工作&#xff0c;并且支持多种负载均衡算法&#xff0c;广泛应用于高流量网站和大型分布式系统中。 社区版…

【数学建模】简单的优化模型-6 血管分支

背景&#xff1a;机体提供能量维持血液在血管中的流动&#xff0c;给血管壁以营养&#xff1b;克服血液流动的阻力&#xff0c;能量消耗与血管的几何形状有关。在长期进化中动物血管的几何形状已经在能量消耗最小原则下达到最优化。 问题&#xff1a;在能量消耗最小原则下&…

现代卷积神经网络

经典的CNN架构 一、早期的CNN架构 LeNet LeNet&#xff0c;&#xff08;也称为LeNet-5&#xff0c;5代表使用了2个卷积层和3个全连接层&#xff09;是一个经典的卷积神经网络架构&#xff0c;最初由Yann LeCun等人开发用于MNIST数据集手写数字&#xff08;灰度图像 输入通道…

nuPlan环境配置和开环及闭环评测

环境配置 下载nuplan mini 数据集 nuPlan Maps nuPlan Mini Split 解压并按照制定目录结构存储 ./nuplan/ |-- maps -- nuplan-v1.1-- splits-- mini为了不修改代码, 需软链目录 ln -s ./nuplan /data/sets/ 下载nuplan镜像 docker pull horizonrobotics/nuplan:cuda11.8.0…

Golang | Leetcode Golang题解之第327题区间和的个数

题目&#xff1a; 题解&#xff1a; func countRangeSum(nums []int, lower, upper int) int {var mergeCount func([]int) intmergeCount func(arr []int) int {n : len(arr)if n < 1 {return 0}n1 : append([]int(nil), arr[:n/2]...)n2 : append([]int(nil), arr[n/2:]…

Flink 实时数仓(八)【DWS 层搭建(二)流量域、用户域、交易域搭建】

前言 今天的任务是完成流量域最后一个需求、用户域的两个需求以及交易域的部分需求&#xff1b; 1、流量域页面浏览各窗口汇总表 任务&#xff1a;从 Kafka 页面日志主题读取数据&#xff0c;统计当日的首页和商品详情页独立访客数。 注意&#xff1a;一般我们谈到访客&…

H264基本原理

文章目录 引子 - 为什么要视频压缩I、 P、 B帧GOP图像序列H264编码介绍其它为什么视频格式一般为YUVH264 画质级别 参考资料 引子 - 为什么要视频压缩 一张为720x480的图像&#xff0c;用YUV420P的格式来表示&#xff0c; 其大小为&#xff1a; 720 * 480 * 1.5 约等于0.5MB。…

【深度学习与NLP】——注意力机制

1 注意力机制 1.1 学习目标 了解什么是注意力计算规则以及常见的计算规则.了解什么是注意力机制及其作用.掌握注意力机制的实现步骤. 什么是注意力: 我们观察事物时&#xff0c;之所以能够快速判断一种事物(当然允许判断是错误的), 是因为我们大脑能够很快把注意力放在事物最具…

使用Python和Flask构建简单的RESTful API

目录 环境准备 创建Flask应用 运行Flask应用 扩展功能&#xff1a;处理POST请求 注意事项 在Web开发中&#xff0c;RESTful API是一种广泛使用的架构风格&#xff0c;它允许客户端和服务器之间通过HTTP请求进行通信。Python的Flask框架以其轻量级和易于上手的特点&#xf…

XML动态sql查询当前时间之前的信息报错

如图&#xff0c;sql语句在数据库里可以正常运行但是再XML文件不可以正常运行&#xff0c;报错。 原因&#xff1a;在XML中小于号"<"是会被默认认定成文一个标签的开始&#xff0c;所以用小于号就会报错。 解决办法&#xff1a; 1.把表达式反过来改成大于号 2…

linux 源码部署polardb-x 错误汇总

前言 在linux 源码部署polardb-x 遇到不少错误&#xff0c;特在此做个汇总。 问题列表 CN 启动报错 Failed to init new TCP 详细错误如下 Caused by: Failed to init new TCP. XClientPool to my_polarx#267b21d8127.0.0.1:33660 now 0 TCP(0 aging), 0 sessions(0 runni…