选择数据结构

Question

根据需要使用不同的数据结构，但是我如何知道应该使用哪种数据结构呢？我只想知道如何选择合适的数据结构？谢谢

Answer 1

此流程图用于C++中的STL，但您可以在C中实现STL容器支持的任何数据结构。

• List是一个链表，向量
• 是一个动态数组
• 是一个动态数组列表-- difference.
• Queue和Priority queue的拆分方式就像它们所说的那样(队列通常是按照双数列实现的，优先级队列通常是根据向量内的堆实现的，或者deque)
• Set/Map/Multiset/Multimap都是使用某种形式的平衡二叉树实现的。

更新2016:显然，我用来链接到这里的图片已经被链接烂了，但你可以在这个问题上看到几张等效的图片：In which scenario do I use a particular STL container?

Answer 2

您需要研究使用哪些数据结构来满足哪些需求(这里没有人会花时间为您详细说明每个选项，并确切地告诉您何时使用它)。

一旦你知道了细节，你应该能够(相当确定地)根据你的需要选择合适的数据结构。

Answer 3

对于不同类型的操作，每个数据结构都有不同的成本:您应该问问自己：

1. 我是否需要能够找到特定的元素(给我一个叫“bob”的人)？
2. 我是否需要关心顺序(即，定期查找第一个或最后一个)？
3. 我是否需要能够有效地删除除最后一个以外的记录？
4. 我是否需要随机访问(给我第20个)？
5. 我是否需要能够进行高效的多线程读写？

注意:列表中没有的一个问题是“我需要能够迭代存储中的所有内容吗”，因为所有实用的数据存储都能够在O(n)时间内访问所有N个元素

另外，所有这些评论都是泛化的：

如果1.的答案是“是”，那么就排除了各种无序数组类型的结构(向量，未排序数组，链表)。

如果2.的答案是“是”，那么就排除了基于散列的存储(hashmap等)。因为它们为了提高搜索效率而放弃了可预测的顺序。您可能需要一个树集或有序列表。

如果3.的答案是“是”，那么就排除了基于列表的(未排序的数组、链表)，您可能需要一个树集、有序列表或散列映射。

如果4的答案是“是”，那么这就排除了hashmap和链表(注意，这是一个与1不同的问题，因为hashmap存储基于索引的所有内容，它们不会以任何特定的顺序存储它们)

如果5的答案是“是”，那么根据您的特定要求提出一个问题可能是可行的，因为这会使前面给出的每个答案都变得复杂(链表、hashmap和缓慢增长的数组允许高效的并行实现，排序后的任何事情都很难用parralel完成)。

如果您想知道为什么所有这些选项都使用树集，但通常不推荐使用，这是因为如果2的答案是“否”，那么hashmap通常更好(随着集合的增长，添加和删除元素的时间比树集慢得多)。同样，如果其他问题的答案是否定的，那么就会有更好的建议。

通常:如果您需要随机访问，可以使用hashmap。如果需要排序的树集，则返回链表。(与直接数组相比，这些方法都会带来内存开销，所以我认为内存限制不是很高)