Jamzy Wang

life is a struggle,be willing to do,be happy to bear~~~

Vector内存管理详解

2012-07-22 21:49

原创声明:本作品采用知识共享署名-非商业性使用 3.0 版本许可协议进行许可,欢迎转载,演绎,但是必须保留本文的署名(包含链接),且不得用于商业目的。

vector内存分配

在C++ STL中,vector是用内建(build-in)的动态数组(dynamic array)实现的。动态数组是相对于静态数组(数组大小不变)而言的,在C++中普通的数组的大小是固定的,在初始化的时候就确定了,使用的时候不能超过其范围,比如:

栈上:

1
int a[100] = {0};

堆上:

1
auto *p = new int(100); memset(p, 0, sizeof(int));

静态数组的缺点就是数组的大小不能改变,如果需要改变数组的大小,就需要手动再重新申请一个数组,再将原来的数组中的元素逐个拷贝到新的数组中。动态数组就是会自动根据需要扩展容量的数组,一般动态数组的实现示例如下述伪代码所示:

1
2
3
4
5
6
7
function insertEnd(dynarray a, element e)
    if (a.size = a.capacity)
        // resize a to twice its current capacity:
        a.capacity  a.capacity * 2
        // (copy the contents to the new memory location here)
    a[a.size]  e
    a.size  a.size + 1

从上述伪代码中可以看到动态数组用sizecapacity两个变量来表示动态数组的使用情况,其中size表示动态数组中元素的个数,capacity表示在不重新分配内存前提下动态数组总共可以拥有的元素的个数。

(图源)

往动态数组中插入元素时,数组会先判断当前的size是否小于capacity,如果是则直接插入元素,如果否则重新申请一块内存区域,将原来的数组中的元素拷贝到这块新的内存中,再将需要插入的新元素插入。

考虑一个问题,往动态数组中插入元素的时间复杂度是多少?

注:动态数组中插入元素的摊还时间复杂度为O(1)

摊还时间复杂度:长期而言,大量操作将按某个时间复杂度进行,但单一操作却可能花费比平均值更长的时间,用大量操作的时间复杂度来表征所有操作的时间复杂度,这个时间复杂度被叫作摊还时间复杂度。

为一个动态数组追加元素,运行时间将取决于动态数组是否尚有备用内存。如果内存足够,就是常数时间复杂度,因为在尾端加入一个新元素不需要移动其他任何元素。如果备用内存不足,就不再属于常数时间复杂度,因为你必须配置足够的内存并搬动(复制)它们,实际耗用时间取决于当时元素的个数,一般而言,分配内存操作是非常耗时的,在程序实际运行过程中,应该尽量避免频繁的内存分配。

既然vector使用动态数组实现的,那么vector的内存管理方式自然与动态数组相似。vector会配置比其所容纳的元素所需更多的内存,这一特性可以很大程度上提高vector的性能。vector中有一个与大小有关的函数capacity(),它返回vector实际能够容纳的元素数量。如果超越这个数量,vector就有必要重新配置内存存储器。在gcc version 4.8.1下vector内存的增长如下例所示:

1
2
3
4
5
6
vector<int> vec(2,10);  //size:2 capacity:2
vec.push_back(10);      //size:3 capacity:4
vec.push_back(10);      //size:4 capacity:4
vec.push_back(10);      //size:5 capacity:8
vec.push_back(10);      //size:6 capacity:8
vec.push_back(10);      //size:7 capacity:8

需要指出的是,不同的STL实现,vector的内存增长方式可能不同(原理大同小异),比如在VS2013下vector的内存增长方式就不同于gcc 4.8.1(下面的讨论都是基于SGI的STL实现):

此处输入图片的描述

vector中的所谓动态增加大小,并不是在原空间之后分配连续的新空间(因为无法保证原空间之后尚有可供配置的空间),而是以原大小的某个倍数另外配置一块较大空间,然后将原内容拷贝过来,然后才开始在原内容之后构造新元素,并释放空间。具体的分配过程如下:

1) 分配一块大小为当前容量的某个倍数的新内存,在大多数是实现中,vector和string的容量每次以2倍的次数增加。

