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,說實話筆者真的又更少見了。


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

 

edisonx 發表在 痞客邦 PIXNET 留言(7) 人氣()


留言列表 (7)

發表留言
  • novus
  • 每次看到你寫文章,我都會想到可以討論的新話題說~~

    1. list 的 iterator 應該也是 stable 的,主要關鍵在於記憶體連續性。

    2. 用 vector 存指標通常有兩個原因
    (1)vector 非常依賴複製,但有時候物件的複製成本很高,用指標比較有效率。
    (2)同前,像 sort 這類的演算法,複製物件可能對速度造成戲劇性的衝擊。
    (3)多型。事實上在多型出現的時候,幾乎都是用指標和參考進行操作,很少直接操作物件本身。

    但一般不會用容器存放原生指標,因為非常容易出問題。比較妥善的做法是存 unique_ptr 之類的東西,或者是另外有 pool 統一建立與銷毀物件,vector 只是提供存取指標而已。

    3. 呃... vector<Type > *v2 並不是什麼奇怪的東西。之所以很少見,是因為適用 vector<Type > *v2; 的場合有 99.99% 用 vector<Type > & v2會更好


    其他等我想到或者你有問題再說吧

  • list iterator 應 stable 沒錯, 我再翻一次 C++ Primer 4e 9.3.7 caution,應是我一直誤會它的敘述。

    vector 存指標,您寫出原因後真的想到一些類似的狀況適合這麼做,unique_ptr 是真的還實際用過 (真汗顏) ,查了一下 C++0x 似乎不錯用。

    >> 每次看到你寫文章,我都會想到可以討論的新話題說~~
    若不會擔誤 novus 太多時間,很歡迎留言討論,不然我永遠只是半調子而已 :)

    edisonx 於 2012/11/02 23:51 回覆

  • novus
  • 提供一個有趣的用途

    // 真正的物件在此,假設物件很肥,複製很花時間
    vector<Data> data;

    // 讓 index1、index2 等於 data 各元素的指標
    vector<Data*> index1;
    vector<Data*> index2;

    // 用不同的條件排序 index
    sort(index1.... compByName() );
    sort(index2.... compByBirthday() );

    將上面全部包成一個 class,於是你就有三套不同的索引順序來存取原來的 data 了。
  • 這個例子真妙,我還真沒想過可以這麼做.. 我再細思一下詳細做法,謝謝您的提供,感謝。

    edisonx 於 2012/11/02 23:52 回覆

  • novus
  • 剛又想到一個用途

    list<Data> data;
    vector<Data*> index;

    讓 index 元素等於 data 各元素的指標,將以上包成一個 class,於是你就會得到一個具有 stable iterator (因為就是 list::iterator)的 vector。缺點是內部記憶體不再是連續。這玩意在 boost 裡面有。

    另,照幾位C++大頭的意見,unique_ptr應該會成為最主要的指標型態,以後比較高階的程式碼將很少用到原生指標。
  • C++ Primer 再讓我念十遍我可能還想不出可以這麼做,看完之後真的是驚嘆! (其實每次看完您的回覆都一直在驚嘆、驚嚇中渡過...)

    edisonx 於 2012/11/03 01:16 回覆

  • novus
  • 忽然想到我很久以前摸索過一個 vector<bool> 的替代方案: basic_string<bool>

    純粹當容器用完全沒有問題,但 basic_string 有一些偏向文字的機能還有一些與 io 有關的機能會發生編譯錯誤。可能要進一步特化 char_traits 來解決吧,不過不知道怎麼改就是了。

    另一個問題是,印象中(懶得查) basic_string 並不保證內容連續,因此要用 c_str() 取得資料。

    其實 vector<bool> 並沒有那麼糟,只要不試圖取得其內部資料的位址,不論用 index 或 iterator 都不會出紕漏。不過 C++11 vector<bool> 已經改回來了。
  • 我還真沒想過用 basic_string 這東西,又上了一課...

    edisonx 於 2012/11/12 01:12 回覆

  • novus
  • 對了,你好像常常需要處理數值問題,我剛想到一個我沒用過幾次的東西 -- valarray。

    valarray 是為數值處理特設的容器,其實 valarray 比較符合數學觀點上的 vector,只是這個名稱已經先被 std::vector 佔用掉了。valarray 無須使用像雙重vector那樣的方式來實現二維陣列,而是透過 slice 做索引轉換。

    理論上 valarray 可以比 vector 作更多優化,不過網路上有些不同的實驗結果。不知道你有沒有實際比較過?我沒試過就是了。

    網路上有一些用 SSE2 優化過的 valarray,聽說速度比多數編譯器內建的 valarray/vector 還要快上好幾倍。
  • 之前還有想說是否要為 valarry 開一篇,不過想說它的特性沒很熟 ,加上手邊的書對它只有輕輕帶過,所以沒對它再多做介紹。
    不過您說的優化過之 valarray 這部份我倒是沒聽說,看到速度比 vector 快倒讓我感到些興趣了,這裡我有空去查查一些資料查詢,謝謝您提供的線索,很寶貴 :)

    edisonx 於 2012/11/18 03:28 回覆

  • 小小
  • 1 2 3 4 6 9 13 19 28 42 63 94 141 211 316 474 711 1066 1599 2398 3597 5395 8092...
    S1=1
    S2=2
    S3=3
    n>3
    Sn=S(n-1)+S(n-3)
    應該是這樣的規律吧
  • 其實你寫的規律也就是 S(n) = 1.5 * S(n-1) ,這數列後來我才看懂,你可驗證一下。

    edisonx 於 2015/03/16 09:34 回覆

  • 訪客
  • 3.5佔住不用

    你應該是在找這個 std::vector::shrink_to_fit
  • 你說的沒錯,c++11 以後有 shrink_to_fit 可以用,在 c++11 前沒 shirnk_to_fit ,只能自己想辦法了。

    edisonx 於 2016/05/17 18:52 回覆

您尚未登入,將以訪客身份留言。亦可以上方服務帳號登入留言

請輸入暱稱 ( 最多顯示 6 個中文字元 )

請輸入標題 ( 最多顯示 9 個中文字元 )

請輸入內容 ( 最多 140 個中文字元 )

請輸入左方認證碼:

看不懂,換張圖

請輸入驗證碼