摘要: 本文介紹了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=() 中去相應地增減。
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() ); // 排序。
可以說，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 );
即拷貝任意的序列 [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 中，並可能引起存儲分配：
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;8. 刪除元素
// 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 );
下列成員函數完成元素刪除：
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 };
[a, a + 6) 是一個隨機訪問序列，指示了 a[] 中的所有元素。這裡疊代子的類型為 int*。
[a + 2, a + 4) 也是一個序列，指示了 a[] 中的 3, 4 兩個元素。疊代子的類型仍然是 int*。
IntVector v( 100, 1 ); // 100 個 1。
[v.begin(), v.end()) 是一個隨機訪問序列，指示了 v 中的所有元素，疊代子的類型是 IntVector::iterator。
[v.begin() + 10, v.end() - 20 ) 也是一個隨機訪問序列，指的是 v 中除了頭 10 個和尾 20 個元素外的其它元素。
[v.rbegin(), v.rend() ) 是一個隨機訪問序列，指的是 v 中的所有元素，但與 [v.begin(), v.end() ) 不同，這個序列是從尾到頭遍歷所有元素。
[v.rbegin() + 20, v.rend() - 10) 與 [v.begin() + 10, v.end() - 20 )指示的元素相同，但遍歷順序相反。
下圖是有十個元素的 vector 的 begin()/end()/rbegin()/end() 的示意：
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)。
