C++------vector【STL】

文章目录

  • vector的介绍及使用
    • vector的介绍
    • vector的使用
  • vector的模拟实现

vector的介绍及使用

vector的介绍

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

vector的使用

需要重点掌握的接口

vector的构造函数

在这里插入图片描述


//    vector的构造int TestVector1()
{// constructors used in the same order as described above:vector<int> first;                                //空vector<int> second(4, 100);                       //4个100初始化vector<int> third(second.begin(), second.end());  //迭代器区间vector<int> fourth(third);                       //拷贝构造// 下面涉及迭代器初始化的部分，我们学习完迭代器再来看这部分int myints[] = { 16,2,77,29 };vector<int> fifth(myints, myints + sizeof(myints) / sizeof(int));cout << "The contents of fifth are:";for (vector<int>::iterator it = fifth.begin(); it != fifth.end(); ++it)cout << ' ' << *it;cout << '\n';return 0;
}

迭代器的使用，这里是左闭右开的区间
在这里插入图片描述

在这里插入图片描述

void PrintVector(const vector<int>& v)
{// const对象使用const迭代器进行遍历打印vector<int>::const_iterator it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;
}void TestVector2()
{// 使用push_back插入4个数据vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);// 使用迭代器进行遍历打印vector<int>::iterator it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;// 使用迭代器进行修改it = v.begin();while (it != v.end()){*it *= 2;++it;}// 使用反向迭代器进行遍历再打印// vector<int>::reverse_iterator rit = v.rbegin();auto rit = v.rbegin();while (rit != v.rend()){cout << *rit << " ";++rit;}cout << endl;PrintVector(v);
}

vector的扩容
在这里插入图片描述

  • capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。这个问题经常会考察，不要固化的认为，vector增容都是2倍，具体增长多少是根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本STL。
  • reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。
  • resize在开空间的同时还会进行初始化，影响size。
// reisze(size_t n, const T& data = T())
// 将有效元素个数设置为n个，如果时增多时，增多的元素使用data进行填充
// 注意：resize在增多元素个数时可能会扩容
void TestVector3()
{vector<int> v;// set some initial content:for (int i = 1; i < 10; i++)v.push_back(i);v.resize(5);v.resize(8, 100);v.resize(12);cout << "v contains:";for (size_t i = 0; i < v.size(); i++)cout << ' ' << v[i];cout << '\n';
}// 测试vector的默认扩容机制
// vs：按照1.5倍方式扩容
// linux：按照2倍方式扩容
void TestVectorExpand()
{size_t sz;vector<int> v;sz = v.capacity();cout << "making v grow:\n";for (int i = 0; i < 100; ++i) {v.push_back(i);if (sz != v.capacity()) {sz = v.capacity();cout << "capacity changed: " << sz << '\n';}}
}// 往vecotr中插入元素时，如果大概已经知道要存放多少个元素
// 可以通过reserve方法提前将容量设置好，避免边插入边扩容效率低
void TestVectorExpandOP()
{vector<int> v;size_t sz = v.capacity();v.reserve(100);   // 提前将容量设置好，可以避免一遍插入一遍扩容cout << "making bar grow:\n";for (int i = 0; i < 100; ++i) {v.push_back(i);if (sz != v.capacity()){sz = v.capacity();cout << "capacity changed: " << sz << '\n';}}
}

vector的增删查改
在这里插入图片描述
在这里插入图片描述

