STL中的vector以及简单实现

vector的简单介绍:

头文件:

#include<vector>

vector是属于STL的一员,虽然vector的英文意思是向量,但是vector就是一个顺序表;

对于vector来说,面对string的设计的复杂和冗余,vector就简洁很多了;

vector就是一个标准的模板,作为类模板,vector只能是显式实例化;

vector 学习时一定要学会查看文档: vector的文档介绍

vector的使用:

vector 在实际中非常的重要,在实际中我们熟悉常见的接口就可以,下面列出了哪些接口是要重点掌握的

构造:

(constructor) 构造函数声明
接口说明
vector() (重点)

无参构造
vector size_type n,
const value_type&val = value_type())

构造并初始化 n val
vector (const vector& x); (重点)

拷贝构造
vector (InputIterator first,
InputIterator last);
使用迭代器进行初始化构造
//对于类模板是要显式实例化的<type_name>
//无参构造
vector<int> v1;
//初始化一个数组,数组有10个1
vector<int> v2(10, 1);
//用迭代器的区间进行初始化
vector<int> v3(++v2.begin(), --v2.end());
//用其他容器的迭代器初始化
//........

迭代器:

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

位置说明

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 增删查改:

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

vector没有提供find,但是在算法中有提供find(函数模板),因为string不仅要find一个字符,还要find一个字符串,所以不用算法里面的find,string比较特殊,所以自己实现

int x;
cin >> x;
auto pos = find(v.begin(), v.end(), x);

C++要求:传迭代器区间都要传左闭右开

迭代器失效:

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

会引起其底层空间改变的操作,都有可能是迭代器失效

比如:resizereserve、insert、assign、push_back等。

1.类似于野指针:

		void reserve(size_t n){if (n > capacity()){size_t old_size = size();T* tmp = new T[n];memcpy(tmp, _start, size() * sizeof(T));delete[] _start;_start = tmp;_finish = tmp + old_size;_end_of_storage = _start + n;}}
