STL容器區域/類競技場分配

Question

我正在寫一個類（一個霍夫曼編碼器，如果你好奇），需要包含一個STL容器不直接適用的專用二叉樹。用一些左/右指針定義一個TreeNode結構並構建它是沒有問題的。我關心的問題是節點本身的分配。

我認爲如果我使用STL容器作爲我的「分配器」，而不是直接爲每個節點調用new，那將會非常好。這很有吸引力，因爲它會使破壞變得微不足道：我不必在析構函數中將我的樹行走到單個delete所有節點;我用作「分配器」的STL容器的股票析構函數會自動執行。

我的「分配器」的第一選擇是std::vector<TreeNode>。但是，這根本不起作用，因爲隨着矢量的增長，它必須重新分配自己，並使我的指針無效。 所以我現在所做的就是堅守std::vector的想法，放棄指針;每個地方我曾經有一個指針，我有一個整數持有索引到我的向量，而不是。 也就是說，在我父類我有一個像

std::vector<TreeNode> _heap;  // all nodes in tree 
int _root;       // index into _heap 

然後成員分配一個新的節點我做這樣的事情：

TreeNode newnode(/*whatever*/); 
nodei = _heap.size(); 
_heap.push_back(newnode); 
// now do something with nodei 

而事實上，這是所有工作得很好，除了：使用索引而不是指針是一個普通的麻煩。我通常會將所指向的節點作爲*nodep，我必須改用_heap[nodei]。 （但是，再次，它的工作原理，這不是問題。）

我的問題是：

1. 有沒有保證不會有它的元素STL容器類後左右移動，這樣指針他們將在集裝箱的一生中保持有效？
2. 指向STL容器內元素的指針永遠是個好主意嗎？
3. 使用迭代器或引用而不是指針來處理這種事情（也就是說，指向容器化堆中的元素）會更好嗎？
4. 有更好的方法來實現本地堆分配器，容易（即隱式）的銷燬語義？

我接受其他想法，但我應該警告你我很保守。我想堅持一些在「基準」C++中起作用的東西，也就是說我會迴避只有C++ 11或其他東西。特別是像sigc和boost這樣的軟件包的開銷和複雜性，所以我不太可能想要使用它們的特殊容器或分配器之一。

Answer 1

是否存在一個STL容器類，保證不會隨後移動它的元素，這樣指向它們的指針將在容器的生命週期內保持有效？

std::deque不會移動元素如果你只會push_back/emplace_back元素，這是足以讓你的任務，你可以採取指針元素。

而且，std::deque最流行的實施方式中的塊，其中，一個塊可以順序存儲多個元件分配內存 - 這改善本地，並降低分配數（相對於std::list）。

指向STL容器內的元素的指針永遠是個好主意嗎？

只要知道底層語義和保證（您可以在C++ ISO中讀取），這是個好主意。

例如，如果您不更改容量std::vector並且不要調整它的大小 - 指向矢量內的元素的指針就可以。

對於這類事情（也就是指向容器化堆中的元素），使用迭代器還是引用而不是指針？

除了一些STL實現可能會在Debug版本中提供額外的防禦檢查之外，我沒有看到任何好處。

有沒有更好的方法來實現本地堆分配器，容易（即隱式）的銷燬語義？

其實我喜歡他們使用的索引，即region[node_index]像你一樣（雖然其中的代碼期待「真正的」指針並不總是在可接受的情況下）的想法。我看到在這個方法有幾個潛在的好處：

• std::vector呈指數級增長，造成O(log N)撥款N元素。有可能爲指針獲得相似的屬性，但它更復雜 - 您應該維護不同大小的塊的列表，如std::vector<std::vector<Node>>，其中每個新塊都具有容量total_size * k，並且您應該確保不會更改它（因爲指向元素的指針）。

• 您可以控制sizeof(index) - 您可以使用適合您的任務的索引類型，例如它可以是1-2個字節。但指針的大小可能更大，特別是在x64 - 特大號8字節的情況下。