// 尾插和尾删：push_back/pop_back
void TestVector4()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);auto it = v.begin();while (it != v.end()) {cout << *it << " ";++it;}cout << endl;v.pop_back();v.pop_back();it = v.begin();while (it != v.end()) {cout << *it << " ";++it;}cout << endl;
}// 任意位置插入：insert和erase，以及查找find
// 注意find不是vector自身提供的方法，是STL提供的算法
void TestVector5()
{// 使用列表方式初始化，C++11新语法vector<int> v{ 1, 2, 3, 4 };// 在指定位置前插入值为val的元素，比如：3之前插入30,如果没有则不插入// 1. 先使用find查找3所在位置// 注意：vector没有提供find方法，如果要查找只能使用STL提供的全局findauto pos = find(v.begin(), v.end(), 3);if (pos != v.end()){// 2. 在pos位置之前插入30v.insert(pos, 30);}vector<int>::iterator it = v.begin();while (it != v.end()) {cout << *it << " ";++it;}cout << endl;pos = find(v.begin(), v.end(), 3);// 删除pos位置的数据v.erase(pos);it = v.begin();while (it != v.end()) {cout << *it << " ";++it;}cout << endl;
}// operator[]+index 和 C++11中vector的新式for+auto的遍历
// vector使用这两种遍历方式是比较便捷的。
void TestVector6()
{vector<int> v{ 1, 2, 3, 4 };// 通过[]读写第0个位置。v[0] = 10;cout << v[0] << endl;// 1. 使用for+[]小标方式遍历for (size_t i = 0; i < v.size(); ++i)cout << v[i] << " ";cout << endl;vector<int> swapv;swapv.swap(v);cout << "v data:";for (size_t i = 0; i < v.size(); ++i)cout << v[i] << " ";cout << endl;// 2. 使用迭代器遍历cout << "swapv data:";auto it = swapv.begin();while (it != swapv.end()){cout << *it << " ";++it;}// 3. 使用范围for遍历for (auto x : v)cout << x << " ";cout << endl;
}

vector迭代器失效问题

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

vector的模拟实现

