视频: C++第173讲：L8_模板及标准模板库7_容器和vector2
分享给好友
您需要先安装&，才能下载视频哦
用优酷App或微信扫一扫，在手机上继续观看。
C++第173讲：L8_模板及标准模板库7_容器和vector2
分享给站外好友
把视频贴到Blog或BBS
flash地址:
<input type="text" class="form_input form_input_s" id="link3" value=''>
<input id="link4" type="text" class="form_input form_input_s" value=''>
节目制作经营许可证京字670号
京公网安备号
药品服务许可证(京)-经营-1568人阅读
本文由&翻译自&&转载请参见文章末尾处的要求。
众所周知，要建一棵树，我们需要关注它的内存分配与释放。为了避开这个问题，我打算用C&#43;&#43; STL(vector和deque)来建一棵小型的BST。很明显，这篇文章是出于这个想法的。
BST是应用最广泛的数据结构之一。C是首选语言，不过因为C&#43;&#43;尤其是C&#43;&#43;11的出现，我更有兴趣用C&#43;&#43;来实现。但是这篇文章里没有涉及到C&#43;&#43;11，代码可用C&#43;&#43;98来编译。
要建BST，我们需要BST的数据结构。传统的BST数据结构包含指向左右子树的指针。我将用vector而不用指针，所以我将用vector的下标作为指向左右子树的指针。
struct bst
unsigned int
int rightI
接下来，我会写各种建BST和它的孩子结点的函数。第一个函数用来建BST。它将用传入的数据来初始化数据结构，并且把左右下标置为-1（相当于置指针为NULL）。
void MakeNode(vector&struct& &v1, int aData)
struct bst b1 = { aData, -, - };
v1.push_back(b1);
下面这个函数的功能是设置结点的左右孩子。设置时，会把左右孩子的真正下标（译者注：相当于它们的地址）赋到根结点上。
void setleft(vector &struct&&v1, int currIndex, int aData)
unsigned int leftIndex = v1.size();
v1[currIndex].leftIdx = leftI
struct bst b1 = { aData, -, - };
v1.push_back(b1);
void setright(vector&struct& &v1, int currIndex, int aData)
unsigned int rightIndex = v1.size();
v1[currIndex].rightIdx = rightI
struct bst b1 = { aData, -, - };
v1.push_back(b1);
下面这个函数用于向BST插入数据。对所有结点（译者注：不应是“所有”，平均时间复杂度应是O(logn)）遍历直至找到合适的位置插入元素，其中会调用上面定义的左右函数。
void Insert(vector&struct bst& &v1, int aData)
if(v1.size() == )
cout&&&Note is not made yet. MakeNode first...&&&
unsigned int currentIdx = ;
while ( currentIdx & v1.size() )
if(aData &= v1[currentIdx].data)
if( v1[currentIdx].leftIdx == -)
setleft(v1, currentIdx, aData);
currentIdx = v1[currentIdx].leftI
if(v1[currentIdx].rightIdx == -)
setright(v1, currentIdx, aData);
currentIdx = v1[currentIdx].rightI
下面的代码将以前序、中序、后序遍历BST。下标参数是开始点。
void InTrav(vector &struct bst& &v1, unsigned int Idx)
if(v1[Idx].leftIdx != -)
InTrav(v1,v1[Idx].leftIdx );
cout&&v1[Idx].data&&
if( v1[Idx].rightIdx != -)
InTrav(v1, v1[Idx].rightIdx);
void PreTrav(vector &struct bst& &v1, unsigned int Idx)
cout&&v1[Idx].data&&
if(v1[Idx].leftIdx != -)
PreTrav(v1,v1[Idx].leftIdx );
if( v1[Idx].rightIdx != -)
PreTrav(v1, v1[Idx].rightIdx);
void PostTrav(vector &struct bst& &v1, unsigned int Idx)
if(v1[Idx].leftIdx != -)
PostTrav(v1,v1[Idx].leftIdx );
if( v1[Idx].rightIdx != -)
PostTrav(v1, v1[Idx].rightIdx);
cout&&v1[Idx].data&&
主程序比较简单，如下
int main()
vector &struct bst& v1;
MakeNode(v1, );
Insert(v1, );
Insert(v1, );
Insert(v1, );
Insert(v1, );
Insert(v1, );
Insert(v1, );
InTrav(v1, );
PreTrav(v1,);
PostTrav(v1,);
1、同样的代码也可用于STL deque。我还没为任何其他容器测试。
2、与原生指针比起来，效率较低，除非做一些vector(STL)优化。我还没去尝试。
3、你可以用它来建小型的BST，可以一下子删除它而不用担心内存释放。
4、对于BST的删除元素操作，我会在下一篇帖子中介绍。
第一篇帖子
本文及相关源代码、文件，由授权。
我热爱编程，甚至在我接受专业教育之前就开始了（1995年）。从那以后，我一直从事于IP网络栈（写IPv6栈和下一代TCP栈），VoIP，IP安全（IKE/IPSec）。
我最热衷的编程语言是C&#43;&#43;，喜欢研究用加强的算法和数据结构来提高基于人工智能的系统。
原文链接：&&翻译：
译文链接：
[&转载必须在正文中标注并保留原文链接、译文链接和译者等信息。]
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：166167次
积分：2535
积分：2535
排名：第6873名
原创：80篇
评论：130条
(1)(1)(1)(4)(1)(1)(1)(1)(1)(1)(1)(3)(1)(8)(4)(1)(5)(7)(1)(2)(2)(7)(16)(8)(2)C++中vector的使用
第一部分 使用入门
vector可用于代替C中的数组，或者MFC中的CArray，从许多说明文档或者网上评论，一般一致认为应该多用vector，因为它的效率更高，而且具备很好的异常安全性。而且vector是STL推荐使用的默认容器，除非你知道你有特殊需要，使用vector不能满足你的需求，例如需要容器在head和tail高效的插入和删除，或者在任何位置高效的删除和插入操作，那么你可能使用deque或者list更加合适。
vector是连续内存容器，换句话说，标准要求所有标准库实现的时候，vector中的元素的内存必须是连续的。所以对于插入和删除的时间复杂度是很高的，因为删除或者插入的时候，需要元素的移动，即元素复制拷贝。
vector的内部实现一般需要用到placement new
，所以效率很高，因为很多的时候，只要我们是使用得到，就可以省去很多的内存分配开销。而且vector的使用，元素可以没有默认的构造函数，但是需要拷贝构造函数的存在，这是使用CArray所无法实现的。
使用原则：
1，尽量使用vector代替C风格的数组或者CArray；
2，尽量使用算法代替手工写的循环；
3，尽量使用vector本身的函数代替其他泛型算法；
vector的接口很容易看懂和使用，这里以一些例子来说明vector的用法。
1，填充vector
如果我们想用原始数组的内容填充vector，那么于有很多种方式。我们来一次学习vector的几个方法。
例如我们有数组int v1[10] =
{0,1,0,0,3,0,0,4,4,4};
初始化方式1：
vector&int& v2(10);
//初始化size为10可以避免数组动态增长的时候不断的分配内存
//v2.reserve(10);//同上，只要使用其中一个就可以了
for( int i=0;
i&10; i++ )
v2.push_back(v1[i]);//增加一个元素
初始化方式2：
vector&int&
v3(&v1[0],&v1[9]);//原始数组的元素指针可以作为迭代器来使用
初始化方式3：
vector&int& v4;
v4.reserve(10);
v4.insert(v4.begin(), &v1[0],
初始化方式4：
vector&int&
copy(v5.begin(),
&v1[0], &v1[9]);
原始数组的元素指针可以作为迭代器来使用。
原则：尽量使用reserve来减少不必要的内存分配次数。
原则：尽量使用empty而不是size()==0 来判断容器是否为空
有可能我们需要在vector中插入相应的元素
vector&int&::iterator i = find(
v1.begin(), v1.end(), 3);
if( i != v1.end()
v1.insert( i, 6 );
2，遍历vector
例如有vector&int& v1;
void print( int
for( int i=0;
i&v1.size(); i++ )
print(v1[i]);
这种方式是我们最熟悉的，但是不够好，写起来不够简洁。而且对于没有随机迭代器的其他容器来说，这样做是办不到的。
vector&int&::
iterator&&
VIntIterator end =
v1.begin();
for( VIntIterator
i=v1.begin(); i != ++i )
print( *i );
注意：先计算end有好处，因为不必要每次去重复计算end,vector的end()不是常数时间的，所以先缓存下来能提高效率。写算法的时候尽量使用!=比较迭代器，因为&对于很多非随机迭代器没有这个操作符。
但是这种方式也写起来比较繁琐。
v1.begin(), v1.end(), print );
使用算法写起来简单多了。
使用算法的时候，可以使用函数对象，例如
void operator ()( double i )
&&&&&&&&&&&&&
std::cout &&
v1.begin(), v1.end(), OutPut );
3，vector中的删除
删除指定元素
vector&double&
//….初始化代码
vector&double&:: iterator i =
find( v1.begin(), v1.end(), 3.0 );
if( i != v1.end()
v1.erase(i);
这样就真的删除了么指定的元素了么？没有。其实只是内部的元素作了移动，vector的删除的时间复杂度是很高的。所以选择容器的时候，如果需要频繁在中间插入和删除元素，那选择vector就会影响效率了。
注意：插入或者删除操作会使得迭代器失效。
原则：使用erase-remove惯用法删除元素
remove(v1.begin(), v1.end(), 3.0), v1.end() );
4，vector是否为空
在判断容器是否为空的时候，使用empty()来代替size()是否为了0的检查方式，因为empty更加高效时间复杂度是常数时间的，size()时间复杂度不是常数时间的。
原则：使用empty判断标准容器是否为空
5，vector中的查找
原则：尽量使用标准容器自带的算法代替公共算法。
但是vector中并没有多少自己的算法，倒是list中有remove
,remove_if,sort,reverse等算法。
6，使用交换技巧来修正过剩的容量
vector&int& v1;
//…初始化v1
//…删除v1中所有的元素
但是这个时候v1的内存容量并不是0，还是很大的一块内存没有释放，如果想清空
用v1.reserve(0);到不到目标，因为reserve只能扩大内存容量，并不能减小。
vector&int& v2;
v2.swap(v1);
这个时候就是真的将之内存容量降到最低了。
6，题外话：使用算法及其他技巧
原则：不要使用auto_ptr作为模板参数来建立容器，这会产生意想不到的陷阱，因为auto_ptr的拷贝有特殊的语义
原则：避免使用vector&bool&,
因为它不能当作标准容器来用
原则：尽量使用区间成员函数代替它们的单元素参数兄弟成员函数
原则：使得容器中元素的拷贝操作轻量而正确，拷贝是STL中容器的运行的基本方式，将元素加入到容器，必然保持一个拷贝，容器中的元素不再是原来的那个元素，所以如果将指针加入容器，必须在容器离开作用域以前删除指针所指的对象。
vector&object*& v1;
……//插入操作
for( vector&object*& :: iterator i =
v1.begin(); i != v1.end(); ++i )
&&&&&&&&&&&&&
delete *i;
原则：注意对于
vector，任何插入删除操作都会引起迭代器失效。所以要小心。
第二部分 使用错误讨论
vector的语义常被误解，所以经常会出现使用错误
你能发现下面的问题所在么？
void func(
vector&.int&& v1
v1.at(0) = 1; //#2 会检查0这个位置是否有效 进行安全检查
#1和#2有何区别？
void func1(
vector&int&& v1
v1.reserve(2);
assert( v1.capacity() == 2 );
v1[0] = 1;
v1[1] = 2;
for( vector&int&::iterator i =
v1.begin(); i&v1.end(); i++ )
&&&&&&&&&&&&&
cout && *i
cout && v1[0];
v1.reserve(100);
assert(v1.capicity() == 100 );
cout && v1[0];
v1[2] = 3;
v1[3] = 4;
v[99] = 100;
for( vector&int&::iterator i =
v1.begin(); i&v1.end(); i++ )
&&&&&&&&&&&&&
cout && *i
函数func1存在什么问题(丛风格和代码正确性做出评价)？会打印出什么？
使用vector的时候最容易发生的运行时错误，莫过于迭代器错误
注意：对于
vector，任何插入删除操作都会引起迭代器失效。所以要小心
以下代码有什么问题，如何修改？
#include &iostream&
#include &vector&
print(vector&int&);
int main()
vector&int&
array.push_back(1);
array.push_back(6);
array.push_back(6);
array.push_back(3);
//删除array数组中所有的6
vector&int&::
vector&int&::iterator itor2;
itor=array.begin();
for(itor=array.begin(); itor!=array.end(); )
if(6==*itor)
array.erase(itor2);
print(array);
void print(vector&int& v)
cout && "n vector size is: "
&& v.size()
vector&int&::iterator p =
v.begin();
我的答案是，迭代器问题，只能删除第一个6，以后迭代器就失效了，不能删除之后的元素。
我给你一个完整的解释：
执行itor=array.erase(itor);这句话后，itor不会移动，而只是把删除的数后面的数都往前移一位，所以删除了第一个6后，指针指向第2个6，然后在来个itor++，指针就指向array.end()了，给你画个草图：
1 6 6 3 array.end() //最开始指针itor指向第一个6；
1 6 3 array.end() //删除第一个6后，指向第二个6
1 6 3 array.end() //itor++后，就指向3了，所以不能删除
Vector成员函数
c.assign(beg,end)
c.assign(n,elem)
& end)区间中的数据赋值给c。
将n个elem的拷贝赋值给c。
传回索引idx所指的数据，如果idx越界，抛出out_of_range。
& 传回最后一个数据，不检查这个数据是否存在。
& 传回迭代器重的可一个数据。
c.capacity()
& 返回容器中数据个数。
& 移除容器中所有数据。
& 判断容器是否为空。
& 指向迭代器中的最后一个数据地址。
c.erase(pos)
c.erase(beg,end)
& 删除pos位置的数据，传回下一个数据的位置。
删除[beg,end)区间的数据，传回下一个数据的位置。
& 传回地一个数据。
get_allocator
& 使用构造函数返回一个拷贝。
c.insert(pos,elem) &
c.insert(pos,n,elem)
c.insert(pos,beg,end)
& 在pos位置插入一个elem拷贝，传回新数据位置。
在pos位置插入n个elem数据。无返回值。
在pos位置插入在[beg,end)区间的数据。无返回值。
c.max_size()
& 返回容器中最大数据的数量。
c.pop_back()
& 删除最后一个数据。
c.push_back(elem)
& 在尾部加入一个数据。
c.rbegin()
& 传回一个逆向队列的第一个数据。
& 传回一个逆向队列的最后一个数据的下一个位置。
c.resize(num)
& 重新指定队列的长度。
c.reserve()
& 保留适当的容量。
& 返回容器中实际数据的个数。
c1.swap(c2) &
swap(c1,c2)
& 将c1和c2元素互换。
同上操作。
vector &Elem&
& c(beg,end)
c.~ & vector
& 创建一个空的vector。
复制一个vector。
创建一个vector，含有n个数据，数据均已缺省构造产生。
创建一个含有n个elem拷贝的vector。
创建一个以[end)区间的vector。
销毁所有数据，释放内存。
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。首先，vector 在VC 2008 中的实现比较复杂，虽然vector 的声明跟VC6.0 是一致的，如下：
&C++ Code&
template&&&
class&_Ty,&
class&_Ax&=&allocator&_Ty&&&
但在VC2008 中vector 还有基类，如下：
&C++ Code&
//&TEMPLATE&CLASS&vector
template&&&
class&_Ty,
class&_Ax&&
class&vector
public&_Vector_val&_Ty,&_Ax&
稍微来看一下基类_Vector_val：
&C++ Code&
//&TEMPLATE&CLASS&_Vector_val
template&&&
class&_Ty,
class&_Alloc&&
class&_Vector_val
public&_CONTAINER_BASE_AUX_ALLOC&_Alloc&
//&base&class&for&vector&to&hold&allocator&_Alval
protected:
&&&&_Vector_val(_Alloc&_Al&=&_Alloc())
&&&&&&&&:&_CONTAINER_BASE_AUX_ALLOC&_Alloc&(_Al),&_Alval(_Al)
//&construct&allocator&from&_Al &&&&}
typename&_Alloc::
&&&&rebind&_Ty&::other&_A
&&&&_Alty&_A&&&
//&allocator&object&for&values };
为了理解_Alty 的类型，还得看一下allocator模板类：
&C++ Code&
class&_Ty&&
class&allocator
template&&&
class&_CRTIMP2_PURE&allocator&
//&generic&allocator&for&type&void &&&&
class&_Other&
struct&rebind
&&&&&&&&&&&&
//&convert&an&allocator&void&&to&an&allocator&&_Other& &&&&&&&&&&&&
typedef&allocator&_Other&&
&&&&&&&&};
&&&&&&&&....
typedef&typename&_Alloc::template&rebind&_Ty&::other&_A 整体来看是类型定义，假设现在我们这样使用
vector&int&， 那么_Ty 即 int, _Ax 即 allocator&int&，由vector 类传递给 基类_Vector_val，则_Alloc 即
&allocator&int& ；可以看到&allocator&void& 是allocator 模板类的特化，&rebind&_Ty&&是成员模板类，other是成员模板类
中自定义类型，_Ty 即是int ， 那么other 类型也就是allocator&int&， 也就是说_Alty 是类型&allocator&int& 。
_Alty _A 即 基类定义了一个allocator&int& 类型的成员，被vector 继承后以后用于为vector 里面元素分配内存等操作。
而在VC6.0，_Alval 是直接作为vector 自身的成员存在的。此外还有一个比较大的不同点在于，两个版本对于capacity 也就是容量的
计算方式不同，接下去的测试可以看到这种不同，在这里可以先说明一下：
VC2008：容量每次增长为原先容量 + 原先容量 / 2;
VC6.0 ：容量每次增长为原先容量的2倍。
容量跟vector 大小的概念是不一样的，capacity 》= size，如下图所示：
size 指的是avail &- data 的区间；capacity 指的是 limit - data 的区间；也就是说存在尚未使用的空间。
下面是模仿VC6.0 中vector 的实现写的Vec 类，程序主要参考《Accelerated C++》 ，略有修改，比如将接口修改成与VC6.0 一致，
这样做的好处是可以传递第二个参数，也就是说可以自己决定内存的分配管理方式；实现capacity() 函数等；
&C++ Code&
/************************************************************************* &&File&Name:&template_class_Vec.h &&Author:&Simba &&Mail:& &&Created&Time:&Thu&07&Feb&:12&PM&CST ************************************************************************/
#include&iostream&
#include&cstddef&
#include&memory&
#include&algorithm&
template&&&
class&A_&=&std::allocator&T&&&
//&interface &&&&
typedef&T&*
const&T&*const_
typedef&size_t&size_
typedef&T&value_
typedef&std::ptrdiff_t&difference_
typedef&T&&
const&T&&const_
&&&&&&&&create();&&&&
//&default&constructor &&&&}
//&const&T&&&t&=&T();意思是默认参数，当没有传递t时，默认使用T()&(type&T's&default&constructor) &&&&
//explicit表示不允许构造函数进行隐式类型转换 &&&&
explicit&Vec(size_type&n,&
const&T&&val&=&T())
&&&&&&&&create(n,&val);
const&Vec&&v)
&&&&&&&&create(v.begin(),&v.end());&&&&
//&copy&constructor &&&&}
operator=(
const&Vec&&);&&
//&assigment&operator &&&&~Vec()
&&&&&&&&uncreate();&&&&
//&destructor &&&&}
&&&&size_type&size()&
return&avail&-&&&&&
//&a&value&of&ptrdiff_t &&&&}
&&&&size_type&capacity()&
return&(data&==&
0&:&limit&-&data);
operator[](size_type&i)
return&data[i];
/*&because&their&left&operand&is&different(const),&we&can&overload&the&operation&*/
operator[](size_type&i)&
return&data[i];
&&&&iterator&begin()
&&&&const_iterator&begin()&
&&&&iterator&end()
&&&&const_iterator&end()&
void&push_back(
const&T&&val)
if&(avail&==&limit)&
//&get&space&if&needed &&&&&&&&&&&&grow();
&&&&&&&&unchecked_append(val);&
//&append&the&new&element &&&&}
void&clear()
&&&&&&&&uncreate();
void&empty()
return&data&==&
&&&&iterator&&
//&first&element&in&the&Vec &&&&iterator&&
//&one&past&the&last&constructed&element&in&the&Vec &&&&iterator&&
//&one&past&the&last&available&element
//&object&to&handle&memory&allocation &&&&
//&allocate&and&initialize&the&underlying&array &&&&
void&create();
void&create(size_type,&
const&T&&);
void&create(const_iterator,&const_iterator);
//&destory&the&element&in&the&array&and&free&the&memory &&&&
void&uncreate();
//&support&functions&for&push_back &&&&
void&grow();
void&unchecked_append(
const&T&&);
template&&&
Vec&T,&A_&&&Vec&T,&A_&::
operator=(
const&Vec&T,&A_&&&rhs)
//&check&for&self-assigment &&&&
if&(&rhs&!=&
&&&&&&&&uncreate();
&&&&&&&&create(rhs.begin(),&rhs.end());
template&&&
void&Vec&T,&A_&::create()
&&&&data&=&avail&=&limit&=&
template&&&
void&Vec&T,&A_&::create(size_type&n,&
const&T&&val)
&&&&data&=&alloc.allocate(n);
&&&&limit&=&avail&=&data&+&n;
&&&&std::uninitialized_fill(data,&limit,&val);
template&&&
void&Vec&T,&A_&::create(const_iterator&i,&const_iterator&j)
&&&&data&=&alloc.allocate(j&-&i);
&&&&limit&=&avail&=&std::uninitialized_copy(i,&j,&data);
/*&return&a&pointer&to&(one&past)&the&last&element&that&it&initialized&*/
template&&&
void&Vec&T,&A_&::uncreate()
//&destroy(in&reverse&order)&the&elements&that&were&constructed &&&&&&&&iterator&it&=&
while&(it&!=&data)
&&&&&&&&&&&&
//&destory&runs&T's&destructor&for&that&object,&rendering&the&storage&uninitialized&again &&&&&&&&&&&&alloc.destroy(--it);
&&&&&&&&alloc.deallocate(data,&limit&-&data);
//&reset&pointers&to&indicate&that&Vec&is&empty&again &&&&data&=&limit&=&avail&=&
template&&&
void&Vec&T,&A_&::grow()
//&when&growing,&allocate&twice&as&much&space&as&currently&in&use &&&&size_type&new_size&=&std::max(
2&*&(limit&-&data),&ptrdiff_t(
//&allocate&new&space&and&copy&elements&to&the&new&space &&&&iterator&new_data&=&alloc.allocate(new_size);
&&&&iterator&new_avail&=&std::uninitialized_copy(data,&avail,&new_data);
//&return&the&old&space &&&&uncreate();
//&reset&pointers&to&point&to&the&newly&allocated&space &&&&data&=&new_
&&&&avail&=&new_
&&&&limit&=&data&+&new_
template&&&
//&error&C4519:&仅允许在类模板上使用默认模板参数
void&Vec&T,&A_&::unchecked_append(
const&T&&val)
&&&&alloc.construct(avail++,&val);
先介绍一下用到的一些类和函数：
allocator 模板类：
&C++ Code&
#include&&memory&
template&&
class&allocator
&&&&T&*allocate(size_t);
void&deallocate(T&*,&size_t);
void&construct(T&*,&size_t);
void&destroy(T&*);
//....... };
当然实际的接口没实现没那么简单，但大概实现的功能差不多:
allocate 调用operator new ；deallocate 调用 construct 调用placement new （即在分配好的内
存上调用拷贝构造函数），destroy 调用析构函数。
两个std函数：
&C++ Code&
template&&&
class&In,&
class&For&
For&uninitialized_copy(In,&In,&For);
template&&&
class&For,&
void&uninitialized_fill(For,&For,&
const&T&&);
如&std::uninitialized_copy(i,&j,&data); 即将i ~ j 指向区间的数值都拷贝到data 指向的区间，返回的是最后一个初始化值的下一个位置。
std::uninitialized_fill(data,&limit,&val); &即将 data ~ limit 指向的区间都初始化为val 。
为了理解push_back 的工作原理，写个小程序测试一下：
&C++ Code&
#include&&iostream&
namespace&
class&Test
&&&&Test()
&&&&&&&&cout&&&&
"Test&..."&&&&
const&Test&&other)
&&&&&&&&cout&&&&
"copy&Test&..."&&&&
&&&&~Test()
&&&&&&&&cout&&&&
"~Test&..."&&&&
&&&&vector&Test&&v2;
&&&&Test&t1;
&&&&Test&t2;
&&&&Test&t3;
&&&&v2.push_back(t1);
&&&&v2.push_back(t2);
&&&&v2.push_back(t3);
从输出可以看出，构造函数调用3次，拷贝构造函数调用6次，析构函数调用9次，下面来分析一下，首先看下图：
首先定义t1, t2, t3的时候调用三次构造函数，这个没什么好说的；接着第一次调用push_back，调用grow进而调用alloc.allocate，
allocate 函数调用operator new 分配一块内存，第一次uncreate 没有效果，接着push_back 里面调用uncheck_append，进而调用
alloc.construct，即调用placement new（new (_Vptr) _T1(_Val); ），在原先分配好的内存上调用一次拷贝构造函数。
接着第二次调用push_back，一样的流程，这次先分配两块内存，将t1 拷贝到第一个位置，调用uncreate()，先调用alloc.destroy，即
调用一次析构函数，接着调用alloc.deallcate，即调用operator delete 释放内存，最后调用uncheck_append将t2 拷贝到第二个位置。
第三次调用push_back，也一样分配三块内存，将t1, t2 拷贝下来，然后分别析构，最后将t3 拷贝上去。
程序结束包括定义的三个Test 对象t1, t2, t3 ，析构3次，Vec&Test& v2; &v2是局部对象，生存期到则调用析构函数~Vec(); 里面调用
uncreate()， 调用3次Test 对象的析构函数，调用operator delete 释放3个对象的内存。故总共析构了6次。
在VC2008 中换成&vector&Test& v2; 来测试的话，输出略有不同，如下：
输出的次数是一致的，只是拷贝的顺序有所不同而已，比如第二次调用push_back 的时候，VC2008 中的vector 是先拷贝t2, 接着拷
贝t1, 然后将t1 释放掉。
最后再来提一下关于capacity 的计算，如下的测试程序：
&C++ Code&
#include&&iostream&
namespace&
&&&&v.push_back(
&&&&cout&&&&v.capacity()&&&&
&&&&v.push_back(
&&&&cout&&&&v.capacity()&&&&
&&&&v.push_back(
&&&&cout&&&&v.capacity()&&&&
&&&&v.push_back(
&&&&cout&&&&v.capacity()&&&&
&&&&v.push_back(
&&&&cout&&&&v.capacity()&&&&
&&&&v.push_back(
&&&&cout&&&&v.capacity()&&&&
&&&&v.push_back(
&&&&cout&&&&v.capacity()&&&&
输出为 1 2 4 4 8 8 8 即在不够的情况下每次增长为原来的2倍。
如果换成 vector&int& 测试，那么输出是 1 2 3 4 6 6 9，即在不够的情况每次增长为原来大小 + 原来大小 / 2；
看到这里，有些朋友会疑惑了，由1怎么会增长到2呢？按照原则不是还是1？其实只要看一下vector 的源码就清楚了：
&C++ Code&
void&_Insert_n(const_iterator&_Where,
&&&&&&&&&&&&&&&size_type&_Count,&
const&_Ty&&_Val)
//&insert&_Count&*&_Val&at&_Where
&&&&size_type&_Capacity&=&capacity();
if&(_Capacity&&&size()&+&_Count)
//&not&enough&room,&reallocate &&&&&&&&_Capacity&=&max_size()&-&_Capacity&/&
2&&&_Capacity
&&&&&&&&&&&&&&&&&&&&?&
0&:&_Capacity&+&_Capacity&/&
//&try&to&grow&by&50% &&&&&&&&
if&(_Capacity&&&size()&+&_Count)
&&&&&&&&&&&&_Capacity&=&size()&+&_C
&&&&&&&&pointer&_Newvec&=&
this-&_Alval.allocate(_Capacity);
&&&&&&&&pointer&_Ptr&=&_N
&&&&&&&&.....
_Insert_n 是被push_back 调用的，当我们试图增长为_Capacity&+&_Capacity&/&2; &时，下面还有一个判断：
&&if&(_Capacity&&&size()&+&_Count)
&&&&&&&&&&&&_Capacity&=&size()&+&_C
现在试图增长为 1 + 1/ 2 = 1； 此时因为 1 & 1 + 1 ; 所以&_Capacity = 1 + 1 = 2;&
其他情况都是直接按公式增长。
从上面的分析也可以看出，当push_back 的时候往往带有拷贝和析构多个操作，所以一下子分配比size() 大的空间capacity，可以减
轻频繁操作造成的效率问题。
C++ primer 第四版 Effective C++ 3rd C++编程规范
阅读(...) 评论()