【C++基础 04】vector详解

按照写博客的习惯一开始总要加点鸡汤文什么的,请原谅我今天想不起来。

=============================================


今天要写的内容是顺序型容器。首先,标准库定义了三种顺序容器类型:vector,list和deque(双端队列),这篇博客介绍的是vector容器。

首先要知道,vector不是一种数据类型,而是一个类模板,可以用来定义任意多种数据类型,比如说vector<int>是一种数据类型,vector<string>也是一种数据类型。使用vector之前我们要先包含头文件

#include<vector>
using std::vector;

1.vector初始化

vector<T> v1;       //初始化一个为空的vector
vector<T> v2(v1);   //v2是v1的一个副本
vector<T> v3(n,i);  //n个值为i的vector
vector<T> v4(n);    //v4含n个默认初始化值的vector(如int默认0,string默认"")

2.迭代器

每个标准库容器类型都定义了名为iterator的成员,也就是迭代器,迭代器所指向的类型为vector容器中实际存储的类型,比如

vector<int>iterator iter;
迭代器常用于遍历容器,最常见的便是begin和end操作,vector.begin()返回vector中的第一个元素,vector.end()返回末端元素的下一个。

vector<int> ivec;
for(int i = 0; i <= 10; i++)
  ivec.push_back(i);

for(vector<int>::iterator iter = ivec.begin(); iter != ivec.end(); ++iter)
{
  *iter = 0;   //遍历vector,更改值为0
}
需要注意的是,如果有元素添加或者删除,会使迭代器失效,从而需要调整迭代器的值。否则很可能会导致运行时崩溃,者点很重要。

3.vector的常用操作

添加:需要注意的是添加新元素可能会使迭代器失效,所以程序需要保证迭代器在插入或者push操作后能得到更新。

//添加元素
v.push_back(t);               //在vector尾部添加一个元素t
v.insert(iter,t);            //在迭代器iter所指向的元素前面插入元素t,返回新添加的元素的迭代器
v.insert(iter,n,t);          //在迭代器iter所指向的元素前面插入n个元素t,返回void
v.insert(iter,iter1,iter2);  //在迭代器iter所指向的元素前面插入迭代器[iter1,iter2)之间的元素(左闭右开),返回void

所有容器类型都支持关系操作符来比较大小,规则是:

//v1和v2长度和所有元素都相等,则v1=v2,否则不等。
//v1长度小于v2,但是v1所有元素和v2 相等,则 v1 < v2。
//v1和v2元素不等,则比较结果取决于第一个不相等的元素。

vector大小的操作:

v.size();      //返回v中元素的个数,返回类型 v::size_type
v.max_size();  //返回v可容纳最多元素个数
v.empty();     //判断是否为空
v.resize(n);   //调整v长度大小,使其能容纳n个元素,如果n<v.size(),则删除多出来的元素,否则添加采用值初始化的元素
v.resize(n,t); //调整v长度大小,使其能容纳n个元素,所有新添加的元素值都为t

vector访问:

v.back();   //返回v最后一个元素的引用
v.front();  //返回v第一个元素的引用
v[n];       //返回v下标为n的引用
v.at[n];    //返回v下标为n的引用

//返回的是引用,注意和迭代器的区别,迭代器返回的是指针
vector<int> v;
//迭代器
vector<int>::iterator iter = v.begin();
//引用,下面val = val2
vector<int>::reference val = v.front();
vector<int>::reference val2 = *v.begin();
vector删除操作:

v.erase(iter);        //删除iter所指向的元素,返回iter下一个元素
v.erase(iter1,iter2); //删除[iter1,iter2)之间的元素(左闭右开)
v.clear();            //全删,返回void
v.pop_back();         //删除最后一个,返回void

赋值操作:

v1 = v2;                //复制v2到v1
v1.swap(v2);            //交换内容:交换v1和v2之间的元素,速度比v2复制到v1快
v1.assign(iter1,iter2); //重新设置:将[iter1,iter2)之间的元素(左闭右开)复制到v中
v1.assign(n,t);         //重新设置:将v中重新设置为n个值为t的元素
注意swap不会使迭代器失效。

