0.概述
vector动态数组, 顾名思义 ,空间可以动态变化的数组,自然与数组array非常相似.
array使用时必须一开始就定好使用空间,定好以后就不能变了,
使用途中要想让空间大一点,必须在重新开辟一块更大的内存空间,然后把原来内存空间的数据都搬运过去.
vector就不一样了,在元素加入的过程中会自动扩充空间,这样就更灵活,没有必要害怕因为内存不足就一开始开辟一个特别大的空间
那么vector是怎么实现这一特性的呢?废话不多说 直接上源码
// alloc 是sgi stl的空间配置器
template
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 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
下面将源码分为几个点依次讲解
vector维护的是一个连续的线性空间,
由于是连续线性空间,
所以其迭代器所要进行的一些操作比如:*,->, ,-, ,--等等普通的指针都可以满足
所以vector的迭代器就是普通指针.
通过普通指针也可让vector随机存取(所以vector的迭代器是random access iterator)
看一下vector源码中,它的迭代器是怎么定义的
emplate
class vector{
public:
typedef t value_type;
typedef value_type* iterator;//vector的迭代器是普通指针
};
因此，如果客户端写出这样的代码：
vector::iterator ivite;
vector::iterator svite;
ivite的型别就是int*,svitede 的型别就是shape*
在将vector的数据结构之前,先说一下vector的存储方式,
vector在使用时正常来说会有一部分正在使用的空间和一部分备用空间,总的空间大小就叫做容量
容量永远大于等于其大使用空间大小,如果相等就是满载了
增加新元素时,如果元素超过了原来的容量,则下次再有新元素时整个vector就得另觅居所了
在另外一个居所上,容量将扩充至原来的两倍,如果还不够,则继续扩充
这个过程会经历"重新开辟新内存->搬运元素->释放原来的内存"
vector实现的关键在于它在内部定义了三个迭代器(指针),
一个start指向正在使用空间的头,一个fininsh指向正在使用空间的尾,一个end_of_storage表示目前可用空间的尾,
源码如下
template
class vector{
...
protected:
iterator start;
iterator finish;
iterator end_of_storage;
};
演示如下图
通过这三个迭代器,就可以实现我们想要的很多操作,比如提供首尾标示,大小,容量,空容器判断,[ ]运算符,最前端元素,最后端元素等
template
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);}
...
};
先用例子说明一下vector的内存扩容机制
下面将结合它的构造函数说明它是怎么开辟内存的
结合它的主要成员函数(push_back,pop_back,insert.erase,clear)是怎么操作内存的
结合它的析构函数说明它是怎么释放内存的
-
内存扩容
扩容原理概述
新增元素：vector通过一个连续的数组存放元素，
如果集合已满，在新增数据的时候，就要分配一块更大的内存，
将原来的数据复制过来，释放之前的内存，在插入新增的元素；
对vector的任何操作，一旦引起空间重新配置，指向原vector的所有迭代器就都失效了 ；
初始时刻vector的capacity为0，塞入第一个元素后capacity增加为1；
不同的编译器实现的扩容方式不一样，vs2015中以1.5倍扩容，gcc以2倍扩容。
代码
#include
#include
using namespace std;
int main()
{
vector 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倍的区别：
-
begin()
返回的是 start
-
end()
返回的是 finish
-
size()
返回的是 size_type(end() - begin()) 为什么这里要这样写法，而不是直接调用 finish - start呢？侯捷大师说道：在使用比较复杂的容器的时候，直接用迭代器相减，可能会出问题，这里用 size 函数可以表示唯一确定函数的使用。
-
capacity()
返回的是 end_of_storage - begin() 的大小 也就是目前可用空间的大小。
-
empty()
只要判断是 begin() == end()即可。
-
构造函数
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 vector{
protected:
typedef simple_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
void vector::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函数
下面展示 vector::insert() 实作内容：从 position 开始，安插 n个元素，元素初值为 x。
-
-
template void vector::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 - elems_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(len); 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; } }}
注意，安插完成后，新节点将位于标兵迭代器（上例之 position，标示出安插点）所指之节点的前方—这是 stl 对于「安插动作」的标准规范。
图 4-3b 展示 insert(position,n,x) 的动作。
可以参照图片里的注解，细细体会。
-
插入点、备用空间大小、待插入元素数量等角度进行分类：
1-1 插入点之后元素个数大于新增元素个数：
a. 将finish之前的n个元素移到finish之后
b. finish变更为finish n得到newfinish
c. 将position之后到oldfinish - n之间的元素后移到oldfinish位置
d. 从position开始填充n个x
1-2 插入点之后元素小于新增元素个数
a. 将差值补到finish之后
b. finish变更为finish n - elems_after得到newfinish
c. 将position到oldfinish的元素拷贝到newfinish之后
d. 在position到oldfinish之间插入x
2. 备用空间小于新增元素个数
a. 申请空间，old_size max(old_size, n)
b. 复制填充：
c. 将原vector插入点之前的元素拷贝到新空间
d. 将新增元素填入新空间
e. 将原vector插入点之后的元素拷贝到新空间
-
erase函数
下面展示 erase(first, last)的动作。
-
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
void vector::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().swap(v1);
//方法二：
vector v_temp;
v1.swap(v_temp);
分析：方法一是将 v1 直接和空的vector交换，原内存当然就被销毁了。
第二种方法是曲线销毁，先定义一个临时变量。由于临时变量没有被初始化，所以，缓冲区大小为0.那么，当 v1 与它交换后，v1 原来占用的缓冲区就被销毁了。而临时变量 v_temp 调用析构函数来进行释放空间。
1. 头文件
#include
2. vector声明及初始化
vector vec; //声明一个int型向量
vector vec(5); //声明一个初始大小为5的int向量
vector vec(10, 1); //声明一个初始大小为10且值都是1的向量
vector vec(tmp); //声明并用tmp向量初始化vec向量
vector tmp(vec.begin(), vec.begin() 3); //用向量vec的第0个到第2个值初始化tmp
int arr[5] = {1, 2, 3, 4, 5};
vector vec(arr, arr 5); //将arr数组的元素用于初始化vec向量
//说明：当然不包括arr[4]元素，末尾指针都是指结束元素的下一个元素，
//这个主要是为了和vec.end()指针统一。
vector 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::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
reverse(vec.begin(), vec.end());
元素排序
#include
sort(vec.begin(), vec.end()); //采用的是从小到大的排序
//如果想从大到小排序，可以采用上面反转函数，也可以采用下面方法:
bool comp(const int& a, const int& b) {
return a > b;
}
sort(vec.begin(), vec.end(), comp);
-
vector与list的区别与应用？
（1）vector为存储的对象分配一块连续的地址空间，随机访问效率很高。但是插入和删除需要移动大量的数据，效率较低。尤其当vector中存储
的对象较大，或者构造函数复杂，则在对现有的元素进行拷贝的时候会执行拷贝构造函数。
（2）list中的对象是离散的，随机访问需要遍历整个链表，访问效率比vector低。但是在list中插入元素，尤其在首尾插入，效率很高，只需要改变元素的指针。
（3）vector是单向的，而list是双向的；
（4）向量中的iterator在使用后就释放了，但是链表list不同，它的迭代器在使用后还可以继续用；链表特有的；
使用原则：
（1）如果需要高效的随机存取，而不在乎插入和删除的效率，使用vector；
（2）如果需要大量高效的删除插入，而不在乎存取时间，则使用list；
（3）如果需要搞笑的随机存取，还要大量的首尾的插入删除则建议使用deque，它是list和vector的折中；
-
vector和deque的区别？
deque与vector的主要不同之处在于：
1. 两端都能快速安插和删除元素，这些操作可以在分期摊还的常数时间（amortized constant time）内完成。
2. 元素的存取和迭代器的动作比vector稍慢。
3. 迭代器需要在不同区块间跳转，所以它非一般指针。
4. 因为deque使用不止一块内存（而vector必须使用一块连续内存），所以deque的max_size()可能更大。
5. 不支持对容量和内存重新分配时机的控制。不过deque的内存重分配优于vector，因为其内部结构显示，deque不必在内存重分配时复制所有元素。
6. 除了头尾两端，在任何地方安插或删除元素，都将导致指向deque元素的所有pointers、references、iterators失效。
7. deque的内存区块不再被使用时，会自动被释放。deque的内存大小是可自动缩减的。
8. deque与vector组织内存的方式不一样。在底层，deque按“页”（page）或“块”（chunk）来分配存储器，每页包含固定数目的元素。而vector只分配一块连续的内存。例如，一个10m字节的vector使用的是一整块10m字节的内存，而deque可以使用一串更小的内存块，比如10块1m的内存。所以不能将deque的地址（如&deque[0]）传递给传统的c api，因为deque内部所使用的内存不一定会连续。
deque的下述特性与vector差不多：
1. 在中部安插、删除元素的速度较慢。
2. 迭代器属于random access iterator（随机存取迭代器）。
优先使用vector，还是deque?
c 标准建议：vector是那种应该在默认情况下使用的序列。如果大多数插入和删除操作发生在序列的头部或尾部时，应该选用deque。