c - 存储仅检索一次然后删除的元素的最佳数据结构是什么？

Question

我想设计一个存储元素的数据结构，插入后只检索一次，插入后删除。

我不能使用堆栈或队列，因为无法保证检索顺序。

[编辑] - 我想使用连续内存(我宁愿避免不时地执行 malloc)而且我也更喜欢可搜索性。

Answer 1

我认为算法的选择需要更多关于算法如何使用的信息。从您想要比线性搜索更好的评论来看，我假设搜索速度很重要。您对连续内存的评论使我相信您希望最大限度地减少内存消耗。我建议自平衡树结构(Red-Black 树)可能是合适的。它会分摊 log(N) 插入/删除，让您实现我概述的两个目标。如果内存使用问题不大，哈希表的查找效率会更高。您可以在连续的内存中实现大小有界的树——尽管实际元素本身不一定是连续的。

另一方面，如果我知道插入顺序是随机的，但检索顺序是确定的并且是按键排序的，那么我可能会建议 priority queue使用堆实现。