C++ STL的vector扩容比例

如题所述

第1个回答 2022-07-31

在vs下，vector 在插入新的元素时，如果容量已满的时候需要扩容为原容量的1.5倍
如果扩容是个常量（M），即下次扩容的容量为上次的M+K，若共有N个元素需要添加进vector(push_back)
则共需要N/M次扩容，若第一次容量为1，下一次1+M时需要复制1次，再下一次1+M```,1+KM(>=N)
则添加N个元素需要时间复杂度：

平均时间复杂度为O(N)

如果扩容量是倍数（M），级下次扩容的容量为上次的MK，同理，共需要次，若第一次容量为1，下一次扩容为M时需要复制1次，再下一次M次···，M^K (>=N)
则添加N个元素需要时间复杂度：

平均时间复杂度为O(1)

对于增长的倍数，一般不大于2，因为若倍数为2，参考如下分配：

由于两倍扩容，因此每次都是正好比上一次分配的空间大，因此之前分配的空间无法再复用
而若是1.5倍，同样的例子：

可知，经历了几次扩容，之前的空间可以复用

相似回答

vector c++ 用法答：vector 是向量类型，它可以容纳许多类型的数据，如若干个整数，所以称其为容器。vector 是C++ STL的一个重要成员，使用它时需要包含头文件：includevector;一、vector的初始化 (1) vectorint a(10); //定义了10个整型元素的向量（尖括号中为元素类型名，它可以是任何合法的数据类型），但没有给出初...

c++,可以大概讲一下关于vector、map的作用吗?答：(1)vector有自动扩容操作,每次扩容伴随着“配置新空间 / 移动旧数据 / 释放旧空间”的操作,因此有一定时间成本。 (2)vector提供了reserve接口,如果能够对元素个数有大概了解,可以一开始就分配合适的空间。 (3)vector的内存空间是连续的,对插入元素的操作而言,在vector尾部插入才是合适的选择。维护的是一个连续线性...

关于C++ STL vector的问题答：你的情况没有报错是因为某些编译器的vector会在你的19的基础上多申请一部分空间，但是size还是19，所以back也只会是a[18]。另外[]算是一种地址查找运算符，并不会增加vector的size。

C++如何在vector的一个元素中添加多个数据?答：1、可以从数组构造比如int a[] = { 0,1,3,5,6,4,2... };vector<int> v( a, a + sizeof( a ) / sizeof( a[0] ) );2、动态添加就只有用push_back了可以用resize预置vector的容量，这样就能免除push_back由于空间超过默认分配的定量内存时而重分配更大的一块新空间并把原内容重...

c++ stl里的向量vector非常好用,那么它是怎么实现的呢答：STL源码剖析》。其实vector本身的实现并不会太复杂，它的实现思路也很简单，但是设计层面的一些取舍就需要经过仔细考量了。一般来说，STL是一个足够坚实的后盾，我们会频繁地使用它，以构建健壮高效的软件。能够理解STL里的一些设计思想和实现方式，对提高我们的编程思维和编程能力会所帮助。

C++ vector用法是什么?答：\x0d\x0a \x0d\x0a举例：\x0d\x0avector v1; // 创建空容器，其对象类型为string类\x0d\x0avector v2(10); // 创建有10个具有初始值（即空串）的string类对象的容器\x0d\x0avector v3(5, "hello"); // 创建有5个值为“hello”的string类对象的容器\x0d\x0avector...

C++ STL vector erase函数中,有没有重新分配内存?答：include <vector>#include <iostream>int main(){ std::vector<int> v{ 1, 2, 3, 4, 5, 6, 7 }; auto p = v.end() - 2; std::cout << &v[0] << "\t" << *p << "\t" << &*p << "\n"; v.erase(v.begin() + 2); std::cout << &v[0] ...

大家正在搜

vector扩容 vector扩容原理 vector怎么做到动态扩容 c++vector vector最大容量获取vector的长度 vector at vector c stl vector