Edison.X. Blog

0. 前言

首先感謝 novus 在 vector 心得整理 提出之意見，讓我花了點時間整理以前閱過書籍及本身遇過的問題。一開始這篇本想從 containner 裡下去著手，再提到一些 Iterator，但實在是太包山包海，故只拿 vector 做為分析對象。

標題方面覺得用英文較清楚點 ( 中文味道有點跑掉 ) ，另筆者犯懶，vector 裡面資料型態都沒放 class，全都放 POD。文章重點如下

(1) initializer lists
(2) vector constructor 
(3) memory mamagement in vector
(4) Iterator stable
(5) vector<bool>
(6) vector constructor in class
(7) Others

Reference 主要為 C++ Primer , C++ Reference , 另一些是以前解掉的問題 , 原始 Reference 已不可考，若有參考到您的文章卻沒註明時請告知，小弟可加註參考來源，或不願公開討論時，會將該 section 刪除。

1. initializer lists

一個 new operator 常見問題是，new 有沒有辦法順便給初始值？

以 int *v = new int[3] 為例，new 時想順便設定 v[0]=1, v[1]=2, v[2]=3，

怎麼做？

這在 C++11 之前辦不到，g++ 編譯參數下 -std=c++11 或 -std=c++0x 可以做得到，

int *v = new int[3]{1,2,3};

注意到大括號與小括號的使用，

int *v1 = new int[3] ;

int *v2 = new int{3};

這兩個是不同意思。v1 指的是配置 3 個 int ，不給初始值； v2 指的是配置 1 個 int，初始值給 3。大括號裡面的東西統稱為 initializer lists

除了 new 可以這麼做之外，vector 也可以這麼搞。

vector<int> v{1,2,3};

v 就自動給三個元素 1, 2, 3 當初值。

尷尬的是，VC 沒有支援上面寫法 ( 環境為 vc2012  )，也可能是筆者沒找到類似 c++11 之編譯參數。

2. vector constructor

基本之 constructor 請查手邊現有資源，或到 C++ Reference 查詢。讓人比較有興趣的是如何配置一份二維 vector<int> 出來，效果相當於 int v[x][y]。

先想一下 vector<Type> Var(Count, Val) ; 這段。

(1) Var : 是一個 vector 型態之變數，裡面元素存放的是 Type 資料型態(或物件)。

(2) Count : 在初始化的時候，Var 就已有 Count 個元素。

(3) Val : Var 裡，每個元素 (一共 Count 個 )，都存放 Val。

(4) 如 : vector<int> v1(3, 1);  v1 初始大小設 3，每個元素都設 1。

換個角度想，若裡個 vector < Type > 裡面的 Type，是一個 vector<int> 時，不就變二層了嗎？

假設要配置的是 int v[x][y]，初值全都設 1，需注意的是裡面的 Count 與 Val 之問題。

vector< vector<int> > v2( x , vector<int>(y, 1) );

(1) v2 : 是一個 vector<int> 型態變數。

(2) x  : v2 共有 x 個 vector<int>

(3) vector<int>(y, 1)  : 每個 v2[i]  (就是 vector<int>)，再以 vector<int>(y, 1) 做為初值設定。

如此配置下來便可將 v2 當  int v2[x][y] 使用。要查有幾個 ROW 時用 v2.size()，要查有幾個 COL 時用 v2[0].size()，其它沒什麼差別。

三維的話呢？應有其它更好的方案。

3. memory management in vector

(3-1) 動態配置策略

大概不多人對這問題有興趣，這份「廣為流傳」的動態配置策略筆者很疑惑，不少書籍或文章都會提到，當(實際用量) > (最大容量) 時是增長 2 倍，而 1/2/2 = 0.25，所以當 (實際用量) < 0.25 * (最大容量) 時就縮為一半。C++ Primer 裡面有份例子，測試例子大致如下

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector<int> v;
    size_t c1 = v.capacity();
    size_t c2;

    for(int i=0; i<100000; ++i) {
        v.push_back(i);
        c2 = v.capacity();
        if(c1!=c2) {
            c1 = c2;
            cout << "capacity = " << c1 << endl;
        }
    }
    return 0;
}

這部碼在 g++ 與 vc 下結果並不相同，g++ 底下是很有規律的 1 2 4 8 16 32 .... ，

而 vc 下結果是 1 2 3 4 6 9 13 19 28 42 63 94 141 211 316 474 711 1066 1599 2398 3597 5395 8092...，這規律筆者還真看不出來。

(3-2) * vector 拿來當引數