2) 把容器的所有元素从旧的内存复制到新的内存中。

3) 析构掉内存中的对象。

4) 释放掉就内存。

在vector中,一旦引起空间重新配置,指向原vector的所有reference、pointers、iterators就都失效了。

考虑到以上这些分配、释放、复制和析构步骤,vector内存的重新分配会非常耗时,会大大影响系统的性能。那么在vector使用中如何避免内存频繁分配呢?主要有两种方式:

1.使用reserve()保留适当容量:

1
2
std::vector<int> v;     //size 0,capacity 0
v.reserve(80);          //size 0,capacity 80

2.初始化期间就向构造函数传递附加参数,构造出足够的空间:

1
std::vector<T> v(5);    //size 0,capacity 80

vector基本操作的时间复杂度

vector基本操作的时间复杂度取决于其底层实现,也就是动态数组相关操作的时间复杂度。这里需要指出一点:

一般而言,STL容器只提供通常具备良好时间效能的成员函数(所谓的良好的时间效能,通常意味具有常数复杂度或对数复杂度)

STL实现的这种特性可以防止程序员调用性能很差的函数。基于此:vector并未提供push_front(),因为其时间性能很差(在vector头端安插一个元素,需要移动全部元素。)

Constructors

此处输入图片的描述

Accessors

此处输入图片的描述

Modifiers

此处输入图片的描述

vector迭代器失效场景

  • push_back(vlaue) 操作导致vector发生内存重分配,所有迭代器失效(不是必然)。
1
2
3
4
vector<int> vec = { 1, 2, 3, 4 };//size:4 capacity:4
auto iter = vec.begin();
vec.push_back(5);   //size:5 capacity:8
cout << *iter << endl;//迭代器已经失效,运行错误
  • insert(iterator, value) 操作导致vector发生内存重分配,所有迭代器失效(不是必然)。
1
2
3
4
vector<int> vec(5,0);//size:5 capacity:5
auto temp = ++vec.begin();
vec.insert(vec.begin(), 4);//size:6 capacity:10
cout << *temp << endl;//迭代器已经失效,运行错误
  • erase(iterator), erase(begin,end) 操作会导致指向删除点及其后元素的迭代器全部失效。
1
2
3
4
vector<int> vec(5,0);//size:5 capacity:5
auto temp = vec.begin();
vec.erase(vec.begin());//size:4 capacity:5
cout << *temp << endl;//迭代器已经失效,运行错误

那么如何防止发生此类错误呢?

程序中如果有push_back()insert(iterator, value)erase(iterator)操作,之后必须用vector.being()操作重新获得迭代器

vector vs 普通数组

在C++中一般强烈推荐使用vector而不是普通的数组。普通的数组存在下面一些问题:

  • 没有检查下标是否出界。(请注意,有些容器类, 如std::vector ,含有不检查下标的元素访问方法。)
  • 数组通常要求从堆中分配内存(见下文的例子),在这种情况下你必须确定手动分配内存最终被删除(即使例外被抛出的情况下)。当你使用容器类,内存管理是自动处理的,但是当你使用数组的时候,你必须手动编写大量代码(不幸的是,通常需要一些技巧)。例如,除了编写代码来析构所有的对象和delete内存之外,对于数组你通常还需要添加额外的try和catch块来析构所有对象和delete内存,然后再重新引发异常。这是个真正的苦差事,如这里所示。当使用容器类, 事情将会更简单。
  • 不能插入元素到数组中间,甚至添加到数组的末尾,除非你是通过堆分配的数组,即使如此,你必须分配一个新的数组和复制所有的元素。
  • 容器类给可以传递引用或值,但数组不能:数组总是通过引用传递。如果你想模拟数组的值传递,你必须手动编写代码来明确复制数组元素(可能从堆中分配),以及编写代码来清理数组的拷贝。如果使用容器类,这一切都是自动处理。
  • 如果你的函数有一个非静态局部数组(即“auto”数组),那么你不能返回该数组。但是如果是容器类对象,那么情况将不是这样。

使用vector可以避免上述问题,同时可以大大提高开发效率。

Ref

Comments