列表的向量。我應該使用指針還是值？

我正在實施數據結構散列表其中使用鏈解決衝突。列表的向量。我應該使用指針還是值？

所以作爲基礎數據結構我需要列表向量。
我的選擇從2種變體：

std::vector<std::list<entry> >
std::vector<std::list<entry>* >

其中條目是結構包含數據和散列值;

問題：如果我使用第一個變體（問題被認爲是一個大的輸入數據），效率會大大下降嗎？

預先感謝您！

來源

2013-04-20 spin_eight

你需要實現一個哈希表嗎？ C++ 11有std :: unordered_set和std :: unordered_map（以及它們的「多」對應）。 – 2013-04-20 02:50:46

是的，這是爲了教育目的。 – 2013-04-20 02:54:40

不要使用'std :: list '，除非你從列表中間插入/移除元素的次數要比迭代次數多得多，否則如果'entry'不可移動且複製成本高，或移動昂貴。 'std :: list'是'std ::'「雙向鏈表」，而不是'std ::'「當你想要一個列表時使用的理想容器」。 – Yakk 2013-04-24 16:42:10

使用指針確實沒有什麼優勢，它增加了在銷燬矢量時需要刪除的複雜性。繼續並使用vector<list<entry> >。 list將爲元素分配內存，但它對您而言是不可見的。

如果向量必須調整大小，可能會有性能損失，但是C++ 11編譯器應該使用移動而不是副本來最小化它。而對於一個學習項目來說，表演不應該是你首先關心的問題。

來源

2013-04-20 03:11:38

我在你的答案中發現了非常有用的信息，即STL容器向量在堆中爲它的元素分配內存。這些信息讓我推斷，在效率的情況下，2個變體會有細微的差別，而2 -nd會導致更多的工作要做（內存分配/釋放），我會選擇1-st。非常感謝你！ – 2013-04-20 03:26:57

-1

唯一真正的區別是，使用第一種方法時，您的存儲桶/鏈中的條目將存儲在堆棧中，而第二種方法的條目將存儲在堆中。對於大型結構，我發現在堆上存儲通常更好，但這是有爭議的。真的，只要你記得當你將它們添加到列表中時添加新條目，那麼你沒事。

來源

2013-04-20 02:53:40 legacybass

這個答案是不正確的。在這兩種情況下，除了'std :: vector'的內部之外，所有東西都將從free-store中分配。 – Mankarse 2013-04-20 03:18:05

當我閱讀Mark Ransom的答案時，我意識到在這兩個變體中，鏈（列表）將存儲在堆棧中，因爲矢量實現。 – 2013-04-20 03:20:44

@spin_eight：編號std :: vector總是在免費商店中分配其內容，Mark的答案中沒有任何其他說明。 – 2013-04-20 03:49:59

列表的向量。我應該使用指針還是值？

回答

相關問題