C++

vector的内存管理以及3种顺序容器的选择

TheHuPost newsletter上线了, 欢迎大家订阅! 
对C++, Java,JavaScript,Python等编程语言有兴趣的,也可以看看编程语言.
也欢迎大家来论坛与我讨论

vector size 相关的接口

C++与容器大小相关的函数有以下几个:

size()   //返回当前元素个数

max_size()    // 当前能存储元素的最多个数

capacity()     // 容器在重新获得更多存储空间时,可以存储的元素总个数

reserve()     //指定vector 预留多少个元素的存储空间 ,当reserve ()< capacity() 时没有动作

shrink_to_fit()   //C++11新增接口,释放掉当前多余的capacity, 调用后 size() = capacity()

empty()   // 判断当前vector 是否为空,等价于size() = 0;

vector的内存管理方式

  • 2.1 vector容器为了获取快速的随机访问,元素必须在内存中连续存储。
  • 2.2 为了避免每次增加或删除元素时都需要重新开辟存储空间, vector 实际分配的内存比当前需要的内存会多一些,即capacity()  一般会大于size()
  • 2.3 vector 新增元素时, 若size 没有超出capacity, 则不需要重新分配空间 
  • 2.4 当size 超过capacity 时,  capacity 一般会自动扩展为当前的2倍,或者也可以通过reserve() 来人工指定vector预留多少空间
  • 2.5 默认空的vector capacity 为0,然后增加到1,然后增加的规律是2倍;  若有通过reserve() 制定初始大小,则在初始大小的基础上double
  • 2.6 max_size() 反应了在特定机器上vector 对象理论上能存储元素个数的上限,maxsize: 1073741823
  • 2.7 当调用pop_back() 接口释放掉存储的元素时,std::vector 不会重新分配内存,减少capacity()

    网上有的说法是,增加是double ,减少时每次减1/4, std::vector 是不会减少的

示例

示例1: 默认起始大小

以下示例程序比较清晰的揭示了这个过程:

typedef vector<int> vectors;



void printVectInfo(vectors& ivec)
{
   cout<<"size: "<<ivec.size()<<endl;
   cout<<"maxsize: "<<ivec.max_size()<<endl;
   cout<<"capacity: "<<ivec.capacity()<<endl;
   cout<<endl;
}



int main(int argc, char* argv[])
{
   vector<int> ivec;
   printVectInfo(ivec);



   for(vectors::size_type i= 0 ; i!= 50 ; ++i)
   {
       ivec.push_back(i);
       printVectInfo(ivec);
   }



   return 0;
}

程序执行结果:

size: 0
maxsize: 1073741823
capacity: 0

size: 1
maxsize: 1073741823
capacity: 1

size: 2
maxsize: 1073741823
capacity: 2

size: 3
maxsize: 1073741823
capacity: 4

size: 4
maxsize: 1073741823
capacity: 4

size: 5
maxsize: 1073741823
capacity: 8

size: 6
maxsize: 1073741823
capacity: 8

size: 7
maxsize: 1073741823
capacity: 8

size: 8
maxsize: 1073741823
capacity: 8

size: 9
maxsize: 1073741823
capacity: 16

size: 10
maxsize: 1073741823
capacity: 16

size: 11
maxsize: 1073741823
capacity: 16

size: 12
maxsize: 1073741823
capacity: 16

size: 13
maxsize: 1073741823
capacity: 16

size: 14
maxsize: 1073741823
capacity: 16

size: 15
maxsize: 1073741823
capacity: 16

size: 16
maxsize: 1073741823
capacity: 16

size: 17
maxsize: 1073741823
capacity: 32

size: 18
maxsize: 1073741823
capacity: 32

size: 19
maxsize: 1073741823
capacity: 32

size: 20
maxsize: 1073741823
capacity: 32

size: 21
maxsize: 1073741823
capacity: 32

size: 22
maxsize: 1073741823
capacity: 32

size: 23
maxsize: 1073741823
capacity: 32

size: 24
maxsize: 1073741823
capacity: 32

size: 25
maxsize: 1073741823
capacity: 32

size: 26
maxsize: 1073741823
capacity: 32

size: 27
maxsize: 1073741823
capacity: 32

size: 28
maxsize: 1073741823
capacity: 32

size: 29
maxsize: 1073741823
capacity: 32

size: 30
maxsize: 1073741823
capacity: 32

size: 31
maxsize: 1073741823
capacity: 32

size: 32
maxsize: 1073741823
capacity: 32

size: 33
maxsize: 1073741823
capacity: 64

size: 34
maxsize: 1073741823
capacity: 64

size: 35
maxsize: 1073741823
capacity: 64

size: 36
maxsize: 1073741823
capacity: 64

size: 37
maxsize: 1073741823
capacity: 64

size: 38
maxsize: 1073741823
capacity: 64

size: 39
maxsize: 1073741823
capacity: 64

size: 40
maxsize: 1073741823
capacity: 64

size: 41
maxsize: 1073741823
capacity: 64

size: 42
maxsize: 1073741823
capacity: 64