#pragma once
#include <iostream>
#include <assert.h>
namespace vec
{template<class T>class vector{typedef T* iterator;typedef const T* const_iterator;public:vector(){}//内置类型也可以有构造函数，我们下一次再说vector(size_t n, const T& it = T()){resize(n, it);}vector(int n, const T& val = T()){resize(n, val);}template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);first++;}}size_t capacity() const{return _endofstorage - _start;}size_t size() const{return _finish - _start;}iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}void reserve(size_t n){if (n > capacity()){size_t sz = size();T* tmp = new T[n];//拷贝原有的数据if (_start){for (size_t i = 0; i < sz; i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + sz;_endofstorage = _start + n;}}void push_back(const T& x){//考虑增容的情况if (_finish == _endofstorage){size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);}//*_finish = x;//_finish++;insert(end(), x);}iterator erase(iterator pos){//考虑pos位置的合法性assert(pos >= _start && pos < _finish);//移动数据iterator p = pos + 1;while (p != _finish){*(p - 1) = *p;p++;}_finish--;return pos;}void resize(size_t n, const T& x = T()){if (n < size()){_finish = _start + n;}else{reserve(n);while (_finish != _start + n){*_finish = x;_finish++;}}}iterator insert(iterator pos, const T& x){//判断pos位置的合法性assert(pos >= _start && pos <= _finish);//考虑扩容if (_finish == _endofstorage){//解决迭代器失效问题size_t len = _finish - _start;size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);pos = _start + len;}//开始插入数据//移动数据iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;end--;}//插入数据*pos = x;_finish++;return pos;}void pop_back(){erase(--end());}T& operator[](size_t pos){assert(pos < size());return _start[pos];}const T& operator[](size_t pos) const{assert(pos < size());return _start[pos];}//拷贝构造vector(const vector<T>& v){//深度拷贝_start = new T[v.capacity()];for (size_t i = 0; i <v.size(); i++){_start[i] = v._start[i];}_finish = _start + v.size();_endofstorage = _start + v.capacity();}void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}//赋值运算符重载vector<T>& operator=(vector<T> v){swap(v);return *this;}~vector(){if (_start){delete[] _start;_start = _finish = _endofstorage = nullptr;}}void print(const vector<T>& v){for (auto e : v){std::cout << e << " ";}std::cout << std::endl;}private:iterator _start;iterator _finish;iterator _endofstorage;};
}

好的，我们下一篇再见！

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

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

相关文章

js数据类型？如何判断js数据类型？

js数据类型？如何判断js数据类型？

在JavaScript中&#xff0c;有以下几种数据类型&#xff1a; 基本数据类型&#xff08;Primitive Data Types&#xff09;&#xff1a; String&#xff08;字符串&#xff09;&#xff1a;表示文本数据&#xff0c;使用引号&#xff08;单引号或双引号&#xff09;括起来。Numb…
阅读更多...
linux运维（二）内存占用分析

linux运维（二）内存占用分析

一、centos内存高&#xff0c;查看占用内存, top命令详解 1.1: free 命令是 free 单位K free -m 单位M free -h 单位Gfree最常规的查看内存占用情况的命令 1.2: 参数说明 total 总物理内存 used 已经使用的内存 free 没有使用的内存 shared 多进程共享内存 buff/cache 读写…
阅读更多...
《TCP/IP网络编程》阅读笔记--基于 TCP 的半关闭

《TCP/IP网络编程》阅读笔记--基于 TCP 的半关闭

目录 1--基于TCP的半关闭 1-1--TCP单方面完全断开的问题 1-2--shutdown()函数 1-3--半关闭的必要性 2--基于半关闭的文件传输程序 1--基于TCP的半关闭 1-1--TCP单方面完全断开的问题 Linux 系统中的 close 函数会将 TCP Socket 的连接完全断开&#xff0c;这意味着不能收…
阅读更多...
el-table自适应列宽实现

el-table自适应列宽实现

【背景小记】 el-table的el-table-column如果不指定width的话&#xff0c;会自动设定一个宽度&#xff0c;表格内容会自动换行&#xff0c;对强迫症用户来说非常不友好&#xff0c;为了追求完美用户体验&#xff0c;所以这里需要实现两个效果&#xff1a; 1. 强制表格内容不换…
阅读更多...
CAS策略

CAS策略

CAS CAS&#xff08;Compare And Swap&#xff09;比较并交换 CAS是多线程环境下对共享变量进行修改时的一种策略&#xff0c;主要存在三个参数&#xff1a;当前值、预估值、结果 CAS采用的策略是当一个线程要对共享变量进行修改时&#xff0c;需要获取内存中共享变量的值作…
阅读更多...
小白备战大厂算法笔试(二)——数组、链表、列表

小白备战大厂算法笔试(二)——数组、链表、列表

文章目录 常见数据结构数组初始化访问元素插入元素删除元素遍历数组查找元素扩容数组关于数组 链表初始化插入节点删除节点访问节点查找节点常见类型典型应用 数组VS链表列表初始化访问元素插入与删除元素遍历列表拼接列表排序列表简单实现 常见数据结构 常见的数据结构包括数…
阅读更多...
工业4.0时代下，到底什么是智慧工厂？

工业4.0时代下，到底什么是智慧工厂？

关键词&#xff1a;智慧工厂、智慧工厂数字化、设备设施数字化、能源管理系统、动环监控、智能运维、数据采集、工业互联网 随着物联网、大数据和移动应用等新一轮信息技术的发展&#xff0c;全球化工业革命开始提上日程&#xff0c;工业转型开始进入实质阶段。作为工业4.0的最…
阅读更多...
自动化测试面试常见技术题目

自动化测试面试常见技术题目

1&#xff1a;一行代码实现1--100之和 print(sum(list(range(1,101)))) 2&#xff1a;如何在一个函数内部修改全局变量 global　　修改全局变量 局部作用域只能调用全局作用域的变量&#xff0c;但是不熊修改全局作用域的变量&#xff0c;如果想要修改全局作用域的变量需要gl…
阅读更多...
【算法】插入排序

【算法】插入排序

插入排序 插入排序代码实现代码优化 排序&#xff1a; 排序&#xff0c;就是使一串记录&#xff0c;按照其中的某个或某些关键字的大小&#xff0c;递增或递减的排列起来的操作。 稳定性&#xff1a; 假定在待排序的记录序列中&#xff0c;存在多个具有相同的关键字的记录&…
阅读更多...
一文讲解Linux内核内存管理架构

一文讲解Linux内核内存管理架构

内存管理子系统可能是linux内核中最为复杂的一个子系统&#xff0c;其支持的功能需求众多&#xff0c;如页面映射、页面分配、页面回收、页面交换、冷热页面、紧急页面、页面碎片管理、页面缓存、页面统计等&#xff0c;而且对性能也有很高的要求。本文从内存管理硬件架构、地址…
阅读更多...
RabbitMQ高级特性

RabbitMQ高级特性

目录 消息的可靠投递confirm和return Consumer Ack 消费端限流 TTL Time To Live&#xff08;存活时间/过期时间&#xff09; 死信队列&#xff08;死信交换机&#xff09; 延迟队列 日志与监控 rabbitmqctl管理和监控 消息追踪 消息的可靠投递confirm和return 持久…
阅读更多...
小程序隐私保护授权处理方式之弹窗组件

小程序隐私保护授权处理方式之弹窗组件

欢迎点击关注-前端面试进阶指南&#xff1a;前端登顶之巅-最全面的前端知识点梳理总结 *分享一个使用比较久的&#x1fa9c; 小程序隐私保护授权弹窗组件 调用wx.getUserProfile进行授权时&#xff0c;返回错误信息&#xff1a;{errMsg: “getUserProfile:fail api scope is…
阅读更多...
李宏毅-21-hw3:对11种食物进行分类-CNN

李宏毅-21-hw3:对11种食物进行分类-CNN

一、代码慢慢阅读理解总结内化&#xff1a; 1.关于torch.nn.covd2d()的参数含义、具体用法、功能&#xff1a; &#xff08;1&#xff09;参数含义&#xff1a; 注意&#xff0c;里面的“padding”参数&#xff1a;《both》side所以是上下左右《四》边都会加一个padding数量…
阅读更多...
jmeter 数据库连接配置 JDBC Connection Configuration

jmeter 数据库连接配置 JDBC Connection Configuration

jmeter 从数据库获取变量信息 官方文档参考&#xff1a; [jmeter安装路径]/printable_docs/usermanual/component_reference.html#JDBC_Connection_Configuration 引入数据库连接&#xff1a; 将MySQLjar包存放至jemter指定目录&#xff08;/apache-jmeter-3.3/lib&#xff09…
阅读更多...
K8S的CKA考试环境和题目

K8S的CKA考试环境和题目

CKA考试这几年来虽然版本在升级&#xff0c;但题目一直没有大的变化&#xff0c;通过K8S考试的方法就是在模拟环境上反复练习&#xff0c;通过练习熟悉考试环境和考试过程中可能遇到的坑。这里姚远老师详细向大家介绍一下考试的环境和题目&#xff0c;需要详细资料的同学请在文…
阅读更多...
pdf怎么转换成jpg图片？

pdf怎么转换成jpg图片？

随着数字文档的广泛应用&#xff0c;将PDF转换为JPG图片格式成为了一个常见的需求。无论是为了在网页上展示内容&#xff0c;还是为了与他人分享图片&#xff0c;以下是一些简单的方法&#xff0c;帮助您将PDF文件快速转换为高质量的JPG图片。 方法一&#xff1a;在线PDF转JPG…
阅读更多...
B-Tree 索引和 Hash 索引的对比

B-Tree 索引和 Hash 索引的对比

分析&回答 B-Tree 索引的特点 B-tree 索引可以用于使用 , >, >, <, < 或者 BETWEEN 运算符的列比较。如果 LIKE 的参数是一个没有以通配符起始的常量字符串的话也可以使用这种索引。 有时&#xff0c;即使有索引可以使用&#xff0c;MySQL 也不使用任何索引。…
阅读更多...
大数据之MapReduce

大数据之MapReduce

MapReduce概述 是一个分布式的编程框架&#xff0c;MapReduce核心功能是将用户编写的业务逻辑代码和自带默认组件整合成一个完整的分布式运算程序&#xff0c;并发运行在一个Hadoop集群上。 优点&#xff1a; 易于编程&#xff0c;简单的实现一些接口&#xff0c;就可以完成一…
阅读更多...
C高级 DAY1

C高级 DAY1

一、复习 命令行提示符 ubuntuubuntu:~$ 第一个ubuntu:用户名 第二个ubuntu:主机名 &#xff1a; ---> 分割符 ~ &#xff1a; 用户的家目录 $: 普通用户 #&#xff1a;管理员 切换用户 su 用户名---》切换至指定用户 su --》切换至超级用户 sudo 加在…
阅读更多...
excel表格怎么换行？好用的3个方法

excel表格怎么换行？好用的3个方法

excel是一款功能齐全的电子表格应用程序&#xff0c;广泛用于数据分析、记录和管理。在创建excel表格时&#xff0c;有时候我们需要在单元格中输入较长的文本内容&#xff0c;这时如何进行换行是一个常见问题。本文将为您介绍excel表格怎么换行的3种方法&#xff0c;帮助您轻松…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023