vector relation

::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() >= 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;

// 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();

這些函數分别删除一個，一串，最後一個，或全部元素。

    v.push_back( i );

// 删除 50, 51, ..., 89:

v.erase( v.begin() + 50, v.end() - 10 );

// 删除 49, 48:

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()

for( int i = 0; i < 10; ++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 )

除了使用 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 另外還提供了

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() 來保留(配置設定)空間，這樣可以避免以後增加元素時不必要的重新配置設定和元素拷貝：

v.reserve( 100 );

請注意，reserve() 和 resize() 是本質上完全不同的。reserve(n) 保留的是未使用而能夠使用的原始空間，而 resize(n) 是真的建立了 n 個對象:

v.resize( 100 ); // v 已經包含 100 個 0.

    v[i] = i; // 可以指派

有時候，一個 vector 可能增長到較多個元素，然後又減少到較少的元素個數，這時，可能希望縮小 vector 配置設定的空間以節約記憶體。CArray<> 中提供了 FreeExtra()，但 vector<> 并沒有提供相應的函數。這時必須進行複制：

IntVector(v).swap( v );