size: 43
maxsize: 1073741823
capacity: 64

size: 44
maxsize: 1073741823
capacity: 64

size: 45
maxsize: 1073741823
capacity: 64

size: 46
maxsize: 1073741823
capacity: 64

size: 47
maxsize: 1073741823
capacity: 64

size: 48
maxsize: 1073741823
capacity: 64

size: 49
maxsize: 1073741823
capacity: 64

size: 50
maxsize: 1073741823
capacity: 64

示例2: reserve() 设置起始大小

在上面的代码中加入人工干预的reserve() :

int main(int argc, char* argv[])
{
   vector<int> ivec;
   printVectInfo(ivec);
   ivec.reserve(10);


   for(vectors::size_type i= 0 ; i!= 50 ; ++i)
   {
       ivec.push_back(i);
       printVectInfo(ivec);
   }



   return 0;
}

再执行的结果:

size: 0
maxsize: 1073741823
capacity: 0

size: 1
maxsize: 1073741823
capacity: 10

size: 2
maxsize: 1073741823
capacity: 10

size: 3
maxsize: 1073741823
capacity: 10

size: 4
maxsize: 1073741823
capacity: 10

size: 5
maxsize: 1073741823
capacity: 10

size: 6
maxsize: 1073741823
capacity: 10

size: 7
maxsize: 1073741823
capacity: 10

size: 8
maxsize: 1073741823
capacity: 10

size: 9
maxsize: 1073741823
capacity: 10

size: 10
maxsize: 1073741823
capacity: 10

size: 11
maxsize: 1073741823
capacity: 20

size: 12
maxsize: 1073741823
capacity: 20

size: 13
maxsize: 1073741823
capacity: 20

size: 14
maxsize: 1073741823
capacity: 20

size: 15
maxsize: 1073741823
capacity: 20

size: 16
maxsize: 1073741823
capacity: 20

size: 17
maxsize: 1073741823
capacity: 20

size: 18
maxsize: 1073741823
capacity: 20

size: 19
maxsize: 1073741823
capacity: 20

size: 20
maxsize: 1073741823
capacity: 20

size: 21
maxsize: 1073741823
capacity: 40

size: 22
maxsize: 1073741823
capacity: 40

size: 23
maxsize: 1073741823
capacity: 40

size: 24
maxsize: 1073741823
capacity: 40

size: 25
maxsize: 1073741823
capacity: 40

size: 26
maxsize: 1073741823
capacity: 40

size: 27
maxsize: 1073741823
capacity: 40

size: 28
maxsize: 1073741823
capacity: 40

size: 29
maxsize: 1073741823
capacity: 40

size: 30
maxsize: 1073741823
capacity: 40

size: 31
maxsize: 1073741823
capacity: 40

size: 32
maxsize: 1073741823
capacity: 40

size: 33
maxsize: 1073741823
capacity: 40

size: 34
maxsize: 1073741823
capacity: 40

size: 35
maxsize: 1073741823
capacity: 40

size: 36
maxsize: 1073741823
capacity: 40

size: 37
maxsize: 1073741823
capacity: 40

size: 38
maxsize: 1073741823
capacity: 40

size: 39
maxsize: 1073741823
capacity: 40

size: 40
maxsize: 1073741823
capacity: 40

size: 41
maxsize: 1073741823
capacity: 80

size: 42
maxsize: 1073741823
capacity: 80

size: 43
maxsize: 1073741823
capacity: 80

size: 44
maxsize: 1073741823
capacity: 80

size: 45
maxsize: 1073741823
capacity: 80

size: 46
maxsize: 1073741823
capacity: 80

size: 47
maxsize: 1073741823
capacity: 80

size: 48
maxsize: 1073741823
capacity: 80

size: 49
maxsize: 1073741823
capacity: 80

size: 50
maxsize: 1073741823
capacity: 80

reserve() 会打乱vector本身2的n次方增长规律,但reserve后也是每次增加为先前的2倍大小

顺序容器的选择

选择标准

容器元素在内存中是否连续存储会显著影响:

  • 1.  在容器中间添加或删除元素的代价
  • 2.  随机访问元素的代价

连续存储时, 可以进行快速的随机访问,但删除或添加元素的代价很高(重新分配空间,元素拷贝);

离散存储时,可以添加或删除元素的代价很低,随机访问代价很高(需要遍历整个链表);

三种顺序容器特点

  • vector: 连续存储, 支持元素的快速随机访问
  • list: 离散存储, 快速的添加删除元素
  • deque: vector 和list 综合,支持元素随机访问,以及高效的在两端进行插入或删除

顺序容器选择

  • 1.  若程序要求随机访问元素, vector 或deque
  • 2.  要求容器中间位置添加或删除元素,list
  • 3.  首尾添加或删除元素,deque
  • 输入时在中间插入元素,然后随机访问元素,则输入时使用list ,然后对list排序, 再将list 复制到vector(使用assign实现)

1 thought on “vector的内存管理以及3种顺序容器的选择”

  1. Pingback: C++怎么提高string操作的性能? – The Hu Post

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top