assign会将vector中所有元素删除,然后再插入新元素。assing可以用于:相同或者不同的容器内,元素类型不同但是相互兼容之间的转换赋值。(比如vector<char*>和list<string>之间的赋值)

vector<char*> v1;
for(int i = 0; i <= 10; i++)
  v1.push_back("dddd");
list<string> list1;
list1.assign(v1.begin(),b1.end());

4.vector容器自增长

首先要明白vector容器的元素在内存中是以连续的方式存放。想一下如果添加新元素的时候时候已经没有空间来容纳新元素,又不能随便找个地儿来放新元素,所以需要重新分配vector的存储空间:copy旧元素到新存储空间,插入新元素,删除旧存储空间。

如果vector在每次添加新元素的时候都这么搞一个那效率何在?所以,显然vector设计的时候也考虑到这方面的问题,作者使用的内存分配策略是:以最小的代价连续存储元素。用通俗大大白话来讲,就是每次分配的时候会比你当前所需要的空间多一些,当已经分配的空间使用完后才会开辟新的空间。

首先来看一下capacity和reserve操作

v.size();     //返回vector中元素的个数
v.capacity(); //返回vector能够存储的元素总数
v.reserve(n); //手动设置vector容器应该预留n个元素的空间
举一个简单的例子来说明他们之间的关系:

vector<int> v;
cout<<"vector size:"<<v.size()<<endl;        //输出0
cout<<"vector capacity:"<<v.capacity()<<endl;//输出0

//添加24个元素
for(int i = 0; i < 24; i++)
  v.push_back(i);

cout<<"vector size:"<<v.size()<<endl;        //输出24
cout<<"vector capacity:"<<v.capacity()<<endl;//输出32
明白了吧,capacity总是要大于或等于size的,至于为什么是32?因为每当vector不得不分配新的存储空间时,会以加倍当前容量 的分配策略来重新分配。比如你添加1个元素,size为1,capacity也为1,然后再添加,capacity 乘2,然后再添加再乘2,如下:

//添加的时候size和capacity的关系:
//v.size() —— v.capacity()
        0  -  0
        1  -  1
        2  -  2
        3  -  4
        4  -  4
        5  -  8
        9  -  16
        以此类推...
或者我们可以自己设置预留空间,修改上面的例子:

vector<int> v;
v.reserve(50);
cout<<"vector size:"<<v.size()<<endl;        //输出0
cout<<"vector capacity:"<<v.capacity()<<endl;//输出50
//添加50个元素
for(int i = 0; i < 50; i++)
  v.push_back(i);
//再多添加一个
v.push_back(51);
cout<<"vector size:"<<v.size()<<endl;        //输出51
cout<<"vector capacity:"<<v.capacity()<<endl;//输出100

5.容器优缺点:

vector:优点:快速随机访问缺点:在容器任意位置插入或删除,比在容器尾部插入或删除,开销大。

list:是不连续存储的,优点:在容器中任何位置高效的插入和删除元素。缺点:不支持随机访问,访问元素需要遍历其他元素。

deuqe :拥有更复杂的数据结构,优点:从容器两端插入和删除都非常快,支持高效随机访问。缺点:在中间插入或删除效率很低。

6.判断选择哪种容器:

(1)需要高效随机访问元素,则使用vector或者deque。

(2)需要高效在容器中间位置插入或者删除元素,则使用list。

(3)若不是在中间位置插入,而是容器首部或者尾部插入,则使用deque。

(4)若既需要高效随机访问又需要高效中间插入,则可以将元素添加到list中然后排序啥的,再复制到vector中。


=========================================


再不睡觉就作死了。。


转载请注明出处:http://blog.csdn.net/shun_fzll/article/details/37917133


【C++基础 04】vector详解,布布扣,bubuko.com

【C++基础 04】vector详解

上一篇:android Binder机制原理


下一篇:【足迹C++primer】47、Moving Objects(1)