這問題大概是呼叫 C 寫的 API 時會發生的問題吧，筆者沒實際遇過，所以也舉不上什麼特別例子。

先從小例子說起，假設由 C 寫之函式如下。

void display(int *arr, int n)
{
    int i;
    for(i=0; i<n; ++i)
        printf("%d", arr[i]);
}

vector<int>  要怎麼傳給 display 當引數？其實 vector 有保證記憶體是連續的，所以直接傳 &arr[0] 就行了。

int main()
{
    const size_t n = 3;
    vector<int> v(n, 1);
    display(&v[0], n);
    return 0;
}

尷尬的一點又來了，如果變成 void display(int **arr, int row, int col); 怎辦？

目前筆者也沒好的方法能由 vector< vector<int> > 傳進去當引數，或許這也是為何大多 C 寫 library 時都盡可能用一維方式表達之 其中一個 原因吧(正常原因我想是 malloc pointer over head 問題，及記憶體碎片化問題) 。

若 API 由 C++ 開發時，直接以 Reference 傳進 vector 就沒這些問題，用 Reference 一方面是避開複製成本問題， 一方面若函式本身具 reallocate 功能時也不會死碼。

(3-3) Capacity / Size

有幾份和大小 / 容量相關之注意事項附上。

若 vector 在管理記憶體時，時常在 heap 做 realloc 動作會拖垮效能，於是會有 capacity 與 size 兩個東西。所謂的 capacity 指的是目前在 heap 上配置的元素個數，但實際上使用的數量是 size，而不是 capaicty ( 也就是 capacity >= size 必定成立)。故在討論時，應將 capacity / size 獨立思考，視為不同東西。

std::vector::size  : 取得目前 vector ，實際使用之元素個數。

std::vector::capacity : 取得目前 vector ，可使用之元素個數。

std::vector::max_size : 取得 vecotr 「可以配置」的最大元素個數，注意它和 size 與 capacity 的不同，這個數值其實很重要，特別是在做 resize / reverse 前建議先用這個做簡單防呆，降低成本。當 std::vector::reverse 比這個數值還大時，會丟出 length_error 例外。

std::vector::resize : 指定 vector 元素個數。若 resize 比原本元素還多時，多出來的預設會變 0 ，當然也可用 vector::resize(Count, Val)，多出來的會以 Val 填滿。若 vector 放的是 class，resize 比原本的還小時， 不會 呼叫 destructor。

std::vector::reverse : reverse 是自己控制記憶體空間，若進行 reverse(100)，則是在 heap 裡 至少保留 了 100 個可用元素。考慮一種情況，若 reverse 比原本的 std::vector::size 還小時，這時並不會把 heap 縮得比 size 還小，故用了 至少保留 這字眼。

std::vector::empty : empty 並不會做任何 capacity / size 上之調整，它只是 判斷 目前 vector 裡是否有元素存在。

std::vector::clear : clear 是將 vector 整個清掉，若 vector 裡放的是 class，clear 會逐一呼叫 destructor，但 capacity 並不一定會直接清零 ( 且通常都不會動 )。

std::vector::erase : erase 可指定將 vector 某個元素，或某個區段之元素清除，會呼叫 destructor。

(3.4) std::vector::at / operator[] 

一般用到 vector 時，大多索引方式用的是足標運算子 (operator [] )，較少用 at，這兩個函式相似，但不完全一樣，最大差別是，std::vector::at 會檢查 bounding，但 operator[] 不會檢查 bounding，若超界時，std::vector::at 會丟出 out_of_range 例外。

(3.5) 佔住不用？

很尷尬一點，vector 在 heap 管理之函式為 reverse，即使先將 vector 做 clear / erase ，再做 reverse，回去查 capacity ，整個大小還是不會變小，目前所熟知之解決方案是，將它和另一個capacity 為 0 之 vector 做交換。

vector<int> v(1000);
/* after do something */
/* want to clear current.. */
vector<int> zero; // zero(0);
v.swap(zero);

template<typename T>
inline void vec_clr(vector<T> & v){
    vector<T> t;
    v.swap(t);
}

4. Iterator Stable

Iterator Stable 不知道是不是專有名詞 ( 恕筆者見識淺薄 )，這裡講的是 Iterator 失效問題。

vector 裡一些操作，會使得原本之 iterator 失效，必須再重新取得才可，最常見的碼是 erase ，假設要在 vector 裡面刪除某個元素

