文档章节

STL容器:vector

尧山少侠
 尧山少侠
发布于 2015/12/23 13:25
字数 2124
阅读 2
收藏 0

1. 概念
vector是一种序列式容器,所谓序列式容器,即其中的元素可以排序,但是并未排序。可以把vector可作为加强版的array,它和array一样,存储空间是一段连续的内存,因此支持随机访问,但是,和array相比,vector支持动态增加数据。
vector支持动态增加数据,同时又需要保持空间的连续性从而支持随机访问,因此,在对vector动态增加元素时,如果旧有空间装满,需要申请更大的内存,并且需要把旧有数据搬到新内存去,因此,数据的搬移效率使我们在开发过程中需要考虑的重要因素。

2. API
vector提供了很多接口,以下列出vector的成员函数和操作:

(constructor) Construct vector (public member function)
(destructor) Vector destructor (public member function)
operator= Copy vector content (public member function )

Iterators:
begin Return iterator to beginning (public member type)
end Return iterator to end (public member function)
rbegin Return reverse iterator to reverse beginning (public member function)
rend Return reverse iterator to reverse end (public member function)

Capacity:
size Return size (public member function)
max_size Return maximum size (public member function)
resize Change size (public member function)
capacity Return size of allocated storage capacity (public member function)
empty Test whether vector is empty (public member function)
reserve Request a change in capacity (public member function)

Element access:
operator[] Access element (public member function)
at Access element (public member function)
front Access first element (public member function)
back Access last element (public member function)

Modifiers:
assign Assign vector content (public member function)
push_back Add element at the end (public member function)
pop_back Delete last element (public member function)
insert Insert elements (public member function)
erase Erase elements (public member function)
swap Swap content (public member function)
clear Clear content (public member function)

Allocator:
get_allocator Get allocator (public member function )

3. Vecotr内存分配
vector内存分配原则是保证一块连续的空间。
vector 并不是随每一个元素的插入而增长自己,而是当vector 需要增长自身时,它实际分配的空间比当前所需的空间要多一些,这主要是基于效率的考虑。 vector内存分配策略的实现是常常是双倍分配(不是所有),比如说当size为4,capacity大小为4,如果再push一个元素,则size为5,capacity为8。

vector在进行增数据操作时有可能会重新分配内存以保证空间的连续性。增数据操作:push_back,insert
vector在进行删数据操作时,内存不会重新分配。删数据操作:erase,pop_back

有两个概念需要明确:size和capacity
vector::size(): Returns the number of elements in the vector container.
vector::capacity(): Returns the size of the allocated storage space for the elements of the
vector container
size是元素个数,capacity则是指为vector分配的内存大小,显然,capacity一定要大于等于size。


4. reserve和resize的区别

reserve会预留内存,但不会创建元素;resize则会创建元素,在空间不足的时候,会申请内存。具体的区别,上代码:

//查看vector:size、capacity
void print(vector<int> &vector)
{
    cout << endl;
    cout << "my vector size:" << vector.size() << endl;
    cout << "my vector capacity:" << vector.capacity() << endl;
}
 
int _tmain(int argc, _TCHAR* argv[])
{
    vector<int> myvector1;
    myvector1.reserve(100);
 
    print(myvector1);
 
    vector<int> myvector2;
    myvector2.resize(100);
 
    print(myvector2);
    return 0;
}


输出:
my vector size:0
my vector capacity:100

my vector size:100
my vector capacity:100



5. Vector使用示例

代码如下:

//插入4个元素
void push4element(vector<int> &vector)
{
    vector.push_back (100);
    vector.push_back (100);
    vector.push_back (100);
    vector.push_back (100);
}
 
//查看vector:size、capacity
void print(vector<int> &vector)
{
    cout << endl;
    cout << "my vector size:" << vector.size() << endl;
    cout << "my vector capacity:" << vector.capacity() << endl;
}
 
int _tmain(int argc, _TCHAR* argv[])
{
    //初始化vector
    vector<int> myvector;
 
    //插入数据、查看大小
    push4element(myvector);
    print(myvector);
 
    //插入数据、查看大小
    push4element(myvector);
    print(myvector);
 
    //插入数据、查看大小
    push4element(myvector);
    print(myvector);
 
    //插入数据、查看大小
    push4element(myvector);
    print(myvector);
 
    //清空vector
    while (!myvector.empty())
    {
        myvector.pop_back();
    }
    print(myvector);
 
    //重置vector大小
    myvector.resize(myvector.size()+2);
    print(myvector);
 
    system("pause");
    return 0;
}

x32,win7,VS2010运行输出结果:
my vector size:4
my vector capacity:4

