一篇文章搞懂STL中的顺序容器之Vector
Table of Contents
0.概述
vector动态数组, 顾名思义 ,空间可以动态变化的数组,自然与数组array非常相似.
array使用时必须一开始就定好使用空间,定好以后就不能变了,
使用途中要想让空间大一点,必须在重新开辟一块更大的内存空间,然后把原来内存空间的数据都搬运过去.
vector就不一样了,在元素加入的过程中会自动扩充空间,这样就更灵活,没有必要害怕因为内存不足就一开始开辟一个特别大的空间
那么vector是怎么实现这一特性的呢?废话不多说 直接上源码
// alloc 是SGI STL的空间配置器
template<class T,class Alloc=alloc>
class vector{
public:
//vector的嵌套型别定义
typedef T value_type;
typedef value_type* pointer;
typedef value_type* iterator;
typedef value_type* reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
protected:
//simple_alloc 是SGI STL的空间配置器
typedef simple_alloc<value_type,Alloc> data_allocator;
iterator start;//表示目前使用空间的头
iterator finish;//表示目前使用空间的尾
iterator end_of_storage;//表示目前可用空间的尾
void insert_aux(iterator position,const T& x);
void deallocate(){
if(start)
data_allocator::deallocate(start,end_of_storage-start);
}
void fill_initialize(size_type n,const T& value)
{
start=allocate_and_fill(n,value);
finish=start+n;
end_of_storage=finsih;
}
public:
iterator begin(){return start;}
iterator end(){return finish;}
size_type size() const {return size_type(end()-begin());}
size_type capacity() const {return size_type(end_of_storage-begin());}
bool empty() const {return begin()==end();}
reference operator[](size_type n) {return *(begin()+n);}
vector():start(0),finish(0),end_of_storage(0){}
vector(size_type n,const T& value){fill_initialize(n,value);}
vector(int n,const T& value){fill_initialize(n,value);}
vector(long n,const T& value){fill_initialize(n,value);}
explicit vector(size_type n){fill_initialize(n,T());}
~vector(){
destroy(start,finish);
deallocate();
}
reference front(){return *begin();}//第一个元素
reference back() {return *(end()-1);}//最后一个元素
void push_back(const T& x){//将元素插入至最尾端
if(finish!=end_of_storage){
construct(finish,x);
++finish;
}
else
insert_aux(end(),x);
}
void pop_back(){//将最尾端元素取出
--finish;
destroy(finish);//全局函数
}
iterator erase(iterator position){//清除某位置上的元素
if(position+1 !=end)
{
copy(position+1,finish,position);//后续元素往前移动
}
--finish;
destroy(finish);
return position;
}
void resize(size_type new_size,const T& x)
{
if(new_size<size())
erase(begin()+new_size,end());
else
insert(end(),new_size-size(),x);
}
void resize(size_type new_size){resize(new_size,T());}
void clear() {erase(begin(),end());}
protected:
//配置空间并填满内容
iterator allocate_and_fill(size_type n,const T& x)
{
iterator result=data_allocator::allocate(n);
uninitialized_fill_n(result,n,x);
return result;
}
};
下面将源码分为几个点依次讲解
1.迭代器(成员变量)
vector维护的是一个连续的线性空间,
由于是连续线性空间,
所以其迭代器所要进行的一些操作比如:*,->,+,-,++,--等等普通的指针都可以满足
所以vector的迭代器就是普通指针.
通过普通指针也可让vector随机存取(所以vector的迭代器是Random Access Iterator)
看一下vector源码中,它的迭代器是怎么定义的
emplate<class T,class Alloc=alloc>
class vector{
public:
typedef T value_type;
typedef value_type* iterator;//vector的迭代器是普通指针
};
因此,如果客户端写出这样的代码:
vector<int>::iterator ivite;
vector<Shape>::iterator svite;
ivite的型别就是int*,svitede 的型别就是Shape*
2.数据结构(成员变量)
在将vector的数据结构之前,先说一下vector的存储方式,
vector在使用时正常来说会有一部分正在使用的空间和一部分备用空间,总的空间大小就叫做容量
容量永远大于等于其大使用空间大小,如果相等就是满载了
增加新元素时,如果元素超过了原来的容量,则下次再有新元素时整个vector就得另觅居所了
在另外一个居所上,容量将扩充至原来的两倍,如果还不够,则继续扩充
这个过程会经历"重新开辟新内存->搬运元素->释放原来的内存"
vector实现的关键在于它在内部定义了三个迭代器(指针),
一个start指向正在使用空间的头,一个fininsh指向正在使用空间的尾,一个end_of_storage表示目前可用空间的尾,
源码如下
template<class T,class Alloc=alloc>
class vector{
...
protected:
iterator start;
iterator finish;
iterator end_of_storage;
};
演示如下图
通过这三个迭代器,就可以实现我们想要的很多操作,比如提供首尾标示,大小,容量,空容器判断,[ ]运算符,最前端元素,最后端元素等
template <class T,class Alloc=alloc>
class vector{
...
public:
iterator begin(){return start;}
iterator end(){return finish;}
size_type size() const {return size_type(end()-begin());}
size_type capacity() const {return size_type(end_of_storage-begin());}
bool empty() const {return begin()==end();}
reference operator[](size_type n){return *(begin()+n);}
reference front(){return *begin();}
reference back() {return *(end()-1);}
...
};
3.内存管理(成员函数)
先用例子说明一下vector的内存扩容机制
下面将结合它的构造函数说明它是怎么开辟内存的
结合它的主要成员函数(push_back,pop_back,insert.erase,clear)是怎么操作内存的
结合它的析构函数说明它是怎么释放内存的
-
内存扩容
扩容原理概述
新增元素:Vector通过一个连续的数组存放元素,
如果集合已满,在新增数据的时候,就要分配一块更大的内存,
将原来的数据复制过来,释放之前的内存,在插入新增的元素;
对vector的任何操作,一旦引起空间重新配置,指向原vector的所有迭代器就都失效了 ;
初始时刻vector的capacity为0,塞入第一个元素后capacity增加为1;
不同的编译器实现的扩容方式不一样,VS2015中以1.5倍扩容,GCC以2倍扩容。
代码
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> vec;
cout << vec.capacity() << endl;
for (int i = 0; i<10; ++i)
{
vec.push_back(i);
cout << "size: " << vec.size() << endl;
cout << "capacity: " << vec.capacity() << endl;
}
system("pause");
return 0;
}
输出:
GCC输出
VS2015输出
分析:
可以根据输出看到,vector是以2倍的方式扩容的。这里让我产生了两个疑问:
1.为什么要成倍的扩容而不是一次增加一个固定大小的容量呢?
2.为什么是以两倍的方式扩容而不是三倍四倍,或者其他方式呢?
第一个问题:
以成倍方式增长
假定有 n 个元素,倍增因子为 m;
完成这 n 个元素往一个 vector 中的 push_back操作,需要重新分配内存的次数大约为 logm(n);
第 i 次重新分配将会导致复制 m^(i) (也就是当前的vector.size() 大小)个旧空间中元素;
n 次 push_back 操作所花费的时间复制度为O(n):
m / (m - 1),这是一个常量,均摊分析的方法可知,vector 中 push_back 操作的时间复杂度为常量时间.
一次增加固定值大小
假定有 n 个元素,每次增加k个;
第i次增加复制的数量为为:100i
n 次 push_back 操作所花费的时间复杂度为O(n^2):
均摊下来每次push_back 操作的时间复杂度为O(n);
总结:对比可以发现采用采用成倍方式扩容,可以保证常数的时间复杂度,而增加指定大小的容量只能达到O(n)的时间复杂度,因此,使用成倍的方式扩容
。
第二个问题:
根据查阅的资料显示,考虑可能产生的堆空间浪费,成倍增长倍数不能太大,
使用较为广泛的扩容方式有两种,以2二倍的方式扩容,或者以1.5倍的方式扩容。
以2倍的方式扩容,导致下一次申请的内存必然大于之前分配内存的总和,
导致之前分配的内存不能再被使用,所以最好倍增长因子设置为(1,2)之间:
知乎上看到一个很好的解释:
C++ STL中vector内存用尽后,为啥每次是两倍的增长,而不是3倍或其他数值?
借用他的一张图来说明2倍与1.5倍的区别:
-
构造函数
vector提供很多构造函数,
其中一个vector(size_type n,const T& value)允许我们指定空间大小以及初值:
我们看一下他是怎么实现的
//构造函数,允许指定vector大小n和初值value
vector(size_type n,const T& value)
{
fill_initialize(n,value);
}
//填充并予以初始化
void fill_initialize(suze_type n,const T& value)
{
start=allocate_and_fill(n,value);
finish=start+n;
end_of_storage=finish;
}
//配置而后填充
iterator allocate_and_fill(size_type n,const T& x)
{
iterator result=data_allocator::allocate(n);//配置n个元素空间
uninitialized_fill_n(result,n,x);
return result;
}
vector缺省参数使用alloc作为空间配置器,并据此另外定义了一个data_allocator,为的是更方便以元素大小为配置单位:
template <class T,class Alloc=alloc>
class vector{
protected:
typedef simple_alloc<value_type,Alloc> data_allocator;
...
};
//data_allocator::allocate(n)表示配置n个元素空间
-
push_back()函数
-
当我们以push_back()将新元素插入于vector尾端时,该函数首先检查是否还有备用空间,如果有就直接在备用空间上构造函数,并调整迭代器finish,使vector变大。如果没有备用空间,就扩充空间(重新配置,移动数据,释放原空间)
正如我们上面所说的
增加新元素时,如果元素超过了原来的容量,则下次再有新元素时整个vector就得另觅居所了
在另外一个居所上,容量将扩充至原来的两倍,如果还不够,则继续扩充
这个过程会经历"重新开辟新内存->搬运元素->释放原来的内存"
所谓动态增加大小,并不是在原空间之后接续新空间(因为无法保证原空间之后尚有可供配置的空间),而是以原大小的两倍另外配置一块较大空间,然后将原内容拷贝过来,然后才开始在原内容之后构造新元素,并释放原空间。
因此,对vector的任何操作,一旦引起空间重新配置,指向原vector的所有迭代器就都失效了。void push_back(const T& x) { if(finish!=end_of_storage) { //还有备用空间 construct(finish,x);//全局函数 ++finish; } else { insert_aux(end(),x);//vector member function } }
template <class T,class Alloc> void vector<T,Alloc>::insert_aux(iterator position,const T& x) { if(finish=!=end_of_storage){ //还有备用空间 //在备用空间起始处构造一个元素,并以vector最后一个元素值为其初值 construct(finish,*(finish-1)); //调整水位 ++finish; T x_copy=x; copy_backward(position,finish-2,finish-1); *position=x_copy; } else{ // 已无备用空间 const size_type old_size=size(); const size_type len=old_size!=0?2*ols_size:1; //以上原则,如果原大小为0,则配置1(个元素) //如果原大小不为0,则配置原大小的两倍 //前半段用来放置元数据,后半段用来放置新数据 iterator new_start=data_allocator::allocate(len);//实际配置 iterator new_finish=new_start; try{ //将原vector的内容拷贝到新的vector new_finish=uninitialized_copy(start,position,new_start); //为新元素设定初值x construct(new_finish,x); //调整水位 ++new_finish; //将安插点的原内容也拷贝过来 new_finish=uninitialized_copy(position,finish,new_finish); } catch(...){ destroy(new_start,new_finish); data_allocator::deallocate(new_start,len); throw; } //析构并释放原vector destory(begin(),end()); deallocate(); //调整迭代器,指向新vector start=new_start; finish=new_finish; end_of_storage=new_start+len; } }
-
pop_back函数
-
insert函数
-
erase函数
-
clear函数
//将尾端元素拿掉,并调整大小 void pop_back(){ --finish;//将尾端标记往前移动一格,表示将放弃尾端元素 destroy(finish); } //清除[first,last]中的所有元素 iterator erase(iterator first,iterator last){ iterator i=copy(last,finish,first); destroy(i,finish); finish=finish-(last-first); return first; } //清除某个位置上的元素 iterator erase(iterator position) { if(position+1!=end()){ } --finish; destroy(finish); return position; } void clear() {erase(begin(),end());} //下面是vector::insert()实现内容 //从position开始,插入n个元素,元素初值为x template<class T,class Alloc> void vector<T,Alloc>::insert(iterator position,size_type n,const T& x) { if(n!=0) { //当n!=0才进行以下操作 if(size_type(end_of_storage-finish)>=n) { //备用空间大于等于“新增元素个数” T x_copy=x; //以下计算插入点之后的现有元素个数 const size_type elems_after=finish-position; iterator old_finish=finish; if(elems_after>n) { //“插入点之后的现有元素个数”大于“新增元素个数” uninitialized_copy(finish-n,finish,finish); finish+=n;//将vector尾端标记后移 copy_backward(position,old_finish-n,old_finish); fill(position,position+n,x_copy);//从插入点开始填入新值 } else{ //“插入点之后的现有元素个数”小于等于“新增元素个数” uninitialized_fill_n(finish,n-eles_after,x_copy); finish+=n-elems_after; uninitialized_copy(position,old_finish,finish); finish+=elems_after; fill(position,old_finish,x_copy); } } else{ //备用空间小于“新增元素个数”(那就必须配置额外的内存) //首先决定新长度:旧长度的两倍,或旧长度+新增元素个数 const size_type old_size=size(); const size_type len=old_size+max(old_size,n); //配置新的vector空间 iterator new_start=data_allocator::allocate(n); iterator new_finish=new_start; __STL_TRY{ //以下首先将旧vector的插入点之前的元素复制到新空间 new_finish=uninitialized_copy(start,position,new_start); //以下再将新增元素(初值皆为n)填入新空间 new_finish=uninitialized_fill_n(new_finish,n,x); //以下再将旧vector的插入点之后的元素复制到新空间 new_finish=uninitialized_copy(position,finish,new_finish); } #ifdef __STL_USE_EXCEPTIONS catch(...){ //如有异常发生,实现“commit or rollback” semantics destroy(new_start,new_finish); data_allocator::deallocate(new_start,len); throw; } #endif /*__STL_USE_EXCEPTIONS*/ //以下清除并释放旧的vector destroy(start,finish); deallocate(); //以下调整水位标记 start=new_start; finish=new_finish; end_of_storage=new_start+len; } } }
析构函数
~vector() { // destroy the object _Tidy(); } void _Tidy() {// free all storage if (_Myfirst != 0) {// something to free, destroy and deallocate it #if _HAS_ITERATOR_DEBUGGING this->_Orphan_all(); #endif /* _HAS_ITERATOR_DEBUGGING */ _Destroy(_Myfirst, _Mylast);//以迭代器的方式,销毁vector中的每一个元素 this->_Alval.deallocate(_Myfirst, _Myend - _Myfirst);//释放缓冲区的空间 } _Myfirst = 0, _Mylast = 0, _Myend = 0;//指针全部归零 }
我们可以看出,删除容器中的数据的时候,缓冲区的大小并不会改变,而在缓冲区内的数据被清除了。
我们知道,只有在调用析构函数的时候,vector 才会自动释放缓冲区。那么,如何根据自己的需要,强制释放缓冲区呢?
有两种方法:// 方法一: vector<int>().swap(v1); //方法二: vector<int> v_temp; v1.swap(v_temp);
分析:方法一是将 v1 直接和空的vector交换,原内存当然就被销毁了。
第二种方法是曲线销毁,先定义一个临时变量。由于临时变量没有被初始化,所以,缓冲区大小为0.那么,当 V1 与它交换后,v1 原来占用的缓冲区就被销毁了。而临时变量 v_temp 调用析构函数来进行释放空间。4.使用方法
1. 头文件 #include<vector> 2. vector声明及初始化 vector<int> vec; //声明一个int型向量 vector<int> vec(5); //声明一个初始大小为5的int向量 vector<int> vec(10, 1); //声明一个初始大小为10且值都是1的向量 vector<int> vec(tmp); //声明并用tmp向量初始化vec向量 vector<int> tmp(vec.begin(), vec.begin() + 3); //用向量vec的第0个到第2个值初始化tmp int arr[5] = {1, 2, 3, 4, 5}; vector<int> vec(arr, arr + 5); //将arr数组的元素用于初始化vec向量 //说明:当然不包括arr[4]元素,末尾指针都是指结束元素的下一个元素, //这个主要是为了和vec.end()指针统一。 vector<int> vec(&arr[1], &arr[4]); //将arr[1]~arr[4]范围内的元素作为vec的初始值 3. vector基本操作 (1). 容量 向量大小: vec.size(); 向量最大容量: vec.max_size(); 更改向量大小: vec.resize(); 向量真实大小: vec.capacity(); 向量判空: vec.empty(); 减少向量大小到满足元素所占存储空间的大小: vec.shrink_to_fit(); //shrink_to_fit (2). 修改 多个元素赋值: vec.assign(); //类似于初始化时用数组进行赋值 末尾添加元素: vec.push_back(); 末尾删除元素: vec.pop_back(); 任意位置插入元素: vec.insert(); 任意位置删除元素: vec.erase(); 交换两个向量的元素: vec.swap(); 清空向量元素: vec.clear(); (3)迭代器 开始指针:vec.begin(); 末尾指针:vec.end(); //指向最后一个元素的下一个位置 指向常量的开始指针: vec.cbegin(); //意思就是不能通过这个指针来修改所指的内容,但还是可以通过其他方式修改的,而且指针也是可以移动的。 指向常量的末尾指针: vec.cend(); (4)元素的访问 下标访问: vec[1]; //并不会检查是否越界 at方法访问: vec.at(1); //以上两者的区别就是at会检查是否越界,是则抛出out of range异常 访问第一个元素: vec.front(); 访问最后一个元素: vec.back(); 返回一个指针: int* p = vec.data(); //可行的原因在于vector在内存中就是一个连续存储的数组,所以可以返回一个指针指向这个数组。这是是C++11的特性。 (4)算法 遍历元素 vector<int>::iterator it; for (it = vec.begin(); it != vec.end(); it++) cout << *it << endl; //或者 for (size_t i = 0; i < vec.size(); i++) { cout << vec.at(i) << endl; } 元素翻转 #include <algorithm> reverse(vec.begin(), vec.end()); 元素排序 #include <algorithm> sort(vec.begin(), vec.end()); //采用的是从小到大的排序 //如果想从大到小排序,可以采用上面反转函数,也可以采用下面方法: bool Comp(const int& a, const int& b) { return a > b; } sort(vec.begin(), vec.end(), Comp);
5.参考 -
- 1.https://www.cnblogs.com/zhonghuasong/p/5975979.html
- 2.https://blog.****.net/sinat_33442459/article/details/75142672#commentBox
- 3.<STL源码剖析> 侯捷