int main()
{
    vector<int> v(10);
    vector<int>::iterator it, end;
    const int val = 1;
    // initialize
    for(size_t i=0; i<v.size(); ++i) v[i]=i;
    it = v.begin();
    end = v.end();
    // remove
    while(it!=end){ /* error */
        if(*it == val) 
            v.erase(it);
        ++it; /* error */
    }    
    return 0;
}

(1) erase 會返回「被移除元素之下一個元素」，故至少要寫 it = v.ease(it) ; ++it 略過，但還是錯誤。

(2) 在做 erase 時，iterator end 會改變，故不能再拿之前的做參考，必須在 loop 裡重覆更新判斷。

稍改一下如下 < 它還是錯的 >。

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector<int> v(10);
    vector<int>::iterator it, end;
    const int val = 1;
    // initialize
    for(size_t i=0; i<v.size(); ++i) v[i]=i;
    // remove
    for(it=v.begin(); it!=v.end(); ++it)
        if(*it==val) 
            it = v.erase(it);
    return 0;
}

上面這版程式有概念了，會更新 erase 後之 iterator，不過邏輯上有誤，最直接的測試法，是將 vector 全設 1。因在 erase 後，會直接跳開下個元素，更正如下。

int main()
{
    vector<int> v(10, 1);
    vector<int>::iterator it, end;
    const int val = 1;
    for(it=v.begin(); it!=v.end(); )
        if(*it==val) it = v.erase(it);
        else ++it;
    return 0;
}

當然刪除的方法有很多種，如 find + erase，remove_if 等方式，這裡就不再贅述。

不只 erase 有這問題，只要是和「刪除」、「插入」、「變大小」有關的都有這 問題，如 clear、pop_back、push_back、insert、resize、reserve 等都會產生，另外在做 pop_back(vector, list, deque) / pop_front(list, deque) 時，若 container  empty 成立，結果將不明確，故需做額外判斷。然而在關連式容器(set, multiset, map, multimap ) 並不會有此問題。如

#include <iostream>
#include <map>
using namespace std;

int main()
{
    map<char, int> m;
    map<char, int>::iterator it, end;
    char val = 'a';

    // fill value
    it = m.begin();
    for(int i=0; i<5; ++i)
        m.insert(it, pair<char, int>('a'+i, i));

    // remove, caution here !!
    it = m.begin(), end = m.end();
    while(it!=end)
        if(val==it->first)    it=m.erase(it);
        else ++it;
    // display
    for(it=m.begin(); it!=m.end(); ++it)
        cout << it->first << ' ' << it->second << endl;
    return 0;
}

其他更深入或較隱喻的問題 (像是在 class 中，iterator 失效問題)，可參考 The C++ Standard Library: A Tutorial and Reference 一書。

5. vector<bool>

vector<bool> 已被特偏化，每個元素只有佔 1 bit，且尷尬的是，傳回值並不是第 n 個 bit，忘了哪本書的條款有提到，never use vector<bool>。

替代方案有 bitset<n> ，非得用 vector<bool> 時也建議用 deque<bool>，其它的就不多述。

6. vector constructor in class

一個較初學的問題是，在一份 class 裡面含一個 vector，想在預設的時候 不調用 resize 給一份大小，該怎做？它的概念如下 (這份碼不能 run)。

class Arr{
    vector<int> mVec(10);
};

當然連編譯都過不去。手法大概只有從 constructor 去下手。

class Arr{
    vector<int> mVec;
public:
    Arr() { mVec.resize(10);}
};

這方法可行，但也還不是好的方法，應擅用建構初始列

class Arr{
    vector<int> mVec;
public:
    Arr() : mVec(vector<int>(10)) {}
};

也可以做 vector< vector<Type> > ，其它的就不贅述。

7. Others

首先有兩個東西意義不同

vector<Type*> v1;

vector<Type > *v2;

這兩樣東西都有人在用，唯筆者 trace 不夠多，沒辦法給例說明。

這兩種作法，大多是因 Type 是自定義之 class，早期有篇文章認為用 vector 搭 pointer 比 vector 內崁好，原因在於那些 pointer 可以自己用 delete 方式，強制把記憶體釋放出來，如此物件之生命週期之掌控便可較彈性。

當然主要原因不是這個，因上面有說過了，要釋放時可用 swap，若要真的重新 realloc heap 時，只要調整 swap 之對象大小即可。

筆者想了一下，主要原因大概是實作多型吧 ( vector<Type* > v )，由於說下去會把 C++ 後面二、三個章節講完，這裡就停住不講，其他的有興趣再翻翻「多型」相關章節。

至於 vector<Type > *v2，說實話筆者真的又更少見了。

這篇文章就先至此，以後想到有什麼東西再追加及更新日期吧。