[筆記] 在STL中vector與deque提供了相似的功能, 請簡單說明兩者的差異及使用

 作者  ie945167 (龍蝦)                                      站內  Lobster
 標題  [筆記] 在STL中vector與deque提供了相似的功能, 請簡單說明兩者的差異及使用
 時間  2012/05/13 Sun 21:38:19
───────────────────────────────────────

Q. 在STL中vector與deque提供了相似的功能, 請簡單說明兩者的差異及使用的時機


在STL中提供了vector, list,deque幾種可當作清單使用的資料結構，

他們都是動態增長的

在這三者之中選擇的準則主要是關注插入特性以及對元素的後續訪問要求。

差異

    從後面刪除vector跟deque差不多一樣快

    vector

    表示一段連續的記憶體區域每個元素被順序存儲在這段記憶體中

    對vector 的隨機訪問效率很高(vector::at())。

    (JiangMiao:不是因為它快，而是因為他不慢且安全).

    刪除非末尾元素效率比較低。

    在任意位置而不是在vector 末尾(插入/刪除)元素則效率很低，

    因為它需要把待(插入/刪除)元素右邊的每個元素都拷貝一遍

    (從前面刪除， "後面的都要copy到前面" )。

    一旦太多東西時,vector容器得另覓連續記憶體區塊,而將整個資料搬移

    vector 的動態自我增長越頻繁元素插入的開銷就越大。

    實際上對於小的物件，vector 在實踐中比list效率更高

    deque

    從前後刪除都很快，也表示一段連續的記憶體區域，

    但是與vector 不同的是它支持高效地在其首部插入和刪除元素

    它通過兩級陣列結構來實現一級表示實際的容器第二級指向容器的首和尾

    如果有大量釋放操作，deque將花費更多的時間(和 vector相比)

    list

    表示非連續的記憶體區域，並通過一對指向首尾元素的指標雙向連結起來，

    從而允許向前和向後兩個方向進行遍歷

    在list 的任意位置插入和刪除元素的效率都很高，指標必須被重新賦值，

    但是不需要用拷貝元素來實現移動

    對隨機訪問的支援並不好，訪問一個元素需要遍歷中間的元素，

    每個元素還有兩個指標的額外空間開銷

使用時機

    對這幾種容器類型選擇的一些準則

    如果我們需要隨機訪問一個容器則：vector 要比list 好得多

    如果我們已知要存儲元素的個數則：vector 又是一個比list 好的選擇

    如果我們需要的不只是在容器兩端插入和刪除元素則：list 顯然要比vector 好

    除非我們需要在容器首部插入和刪除元素：否則vector 要比deque 好

    vector

    優先默認選擇的容器

    已經知道vector要很大的szie 你可以一開始就擴充至你要的size，

    這樣就可以減少配置和copy了

    停止擴充後 對iterator的存取率很高的時候

    因為deque的記憶體是分開的 所以他的 iterator的運算會多幾個檢查會比較慢

    所以此時用vector會比較好

    當有大量數據要push_back，記得要vector::reserve().

    deque

    當有大量的首或尾刪除操作.

    或記憶體須不斷配置

    或copy成本很高

    如果你打算用insert或者有pop_front()的需要，使用deque.


使用記憶體圖解

vector
□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□

deque
□□□□□□

□□□□□□

□□□□□□

□□□□□□

□□□□□□

list
[ ]□[ ]
[ ]□[ ]
[ ]□[ ]
[ ]□[ ]
[ ]□[ ]
[ ]□[ ]



書上雖說除非有其他不利於 vector 的因素，不然主要還是以使用 vector 為主，

但主管說在他實際使用的經驗上，除非對於「連續記憶體」這點很要求，

不然還是會比較常用 deque，

不過我還是認為看程式需求吧，畢竟這兩個各佔擅場。



--
▅◣ Origin:  謠 言 報  bbs.csie.fju.edu.tw
▋◤ Author: ie945167 從 219-85-42-130-adsl-TPE.dynamic.so-net.net.tw 發表

[筆記] 請簡單說明（或舉例）Deadlock發生的條件

 作者  ie945167 (龍蝦)                                      站內  Lobster
 標題  [筆記] 請簡單說明（或舉例）Deadlock發生的條件
 時間  2012/05/13 Sun 21:26:52
───────────────────────────────────────

