FIFO實現

儘管實現我用以下結構的FIFO：FIFO實現

struct Node 
{ 
    T info_; 
    Node* link_; 
    Node(T info, Node* link=0): info_(info), link_(link) 
    {} 
};

我認爲這是一個衆所周知的伎倆很多STL容器（例如用於列表）。這是一個很好的做法嗎？當你說Node有一個指針類型的成員時，它對編譯器意味着什麼？這是一種無限循環嗎？

最後，如果這是一個不好的做法，我該如何實現更好的FIFO。

編輯：人，這是所有關於實現。我對STL庫足夠熟悉，並且知道來自多個庫的大量容器。只是我想與能夠提供良好實施或良好建議的人討論。

來源

2010-06-13 Narek

指向正在聲明的類型的對象的指針在C和C++中都很好。這是基於這樣一個事實，即指針是固定大小的對象（也就是說，在32位平臺上總是32位整數），因此您不需要知道指向類型的全部大小。

事實上，你甚至不需要一個完整的類型聲明來聲明一個指針。預先聲明就足夠了：

class A; // forward declared type 

struct B 
{ 
    A* pa; //< pointer to A - perfectly legal 
};

當然，你在點需要在範圍上一個完整的聲明，你實際訪問的成員：

#include <A.hpp> // bring in full declaration of class A 
... 
B b; 
b.pa = &a; // address of some instance of A 
... 
b.pa->func(); // invoke A's member function - this needs full declaration

對於FIFO考慮std::queue。 std::list,std::deque和std::vector都可用於此目的，但也提供其他設施。

來源

2010-06-13 19:33:30

您可以使用現有的FIFO std::queue。

來源

2010-06-13 19:23:58 Stephen

這是關於實施的。我知道在哪裏找到一個好的容器;）。 – Narek 2010-06-13 19:26:44

@Narek：我覺得應該是這樣，但沒有時間寫更多:)我同意其他評論 - 你的實現沒有任何問題，但使用'deque'會更好的性能。 – Stephen 2010-06-13 23:21:56

這是一個很好的做法嗎？

我沒有看到任何特別的錯誤。

當你說Node有一個指針類型的成員時，它對編譯器意味着什麼？

存儲指向同一類的對象的類沒有任何問題。

最後，如果這是一個不好的做法，我該如何實現更好的FIFO。

我會使用std::queue;）

來源

2010-06-13 19:25:01 Cogwheel

deque比排隊方式更冷 – Inverse 2010-06-13 19:36:26

這是實現一個節點的一個好辦法。節點指針用於創建到容器中下一個節點的鏈接。你說得對，它可以用來創建一個循環。如果容器中的最後一個節點引用第一個節點，則迭代該容器將遍歷所有節點。

例如，如果容器是一個FIFO隊列，指針會引用隊列中的下一個節點。也就是說，link_的值將是類別Node的另一個實例的地址。

如果值類型T實施昂貴的拷貝構造函數，更有效的Node類將是

struct Node 
{ 
    T * info_; 
    Node* link_; 
    Node(T * info, Node* link=0): info_(info), link_(link) 
    {} 
};

注意info_現在是一個指針的T一個實例。使用指針的想法是分配指針比複製複雜對象要便宜。

來源

2010-06-13 19:30:35

好的，但是指針會帶來所有權問題。現在誰負責刪除'info'？ – 2010-08-06 04:55:03

顯然你使用鏈表作爲隊列的底層實現。這沒有什麼特別的壞處。

雖然只是FYI，在實現方面，std :: queue本身使用std :: deque作爲它的底層實現。 std :: deque是一個更復雜的數據結構，它由巧妙管理的動態數組塊組成。它最終比鏈表更好，因爲：

對於鏈接列表，每個插入意味着您必須執行昂貴的動態內存分配。使用動態數組，你不需要。緩衝區必須增長時才分配內存。
數組元素是連續的，這意味着元素訪問可以在硬件中輕鬆緩存。

來源

2010-06-13 19:45:41 ryaner

回答

相關問題