副标题#e#
摘要: 本文先容了C++尺度库中的容器类vector，阐明白它的利益，而且发起在应用措施中利用它作为动态数组的优先选择，而不是MFC的CArray<>等其他类模板。最后先容了vector的接口和利用时的留意事项。
在一些利用 MFC 的措施中，常常看到很多措施利用 CArray<>，由于 CArray<>的设计问题，造成利用它的代码的巨大化，增加了维护难度。因此发起利用 ::std::vector<> 取代 CArray<>。
别的，也看到一些措施在用 malloc/realloc/free/new[]/delete[] 等手工打点内存。在应用措施中，手工打点内存是容易导致错误的，应该用 ::std::vector<> 之类的工具来打点动态数组。
由于 MSDN 中关于 ::std::vector 的内容较少，我们在这里做一些先容，供参考。
不熟悉 CArray<>/WIN32 也不要紧，这里提到它们的处所并不太多。
1. CArray<> VS ::std::vector<> ?
CArray<> 和 ::std::vector<> 一样，都是模板类，用于打点任意范例的工具的动态数组。都在解构时释放所打点的动态内存。因此都可以用于取代手工动态数组打点。
可是，CArray<> 是在 C++ 尺度化之前许多年(VC++2.0时代)设计的，其时对 C++措施设计，面向工具措施设计，模板措施设计等技能认识严重不敷，尤其是其时劈面向工具技能的错误信仰与宣传，造成 CArray<> 的设计有重大错误。
在 C++ 语言尺度化今后(1998)，以及 VC++ 6.0 出世今后，提供了尺度的::std::vector<> 模板，根基上在任何方面都要优于 CArray<>。Microsoft 由于要支持老的措施，因此一直保存了 CArray<>，但显然并没有规划凭据新的思想去成长它(至少应该提供operator=(CArray const&)吧)。
归纳综合起来，CArray<> 与 ::std::vector<> 有以下差异：
1) CArray<> 是 MFC 中的，::std::vector<> 存在于任何尺度的 C++ 实现中。因此，你用熟了 CArray<> 也只能在 MFC 顶用，若用熟了 ::std::vector<>，你可以在任何平台的任何 C++ 编译器下利用。利用尺度的部件也有利于别人领略你的措施。 . CArray<> 担任了 CObject，仅仅为了实现 serialization，这是不得当的， 违反了 "You don’t pay for what you don’t use." 的 C++ 设计原则。::std::vector<> 没有担任任何对象，只是实现了打点一个动态数组该做的事。
2) CArray<> 不是一个得当的值范例，譬喻下列操纵都是不正当的：
CArray<int,int> a;
CArray<int,int> b(a); // error, must use Copy().
b = a; // error, must use Copy().
b == a; // error, you must write your own.
b < a; // error, you must write your own.
与 CArray<> 相反，::std::vector<> 是一个当真设计的值范例，天生是可以拷贝结构和可赋值的。假如 T 是可较量的，那么 ::std::vector<T> 将自动地是可以较量的。
另外，由于涉及到四个非凡成员函数；
T(); // 缺省结构函数(default constructor)
~T(); // 解构函数(destructor)
T( T const& ); // 拷贝结构函数
T& operator=( T const& ); // 拷贝赋值函数
的自动生成，假如利用 CArray() 作为 T 的成员变量，那么上述的四个非凡函数中的后两个将无法自动生成，需要手工写：
struct T
{
T() {}
T( T const& t )
{
a_.Copy( t.a_ );
i_ = t.i_;
d_ = t.d_;
s_ = t.s_;
}
T& operator = ( T const& t )
{
if( this != &t )
{
a_.Copy( t.a_ );
i_ = t.i_;
d_ = t.d_;
s_ = t.s_;
}
return *this;
}
private:
CArray<int,int> a_;
int i_;
double d_;
::std::string s_;
};
假如利用 ::std::vector<>：
struct T
{
private:
::std::vector<int> a_;
int i_;
double d_;
::std::string s_;
};
上面列出的三个非凡成员函数都不需要写。长处是明明的：当你增减 T 的成员变量时，你不必到T(T const&) 和 operator=() 中去相应地增减。
#p#副标题#e#
3) 没有现成的算法可以对 CArray<> 举办操纵，而尺度 C++ 里的尺度算法大多都可以直接在
::std::vector<> 上运行。譬喻：
static int const init_vals[] = { 3, 1, 4, 1, 6, 9 };
vector<int> a( init_vals, init_vals + 6 );
*find( a.begin(), a.end(), 6 ) = 5; // 把6改成5
sort( a.begin(), a.end() ); // 排序。
#p#分页标题#e#
可以说，CArray<> 的主要设计错误是把一个原来应该是一个简朴的“值”范例的对象设计成一个难用的“工具”范例了。所有的“值”的好特性都丧失了，但那些从CArray<>担任的派生类呢？
CByteArray等的问题与 CArray<> 的问题一样，甚至更多(譬喻，CPtrArray，永远不要用)。
同样，其他的 MFC container 模板，象 CMap<>, CList<> 等，都有雷同问题，都应该用
::std::map<>，::std::list<> 等设计更好的对象取代。
2. ::std::vector<> 在那边?
::std::vector<> 在头文件 <vector> 中界说:
(留意，尺度的 C++ 头文件都没有 .h 后缀，有 .h 的文件是与 C 兼容的，或支持老的不尺度的对象，象 <iostream.h>。)
namespace std
{
template<typename T, typename A = allocator<T> >
struct vector
{
// 详细内容稍后接头
};
template<typename T, typename A>
bool operator == ( vector<T,A> const& a, vector<T,A> const& b );
template<typename T, typename A>
bool operator != ( vector<T,A> const& a, vector<T,A> const& b );
template<typename T, typename A>
bool operator < ( vector<T,A> const& a, vector<T,A> const& b );
template<typename T, typename A>
bool operator >= ( vector<T,A> const& a, vector<T,A> const& b );
template<typename T, typename A>
bool operator > ( vector<T,A> const& a, vector<T,A> const& b );
template<typename T, typename A>
bool operator >= ( vector<T,A> const& a, vector<T,A> const& b );
}
vector<> 界说在 namespace std 中，利用时为了淘汰击键次数，凡是利用一个范例界说缩短范例名称：
#include <vector>
typedef ::std::vector<int> IntVector;
IntVector a;
IntVector b( a );
IntVector c;
c = b;
assert( a == c );
请留意 <vector> 中界说了六个 vector<T,A> 的较量函数。这些函数只在真的用到时才会被实例化，才会要求 T 也提供 operator==() 和 operator<()。
别的，A = alloctor<T>：用于提供一个用户界说的存储打点类。由于这个参数很罕用到，并且在 VC++6 的实现中有问题，不能用，因此以下的接头忽略这一部门的内容。
3. ::std::vector<> 中的范例界说
vector<> 中界说了一些范例，下面只列出常用的：
typedef T value_type;
typedef T0 iterator;
typedef T1 const_iterator;
typedef T2 reverse_iterator;
typedef T3 const_reverse_iterator;
value_type 就是 vector<T> 的元素范例，也就是 T。当写通用的算法处理惩罚任意范例的 vector<> 或其他容器范例时是很有用的。
iterator/const_iterator 是两个 vector<> 的实现界说的未知范例，用于会见vector<> 中的元素，雷同于 T*/T const* 指针，他们的区别是一个指向的元素可被修改，另一个只可以读：
typedef ::std::vector<int> IntVector;
IntVector::iterator iter;
IntVector::const_iterator c_iter;
// ...
++iter; iter++; // ok: increment, post-increment.
--iter; iter--; // ok: decrement, post-decrement.
++c_iter; c_iter++; // ok: increment, post-increment.
--c_iter; c_iter--; // ok: decrement, post-decrement.
*iter = 123; // ok.
int k = *iter; // ok.
k = *--c_iter; // ok.
*c_iter = k; // error.
c_iter = iter; // ok: iterator is convertible to const_iterator.
iter = c_iter; // error: can't convert const_iterator to iterator.
在利用上 iterator/const_iterator 和 T*/T const* 基内情同，事实上有些vector<> 的实现里就是用 T*/T const* 实现 iterator/const_iterator 的，但又不行以把 iterator/const_iterator 看成真正的 T*/T const*：
T* p = iter; // may fail to compile.
T const* q = c_iter; // may fail to compile.
reverse_iterator/const_reverse_iterator 与 iterator/const_iterator 雷同，但以相反的序次(从尾至头)会见 vector 中的元素。
各类百般的 iterator 在 STL 中有出格重要的意义，但这里我们不做详细先容。只要领略通过 iterator 可以会见 vector 中的元素，或许相当于一个指示位置的指针就行了。
4. ::std::vector<> 的结构
vector<> 提供了以下结构函数：(忽略 allocator 参数)
vector();
vector( size_t n, T const t=T() );
vector( vector const & );
vector( const_iterator first, const_iterator last );
1) vector();
结构一个空的 vector，不包括任何元素。
IntVector v1; // 空的整数向量。
2) vector( size_t n, T const t=T() );
结构一个 n 个沟通元素 t 构成的 vector。假如不给出 t，那么将用 T() 做缺省值:
IntVector v2( 100, 1234 ); // 100 个 1234.
IntVector v3( 100 ); // 100 个 0。
3) vector( vector const& other );
复制结构函数，复制 other 中的内容：
IntVector v4( v2 ); // 100 个 1234。
4) vector( const_iterator first, const_iterator last );
事实上，这个结构函数应该为
template<typename Iter>
vector( Iter first, Iter last );
#p#分页标题#e#
即拷贝任意的序列 [first,last) 到 vector 中。由于 VC++6sp0 编译措施的限制， Iter 被换为 const_iterator 了。不外，可巧 const_iterator就是 T const*，所以可以如下利用：
int a[] = { 1, 2, 3, 4, 5 };
IntVector v5( a, a + 5 ); // {1,2,3,4,5}
IntVector v6( v5.begin() + 2, v5.end() ); // {3,4,5}
5. 会见 vector<> 中的元素
以下成员函数/运算符用于会见 vector 中的一个元素:
T& at( size_t n );
T const& at( size_t n ) const;
T& operator [] ( size_t n );
T const& operator [] ( size_t n ) const;
T& front();
T const& front() const;
T& back();
T const& back() const;
请留意，由于 vector 是一个“值”语义的工具，所有的操纵函数都必需严格担保 const 的正确性。所以，所有的元素会见要领都有 const 和非 const两个版本。
at(n) 和 operator [] (n) 都返回下标为 n 的元素的引用，他们的区别是，at() 举办下标越界查抄，若发明越界，抛出 range_error 异常，operator[]不举办下标查抄。
front() 返回下标为 0 的元素的引用，back() 返回最后一个元素的引用。
int a[] = { 4, 1, 4, 1, 5, 8 };
IntVector v( a, a + 6 );
// 利用 front(), back():
v.front() = 3;
v.back() = 9;
// 利用 operator [] ():
for( size_t i = 0; i < v.size(); ++i )
::std::cout << v[i] << '\n';
6. ::std::vector<> 的存储打点
以下成员函数用于存储打点：
void reserve( size_t n );
size_t capacity() const;
void resize( size_t n, T t=T() );
void clear();
size_t size() const;
bool empty() const { return size() == 0; }
size_t max_size() const;
别的，push_back(), insert() 等也涉及到存储打点，后头另行先容。
1) max_size()
返回 vector<T> 理论上可以装的最多 T 的个数。这只是一个理论上的数字， 或许是 4GB/sizeof(T)，没有多大实用代价。在措施中不要用。
2) size()
返回 vector<T> 中实际装的 T 的个数。相当于 CArray<>::GetSize()。
3) empty()
假如 vector<T> 中没有任何 T 工具，返回 true。也就是返回 size() == 0。
4) clear();
排除 vector<T> 中的所有 T 工具。执行后 empty() 返回 true。大抵相当于 resize(0)，但不要求 T 可被缺省结构。相当于 CArray<>::RemoveAll()。
5) resize( size_t n, T t = T() );
将 vector 中的元素个数配置为 n，n 可以大于 size() 也可以小于 size。假如 n 小于 size()，那么 vector 中下标为 n..size()-1 的元素都将被解构。假如 n > size()，那么将在 vector 的后头新增加
n – size() 个沟通的元素 t。在增大 vector 时，大概发保留储再次分派。总之，挪用resize( n, t ) 后，(size() == n) 创立。
请留意，假如挪用 resize( n ) 不带参数 t ，那么 T 必需可以缺省结构。
6) reserve( size_t n );
事先分派至少可以生存 n 个 T 工具的空间。挪用后 (capacity() >= n)创立。
7) capacity();
返回已经分派的存储空间够容纳的 T 范例工具的个数。后续的增加元素操纵(如 push_back(), insert())假如增加元素后 vector 中的总元素个数不高出 capacity()，那么 vector 的实现担保不从头分派存储空间。
vector 打点的动态存储空间是持续的。执行操纵
IntVector v(7, 1); // seven ones.
v.reserve( 12 );
后，v 的状态可以用下图暗示:
/--size()---\
|1|1|1|1|1|1|1|-|-|-|-|-|
\--capacity()---------/
个中，1 是已经结构的 int 范例的工具，- 是可以结构一个 int 范例的工具，但还没有结构的原始空间。再执行
v.push_back( 2 );
v.push_back( 3 );
后，v 的状态可用下图暗示：
/----size()-----\
|1|1|1|1|1|1|1|2|3|-|-|-|
\----capacity()-------/
执行 resize( 11, 4 ); 后：
/----size()---------\
|1|1|1|1|1|1|1|2|3|4|4|-|
\----capacity()-------/
capacity() >= size() 老是创立的。对付下标为 [size()..capacity()-1]的未结构工具的存储空间，是不行以会见的：
v[11] = 5; // undefined behavior - anything can happen.7. 添加元素到 vector 中
下列操纵添加元素到 vector 中，并大概引起存储分派：
#p#分页标题#e#
void push_back( T const& t );
void insert( iterator pos, T const& t=T() );
void insert( iterator pos, size_t n, T const& t );
template<typename Iter>
void insert( iterator pos, Iter first, Iter last );
push_back() 是把一个元素添加到 vector 的末端。insert() 是把一个 t，或 n 个 t，或从 first 开始到 last 竣事的一个序列插入到 pos 指示的位置之前。
当插入元素后 size() 将会大于 capacity() 时，将引起自动存储分派。vector 将会分派一个比需要的存储区大若干倍(凡是是1.5到2)的新的存储区，把老的元素拷贝已往，同时完成添加或插入，然后释放老的存储区。
这就是说，vector 自动存储分派的空间巨细是指数式增长的，这可以担保多次添加元素到 vector 中时，平均用时是靠近于常数的。
IntVector v;
// add 0, 1, ..., 99 to v:
for( int i = 0; i < 100; ++i )
v.push_back( i );
// append 9, 8, 7,..., 0 to the end:
int a[] = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
v.insert( v.end(), a, a + 10 );8. 删除元素
下列成员函数完成元素删除：
void erase( iterator );
void erase( iterator first, iterator last );
void pop_back();
void clear();
这些函数别离删除一个，一串，最后一个，或全部元素。
IntVector v;
for( int i = 0; i < 100; ++i )
v.push_back( i );
// 删除 50, 51, ..., 89:
v.erase( v.begin() + 50, v.end() - 10 );
// 删除 49, 48:
v.pop_back();
v.pop_back();
// 全部删除：
v.clear();
留意，删除操纵不会引起存储分派，因此 capacity() 稳定。
9. 作为序列会见 vector 中的元素
序列(sequence)在 STL 中是一个很是重要的观念，所有的容器范例和算法都涉及到，并且所有的算法都是成立在“序列”这个观念之上的。
“序列”是一个线性布局，由一个指示其起始和一个指示竣事的叠代子(iterator)来抉择。假如 first 和 last 是某种范例的叠代子，那么常常用[first, last) 来暗示一个序列。留意，first 指向的元素是这个序列的一个元素，而 last 指示的是这个序列最后一个元素之后的位置，大概基础没有元素可以会见。这种半闭半开的区间暗示是整个 C++ 尺度中的约定，并且确实可以简化措施。
叠代子是传统的 C/C++ 中指针的抽象和进一步分类。在 C++ 中把 iterator分别为 input iterator, output iterator, forward iterator,bidirectional iterator, random access iterator 五类。个中的 randomaccess iterator 是最强的一类，即答允的操纵最多。C++ 中的指针范例以及vector<>/deque<> 的 iterator/const_iterator/reverse_iterator/const_reverse_iterator 都满意 random access iterator 的要求。
vector<> 中界说了以下函数用于获取被节制(打点的)序列(动态数组)的各类叠代子：
iterator begin();
iterator end();
const_iterator begin() const;
const_iterator end() const;
reverse_iterator rbegin();
reverse_iterator rend();
const_reverse_iterator rbegin() const;
const_reverse_iterator rend() const;
这里我们不接头叠代子的一般观念，只举几个 random access iterator 的例子：
int a[] = { 1, 2, 3, 4, 5, 6 };
IntVector v( 100, 1 ); // 100 个 1。
下图是有十个元素的 vector 的 begin()/end()/rbegin()/end() 的示意：
#p#分页标题#e#
begin() ----------> end()
| |
v v
|0|1|2|3|4|5|6|7|8|9|
^ ^
| |
rend() <---------- rbegin()
IntVector v;
for( int i = 0; i < 10; ++i )
v.push_back( i );
// print 0, 1, 2, ..., 9:
for( IntVector::iterator i = v.begin(); i != v.end(); ++i )
::std::cout << *i << '\n ';
// print 9, 8, ..., 0:
for( IntVector::reverse_iterator i = v.rbegin(); i != v.rend(); ++i )
::std::cout << *i << '\n ';
除了利用 begin()/end()/rbegin()/rend() 来遍历 vector 中的元素外，由于 vector 打点的空间是持续的，因此可以直接取地点举办处理惩罚：
::std::vector<HANDLE> handles;
handles.push_back( handle1 );
handles.push_back( handle2 );
::WaitForMultipleObjects(handles.size(), &handles[0],TRUE, INFINITE);
这在与 C 库函数接口时尤其有用。
10. 赋值和互换
vector<> 是可以赋值的，这也是一般的“值”范例必需提供的操纵：
IntVector v( 100, 123 );
IntVector v1;
v1 = v;
vector 别的还提供了
template<typename Iter>
void assign( Iter first, Iter last );
void assign( size_t n, T const& t = T() );
用于赋值：
int a[] = { 1, 3, 5, 7 };
v.assign( a, a + 4 ); // v 将包括 1, 3, 5, 7.
v.assign( 100 ); // 100 个 0。
尚有一个很重要的操纵：
void swap( vector& v ) throw();
用于互换两个同范例的 vector 的值。它的特点是快速(只需要互换内部的三个指针)，不发生异常。这在写一些担保异常安详的措施时很是有用。
事实上，swap() 根基上已经被看成雷同于 operator=() 的一个“值”范例应该提供的根基操纵，::std::swap() 也应该为用户界说的范例举办特例化，挪用相应的类的成员 swap() 函数：
struct MyVal
{
// blah blah.
void swap( MyVal& ) throw();
};
namespace std {
template<>
void swap( MyVal& a, MyVal& b )
{ a.swap( b ); }
}
关于 swap()，值得专文接头。这里我们只指出，vector<T>::swap() 是快速的，不抛出异常的，很有代价。
11. 利用 vector 时的存储打点计策
从前面的先容中可以看到，vector 的自动存储分派是指数式的增加存储空间，并且永不缩小已经分派的空间。这在大大都环境下是符合的。 假如应用措施事先知道要用到的元素个数，可以先挪用 reserve() 来保存(分派)空间，这样可以制止今后增加元素时不须要的从头分派和元素拷贝：
IntVector v;
v.reserve( 100 );
for( int i = 0; i < 100; ++i )
v.push_back( i );
请留意，reserve() 和 resize() 是本质上完全差异的。reserve(n) 保存的是未利用而可以或许利用的原始空间，而 resize(n) 是真的建设了 n 个工具:
IntVector v;
v.resize( 100 ); // v 已经包括 100 个 0.
for( int i = 0; i < 100; ++i )
v[i] = i; // 可以赋值
有时候，一个 vector 大概增长到较多个元素，然后又淘汰到较少的元素个数，这时，大概但愿缩小 vector 分派的空间以节省内存。CArray<> 中提供了 FreeExtra()，但 vector<> 并没有提供相应的函数。这时必需举办复制：
IntVector(v).swap( v );
有一种观点认为拷贝结构函数同时也复制了capacity()，而尺度中并没有很明晰地指出这一点，因此更安详的要领是
IntVector(v.begin(),v.end()).swap(v);
假如一个 vector 中大概要存储的元素个数较多(譬喻，高出100个)，并且事先无法确定其个数(因此无法挪用 reserve())，那么凡是 vector 不是一个得当的数据布局，应该思量用 ::std::deque<>。与 vector<> 对比，deque<>不担保背后的存储空间是持续的(因此象上面的WaitForMultipleObjects()中的应用不能用 deque<HANDLE> 取代)，但有较好的伸缩性，还可以在数组的前端用 push_front()/pop_front() 增减元素(hence its name, doubly endedqueue)。