my vector size:8
my vector capacity:9

my vector size:12
my vector capacity:13

my vector size:16
my vector capacity:19

my vector size:0
my vector capacity:19

my vector size:2
my vector capacity:19


lx64 inux 2.6.9 gcc 运行输出结果:
my vector size:4
my vector capacity:4

my vector size:8
my vector capacity:8

my vector size:12
my vector capacity:16

my vector size:16
my vector capacity:16

my vector size:0
my vector capacity:16

my vector size:2
my vector capacity:16

从capacity的增长情况来看,不同库内存分配策略实现不一样,但总体上都是增量分配。

6. Vecotr使用常见问题

1)迭代器失效
iterator失效主要有两种情况:
a.iterator变量已经变成了“悬空指针”,对它进行*,++,--都会引起程序内存操作异常;
b.iterator所指向的变量已经不是你所以为的那个变量了。

vector迭代器的几种失效的情况:
a.当插入(push_back)一个元素后,end操作返回的迭代器肯定失效。
b.当插入(push_back)一个元素后,capacity返回值与没有插入元素之前相比有改变,则需要重新加载整个容器,此时first和end操作返回的迭代器都会失效。
c.当进行删除操作(erase,pop_back)后,指向删除点的迭代器全部失效;指向删除点后面的元素的迭代器也将全部失效。

比较常见的一种场景是遍历一个vector,删除符合条件的数据,正确的写法如下:

vector<int> myvector;
for(vector<int>::iterator iter=myvector.begin();iter!=myvector.end();)
{
    if(10 == (*iter))
        iter=myvector.erase(iter);
    else
        ++iter;
}


在erase之后,删除的迭代器之后的数据前移,因此,在删除之后,不需要对迭代器++

2)元素访问
vector支持随机内存访问,我们可以使用at和[]来访问元素,这两者有什么区别呢?
在不越界的情况下,两者没有区别;在越界的情况下,at会抛出一个std::out_of_range异常。而C++98标准说[]可以、但不一定要进行下标越界检查。因此,标准库实现方可以自由选择是否为operator[]加上下标越界检查功能。上代码

at:

vector<int> myvector;
myvector.reserve(10);
try
{
    cout << myvector.at(100);
}
catch(...)
{
    cout << "got you" << endl;
}


VS2010输出:
got you

[]:

vector<int> myvector;
myvector.reserve(10);
 
try
{
    cout << myvector[100];
}
catch(...)
{
    cout << "got you" << endl;
}

VS2010:
程序崩溃

 


3)拷贝构造函数
初学者使用vector使用常常会遇到的一个麻烦就是忘记定义拷贝构造函数。向上代码,看什么时候我们需要拷贝构造函数

class A
{
public:
    A(){cout << "construct" << endl;}
    ~A(){cout << "deconstruct" << endl;}
    A(const A&){cout << "copy construct" << endl;}
};
 
void push_vec(vector<A>& myvector)
{   
    A a;
    myvector.push_back(a);
    cout << "my vector capacity:" << myvector.capacity() << endl;
}
 
void fun()
{
    vector<A> myvector;
 
    cout << "---begin----"<<endl;
    push_vec(myvector);
    cout << "---end----"<<endl;
 
    cout << "---begin----"<<endl;
    push_vec(myvector);
    cout << "---end----"<<endl;
 
    cout << "---begin----"<<endl;
    push_vec(myvector);
    cout << "---end----"<<endl;
 
    cout << "---begin----"<<endl;
    push_vec(myvector);
    cout << "---end----"<<endl;
 
}
 
int _tmain(int argc, _TCHAR* argv[])
{
    fun();
 
    system("pause");
    return 0;
}


输出:

---begin----
construct
copy construct
my vector capacity:1
deconstruct
---end----
---begin----
construct
copy construct
deconstruct
copy construct
my vector capacity:2
deconstruct
---end----
---begin----
construct
copy construct
copy construct
deconstruct
deconstruct
copy construct
my vector capacity:3
deconstruct
---end----
---begin----
construct
copy construct
copy construct
copy construct
deconstruct
deconstruct
deconstruct
copy construct
my vector capacity:4
deconstruct
---end----
deconstruct
deconstruct
deconstruct
deconstruct

分析:
第一个push_vec(myvector),输出:
construct // A a
copy construct // myvector.push_back(a);调用拷贝构造函数
my vector capacity:1
deconstruct // a的生命周期到,析构

