STL哈希列表 - 我可以指向STL列表中的項目到另一個項目嗎？

比方說，我有一個：STL哈希列表 - 我可以指向STL列表中的項目到另一個項目嗎？

std::vector<std::list<Node> >

而且假設節點是：

class Node { 
    Node* next; 
    int data; 
};

細胞對應的散列函數值的快速查找窗口的向量。這個想法是你將元素插入到矢量中，但仍然將它們與Node-> next成員鏈接在一起。因此，您有一個列表，可以通過密鑰使用散列函數有效查找元素，以查找從哪個元素開始的正確矢量單元格。

無論如何，所有這一切。我的問題是：

我可以讓我的Node :: next指針指向列表中的其他節點（是同一個還是來自不同矢量單元的另一個節點），而不會導致問題？我不確定列表的標準庫實現是否允許這樣做。我似乎遇到了問題（我的代碼在這裏無法訪問），我想看看這是否可能是原因。

來源

2011-12-23 John Humphreys - w00te

據我所知，的std :: list和std ::矢量分配一定的一堆內存，並加入項目時，可能當沒有足夠的空間適合所有人時，將所有項目移到內存的不同部分。這顯然會導致此代碼中的問題。 – nijansen 2011-12-23 18:30:58

我知道std :: vector做到了這一點，因爲它需要連續的內存 - 我不會期望它從列表中，但因爲它會涉及額外的元素複製，沒有任何好處。你確定名單嗎？ – 2011-12-23 18:32:48

@nijansen你對'std :: vector'正確，但'std :: list'不移動項目。（當然，在'vector'裏面有一個'list'，就有可能複製'list'。） – 2011-12-23 18:34:53

如果你希望它指向列表中的其他節點，那是完全可行的，是的。然而，我會提出一個不同的設計：一個std::list<int>和一個std::unordered_map<int, std::list<int>::iterator>，一個類的唯一目的是保持兩個容器同步化。這應該比你現在的計劃更容易，更安全和更快速（我的解釋）。

添加和兩個列表刪除對象是輕而易舉的事情：

std::unordered_map<int, std::list<int>::iterator> fast; 
std::list<int> linked; 

void add(int data) { 
    fast[data] = linked.insert(linked.end(), data); 
}; 
std::list<int>::iterator erase(std::list<int>::iterator iter) { 
    fast.erase(*iter); 
    return linked.erase(iter);   
}

來源

2011-12-23 18:53:39

Dangit，愚蠢的手機。有人可以改變這些反引號，以便它正確顯示？ – 2011-12-23 18:54:38

我沒有修復<>符號，因爲內容混淆了我 - 別人可以這樣做：p – 2011-12-23 19:13:50

我怎樣才能得到我push_backed到列表中的最後一個元素的指針，所以我可以存儲它供以後使用？我想我知道，但這是看起來沒有正確工作的部分 – 2011-12-23 19:14:51

STL列表是雙向鏈接的，擁有私人的上一個和下一個指針。元素中的下一個指針不會與列表的下一個指針相關，因此它可以是任何你想要的。你將不得不自己管理它。它看起來像你正在實施散列與鏈接列表哈希碰撞（說clippy）。你看過地圖容器嗎？

來源

2011-12-23 18:43:48

我怎樣才能得到指向我push_backed到列表中的最後一個元素所以我可以存儲它以備後用？我想我知道，但那是不正確的部分。 – 2011-12-23 19:14:41

感謝幫忙的人，+1 :) – 2011-12-23 19:26:52

list :: end方法給出列表的最後一個元素。 – 2011-12-23 19:45:22

STL哈希列表 - 我可以指向STL列表中的項目到另一個項目嗎？

回答

相關問題