1. 互斥(mutual exclusion)：

    每次只能有一個process 可以使用該資源(該資源不允許共享)，

    如果另一process 對該資源提出申請，則此提出申請的process 必須等待，

    直到該資源被釋放為止。

    eg. printer、Disk、CPU etc.
    eg. 不具mutual exclusion→Read-only File

1. 佔用及等待(hold and wait)：

    系統中至少存在一個process持有某項資源，

    並正在等待獲取別項正被其它process所持有之資源。

    EX：
          (□a)←－－╮
        process A   process B
            ╰－－→(□b)

        如果 process A, B 已經各自拿到 a 和 b 的資源，

        但 A 還要需要 b資源，且 B也需要 a 資源，但是這些資源都已經被佔住了，

        所以就形成 deadlock。

    那麼如何在程式中避免掉這個問題呢？

    ANS：資源 lock 的順序需相同。

         也就是兩個 process 在 lock 住資源的順序需相同，

         都必須先 lock 住 A 或 B，才能再 lock 另一個資源。

         如此可避免掉 deadlock 的情況。

3. 禁止搶先(不可強取)(no preemption)：

    一個資源只能由持有它的process 在該process完成其工作之後自願釋放才行。

4. 循環等待(circular wait)：

    必須存在一組正在等待的process{ P0,P1,…,Pn}，

    其中P0 正在必須等待P1 持有的某個資源，P1 又等待被P2持有的某個資源，

    最後Pn 也正等待被P0 持有的某個資源。

    process各自佔用一些資源，而彼此互相在等待對方的資源，而形成一個迴圈。



所以為了預防死結的發生，必須針對這四個條件下功夫，

只要一個條件不成立，死結就會不成立。

--

     接球會"噴"

我             舉球會"歪"              但是！   我算分超強 o(一︿一+)o

                         攻擊會"OUT"

--
▅◣ Origin:  謠 言 報  bbs.csie.fju.edu.tw
▋◤ Author: ie945167 從 219-85-42-130-adsl-TPE.dynamic.so-net.net.tw 發表
▋※ Modify: 2012/05/13 Sun 21:27:13

[筆記] 全文轉錄 - 好的遊戲程式系統簡介

 作者  ie945167 (龍蝦)                                      站內  Lobster
 標題  [筆記] 全文轉錄 - 好的遊戲程式系統簡介
 時間  2012/04/04 Wed 17:53:15
───────────────────────────────────────

好的遊戲程式系統簡介
日前發於DCI的文章...
關於遊戲系統架構的一點淺見

http://forum.dci.org.tw/viewtopic.php?t=519

文章主題: 自問自答: 怎樣才是好的遊戲系統? (一個技術與非技術的討論)
1. 符合玩家需求(非技術性，歡迎參與討論...)

文章主題: 2. 應用物件導向設計系統(技術篇)

文章主題: 3. 最終章 封閉系統但是保持系統擴充性


內容太多了…懶得貼了…有興趣的自己去看吧…0rz

--

     身高不是距離
                   技巧不是問題
                                 只要有"心"
                                             人人都可 定‧三‧米


--
▅◣ Origin:  謠 言 報  bbs.csie.fju.edu.tw
▋◤ Author: ie945167 從 219-85-0-189-adsl-nei3.dynamic.so-net.net.tw 發表

[筆記] 全文轉錄 - 類別的設計

 作者  ie945167 (龍蝦)                                      站內  Lobster
 標題  [筆記] 全文轉錄 - 類別的設計
 時間  2012/04/04 Wed 17:50:12
───────────────────────────────────────

http://imandrewliao.blogspot.com/2009/01/blog-post_16.html

類別是C++實踐物件導向程式的基礎，一般人對類別設計應該都有了些基本的概念，

這篇想要以系統開發的角度，來強調類別設計與使用的注意事項。


1. 變數封裝

基本上除了特別特別的需求，一般都建議你，把資料放在private區段，

為什麼呢，這樣我才可以設計函式，管控如何存取這些變數值，

避免變數被莫名奇妙的變更，

造成錯誤時，難以追蹤的困擾，

所以一個基本的變數，如果需要被外界存取，那需要一個設定函式，一個讀取函式，

如果不需要，內部使用，那一個都不需要提供。


可以放在protected嘛？基本上，類別設計，建議你忘記有這個區間的存在，為什麼？

protected區間可以被後續繼承類別存取，除非你有特殊用途，否則你埋下了一個炸彈，

