data-structures - 列表的向量。我应该使用指针还是值？

Question

我正在实现使用链解决冲突的数据结构哈希表。

因此，作为基础数据结构，我需要列表向量。
我从 2 个变体中进行选择：

其中 entry 是包含数据和哈希值的结构体；

问题：如果我使用第一个变体（在大输入数据上考虑问题），效率会大大降低吗？

先感谢您！

score 3 · Accepted Answer

使用指针确实没有任何优势，而且它增加了在销毁向量时需要删除的复杂性。继续使用vector<list<entry> >. list无论如何都会为元素分配内存，但它对你来说是不可见的。

如果必须调整向量的大小，可能会有性能损失，但 C++11 编译器应该使用移动而不是副本来最小化它。对于学习项目，性能不应该是你首先关心的问题。

score -1 · Accepted Answer

唯一真正的区别是，第一种方法的存储桶/链中的条目将存储在堆栈中，而第二种方法的条目将存储在堆中。对于大型结构，我发现在堆上存储通常更好，但这值得商榷。真的，只要在将条目添加到列表时记得更新条目，就可以了。

2 回答 2