如何实现一套？

Question

我想在C中实现一个Set.在创建SET时使用链表是否可以,或者我应该使用其他方法？

你通常如何实现自己的集合(如果需要).

注意:如果我使用链接列表方法,我可能会有以下复杂性设置我的操作:

• init:O(1);
• 毁灭:O(n);
• insert:O(n);
• 删除:O(n);
• 联盟:O(n*m);
• 交点:O(n*m);
• 差异:O(n*m);
• 成员:O(n);
• issubset:O(n*m);
• setisequal:O(n*m);

O(n*m)似乎可能有点大,特别是对于大数据......有没有办法实现我的Set更高效？

Answer 1

集合通常实现为红黑树(需要元素具有总顺序),或者实现为自动调整大小的哈希表(需要哈希函数).

后者通常通过使哈希表的大小加倍来实现,并在超过某个容量阈值(75%效果良好)时重新插入所有元素.这意味着单独的插入操作可以是O(n),但是当在许多操作中分摊时,它实际上是O(1).

Answer 2

std::set通常被实现为红黑树:http://en.wikipedia.org/wiki/Red-black_tree

这种方法可以让您在所有列出的操作中获得更好的复杂性.

Answer 3

我过去曾使用红黑树来构建集合。

以下是维基百科文章中的时间复杂度。

空间 O(n)
搜索 O(log n)
插入 O(log n)
删除 O(log n)