void insert(iterator pos, const T& x)
{if (_finish == _end_of_storage){//空间满了reserve(capacity() == 0 ? 4 : capacity() * 2);}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;
}

问题出现在pos还指向在原来的空间,没有跟着变换到新的空间,所以,解决该问题的方法就是还原pos的相对位置:

void insert(iterator pos, const T& x)
{if (_finish == _end_of_storage){//空间满了size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;
}

另外:insert以后pos就实效了,不要去访问:因为pos还是指向旧的空间,其实就是形参的改变不影响实参,pos依旧是指向原来的位置,形参的改变并没有影响到实参,但是严格来说也不能加引用,这样就把带有常性的临时对象和普通引用放到一起了,权限放大了 ,如果const的话,那就不能修改了:(实在要访问修改的话,库中有说明,要访问就更新这个失效的迭代器的值)

int x;
cin >> x;
auto p = find(v.begin(), v.end(), x);
if (p != v.end())
{/*v.insert(p, 40);(*p) *= 10;*/p = v.insert(p, 40);(*(p + 1)) *= 10;
}
print_vector(v);

更新这个失效的迭代器的值:

iterator insert(iterator pos, const T& x)
{if (_finish == _end_of_storage){//空间满了size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;return pos;
}

总之:还是不要访问的好 ,本质就是类似野指针。(空间扩容)

2.位置意义已经发生改变:

在没有发生扩容的时候,pos位置并没有跟随数据的向后移动而跟随,整体来说,pos已经不是指向原来数据,位置意义也已经发生改变,这种情况也可以称为迭代器失效(上面情况是空间扩容带来的类似野指针的行为)

3. 注意:Linux下,g++编译器对迭代器失效的检测并不是非常严格,处理也没有vs下极端:

// 1. 扩容之后,迭代器已经失效了,程序虽然可以运行,但是运行结果已经不对了
int main()
{vector<int> v{ 1,2,3,4,5 };for (size_t i = 0; i < v.size(); ++i)cout << v[i] << " ";cout << endl;auto it = v.begin();cout << "扩容之前,vector的容量为: " << v.capacity() << endl;// 通过reserve将底层空间设置为100,目的是为了让vector的迭代器失效v.reserve(100);cout << "扩容之后,vector的容量为: " << v.capacity() << endl;// 经过上述reserve之后,it迭代器肯定会失效,在vs下程序就直接崩溃了,但是linux下不会// 虽然可能运行,但是输出的结果是不对的while (it != v.end()){cout << *it << " ";++it;}cout << endl;return 0;
}
//程序输出:
//1 2 3 4 5
//扩容之前,vector的容量为: 5
//扩容之后,vector的容量为 : 100
//0 2 3 4 5 409 1 2 3 4 5
// 2. erase删除任意位置代码后,linux下迭代器并没有失效
// 因为空间还是原来的空间,后序元素往前搬移了,it的位置还是有效的
#include <vector>
#include <algorithm>
int main()
{vector<int> v{ 1,2,3,4,5 };vector<int>::iterator it = find(v.begin(), v.end(), 3);v.erase(it);cout << *it << endl;while (it != v.end()){cout << *it << " ";++it;}cout << endl;return 0;
}
//程序可以正常运行,并打印:
//4
///4 5
// 3: erase删除的迭代器如果是最后一个元素,删除之后it已经超过end
// 此时迭代器是无效的,++it导致程序崩溃
int main()
{vector<int> v{ 1,2,3,4,5 };// vector<int> v{1,2,3,4,5,6};auto it = v.begin();while (it != v.end()){if (*it % 2 == 0)v.erase(it);++it;}for (auto e : v)cout << e << " ";cout << endl;return 0;
}
========================================================
// 使用第一组数据时,程序可以运行
[sly@VM - 0 - 3 - centos 20220114]$ g++ testVector.cpp - std = c++11
[sly@VM - 0 - 3 - centos 20220114]$ . / a.out
1 3 5
======================================================== =
// 使用第二组数据时,程序最终会崩溃
[sly@VM - 0 - 3 - centos 20220114]$ vim testVector.cpp
[sly@VM - 0 - 3 - centos 20220114]$ g++ testVector.cpp - std = c++11
[sly@VM - 0 - 3 - centos 20220114]$ . / a.out
Segmentation fault

4. 与vector类似,string在插入+扩容操作+erase之后,迭代器也会失效 

#include <string>
void TestString()
{string s("hello");auto it = s.begin();// 放开之后代码会崩溃,因为resize到20会string会进行扩容// 扩容之后,it指向之前旧空间已经被释放了,该迭代器就失效了// 后序打印时,再访问it指向的空间程序就会崩溃//s.resize(20, '!');while (it != s.end()){cout << *it;++it;}cout << endl;it = s.begin();while (it != s.end()){it = s.erase(it);// 按照下面方式写,运行时程序会崩溃,因为erase(it)之后// it位置的迭代器就失效了// s.erase(it);++it;}
}

vector的模拟实现:

要时常注意浅拷贝带来的问题:

代码:直接在类里面实现了_and_测试代码:(放在了头文件)

#pragma once
#include<iostream>
#include<assert.h>
#include<vector>
#include<list>
using namespace std;
namespace home
{template<class T>class vector{public:typedef T* iterator;//模板typedef const T* const_iterator;//vector()//{}//写不写都会走初始化列表,有缺省值给到了(初始化)//C++11后//强制生成默认构造vector() = default;vector(const vector<T>& v){reserve(v.size());//提高效率,避免下面的扩容for (auto& e : v)//给引用,减少想string的拷贝{push_back(e);}}void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}//vector<T>& operator=(const vector<T>& v)//类里面可以用类名替换类型,类外面不行vector& operator=(vector& v){//现代:swap(v);return *this;}//迭代器区间构造//类模板的成员函数,还可以继续是函数模板//这就可以是任意类型的迭代器template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}vector(size_t n, const T& val = T()){reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}}vector(int n, const T& val = T()){reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}}~vector(){if (_start){delete[] _start;_start = _finish = _end_of_storage = nullptr;}}iterator begin(){return _start;}iterator end(){return _finish;}void clear(){_finish = _start; }const_iterator begin()const{return _start;}const_iterator end()const{return _finish;}size_t size()const{return _finish - _start;//左闭右开,相减得size数}size_t capacity()const{return _end_of_storage - _start;}void reserve(size_t n){size_t old_size = size();T* tmp = new T[n];//memcpy(tmp, _start, old_size * sizeof(T));//对于string像这种数据深拷贝类型的,对于内置类型就没什么问题,memcpy会出问题,memcpy按字节拷贝,之前的被delete,变为随机值//解决:需要深拷贝for (size_t i = 0; i < old_size; i++){tmp[i] = _start[i];//调用赋值:释放旧空间,拷贝新空间}delete[] _start;_start = tmp;_finish = tmp + old_size;_end_of_storage = tmp + n;}bool empty(){return _start == _finish;}void push_back(const T& x){if (_finish == _end_of_storage){//空间满了reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;_finish++;}void pop_back(){assert(!empty());--_finish;}//迭代器失效iterator insert(iterator pos, const T& x){assert(pos >= _start && pos <= _finish);if (_finish == _end_of_storage){//空间满了size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;return pos;}void erase(iterator pos){assert(pos >= _start && pos <= _finish);auto it = pos + 1;while (it != end()){*(it - 1) = *it;++it;}--_finish;}void resize(size_t n, const T val = T())//用默认构造去构造一个匿名对象,再去拷贝构造,但是编译器优化后是直接构造的,以后大概就是这种形式来给缺省值,但是在之前内置类型并没有构造,后来出现了模板,也有了内置类型的构造,析构概念{//n<size:删除//size<n<capacity:少的补val//n>capacity:开足够空间,少的补valif (n < size()){_finish = _start + n;}else{reserve(n);while (_finish < _start + n){*_finish = val;++_finish;}}}T& operator[](size_t i){assert(i < size());return _start[i];}const T& operator[](size_t i)const{assert(i < size());return _start[i];}private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage;};template<class T>void print_vector(const vector<T>& v){//编译器编译到这的时候,类模板是还没有被实例化的,并不知道vector<T>是什么,//类模板有一个原则://类模板没有被实例化的时候不敢到里面去取东西,因为里面的东西也有可能有各种的坑,分不清楚到底是类型还是静态成员变量//需要在前面+:typename(这就是于class的区别)//->规定:没有实例化的类模板里面取东西,编译器不能区分这里const_iterator是类型还是静态成员变量//还有一种解决方案:用autoauto  it = v.begin();while (it != v.end()){cout << *it << " ";it++;}cout << endl;for (auto e : v){cout << e << " ";}cout << endl;}//写成模板,打印各种容器(更通用)template<class Container>void print_container(const Container& v){auto  it = v.begin();while (it != v.end()){cout << *it << " ";it++;}cout << endl;for (auto e : v){cout << e << " ";}cout << endl;}void test_vector1(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.pop_back();for (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;vector<int>::iterator it = v.begin();while (it != v.end()){cout << *it << " ";it++;}cout << endl;for (auto e : v){cout << e << " ";}cout << endl;print_vector(v);vector<double> vd;vd.push_back(1.0);vd.push_back(2.2);vd.push_back(3.2);vd.push_back(4.2);vd.push_back(5.2);print_vector(vd);}void test_vector2(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);//v.push_back(5);print_vector(v);v.insert(v.begin() + 2, 30);print_vector(v);int x;cin >> x;auto p = find(v.begin(), v.end(), x);if (p != v.end()){/*v.insert(p, 40);(*p) *= 10;*/p = v.insert(p, 40);(*(p + 1)) *= 10;}print_vector(v);}void test_vector3(){int i = int();int j = int(1);int k(2);vector<int> v;v.resize(10, 1);v.reserve(20);print_container(v);cout << v.size() << endl;cout << v.capacity() << endl;v.resize(15, 2);print_container(v);v.resize(5);print_container(v);}void test_vector4(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);print_container(v);vector<int> v1 = v;print_container(v);vector<int> v2;v2.push_back(1);v2.push_back(2);v2.push_back(3);v = v2;//v1之前的空间释放掉print_container(v);vector<int> v3(v.begin()+1, v.end()-1);print_container(v3);//模板价值//任意容器迭代器初始化//要求类型是匹配的list<int> lt;lt.push_back(12);lt.push_back(22);lt.push_back(32);vector<int> v4(lt.begin(), lt.end());print_container(lt);printf("\n");print_container(v4);vector<string> v5(10,"1111111");print_container(v5);//会报错,因为有模板的选择,匹配不上/*vector<int> v6(10, 1);print_container(v6);*///解决://指定访问最后这个vector<int> v6(10u, 1);print_container(v6);//再给一个更佳的选择(现成)vector<int> v7(10, 2);print_container(v7);}void test_vector5(){vector<string> v;v.push_back("11111");v.push_back("11111");v.push_back("11111");v.push_back("11111");print_container(v);v.push_back("11111");print_container(v);}
}

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

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

相关文章

【从零开始一步步学习VSOA开发】创建VSOA的server端

创建VSOA的server端 创建工程 参考 hellovsoa 工程&#xff0c;创建 server 工程&#xff0c;工程源码修改如下&#xff1a; #include <stdio.h> #include <stdlib.h> #include <string.h> #include <netinet/in.h> #include <arpa/inet.h> #…

【数据结构面试有那些常见问题?】

&#x1f3a5;博主&#xff1a;程序员不想YY啊 &#x1f4ab;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f917;点赞&#x1f388;收藏⭐再看&#x1f4ab;养成习惯 ✨希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出…

提升实训效果,智慧校园实验室建设计划解析

在智慧校园解决方案中&#xff0c;实训管理系统的实验室建设计划功能深刻展示了基础设置建设的重要性&#xff0c;它不仅聚焦于教育资源的精准投放&#xff0c;更是教学质量与科研创新的重要推手。这一功能的核心价值&#xff0c;在于运用先进的数字化工具&#xff0c;实现从需…

RabbitMQ高级特性 - 消费者消息确认机制

文章目录 RabbitMQ 消息确认机制背景消费者消息确认机制概述手动确认&#xff08;RabbitMQ 原生 SDK&#xff09;手动确认&#xff08;Spring-AMQP 封装 RabbitMQ SDK&#xff09;AcknowledgeMode.NONEAcknowledgeMode.AUTO&#xff08;默认&#xff09;AcknowledgeMode.MANUAL…

JAVA通过debezium实时采集mysql数据

前期准备 需要提前安装mysql并且开启binlog,需要准备kafka和zookeeper环境 示例采用debezium1.9.0版本 Maven配置 <version.debezium>1.9.0.Final</version.debezium> <dependency> <groupId>io.debezium</groupId> <artifactId>debe…

Java获取exe文件详细信息:产品名称,产品版本等

使用Maven项目&#xff0c;在pom.xml文件中注入&#xff1a; <dependency><groupId>com.kichik.pecoff4j</groupId><artifactId>pecoff4j</artifactId><version>0.4.1</version></dependency> 程序代码&#xff1a; import …

Sun Frame:基于 SpringBoot 的轻量级开发框架(个人开源项目)

文章目录 &#x1f31e; Sun Frame&#xff1a;基于 SpringBoot 的轻量级开发框架&#xff08;个人开源项目&#xff09;&#x1f680; 欢迎使用 Sun Frame&#x1f31f; 项目亮点&#x1f4e6; 模块结构&#x1f310; Sun-Cloud&#x1f4e6; Sun-Common &#x1f4a1; 示例与…

微力同步如何安装使用并使用内网穿透配置公网地址远程访问

文章目录 1.前言2. 微力同步网站搭建2.1 微力同步下载和安装2.2 微力同步网页测试2.3 内网穿透工具安装 3.本地网页发布3.1 Cpolar云端设置3.2 Cpolar本地设置 4. 公网访问测试5. 结语 1.前言 私有云盘作为云存储概念的延伸&#xff0c;虽然谈不上多么新颖&#xff0c;但是其广…

主成分分析和线性判别分析

主成分分析 (PCA) PCA 是一种线性降维方法&#xff0c;通过投影到主成分空间&#xff0c;尽可能保留数据的方差。 原理 PCA 通过寻找数据投影后方差最大的方向&#xff0c;主成分是这些方向上的正交向量。 公式推理 对数据中心化&#xff1a; 其中&#xff0c;μ 是数据的…

“微软蓝屏”事件敲响网络安全的警钟

文章目录 前言一、对网络安全的警醒二、我们如何应对&#xff1f;总结 前言 “微软蓝屏”事件是一次由微软合作伙伴CrowdStrike的终端安全产品更新与操作系统内核冲突导致的全球性技术故障。这一事件不仅影响了多个国家的航空、银行、金融、零售、餐饮等多个行业&#xff0c;还…

吴恩达老师机器学习-ex8

data1 导入库&#xff0c;读取数据并进行可视化 因为这次的数据是mat文件&#xff0c;需要使用scipy库中的loadmat进行读取数据。 通过对数据类型的分析&#xff0c;发现是字典类型&#xff0c;查看该字典的键&#xff0c;可以发现又X等关键字。 import numpy as np import…

十七、Intellij IDEA2022.1.1下载、安装、激活

目录 &#x1f33b;&#x1f33b; 一、下载二、 安装三、激活 一、下载 官网下载地址 本地直接下载 目前Intellij IDEA的最新版本已经更新到了 2024.1.4&#xff0c;由于最新版本可能存在不稳定的问题&#xff0c;此处选择其他版本进行下载&#xff0c;此处以2022.1.1为例进行下…

【Spring】Bean详细解析

1.Spring Bean的生命周期 整体上可以简单分为四步&#xff1a;实例化 —> 属性赋值 —> 初始化 —> 销毁。初始化这一步涉及到的步骤比较多&#xff0c;包含 Aware 接口的依赖注入、BeanPostProcessor 在初始化前后的处理以及 InitializingBean 和 init-method 的初始…

基于STM32的智能家居安防系统教程

目录 引言环境准备智能家居安防系统基础代码实现&#xff1a;实现智能家居安防系统 门窗传感器模块视频监控模块报警与通知模块用户界面与远程控制应用场景&#xff1a;家庭安防与监控常见问题与解决方案收尾与总结 引言 随着智能家居的普及&#xff0c;家庭安防系统成为保护…

艾瑞白皮书解读(一)丨为什么说数据工程是中国企业数据治理的最佳实践?

2024年7月 艾瑞咨询公司对国内数据治理行业进行了研究&#xff0c;访问了国内多位大中型企业数据治理相关负责人&#xff0c;深度剖析中国企业在数字化转型过程中面临到的核心数据问题后&#xff0c;重磅发布《2024中国企业数据治理白皮书》&#xff08;以下简称“白皮书”&…

算法通关:017_1:二叉树及三种顺序的递归遍历

文章目录 题目思路代码运行结果 题目 二叉树及三种顺序的递归遍历 思路 代码 /*** Author: ggdpzhk* CreateTime: 2024-08-04** 二叉树及三种顺序的递归遍历* LeetCode 144. 二叉树的前序遍历* LeetCode 94. 二叉树的中序遍历* LeetCode 145. 二叉树的后序遍历* LeetCode 10…

龙迅LT8713SX 高性能TYPE-C/DP转三端口DP1.4/HDMI 2.0转换器,带音频

龙迅LT8713SX描述&#xff1a; LT8713SX是一个高性能类型-C/DP1.4到Type-C/DP1.4/HDMI2.0转换器&#xff0c;具有三个可配置的DP1.4/HDMI2.0/DP输出接口和音频输出接口。LT8713SX同时支持显示端口™单流传输&#xff08;SST&#xff09;模式和多流传输&#xff08;MST&#xf…

Adobe Acrobat不支持图片格式转换PDF文件

我在将图片格式&#xff08;PNG,JPEG&#xff09;转换为PDF的过程中遇到了如下问题&#xff1a; 单文件的解决办法——在软件外实现转换&#xff1a; 使用照片打开图片 选择打印 打印机选择Adobe PDF&#xff0c;执行打印 选择PDF文件的保存位置&#xff0c;过一会儿可以正…

基本K8s搭建Jekins+gitee项目自动部署

这里写目录标题 1.基本K8s部署安装Jekins2.设置Jenkins国内镜像源2.安装Gitee插件1.安装Gitee Plugin2.验证安装Gitee Plugin 3.新建任务1.输入任务名称2.输入你gitee上的项目链接3.测试构建 4.查看项目在k8s集群master节点的位置1.确认 Jenkins Pod 名称2.使用kubectl exec到 …

视频如何生成二维码(自动生成二维码)完整教程

在企业中&#xff0c;产品视频二维码怎么制作&#xff0c;产品二维码怎么实现微信扫码便捷观看&#xff1f;上图文教程&#xff1a;视频二维码生成器/上传视频自动生成二维码完整教程。 目前市面上有很多工具&#xff0c;可以实现&#xff0c;比如草料二维码、酷播云二维码等等…