第2个push_vec(myvector),输出:
construct // A a
copy construct // myvector.push_back(a); 此时capacity不够大,需要重新分配内存,先将第一次push的a调用拷贝构造函数拷贝到新的内存,
deconstruct // 析构掉第一次push的a(原有内存)
copy construct //将第2个a 调用拷贝构造函数push到vector新申请的内存中
my vector capacity:2
deconstruct // a的生命周期到,析构


我们可以看到,在vector push_back遇到capacity不够的过程中,会调用拷贝构造函数搬移数据。其实,在erase的过程中,也会有调用拷贝构造函数的需要,因此,在我们的对象中有使用指针申请内存的情况下,需要定义好拷贝构造函数。

4)释放内存

vector在调用erase,pop_back删除元素的时候,并不会释放内存,因此,在vector生命期内,需要释放vector所占用内存的时候,可以使用如下代码:

template < class T >
void ClearVector( vector< T >& vt )
{
vector< T > vtTemp;
veTemp.swap( vt );
}

如果需要部分释放,可以先将vector的数据拷贝到另一个vector,然后调用swap。

7. 结语
vector具有很多优秀的特点:随机访问、动态扩张、额外消耗少,非常适合多查询的应用场景。但是,由于其需要保持内存连续,在删除某个元素之后,后续元素需要拷贝前移,这会带来一些消耗,因此不适合随机删除的场景。

本文转载自:http://blog.csdn.net/yfkiss/article/details/6537234

尧山少侠

尧山少侠

粉丝 7
博文 321
码字总数 26520
作品 0
海淀
程序员
私信 提问
C++ STL编程轻松入门 4

 2.2.2 第二版:工业时代--组件化大生产   我们应该庆幸自己所生活的年代。工业时代,科技的发展所带来的巨大便利已经影响到了我们生活中的每个细节。如果你还在以原始人类的方式生活着,...

暖冰
2015/11/21
84
0
STL vector 介绍连载1-2-3

STL简介: STL = Standard Template Library,标准模板库,惠普实验室开发的一系列软件的统称。它是由Alexander Stepanov、Meng Lee和David R Musser在惠普实验室工作时所开发出来的。这可能是...

天远
2012/05/20
152
0
C++ STL学习——vector

学过C++的人肯定会很熟悉STL标准模板库,STL其实就是封装了一系列的接口,供我们调用。很多函数或者算法的实现不需要我们从头开始写,大大提高我们的编程效率。这篇博客在简单介绍STL的情况下...

chenyufeng1991
2016/08/21
0
0
Effective STL - 容器

STL(standard template library)提供了一组表示容器,迭代器,函数对象和算法的模板。容器是一个与数组类似的单元,可以存若干个值。 STL容器是同质的,即存储的值的类型相同;算法是完成特...

積木leayn
2013/10/07
148
0
在 Qt4 中使用 C++11

在 Qt4 中使用 C++11 原文出处:blog.qt.digia.com/cn/2011/08/22/cpp0x-in-qt 我们前面介绍了许多 C++ 11 的优点,而且介绍了如何在 Qt 5 中使用 C++ 11。但是,Qt 5 毕竟只是一个尚未发布的...

ruguonandao
2013/03/14
827
0

没有更多内容

加载失败,请刷新页面

加载更多

js如何控制table中的某一行动态置顶

两行代码搞定: $('#'+item.roadCode).fadeOut().fadeIn();//获取到需要置顶的行 $(".table").prepend($('#'+item.roadCode)); 其中,fadeOut()方法 作用 --- 从可见到隐藏 如下: prepend(......

码妞
59分钟前
4
0
四种解决Nginx出现403 forbidden 报错的方法

我是在在本地用虚拟机中通过yum安装nginx的,安装一切正常,但是访问时报403, 于是查看nginx日志,路径为/var/log/nginx/error.log。打开日志发现报错Permission denied,详细报错如下: 1....

dragon_tech
今天
3
0
获取RestResultResponse返回的值

Springboot项目,需要调其他服务的接口,返回值类型是RestResultResponse 打断点的结果集是这个 打印出来的getData(): [{id=3336b624-8474-4dd9-bd5b-c7358687c877, paraNo=104, para=Postpo...

栾小糖
今天
4
0
【小学】 生成10以内的加减法

#!/usr/bin/env python# coding: utf-8from random import randrange# 题目的最大数值R_MAX = 10# 生成的题目的数量R_PAGE = 70# 生成减法列表def get_sub_list():...

Tensor丨思悟
今天
11
0
JavaScript设计模式——适配器模式

  适配器模式是设计模式行为型模式中的一种模式;   定义:   适配器用来解决两个已有接口之间不匹配的问题,它并不需要考虑接口是如何实现,也不用考虑将来该如何修改;适配器不需要修...

有梦想的咸鱼前端
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部