STL之vector的使用
第一部分 使用入門
vector可用于代替C中的數(shù)組，或者MFC中的CArray，從許多說明文檔或者網上評論，一般一致認為應該多用vector，因為它的效率更高，而且具備很好的異常安全性。而且vector是STL推薦使用的默認容器，除非你知道你有特殊需要，使用vector不能滿足你的需求，例如需要容器在 head和tail高效的插入和刪除，或者在任何位置高效的刪除和插入操作，那么你可能使用deque或者list更加合適。
vector是連續(xù)內存容器，換句話說，標準要求所有標準庫實現(xiàn)的時候，vector中的元素的內存必須是連續(xù)的。所以對于插入和刪除的時間復雜度是很高的，因為刪除或者插入的時候，需要元素的移動，即元素復制拷貝。
vector的內部實現(xiàn)一般需要用到placement new ，所以效率很高，因為很多的時候，只要我們是使用得到，就可以省去很多的內存分配開銷。而且vector的使用，元素可以沒有默認的構造函數(shù)，但是需要拷貝構造函數(shù)的存在，這是使用CArray所無法實現(xiàn)的。
使用原則：
1，盡量使用vector代替C風格的數(shù)組或者CArray；
2，盡量使用算法代替手工寫的循環(huán)；
3，盡量使用vector本身的函數(shù)代替其他泛型算法；
vector的接口很容易看懂和使用，這里以一些例子來說明vector的用法。
1，填充vector
如果我們想用原始數(shù)組的內容填充vector，那么于有很多種方式。我們來一次學習vector的幾個方法。
例如我們有數(shù)組int v1[10] = {0,1,0,0,3,0,0,4,4,4};
初始化方式1：
vector<int> v2(10); //初始化size為10可以避免數(shù)組動態(tài)增長的時候不斷的分配內存
//v2.reserve(10);//同上，只要使用其中一個就可以了
for( int i=0; i<10; i++ )
{
v2.push_back(v1[i]);//增加一個元素
}
初始化方式2：
vector<int> v3(&v1[0],&v1[9]);//原始數(shù)組的元素指針可以作為迭代器來使用
初始化方式3：
vector<int> v4;
v4.reserve(10);
v4.insert(v4.begin(), &v1[0], &v[9]);
初始化方式4：
vector<int> v5(10);
copy(v5.begin(), &v1[0], &v1[9]);
原始數(shù)組的元素指針可以作為迭代器來使用。
原則：盡量使用reserve來減少不必要的內存分配次數(shù)。
原則：盡量使用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 i)
{
cout << i << endl;
}
方式1：
for( int i=0; i<v1.size(); i++ )
{
print(v1[i]);
}
這種方式是我們最熟悉的，但是不夠好，寫起來不夠簡潔。而且對于沒有隨機迭代器的其他容器來說，這樣做是辦不到的。
方式2：
typedef vector<int>:: iterator VIntIterator;
VIntIterator end = v1.begin();
for( VIntIterator i=v1.begin(); i != end; ++i )
{
print( *i );
}
注意：先計算end有好處，因為不必要每次去重復計算end,vector的end()不是常數(shù)時間的，所以先緩存下來能提高效率。寫算法的時候盡量使用!=比較迭代器，因為<對于很多非隨機迭代器沒有這個操作符。
但是這種方式也寫起來比較繁瑣。
方式3：
for_each( v1.begin(), v1.end(), print );
使用算法寫起來簡單多了。
使用算法的時候，可以使用函數(shù)對象，例如
class OutPut
{
public:
void operator ()( double i )
{
std::cout << i;
}
}
for_each( v1.begin(), v1.end(), OutPut );
3，vector中的刪除
刪除指定元素
vector<double> v1;
//….初始化代碼
vector<double>:: iterator i = find( v1.begin(), v1.end(), 3.0 );
if( i != v1.end() )
{
v1.erase(i);
}
這樣就真的刪除了么指定的元素了么？沒有。其實只是內部的元素作了移動，vector的刪除的時間復雜度是很高的。所以選擇容器的時候，如果需要頻繁在中間插入和刪除元素，那選擇vector就會影響效率了。
注意：插入或者刪除操作會使得迭代器失效。
原則：使用erase-remove慣用法刪除元素
v1.erase( remove(v1.begin(), v1.end(), 3.0), v1.end() );
4，vector是否為空
在判斷容器是否為空的時候，使用empty()來代替size()是否為了0的檢查方式，因為empty更加高效時間復雜度是常數(shù)時間的，size()時間復雜度不是常數(shù)時間的。
原則：使用empty判斷標準容器是否為空
5，vector中的查找
原則：盡量使用標準容器自帶的算法代替公共算法。
但是vector中并沒有多少自己的算法，倒是list中有remove ,remove_if,sort,reverse等算法。
find
find_if
6，使用交換技巧來修正過剩的容量
vector<int> v1;
//…初始化v1
//…刪除v1中所有的元素
但是這個時候v1的內存容量并不是0，還是很大的一塊內存沒有釋放，如果想清空
用v1.reserve(0);到不到目標，因為reserve只能擴大內存容量，并不能減小。
vector<int> v2;
v2.swap(v1);
這個時候就是真的將之內存容量降到最低了。
6，題外話：使用算法及其他技巧
原則：不要使用auto_ptr作為模板參數(shù)來建立容器，這會產生意想不到的陷阱，因為auto_ptr的拷貝有特殊的語義
原則：避免使用vector<bool>, 因為它不能當作標準容器來用
copy
find_if
for_each
原則：盡量使用區(qū)間成員函數(shù)代替它們的單元素參數(shù)兄弟成員函數(shù)
區(qū)間構造
區(qū)間刪除
區(qū)間賦值
區(qū)間插入
原則：使得容器中元素的拷貝操作輕量而正確，拷貝是STL中容器的運行的基本方式，將元素加入到容器，必然保持一個拷貝，容器中的元素不再是原來的那個元素，所以如果將指針加入容器，必須在容器離開作用域以前刪除指針所指的對象。
void fun（）
{
vector<object*> v1;
……//插入操作
for( vector<object*> :: iterator i = v1.begin(); i != v1.end(); ++i )
{
delete *i;
}
}
原則：注意對于 vector，任何插入刪除操作都會引起迭代器失效。所以要小心。
第二部分 使用錯誤討論
vector的語義常被誤解，所以經常會出現(xiàn)使用錯誤
1，案例一
你能發(fā)現(xiàn)下面的問題所在么？
void func( vector<.int>& v1 )
{
v1[0] = 1; //#1
v1.at(0) = 1; //#2
}
#1和#2有何區(qū)別？
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 << andl;
}
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 << andl;
}
}
函數(shù)func1存在什么問題(叢風格和代碼正確性做出評價)？會打印出什么？
2，案例二
使用vector的時候最容易發(fā)生的運行時錯誤，莫過于迭代器錯誤
注意：對于 vector，任何插入刪除操作都會引起迭代器失效。所以要小心