你如何知道後續繼成出去的類別，不會胡亂更動其值？

不會又寫了一個函式，把資料public出去？


class NPC
{
    private:
    int m_iHp;  // 生命力，除了初值化外，不應該由外界來操作這個變數
    int m_iAcc; // 物理攻擊準確度，由企劃公式產生，更不應該由外界來操作
};


這樣的寫法，也斷絕了，系統開發時，有人妄想修改資料的念頭，減少將來系統長大時，

潛藏錯誤發生的機會，真的需要處裡內部數值時，再以下列方法處理:

class AStrangeClass
{
    private:
        NPC *m_pNpc;

    public:
        void SetNpc( NPC *npc ){ m_pNpc=npc; }
        NPC *GetNpc(){ return m_pNpc; }
};

關於全域變數呢，基本上建議，寫程式應該要把他視為罪惡，

這意味著有一個完全不能改的機制在那邊，無法控制其變數名稱，

只要跟這個變數有瓜葛的類別，形成了一個盤根糾結的系統，

如同先前我提到的，少用繼承一樣的結果，

將來改其中任何一個地方，潛在需要修改的程式是全部。


可是全域變數一定會用到的，這個地方建議去參考"Design Patterns"的Singleton樣式，

提供了一個將變數全域化，但卻被類別管控的方法。

2. 成員函式設計

成員函式設計，視目的而定，沒有一定的規範（除非專案本身的規定），

這裡建議，請在函式放置位置的時候，多思考一下，要放在哪個區段，

一般的建議是這樣，

如果函式需要被外界存取，放public(廢話...)，

不需要的時候，請放private(廢話兩枚)。

是廢話嗎？回去隨便拿一個別人寫的類別看看，

是不是有很多函式被外界呼叫後，如果數值亂填，可能造成系統錯誤之類的？

你也許會反駁說，說明中有寫，這是內部使用的，錯誤是因為外界亂用啊？

可是我要說，設計類別的基本原則，就是讓人容易使用，且不容易出錯，

與其你放任函式public，裡頭寫一大堆exception，

為什麼不把這些函式private起來，錯誤發生率也小多了不是嗎？


常在程式之間流傳的對答：

啊，我知道bug發生原因了，是因為某某某呼叫了我一個函式，

而這個函式是內部使用的，不可以這樣呼叫...，



謹慎考慮多少可以減少潛藏可能發生問題的機會。


3. 注意別人類別的規範

接下來是使用別人類別的注意事項，不要企圖去改變回傳值的屬性，

原因是來自Ｃ＋＋轉型的方便，許多人喜歡把參數或是回傳值，

亂轉型，變成其他的類型來操作，

這本是無可厚非的事情，最明顯的就是const回傳值，

但是，系統開發的時候，標明const，就是不希望你去改變這個數值，

嚴重的說來，改變這個值，搞不好會發生嚴重的錯誤，而經常有人就愛去碰：


class A
{
    public:
        const char *GetTypeName(){ return "this is a type"; }
};

void main()
{
    A a;
    const char *ptr=a.GetTypeName();
    strcpy( (char *)ptr, "this is not a type" );
}

編譯都對，執行的時候，就當給你看，所以

(a) 當你看見函式回傳值有const時，不要嘗試去改變回傳值內容

(b) 當函式宣告有throw時，請處理exception

    因為throw表示，函式內可能發生無法預期的錯誤，catch它，

    可以明瞭錯誤的原因，方便除錯

(c) 當類別裡面沒有虛擬函式時，不要嘗試去繼承它

    如果你寫個類別，會給後續類別繼承，你會怎麼寫？一定是在裡面寫一些虛擬函式，

    暗示後來的程式師，這幾個函式可能以後會有其他的寫法，

    如果你寫個類別，沒有任何虛擬函式，那表示什麼？

    不想被別人繼承？功能已經完備？不論哪個答案，都不該再有類別繼承它了。

    除此之外，還有一個原因，虛擬解構式，在繼承情況下，

    解構的記憶體才會正確的釋放，

    你的類別什麼虛擬函式都沒有（含解構式），繼承它，

    未來背負著一個memory leak的風險。

