列表向量我应该使用指针还是值？

Question

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

因此，作为底层数据结构，我需要列表的向量。

我从两个变体中选择：

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

其中条目是结构化的，包含数据和散列值；

问题:如果我使用第一个变量(在一个大的输入数据上考虑问题)，会大大降低效率吗？

提前谢谢你！

Answer 1

使用指针没有任何好处，它增加了在销毁向量时需要删除的复杂性。继续使用vector<list<entry> >。无论如何，list将为元素分配内存，但对您来说它是不可见的。

如果必须调整向量的大小，可能会导致性能损失，但是C++11编译器应该使用移动而不是副本来最小化它。对于一个学习项目，表现不应该是你的首要考虑。

Answer 2

唯一真正的区别是，使用第一种方法，桶/链中的条目将存储在堆栈上，而第二种方法的条目将存储在堆中。对于大型结构，我发现存储在堆上通常更好，但它是有争议的。实际上，只要您在将条目添加到列表中时记得重新添加它们，那么您就可以了。