c++ - 查找无序元素的最佳 STL 数据结构

Question

我目前正在尝试用 C++ 实现一个哈希表作为家庭作业...

我选择使用内部链接作为表格冲突的解决方案...

我正在寻找一个好的 STL 容器，它可以在一组无序的数据中找到一个特定的条目。

我不能使用基于树(集合、 map 、树等...)的 STL 容器

现在我正在使用 vector ，这是一个不错的选择吗？搜索时间是线性的，对吧？还能更好吗？

Answer 1

正如您所说的我假设桶会变大...，最好使用std::list。在这两种情况下搜索都是线性的，但在 std::list 中添加元素是常量。

我猜它们都是一样的，因为数据没有排序 - 不，它们不是。如果是的话，那就只有一个容器了。每个容器都有自己的优点和缺点，不同的容器用于不同的情况。

关于 vector 的一些信息:

• std::vector 具有容量，这就是它具有capacity() 和size() 方法。他们都是不同的。所以，假设容量是 4，你有 2 个元素，那么大小就是 2。所以，添加另一个元素会增加大小(将是 3)，而且速度非常快。

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

或双哈希。

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

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

希望有所帮助(:

---

编辑:我向您推荐这篇文章 - comparing std::vector and std::deque - 完美 - 比较内存使用情况(分配、取消分配、增长)、CPU 使用情况等。我推荐整个 site对于此类文章 - 数量不多，但写得非常好。