(d) 正確的繼承

    假設，CHuman是個基底類別，CHuman人物會動、可裝備、會說話....，

    假設遊戲中出現了一種東西叫"假人"，人類經常習慣用名稱將之歸類為人類的一種，

    所以他該繼承CHuman，然後把所有不能用的功能重寫。

    你做了什麼事？把一個功能齊全的人類別，降級成什麼都不會的假人？

    只因為它長得像人？

    或者應該由一個物品，開始去繼承，增加功能比較適合？


    這裡提一個繼承基本上的判斷標準: 假人是不是一種人?

    意思是，人類會什麼，應該假人也要會什麼，少把類別寫成，假人是人的一種，

    但是他太多不會這不會那時...，大概就是錯誤的繼承關係了。



--
▅◣ Origin:  謠 言 報  bbs.csie.fju.edu.tw
▋◤ Author: ie945167 從 219-85-0-189-adsl-nei3.dynamic.so-net.net.tw 發表

[筆記] 全文轉錄 - 少用繼承

 作者  ie945167 (龍蝦)                                      站內  Lobster
 標題  [筆記] 全文轉錄 - 少用繼承
 時間  2012/04/04 Wed 17:46:41
───────────────────────────────────────

http://imandrewliao.blogspot.com/2009/01/blog-post_07.html

物件導向程式設計中，為了提升程式碼的再利用性，提供了繼承這樣的架構給我們使用，

只要看不順眼的類別，就可以用繼承改寫舊功能，達到擴展的目的，範例如下:

class AI
{
    private:
    virtual void FSM(); // AI類別實做FSM
};

class Monster : public AI
{
    private:
    virtual void FSM(); // Monster類別改寫原來的函式
};


但就"程式碼再利用的"目的而言，事實上，我們常用的方法還有一種，

"組成"，利用物件彼此間的協力，完成特定工作，

譬如，老闆要求去做一件A、B君都只會做部分功能的工作，

依照繼承的觀念，是否要生成第三個類別C，繼承A、B的能力，

然後改寫部分關聯而增加的程式碼?

然而我們是不是可以換個方向思考，

我可以設計個類別C，工作交代C，C會先請A君做完他會做的，

然後B繼續接手，一樣可以完成工作，

與繼承兩者，事實上複雜度一樣，都需要3個類別，

但是程式維護的小心程度卻是不可相提並論，程式如下


class AI
{
    public:
        void FSM();
};

class TimeControl
{
    public:
        void DoSomething();
};


用繼承:
class Npc:public AI, public TimeControl
{
    void DoSomething(); // 這裡遭遇第一個難關
                        // 多重繼承，要小心AB的成員變數、成員函式設計關係
};

用組成:
class Npc
{
    private:
        AI ai;
        TimeControl tc;

    public:
        void DoSomething(); // 我可以在這裡，靈活運用ai, tc物件的函式
                            // 達成老闆目標
};

你可以看見，往後ABC三個類別的修改，相依性是否會降低很多很多，

說白話，只要AB類別確定功能正常，發生BUG一定就是C，

A類別新增怎樣的功能，不會影響C或B的運作，同理C增減怎樣的函式，AB都不會影響，

而使用繼承呢? 就算你確定ABC三類別功能都正確，卻有可能因為繼承的關係，

造成邏輯錯誤，像是C發生BUG的原因，是因為C修改了一個變數值，

然後是A或B非常重要的變數，不允許由外部變更的

(這裡有個小伏筆，避免修改到別人家的變數，變數請用private封裝...)。


加上有許多程式濫用繼承，一個遊戲專案裡頭隨便都成千上百個類別，

加上彼此繼承的關係，專案像是N坨大肉粽樹，盤根錯節，

某Z類別有BUG，原因卻是在千里之外八竿子打不到關係的A類別造成，

改了A，卻連鎖反應要把某個肉粽樹的函式都要改過，想到就累人啊，

所以，有得選的情形下，請少用繼承多用組成。


再舉個生活上的例子，老闆要設計個簡報在客戶面前推銷商品，為了達到目標，

他需要繼承文書小姐的能力+產品部門對商品規格特色了解的能力+簡報能力+....，

或者，

他可以把公司內文書小姐、產品部經理、行銷推廣部經理叫來，說出需求，

接下來大家就自動會把事情搞定，而老闆則可專心挑毛病去，

愛用繼承的，通常工作累得要死，

愛用組成的，通常是老闆，你選哪個?



--
▅◣ Origin:  謠 言 報  bbs.csie.fju.edu.tw
▋◤ Author: ie945167 從 219-85-0-189-adsl-nei3.dynamic.so-net.net.tw 發表