用于查找无序元素的最佳STL数据结构

Question

我目前正在尝试用C++实现哈希表来完成作业......

我选择使用内部链接作为表中碰撞的解决方案......

我正在寻找一个好的STL容器,它将在无序的数据集中找到特定的条目.

我不能使用基于树的集合(集合,地图,树等等)...

现在我正在使用矢量,这是一个不错的选择吗？搜索时间是线性的,对吧？可以更好吗？

Answer 1

正如你所说 I assume the buckets can get big...，最好使用std::list。在这两种情况下搜索都是线性的，但添加元素在 中是恒定的std::list。

I guess they're all the same, since data isn't ordered- 不，他们不是。如果是的话，那就只有一个容器了。每个容器都有自己的优点和缺点，不同的容器用于不同的情况。

关于向量的一些信息：

• std::vector有能力，所以有capacity()方法size()。他们都是不同的。因此，假设容量为 4 并且您有 2 个元素，则大小将为 2。因此，添加另一个元素将增加大小（将是 3），而且速度非常快。

• 但是当你必须添加 5 个以上的元素并且容量为 4 时会发生什么？分配全新的内存，将所有旧元素复制到新内存中，销毁所有旧元素（如果是用户定义的类型，则调用它们的析构函数）。然后旧的内存必须被释放。如果您认为添加/删除元素会更频繁，那么这些操作都是昂贵的。 您可以避免这种情况，使用提前保留一些内存的方法，而不是一直重新分配新内存并一遍又一遍地复制所有内容。但是当您知道这些向量的大致大小时，这很有用。我想你不适合你的情况（保留大量内存也不是一个好的解决方案 - 你不应该像那样浪费内存）所以，再说一遍，我更喜欢 std::list。
  std::vector::reserve

或者双哈希。

无论如何，这种新内存的分配和对象的复制不会经常发生，因为它std::vector很“聪明”，并且当分配新空间时，它不会只用 1 个元素或其他东西来增加容量。我认为它会翻倍，但我对此不太确定。啊，我不知道这在英语中到底是怎么称呼的。可能是“累积时间/内存”或“累积复杂度”之类的东西：？不知道：/

注意： 无论您选择什么，我建议您注意哈希函数。这是这里最重要的。哈希容器不应该有太多具有相同哈希值的元素。所以，我的建议是寻找一个好的哈希函数，然后这就不那么重要了。

希望有帮助（：

编辑：我会向您推荐这篇文章 -比较std::vector和std::deque- 它是完美的 - 比较内存使用情况（分配、解除分配、增长）、CPU 使用情况等。我会推荐此类文章的整个网站- 数量不多，但是写得真的很好。