Vector_vector时间复杂度-程序员宅基地

技术标签: C++  c++  leetcode  动态规划  

Vector容器:

Vector相比于 array 空间的运用更灵活, array是静态空间,一旦配置了就不能再改变。 而vector 是动态空间会随着数据量的增加

自动扩容(扩容机制 (重新开辟内存, 复制, 为什么二倍扩容))

首先 自动扩容为什么是成倍的 而不是一次性增加多少数值这样子。

(原因:因为成倍扩容它的复杂度平均下来是 常数级, 而一次性增加多少数值是O(n))

为什么是2倍

原因: (首先不一定是2倍 也有可能是1.5倍)考虑可能产生的堆空间浪费,成倍增长倍数不能太大,使用较为广泛的扩容方式有两种,以2二倍的方式扩容,或者以1.5倍的方式扩容。

以2倍的方式扩容,导致下一次申请的内存必然大于之前分配内存的总和,导致之前分配的内存不能再被使用(这句话表述是不是有点问题),所以最好倍增长因子设置为(1,2)之间: 

Vector 底层实现:

vector,底层是一块具有连续内存的数组,vector的核心在于其长度自动可变。vector的数据结构主要由三个迭代器(指针)来完成:指向首元素的start,指向尾元素的finish和指向内存末端的end_of_storage。vector的扩容机制是:当目前可用的空间不足时,分配目前空间的两倍或者目前空间加上所需的新空间大小(取较大值),容量的扩张必须经过“重新配置、元素移动、释放原空间”等过程。

Vector 查找 插入 删除的时间复杂度

vector,vector支持随机访问(通过下标),时间

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_46911332/article/details/121452185

智能推荐

服务器数据收发测试软件,Packet Sender(UDP/TCP网络测试工具) v7.0.5-程序员宅基地

文章浏览阅读4k次。Packet Sender(UDP/TCP网络测试工具)是一个开源实用程序,允许发送和接收TCP、UDP和SSL(加密的TCP)数据包,主线分支正式支持Windows、Mac和桌面Linux,其他地方可以重新编译和重新分发分组发送器。Packet Sender软件特色数据包发送方可以在您选择的端口上发送和接收UDP、TCP和SSL。所有服务器和客户端可以同时运行。100%免费开源。没有广告,没有捆..._packet sender

Java 使用工具类 Collections.sort() 对集合根据时间排序(DESC)_java list 日期 desc-程序员宅基地

文章浏览阅读1.2k次,点赞2次,收藏2次。# 使用Coollections.sort(@NotNull List<T> list,@NotNull Comparator<? super T> c)Collections.sort(warcEnterInfos, new Comparator<WARCEnterInfo>() { @Override public int compare..._java list 日期 desc

sql语句 改变日期格式_易语言sql语言修改日期框-程序员宅基地

文章浏览阅读7.2k次。一般存入数据库中的时间格式为yyyy-mm-ddhh:mm:ss 如果要转换为yyyy-mm-dd 短日期格式.可以使用convert函数.下面是sqlserver帮助中关于convert函数的声明:使用 CONVERT:CONVERT (data_type[(length)],expression[,style])参数expression是任何有效的 Micr_易语言sql语言修改日期框

转载和积累系列 - Nodejs HTTP多线程_node http 多线程吗-程序员宅基地

文章浏览阅读3.1k次。译自:http://developer.yahoo.net/blog/archives/2010/07/multicore_http_server_with_nodejs.html(稍有修改), 转载请指明原文链接:http://www.grati.org/?p=307简单地说,NodeJS是一个使用了Google高性能V8引擎 的服务器端JavaScript实现。它提供了一个(几乎)_node http 多线程吗

Android Studio Error:Connection timed out: connect._android studio connection timed out-程序员宅基地

文章浏览阅读813次。最近在配置使用android studio时遇到了个错误Android Studio Error:Connection timed out: connect.,纠结了很久,后来在网上看到了一篇文章,试了下很有帮助,在这里给大家也看一下,希望能帮到同样错误的小伙伴Error:Connection timed out: connect. If you are behind an HTTP proxy,..._android studio connection timed out

php判断是否为手机浏览器_php 判断为手机浏览器-程序员宅基地

文章浏览阅读3.8k次。function is_mobile(){ // returns true if one of the specified mobile browsers is detected // 如果监测到是指定的浏览器之一则返回true $regex_match="/(nokia|iphone|android|motorola|^mot_php 判断为手机浏览器

随便推点

单片机(八)__ds18b20测试温度_void ds_reset-程序员宅基地

文章浏览阅读949次。首先我们看一下ds18b20的结构图:通过结构图,我们大致能了解一些DS18B20的内部结构,重点是我们要知道,他是如何测温度的,以及温度是怎么计算为我们想要的值的。ds18b20采用的是单总线结构,我们来了解它是如何初始化的:通过它初始化的时序图,我们可以写出程序:void ds_reset()//初始化{ ds = 1;_void ds_reset

vue出现空白页面的可能情况_前端导出v-if是空白-程序员宅基地

文章浏览阅读4.2k次。如果在父组件中注册了组件,然后又用路由出口跳转到这个组件,当点击页面刷新的时候,就会出现空白的页面,解决方法就删除父组件里的注册。_前端导出v-if是空白

在ubuntu20.10上安装unity3d-程序员宅基地

文章浏览阅读1.1k次。打开下载页面,点击start here点击agree and download下载完成后开始安装先授权后安装启动前要登陆_在ubuntu20.10上安装unity3d

离线安装Cloudera Manager 5和CDH5(最新版5.9.3) 完全教程(四)数据库安装(单节点)_cdh5.9 重新配置数据库-程序员宅基地

文章浏览阅读159次。离线安装Cloudera Manager 5和CDH5(最新版5.9.3) 完全教程(四)数据库安装(单节点)一、卸载CentOS自带的MySQL1.1 查看之前是否安装过mysql[root@master mysql]# rpm -qa|grep -i mysqlmysql-libs-5.1.71-1.el6.x86_64[root@master mysql]#1.2 卸载自带的..._cdh5.9 重新配置数据库

安装gitbook sourcetree或命令行推送数据到Githup上 No “xxx“ file (or is ignored) which查看软件安装目录 operation not permi_"filenotfounderror: no \"readme\" file (or is igno-程序员宅基地

文章浏览阅读1.1k次。mac如何安装gitbook、sourcetree、typera等。如何使用sourcetree或命令行推送数据到Githup上。以及在安装的过程中,解决FileNotFoundError: No "README" file (or is ignored)的问题。使用which gitbook可以查看Gitbook安装到哪里。解决operation not permitted的权限问题。......_"filenotfounderror: no \"readme\" file (or is ignored)"

FTP-----局域网内部远程桌面_远程登陆ftp-程序员宅基地

文章浏览阅读1.8k次。从此文学会远程桌面(局域网内部)。_远程登陆ftp