javascript - 具有对数搜索时间的 JavaScript 集数据结构

Question

可能重复：
Javascript 中是否有用于 Set 数据类型的库？

有没有办法创建一个模仿 c++ 集的 JavaScript 数据结构？我需要在 log(n) 时间内执行搜索，但找不到任何可以很好服务的语言。我已经看到几个问题说我应该将集合表示为一个对象。那会奏效吗？数组的键和有效负载是数字。

Answer 1

对于无序集，使用哈希表实现可能会更好。只要哈希表没有过载，它们就会进行 O(1) 查找。

对于有序的内存集，标准答案似乎是陷阱（平均时间好，标准差高）和红黑树（平均时间差，标准差低）。这些都是 O(logn) 查找。

Answer 2

如果你需要有序集（它允许你按照你定义的顺序从最小元素循环到最大元素），你可以在 JS 中实现你自己的数据结构。我无法提供更多信息，因为我没有亲身体验过。

如果您对无序集感到满意，则可以按如下方式实现：

1. 定义要存储在集合中的对象的规范化字符串表示。如果您需要带有数字的集合，只需使用数字的字符串表示形式。如果您需要一组用户定义的对象，您可以挑选出定义对象身份的属性，并在规范化的字符串表示中使用它们。
2. 通过将规范化的字符串表示映射到实际对象来创建一个要使用的 JS 对象。
3. 可以通过使用字符串表示检查属性名称来完成搜索。
4. 可以通过以下方式插入到集合中：首先通过搜索检查字符串表示是否已经存在，如果对象尚未在集合中，则将字符串表示映射到实际对象。
5. 删除可以使用 来完成delete，属性名称是要删除的对象的字符串表示形式。

Answer 3

它必须，在 javascript 中，一切都是对象。